Nyckelutbyte genom jonglering

July 16th, 2008 by Joachim Strömbergson Leave a reply »

(Fixat trasig länk – tack JörgenL.)

Light Blue Touchpaper, bloggen från säkerhetsguppen vid Cambridge Computer Laboratory har det dykt upp en intressant postning om ett nytt sätt att utföra lösenordsbaserad nyckelutbyte.

Lösenordsbaserad nyckelutbyte (Password Authenticated Key Exchange – PAKE) är en metod för att utbyta sessionsnycklar för säker kommunikation mellan parter baserad på lösenord (delad hemlighet). De två mest kända versionerna av PAKE är Encrypted Key Exchange – EKE och Simple Password Exponential Key Exchange – SPEKE.

Artikeln Password Authenticated Key Exchange by Juggling är skriven av Feng Hao och Peter Ryan. Artikelns sammanfattning förklarar nyttan med J-PAKE:


Password-Authenticated Key Exchange (PAKE) studies how to establish secure communication between two remote parties solely based on their shared password, without requiring a Public Key Infrastructure (PKI). Despite extensive research in the past decade, this problem remains unsolved. Patent has been one of the biggest brakes in deploying PAKE solutions in practice. Besides, even for the patented schemes like EKE and SPEKE, their security is only heuristic; researchers have reported some subtle but worrying security issues. In this paper, we propose to tackle this problem using an approach different from all past solutions.

Our protocol, Password Authenticated Key Exchange by Juggling (J-PAKE), achieves mutual authentication in two steps: first, two parties send ephemeral public keys to each other; second, they encrypt the shared password by juggling the public keys in a verifiable way. The first use of such a juggling technique was seen in solving the Dining Cryptographers problem in 2006. Here, we apply it to solve the PAKE problem, and show that the protocol is zero-knowledge as it reveals nothing except one-bit information: whether the supplied passwords at two sides are the same.

With clear advantages in security, our scheme has comparable efficiency to the EKE and SPEKE protocols.

Jonglering
(Jonglering med nycklar – om din nyckel heter som ditt husdjur…)

Artikeln innehåller en hel del referenser till koncept och metoder jag inte kände till innan, exempelvis Dining Cryptographers. (Det verkar pågå verksamhet på Wikipedia för att skriva om förklaringen av problemet – se den här och den här sidan.)

Implementationsmässigt verkar den nya metoden inte vara så hemsk. Författarna skriver:


Since our protocol involves several zero-knowledge proofs, one might concern about its cost. We now count the number of exponentiations in the protocol and evaluate its computational effciency..in our protocol, each party would need to perform 14 exponentiations in total – including 8 in the first step, 4 in the second step, and 2 in computing the session key.

To better assess the cost in real terms, we implement the protocol in Java on a 2.33-GHz laptop running Mac OS X. The modulus p is chosen 1024-bit and the subgroup order q 160-bit
...
The results demonstrate that the protocol – executed only once in a session – runs sufficiently fast. The total computation time is merely 0.075 sec. As compared to the time that the user keys in his password, this latency is negligible at the client.

However, the cost at the server may accumulate to be significant if requests are dealt with simultaneously. Therefore, the threat of Denial of Service (DoS) attacks still needs to be properly addressed in practical deployments.

Vad gäller säkerheten skriver författarna att:


EKE requires changing the protocol in its existing form for a secure implementation. As for a SPEKE, it has the drawback that an active attacker may test multiple passwords in one protocol execution. Furthermore, neither protocol – in the original form – accommodates short exponents securely. Finally, neither protocol is provably secure; formal security proofs seem unlikely without introducing new security assumptions or relaxing security requirements.

We choose to solve the PAKE problem using a different approach. The novelty of our design is that we encrypt the password by juggling the public keys in a way that can be verified. As a result, our scheme is provably secure, allows flexible use of short exponents, and strictly limits an active attacker to test only one password per protocol execution.

För ett tag sedan blev Java-koden till implementationen av J-PAKE tillgänglig. Jag har inte testat den själv. Intressant nog kallas den för JPAKE2, vilket skulle kunna betyda att det funnits en tidigare version av algoritmen som man av någon anledning inte var nöjd med.

Författarna har även skickat in J-PAKE som förslag till en framtida utökning av IEEE P1363.

När J-PAKE uppmärksammades på Cyptography-listan dök det upp referenser till en annan, ny PAKE-algoritm. Det finns en Internet Draft, EAP Authentication Using Only A Password som tydligen är under utvärdering av IEEE för den kommande WLAN-standarden 802.11s.

Bra och enkla och allmänt tillgängliga metoder för nyckelutbyte är klart intressant. Med två stycken nya, säkra och ej patenterade utan öppna algoritmer kanske PAKE kan få bättre spridning. Inte minst för inbyggda system är J-PAKE klart intressant.

No related posts.

Related posts brought to you by Yet Another Related Posts Plugin.

Advertisement

2 comments

  1. jorgenl says:

    Länken Dining Cryptographers funkar inte.

Leave a Reply

You must be logged in to post a comment.