Warning: Missing argument 2 for wpdb::prepare(), called in /home/stromber/public_html/kryptoblog/wp-content/plugins/wp-super-edit/wp-super-edit.core.class.php on line 109 and defined in /home/stromber/public_html/kryptoblog/wp-includes/wp-db.php on line 1222
Artikel om attacker på Feistelbaserade krypton » Kryptoblog

Artikel om attacker på Feistelbaserade krypton

February 13th, 2008 by Joachim Strömbergson Leave a reply »

Det har dykt upp en artikel på IACR om attacker på Feistelbaserade blockkrypton. Generic Attacks on Feistel Schemes av Jacques Patarin skriver i sammanfattningen:


Let A be a Feistel scheme with 5 rounds from 2n bits to 2n bits. In the present paper we show that for most such schemes A:
1. It is possible to distinguish A from a random permutation from 2n bits to 2n bits after doing at most O(2n) computations with O(2n) non-adaptive chosen plaintexts.

2. It is possible to distinguish A from a random permutation from 2n bits to 2n bits after doing at most O(3n/2) computations with
O(3n/2) random plaintext/ciphertext pairs.

Since the complexities are smaller than the number 22n of possible inputs, they show that some generic attacks always exist on Feistel schemes with 5 rounds. Therefore we recommend in Cryptography to use Feistel schemes with at least 6 rounds in the design of pseudo-random permutations.

We will also show in this paper that it is possible to distinguish most of 6 round Feistel permutations generator from a truly random permutation generator by using a few (i.e. O(1)) permutations of the generator and by using a total number of O(2**2n) queries and a total of O(2**2n) computations.

This result is not really useful to attack a single 6 round Feistel permutation, but it shows that when we have to generate several pseudo-random permutations on a small number of bits we recommend to use more than 6 rounds. We also show that it is also possible to extend these results to any number of rounds, however with an even larger complexity.

Först skall jag nog säga att artiklar som publiceras på IACR inte självklart har granskats och därmed är det svårt att bedöma om det som presenterats stämmer eller ej.

Vad det handlar om är alltså skiffer uppbyggda enligt den struktur som Horst Feistel hittade på där blocket som bearbetas delas upp i två sidor (delar) och sidorna bearbetas var för sig. Mellan varje varv byter sidorna plats:

Feistel-struktur

Det artikeln visar (så vitt jag fattar) är att oavsett nyckel och väsentligen oavsett vilka operationer som utförs på de olika sidorna i ett varv går det att identifiera utdata från kryptot i jämförelse med en en ren slumpmässig mängd data.

Rent praktiskt innebär inte detta att ett stort antal krypton plötsligt blivit osäkra (ens om resultaten i artikeln stämmer). De flesta Feistel-krypton, ex 3DES har ett stort antal varv och som författaren till artikeln skriver:


it is possible to distinguish most generators of 6 round Feistel permutations from truly random permutations on 32 bits, within approximately 2**32 computations and 2**32 chosen plaintexts (and this whatever the length of the secret key may be)

Det är alltså för ett krypto med ett block på 32 bit och sex varv. För ex 3DES med 64 bit block och 48 varv är det fortfarande praktiskt omöjligt. Men ett krypto där säkerhetsmarginalen i och med artikelns resultat kanske börjar bli liten kan vara KASUMI, kryptot i 3G.

Eller tänker jag snett?

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.