[SOLVED] need help breaking a stream cipher given as assignment

Nabeel · 11-24-2012, 07:57 AM

Well I am given a couple of crypted messeges and my goal is to break them and then submit the message. There are 10 messages that are encrypted using a stream cipher. And all are encrypted using the same key. Our teacher expects us to figure out the key from these 11 messeges somehow. I need advice on how to achieve this. What steps should I take to proceed and how to figure out the key?

The messages are in Hex, which in turn are Xor of the ASCII of the message characters and PRG key.

Thanks

millgates · 11-24-2012, 08:09 AM

Can you show us what have you tried so far? Also, is this all the available information?

linosaurusroot · 11-24-2012, 08:50 AM

If they are encrypted with the SAME keystream then XOR of one ciphertext with another exposes text with no key but with the XOR of two plaintexts. If that is the arrangement you can get 10 of these independently.

Plaintext XOR plaintext reveals information - and for English text for instance leads to the messages being detectable.

All that is an information problem rather than a Linux problem. Have you tried a crypto forum?

Nabeel · 11-24-2012, 09:11 AM

Well Here are the Encrypted messeges

Quote:

315c4eeaa8b5f8aaf9174145bf43e1784b8fa00dc71d885a804e5ee9fa40b16349c146fb778cdf2d3aff021dfff5b403b510 d0d0455468aeb98622b137dae857553ccd8883a7bc37520e06e515d22c954eba5025b8cc57ee59418ce7dc6bc41556bdb36b bca3e8774301fbcaa3b83b220809560987815f65286764703de0f3d524400a19b159610b11ef3e

Quote:

234c02ecbbfbafa3ed18510abd11fa724fcda2018a1a8342cf064bbde548b12b07df44ba7191d9606ef4081ffde5ad46a506 9d9f7f543bedb9c861bf29c7e205132eda9382b0bc2c5c4b45f919cf3a9f1cb74151f6d551f4480c82b2cb24cc5b028aa76e b7b4ab24171ab3cdadb8356f

Quote:

32510ba9a7b2bba9b8005d43a304b5714cc0bb0c8a34884dd91304b8ad40b62b07df44ba6e9d8a2368e51d04e0e7b207b70b 9b8261112bacb6c866a232dfe257527dc29398f5f3251a0d47e503c66e935de81230b59b7afb5f41afa8d661cb

Quote:

32510ba9aab2a8a4fd06414fb517b5605cc0aa0dc91a8908c2064ba8ad5ea06a029056f47a8ad3306ef5021eafe1ac01a811 97847a5c68a1b78769a37bc8f4575432c198ccb4ef63590256e305cd3a9544ee4160ead45aef520489e7da7d835402bca670 bda8eb775200b8dabbba246b130f040d8ec6447e2c767f3d30ed81ea2e4c1404e1315a1010e7229be6636aaa

Quote:

3f561ba9adb4b6ebec54424ba317b564418fac0dd35f8c08d31a1fe9e24fe56808c213f17c81d9607cee021dafe1e001b21a de877a5e68bea88d61b93ac5ee0d562e8e9582f5ef375f0a4ae20ed86e935de81230b59b73fb4302cd95d770c65b40aaa065 f2a5e33a5a0bb5dcaba43722130f042f8ec85b7c2070

Quote:

32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd2061bbde24eb76a19d84aba34d8de287be84d07e7e9a30ee714 979c7e1123a8bd9822a33ecaf512472e8e8f8db3f9635c1949e640c621854eba0d79eccf52ff111284b4cc61d11902aebc66 f2b2e436434eacc0aba938220b084800c2ca4e693522643573b2c4ce35050b0cf774201f0fe52ac9f26d71b6cf61a711cc22 9f77ace7aa88a2f19983122b11be87a59c355d25f8e4

Quote:

32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd90f1fa6ea5ba47b01c909ba7696cf606ef40c04afe1ac0aa814 8dd066592ded9f8774b529c7ea125d298e8883f5e9305f4b44f915cb2bd05af51373fd9b4af511039fa2d96f83414aaaf261 bda2e97b170fb5cce2a53e675c154c0d9681596934777e2275b381ce2e40582afe67650b13e72287ff2270abcf73bb028932 836fbdecfecee0a3b894473c1bbeb6b4913a536ce4f9b13f1efff71ea313c8661dd9a4ce

Quote:

315c4eeaa8b5f8bffd11155ea506b56041c6a00c8a08854dd21a4bbde54ce56801d943ba708b8a3574f40c00fff9e00fa143 9fd0654327a3bfc860b92f89ee04132ecb9298f5fd2d5e4b45e40ecc3b9d59e9417df7c95bba410e9aa2ca24c5474da2f276 baa3ac325918b2daada43d6712150441c2e04f6565517f317da9d3

Quote:

271946f9bbb2aeadec111841a81abc300ecaa01bd8069d5cc91005e9fe4aad6e04d513e96d99de2569bc5e50eeeca709b50a 8a987f4264edb6896fb537d0a716132ddc938fb0f836480e06ed0fcd6e9759f40462f9cf57f4564186a2c1778f1543efa270 bda5e933421cbe88a4a52222190f471e9bd15f652b653b7071aec59a2705081ffe72651d08f822c9ed6d76e48b63ab15d020 8573a7eef027

Quote:

466d06ece998b7a2fb1d464fed2ced7641ddaa3cc31c9941cf110abbf409ed39598005b3399ccfafb61d0315fca0a314be13 8a9f32503bedac8067f03adbf3575c3b8edc9ba7f537530541ab0f9f3cd04ff50d66f1d559ba520e89a2cb2a83

And here is the code that was used to encode the messeges

Code:

import sys

MSGS = ( ---  11 secret messages  --- )

def strxor(a, b):     # xor two strings of different lengths
    if len(a) > len(b):
        return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a[:len(b)], b)])
    else:
        return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a, b[:len(a)])])

def random(size=16):
    return open("/dev/urandom").read(size)

def encrypt(key, msg):
    c = strxor(key, msg)
    print
    print c.encode('hex')
    return c

def main():
    key = random(1024)
    ciphertexts = [encrypt(key, msg) for msg in MSGS]

I have proceeded like I XOR-ed the messeges 1 and 2

Quote:

'0x12104c06134e5709140f104f02521b0a0442020c4d070b184f4815541f0800484e1e0241061d064d540b0a02021019451 0164d4f3a005343004e430e1e1d0a524612171b0117001b0e45431c0c1d160a520d11744e19061a114d0e55174f084e54371 4050b174353541b48070e000e4dL'

,

then I did the same with 2 and 3. Note (I chosed the smaller string and striped the end portion of the long string to make it equal)

Quote:

0x111d094511490707101e104508064f12130d080c43000a4a0d00001548161141054f124e0b1b0a5000010a01520401470d 170a1b0508534c0e4f081c520f1652471c1b0b4e04534f0549131a1c02000a585900311c010b1b1a080b5511594fL

Now Since they are encryped using the same key therefore Xoring would cancel out the keys and return the XOR of two original messeges
Then I Xor-ed "Space" with the alphabats and then I started looking for that in m1.XOR.m2 and I got my eyes on '4c' then I tried XOring the Third Characer on m1 and m2 with '20'(hex of Space key code in ascii) and I got two options '6e' and '22'. Now since one of these had to be the third bit of the key so I Xor-ed bot these keys with the 3rd bit in m2 and m3. Now If one of them was the key so XOR-ing the resultant should yeild the 3rd bit of m2.XOR.m3 But It didn't happened. The closest I got was '0x9' with key '22' as compared to the 3rd bit of m2.XOR.m3 '09' so I'm kinda stuck here thinking what else should I do.and I am panicking because I have to submit it by monday.

linosaurusroot · 11-24-2012, 11:06 AM

Two messages start "32 51 0b a9" and two start "32 51 0b fb ac fb b9 be fd 54 41 5d a2 43 e1 69 5e ca bd 58 c5 19 cd 4b" which if you thought was "The " and so on you'd have a start. Guessing just the next char in one message if you're right reveals the next char in all messages.

We can fac 41 45 bf 43 e1 78 4b 8f a0 0d
Euler woul 51 0a bd 11 fa 72 4f cd a2 01
The nice t 5d 43 a3 04 b5 71 4c c0 bb 0c
The cipher 41 4f b5 17 b5 60 5c c0 aa 0d
You don't 42 4b a3 17 b5 64 41 8f ac 0d
There are 41 5d a2 43 e1 69 5e ca bd 58
There are 41 5d a2 43 e1 69 5e ca bd 58
We can see 15 5e a5 06 b5 60 41 c6 a0 0c
A (private 18 41 a8 1a bc 30 0e ca a0 1b
The Conci 46 4f ed 2c ed 76 41 dd aa 3c

linosaurusroot · 11-24-2012, 11:17 AM

We can factor the number 15 w 40 b1 63 49 c1 46 fb 77 8c df 2d
Euler would probably enjoy th 48 b1 2b 07 df 44 ba 71 91 d9 60
The nice thing about Keeyloq 40 b6 2b 07 df 44 ba 6e 9d 8a 23
The ciphertext produced by a 5e a0 6a 02 90 56 f4 7a 8a d3 30
You don't want to buy a set o 4f e5 68 08 c2 13 f1 7c 81 d9 60
There are two types of crypto 4e b7 6a 19 d8 4a ba 34 d8 de 28
There are two types of cyptog 5b a4 7b 01 c9 09 ba 76 96 cf 60
We can see the point where th 4c e5 68 01 d9 43 ba 70 8b 8a 35
A (private-key) encryption s 4a ad 6e 04 d5 13 e9 6d 99 de 25
The Concise OxfordDictionary 09 ed 39 59 80 05 b3 39 9c cf af

dugan · 11-24-2012, 11:43 AM

Linosaurusroot, stop doing the OP's homework for him.

Nabeel · 11-25-2012, 05:43 AM

Quote:

Originally Posted by linosaurusroot

We can factor the number 15 w 40 b1 63 49 c1 46 fb 77 8c df 2d
Euler would probably enjoy th 48 b1 2b 07 df 44 ba 71 91 d9 60
The nice thing about Keeyloq 40 b6 2b 07 df 44 ba 6e 9d 8a 23
The ciphertext produced by a 5e a0 6a 02 90 56 f4 7a 8a d3 30
You don't want to buy a set o 4f e5 68 08 c2 13 f1 7c 81 d9 60
There are two types of crypto 4e b7 6a 19 d8 4a ba 34 d8 de 28
There are two types of cyptog 5b a4 7b 01 c9 09 ba 76 96 cf 60
We can see the point where th 4c e5 68 01 d9 43 ba 70 8b 8a 35
A (private-key) encryption s 4a ad 6e 04 d5 13 e9 6d 99 de 25
The Concise OxfordDictionary 09 ed 39 59 80 05 b3 39 9c cf af

Thanks linosaurusroot! couldn't have done it without ya.

Finally solved the problem. If you hadn't given me the first couple of the bits in the key I wouldn't had done it.Any ways here is the full key . Took me more then two hours but finally!

Quote:

'0x66396e89c9dbd8cc9874352acd6395102eafce78aa7fed28a07f6bc98d29c50b69b0339a19f8aa401a9c6d708f80c066c 763fef0123148cdd8e802d05ba98777335daefcecd59c433a6b268b60bf4ef03c9a611098bb3e9a3161edc7b804a33522cfd 202d2c68c57376edba8c2ca50027c61246ce2a12b0c4502175e'

BTW linosaurusroot! could you be kind enough to explain the process (step by step) using which you broke those ciphrs? Since I didn't had a clue what to do until you showed those bits. I 've just signed up for this online cryptography course, and I don't have much of that crypto background.

linosaurusroot · 11-25-2012, 06:21 AM

First I read the beginning of the message strings looking for common beginnings. (In a different analysis problem for monoalphabetic substitution I would have wanted to look for any repetition which could be the same word in different places. And would have done other things - a helpful book on pencil+paper crypto is http://www.amazon.com/The-Codebreake...dp/0684831309/ ). In this case I guessed the first 3 chars right away.

Then I wrote a program to read in your message strings and a keystream and display the messages: when they key byte was defined (right or wrong) XOR and display the plaintext else show the hex ciphertext. And I ran it only over the first so many chars.

Looking over the output I could guess a character a time (mostly correct); add to the keystream and rerun.

See also http://www.schneier.com/book-applied.html although it's outdated in some ways. And http://cacr.uwaterloo.ca/hac/ is highly thought of but I've not read it.

Nabeel · 11-25-2012, 11:19 AM

Thanks I'm looking at "The Codebreaker" right now. But I must say that a man with your skill should take that stanford university's online cryptography course. The way you decoded those ciphers is just amazing! I'm still Astounded.