View Full Document

# CMEA

View Full Document
View Full Document

27 views

Unformatted text preview:

CMEA CMEA 1 CMEA Cellular Message Encryption Algorithm Designed for use with cell phones o To protect confidentiality of called number o For control channel not the data channel o Data channel encrypted with ORYX Part of a standard developed by TIA o Flaw in cipher discovered in 1997 Cipher design process not open o In violation of Kerckoffs Principle CMEA 2 CMEA Block cipher o 64 bit key o Variable block size typically 2 to 6 bytes CMEA is its own inverse o Recall that Enigma is its own inverse o Not clear that this is useful for CMEA CMEA uses Cave Table o A fixed 256 byte lookup table o Not a permutation CMEA 3 Cave Table Table has 256 bytes o 164 distinct values o 97 appear just once o 44 occur twice o 21 occur three times o 2 occur four times o Highly non uniform CMEA For example C 0x6a 0xf3 4 CMEA Let K0 K1 K7 be bytes of 64 bit key Let C be Cave Table For byte x define all are mod 256 Q x C x K0 K1 x R x C Q x K2 K3 x S x C R x K4 K5 x T x C S x K6 K7 x Table defined by T x used in CMEA CMEA 5 CMEA We have Q x C x K0 K1 x R x C Q x K2 K3 x S x C R x K4 K5 x T x C S x K6 K7 x Note that T x x is in C o Same is true of S x x R x x and Q x x Implies these values are biased o These facts used heavily in attacks CMEA 6 CMEA Algorithm Encrypt block of n bytes Uses T table o Which uses Cave Table Cipher is its own inverse o Same algorithm used for decryption CMEA 7 SCMEA The 1 in line 10 of CMEA complicates attack We define Simplified CMEA SCMEA to be same as CMEA without 1 That CMEA is replace line 10 of CMEA with 8 SCMEA Chosen Plaintext Attack Consider plaintext block of the form Corresponding 1st ciphertext byte is The plan of attack o Use chosen plaintext to find putative T 0 o With more chosen plaintext can then find putative T j for j 1 2 255 Note Recover T table and key is broken CMEA 9 SCMEA Chosen Plaintext Choose plaintext blocks of the form p0 p1 p2 1 x0 1 x0 0 where x0 is in the Cave Table Suppose we obtain Setting l j 0 in and we see that such an x0 is consistent with T 0 x0 Then we have found a candidate for T 0 CMEA 10 SCMEA Chosen Plaintext Given candidate x0 T 0 choose plaintext p0 p1 p2 1 x0 j 2 x0 0 for each j 1 2 255 Then from with l 0 we have c0 1 xj x0 and we can solve for xj If it is true that x0 T 0 then xj T j CMEA 11 SCMEA Chosen Plaintext We can obtain putative T 0 and putative T j for j 0 1 255 How can we know whether this is correct T table Recall Check T j j is in Cave Table for all j whether xj j is in Cave Table o If it fails for any j then T 0 incorrect CMEA 12 SCMEA Chosen Plaintext Attack Algorithm Use l j 0 in to find putative T 0 Set l 0 in and j 1 2 255 to find putative T j For each putative T j check if T j j is in the Cave Table o If this fails for any j then start over o If holds for all j then have found T table CMEA 13 SCMEA Chosen Plaintext How much chosen plaintext needed Recall 164 distinct elements in Cave Table Ignoring false alarms o Since T 0 is in Cave Table need 82 chosen plaintext blocks to find T 0 o Then 255 more blocks to find T table o Total of 337 chosen plaintext blocks Consider false alarms for CMEA attack CMEA 14 CMEA Chosen Plaintext Attack Similar to SCMEA if then and A more complex expression for c2 o Homework problem As in SCMEA attack let l j 0 CMEA 15 CMEA Chosen Plaintext Letting l j 0 we have that plaintext p0 p1 p2 1 T 0 1 T 0 0 yields ciphertext Again choose plaintext of the form p0 p1 p2 1 x0 1 x0 0 CMEA 16 CMEA Chosen Plaintext Choose plaintext of the form p0 p1 p2 1 x0 1 x0 0 Any of these that satisfy are consistent with x0 T 0 Can reduce false alarms by using Cave Table conditions on both c1 and c2 CMEA 17 CMEA Chosen Plaintext Given candidate x0 T 0 choose p0 p1 p2 1 x0 j 2 x0 0 for each j 1 2 255 Then from with l 0 we have c0 1 T j 1 T 0 and we can solve for T j 1 Note CMEA low order bit of T j is unknown 18 CMEA Chosen Plaintext Attack algorithm Use l j 0 in to find x0 putative T 0 Set l 0 in and j 1 2 255 to find xj which is putative T j 1 For each xj check if xj j is in the Cave Table and or xj 1 j is in the Cave Table o If both fail for any j then x0 incorrect o If one fails then have unique putative T j o If neither fails then 2 choices for T j CMEA 19 CMEA Chosen Plaintext How to resolve ambiguous xj T j o Both xj j and xj 1 j in Cave Table Create array A of size 256 Set Ai 0 if low order bit of xi is known o And Ai 1 if low order bit of xi is ambiguous We can use this array to resolve ambiguous low order bits CMEA 20 CMEA Chosen Plaintext Suppose putative T k is ambiguous Find t and j with k t T j 1 where At 0 Let p0 p1 p2 t 1 T 0 j 2 t 1 T t 0 Encrypting this chosen plaintext yields T t T j 1 j 2 t 1 c1 Which implies T k j 2 t 1 c1 We have resolved ambiguity in T k CMEA 21 CMEA Chosen Plaintext How much chosen plaintext is required 82 blocks to find T 0 on average 255 more to recover T table 0 6 255 153 to resolve ambiguous o 0 6 probability that both are in Cave Table 0 258 9 2 3 for incorrect T 0 s o 0 258 prob each takes 9 blocks to resolve Total CMEA chosen plaintext blocks 492 3 22 CMEA Chosen Plaintext Analytically have shown that 492 3 chosen plaintexts required Empirical results from 106 trials very close to predicted results CMEA 23 CMEA Chosen Plaintext Attack Bottom Line Recover T table not the actual key Relies …

Unlocking...