Feistel-netwerken en patronen

Feistel-netwerken en patronen

zondag 10 juni 2012 14:23

http://tools.ietf.org/html/rfc2144#section-2.2

CAST-128 belongs to the class of encryption algorithms known as
   Feistel ciphers; overall operation is thus similar to the Data
   Encryption Standard (DES).  The full encryption algorithm is given in
   the following four steps.

   INPUT:  plaintext m1…m64; key K = k1…k128.
   OUTPUT: ciphertext c1…c64.

   1. (key schedule) Compute 16 pairs of subkeys {Kmi, Kri} from K
      (see Sections 2.1 and 2.4).
   2. (L0,R0) <– (m1…m64).  (Split the plaintext into left and
      right 32-bit halves L0 = m1…m32 and R0 = m33…m64.)
   3. (16 rounds) for i from 1 to 16, compute Li and Ri as follows:
      Li = Ri-1;
      Ri = Li-1 ^ f(Ri-1,Kmi,Kri), where f is defined in Section 2.2
       (f is of Type 1, Type 2, or Type 3, depending on i).
   4. c1…c64 <– (R16,L16).  (Exchange final blocks L16, R16 and
      concatenate to form the ciphertext.)

   Decryption is identical to the encryption algorithm given above,
   except that the rounds (and therefore the subkey pairs) are used in
   reverse order to compute (L0,R0) from (R16,L16).

2.2. Non-Identical Rounds

   Three different round functions are used in CAST-128.  The rounds are
   as follows (where “D” is the data input to the f function and “Ia” –
   “Id” are the most significant byte through least significant byte of
   I, respectively).  Note that “+” and “-” are addition and subtraction
   modulo 2**32, “^” is bitwise XOR, and “<<<” is the circular left-
   shift operation.

       Type 1:  I = ((Kmi + D) <<< Kri)
                f = ((S1[Ia] ^ S2[Ib]) – S3[Ic]) + S4[Id]

       Type 2:  I = ((Kmi ^ D) <<< Kri)
                f = ((S1[Ia] – S2[Ib]) + S3[Ic]) ^ S4[Id]

       Type 3:  I = ((Kmi – D) <<< Kri)
                f = ((S1[Ia] + S2[Ib]) ^ S3[Ic]) – S4[Id]

   Rounds 1, 4, 7, 10, 13, and 16 use f function Type 1.
   Rounds 2, 5, 8, 11, and 14 use f function Type 2.
   Rounds 3, 6, 9, 12, and 15 use f function Type 3.

Bij de meeste symmetrische encryptie-algoritmen bestaat er een relatie tussen de bits in de subkeys. Hier kan een tweede relatie uit volgen die zich voordoet tussen de outputs van de rounds in het Feistel-netwerk. Doet dit zich voor, dan hebben we een onveilig algoritme.

Met betrekking tot het vorige is een mogelijke zwakte van het algoritme dat de S-box dezelfde waarde teruggeeft als de input of dat de output een gekende relatie zal hebben met de input. Zo wordt het aantal rounds gereduceerd.
Kan er input gezonden worden om output te verkrijgen, dan kan het aantal rounds zo worden geëlimineerd.

Is er toegang tot de hardware, dan kan bij sommige algoritmen de klok vertraagd worden om te kijken hoeveel bewerkingen worden uitgevoerd en zo te schatten welk pad zich in het algoritme heeft voorgedaan. Nog beter is als we instructies zoals CMP in de CPU kunnen meten zodat we precies weten welk geval zich heeft voorgedaan (denk aan creditcards en stroomafname).
Sowieso kunnen we de S-Box extraheren als we fysieke toegang hebben tot het geheugen. Naar het schijnt kan geheugen bevroren worden als het in suspend-modus is door koelingsspray te gebruiken en zo verplaatst worden naar een tweede computer, zoals een laptop, die ook in suspend staat.

Wat de patronen betreft :
       Type 1:  I = ((Kmi + D) <<< Kri)
                f = ((S1[Ia] ^ S2[Ib]) – S3[Ic]) + S4[Id]

       Type 2:  I = ((Kmi ^ D) <<< Kri)
                f = ((S1[Ia] – S2[Ib]) + S3[Ic]) ^ S4[Id]

       Type 3:  I = ((Kmi – D) <<< Kri)
                f = ((S1[Ia] + S2[Ib]) ^ S3[Ic]) – S4[Id]

Ik geloof dat op standaard Intel CPU’s +, – en XOR verschillende tijdsspannes hebben. Hier is er een mooi circulair patroon te zien :

<<<
^ – + ^
<<<
– + ^ –
<<<
+ ^ – +

Dit doet zich meerdere keren 16 keer voor. Het hangt van de implementatie van het algoritme af of tussen twee rondes nog bewerkingen worden uitgevoerd of niet. Hoe repititiever, hoe moeilijker het te zien is waar het algoritme op die moment zit.
Maar als we een patroon hebben dat zich lang genoeg voordoet, kan dit dan gedetecteerd worden vanop afstand? Kan dit gebruikt worden om te kijken wanneer het algoritme wordt uitgevoerd?

* Kunnen we dit van buitenaf meten en zo het algoritme tracken?

Meten op CPU-frequentie, als we dichtbij genoeg zijn.

* En als we dit kunnen, kunnen we dan de S-Boxes extraheren door het geheugen in d’oog te houden met een antenne of door de stroom en van de mogelijk fout gemeten waarden de meest voorkomende waarden te proberen?

Dit is een theorie, ik heb het nog niet geprobeerd :
Geheugen werkt op een specifieke frequentie. Het aantal hoge bits kan geschat worden door de stroomafname op die frequentie in d’oog te houden. We schatten eerst het minimum en dan het maximum van het aantal hoge bits. Dan zoeken we de functie die de waarden ertussen geeft.

dagelijkse newsletter

take down
the paywall
steun ons nu!