A5/3-attacken publicerad

January 12th, 2010 by Joachim Strömbergson Leave a reply »

Den nya attack på kryptot A5/3 i 3G jag tidigare bloggat om har nu publicerats på IACR. A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony (här är pdf-version av artikeln) av Orr Dunkelman, Nathan Keller och Adi Shamir är klart intressant läsning. Författarna skriver i sin sammanfattning att:

The privacy of most GSM phone conversations is currently protected by the 20+ years old A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They will soon be replaced in third generation networks by a new A5/3 block cipher called KASUMI, which is a modified version of the MISTY cryptosystem.

In this paper we describe a new type of attack called a sandwich attack, and use it to construct a simple distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of $2**-14.

By using this distinguisher and analyzing the single remaining round, we can derive the complete 128 bit key of the full KASUMI by using only 4 related keys, 2**26 data, 2**30 bytes of memory, and 2**32 time.

These complexities are so small that we have actually simulated the attack in less than two hours on a single PC, and experimentally verified its correctness and complexity. Interestingly, neither our technique nor any other published attack can break MISTY in less than the 2^**128 complexity of exhaustive search, which indicates that the changes made by the GSM Association in moving from MISTY to KASUMI resulted in a much weaker cryptosystem.

Eller om man vill sammanfatta det ännu mer: AJ!.

Samtidigt skall man påpeka att attacken ändå kan vara praktiskt svår att genomföra. Som författarna skriver: However, the new attack uses both related keys and chosen messages, and thus it might not be applicable to the specific way in which KASUMI is used as the A5/3 encryption algorithm in third generation GSM telephony. Att säkerheten skulle hänga på att inte kunna tvinga fram fyra olika nycklar och meddelanden av en viss typ låter dock inte bra.

Det skall bli intressant att se hur ETSI SAGE och 3GPP reagerar på detta resultat. Det var ETSI SAGE som specificerade KASUMI baserat på Mitsubishis blockkrypto MISTY1. Enligt Wikipedia är de ändringar som gjordes för att underlätta effektiv implementation i hårdvara.

Det vore dessutom intressant att höra vad författarna till exempelvis den här artikeln eller den här artikeln anser. Speciellt den senare hävdar att KASUMI är en bra PRNG, vilket den nya attacken väldigt tydligt motsäger.

No related posts.

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

Advertisement

Leave a Reply

You must be logged in to post a comment.