|
Stream ciphers
|
|
Topic Started: Feb 13 2014, 06:22 PM (223 Views)
|
|
encrypted
|
Feb 13 2014, 06:22 PM
Post #1
|
- Posts:
- 4
- Group:
- Members
- Member
- #3,827
- Joined:
- February 26, 2013
|
Hi, recently I wrote XorBreaker, an application that restores key from ciphertext created by simple xor cipher. First thing I do is finding key length which is done by shifting ciphertext against itself and calculating kappa value. When I get 0.06 for English I know period of the cipher, key length in other words. Finding letters of the key is done by xoring most frequent character in each subciphertext with space character. I take advantage of the fact that every n_i+i*key_length character is encoded with the same key character.
I was thinking about the way of immuning simple xor against such attack. I came up with this idea:
- Code:
-
void[space]strEncrypt(std::string[space]&[space]data,[space]const[space]std::string[space]&[space]key) { [space]char[space]prev[space]=[space]data[0];
[space]data[0][space]^=[space]key[0];
[space]for[space](size_t[space]i[space]=[space]1[space];[space]i[space]<[space]data.length()[space];[space]i++) [space]{ [space][space]char[space]k[space]=[space]key[i[space]%[space]key.length()][space]^[space]prev;
[space][space]prev[space]=[space]data[i];
[space][space]data[i][space]^=[space]k; [space]} }
void[space]strDecrypt(std::string[space]&[space]data,[space]const[space]std::string[space]&[space]key) { [space]data[0][space]^=[space]key[0];
[space]for[space](size_t[space]i[space]=[space]1[space];[space]i[space]<[space]data.length()[space];[space]i++) [space]{ [space][space]data[i][space]^=[space]key[i[space]%[space]key.length()][space]^[space]data[i[space]-[space]1]; [space]} }
This cipher chains all characters in the message together and obscures real kappa value. What is the easiest way to attack and break this cipher assuming that plaintext is in English?
When I analyse ~35k ciphertext I get this:
- Quote:
-
Kappa for shift 34403 equals 0.0134228 Kappa for shift 34404 equals 0.00537634 Kappa for shift 34405 equals 0.00403769 Kappa for shift 34406 equals 0.0107817 Kappa for shift 34407 equals 0.0161943 Kappa for shift 34408 equals 0.00405405 Kappa for shift 34409 equals 0.0162382 Kappa for shift 34410 equals 0.0758808 Discovered key length is 34410
Another "harder" variation of this approach:
- Code:
-
void[space]strEncryptHarder(std::string[space]&[space]data,[space]const[space]std::string[space]&[space]key) { [space]char[space]prev[space]=[space]data[0];
[space]data[0][space]^=[space]key[0];
[space]for[space](size_t[space]i[space]=[space]1[space];[space]i[space]<[space]data.length()[space];[space]i++) [space]{ [space][space]char[space]k[space]=[space]key[i[space]%[space]key.length()][space]^[space]prev;
[space][space]prev[space]^=[space]data[i];
[space][space]data[i][space]^=[space]k; [space]} }
void[space]strDecryptHarder(std::string[space]&[space]data,[space]const[space]std::string[space]&[space]key) { [space]char[space]prev[space]=[space]data[0];
[space]data[0][space]^=[space]key[0];
[space]for[space](size_t[space]i[space]=[space]1[space];[space]i[space]<[space]data.length()[space];[space]i++) [space]{ [space][space]data[i][space]^=[space]key[i[space]%[space]key.length()][space]^[space]prev;
[space][space]prev[space]^=[space]data[i]; [space]} }
And results:
- Quote:
-
Kappa for shift 35126 equals 0.0454545 Kappa for shift 35127 equals 0 Kappa for shift 35128 equals 0 Kappa for shift 35129 equals 0 Kappa for shift 35130 equals 0 Kappa for shift 35131 equals 0 Kappa for shift 35132 equals 0 Kappa for shift 35133 equals 0 Kappa for shift 35134 equals 0 Kappa for shift 35135 equals 0 Kappa for shift 35136 equals 0 Kappa for shift 35137 equals 0 Kappa for shift 35138 equals 0 Kappa for shift 35139 equals 0 Kappa for shift 35140 equals 0 Kappa for shift 35141 equals 0.142857 Discovered key length is 35141
|
|
|
| |
|
mok-kong shen
|
Feb 13 2014, 07:49 PM
Post #2
|
- Posts:
- 1,874
- Group:
- Members
- Member
- #3,310
- Joined:
- December 12, 2009
|
- encrypted
- Feb 13 2014, 06:22 PM
This cipher chains all characters in the message together ... Chaining, which is commonly employed in block encryptions, is IMHO certainly beneficial for stream processing as well. (Cf. also my code in http://s13.zetaboards.com/Crypto/topic/7153822/1/ which has components "autokey Vigenere substitution" that perform chaining there.)
|
|
|
| |
|
encrypted
|
Feb 13 2014, 08:05 PM
Post #3
|
- Posts:
- 4
- Group:
- Members
- Member
- #3,827
- Joined:
- February 26, 2013
|
Well CBC is one of modes of operation that turns block cipher into stream cipher. Above I've posted two versions of this chaining approach. I see that in the first version kappa equals 0.0758808 near the end of file. So looks like some kind of very long key has been created. I think when file contains long runs of the same letter, chaining with only previous letter is not sufficient. So I've posted second "harder" version which chains all previous characters and this has kappa = 0.142857 near the end of file but further than simpler version. This kappa doesn't point out that English is used but it may indicate weakness of the cipher. Ciphertext ought to look like random data which does't seem to be the case with my cipher.
|
|
|
| |
|
mok-kong shen
|
Feb 13 2014, 08:21 PM
Post #4
|
- Posts:
- 1,874
- Group:
- Members
- Member
- #3,310
- Joined:
- December 12, 2009
|
- encrypted
- Feb 13 2014, 08:05 PM
chaining with only previous letter is not sufficient. I agree with you. The CBC chainging of block encryption is IMHO rather poor. That's why I use to employ in several of my codes a more complicated chaining value (I name it sigma), see e.g. in http://s13.zetaboards.com/Crypto/topic/7115671/1/
|
|
|
| |
|
encrypted
|
Feb 15 2014, 05:36 PM
Post #5
|
- Posts:
- 4
- Group:
- Members
- Member
- #3,827
- Joined:
- February 26, 2013
|
I've prepared stronger version of cipher. I compared entropy of plain, simple xor, /dev/urandom, aes 128 cbc, rc4 and my cipher:
- Quote:
-
Plain: Entropy: 93.5373%
Simple XOR: Entropy: 97.9913%
/dev/urandom Entropy: 99.6069%
AES-128-CBC Entropy: 99.6069%
RC4 Entropy: 99.6063%
LK1: Entropy: 99.6068%
Are there some well known tests that can be performed on encrypted file in order to reveal weaknesses of my cipher?? I'm very curious how this cipher can be successfully attacked.
- Code:
-
void[space]lk1_create_key(std::string[space]&[space]mykey,[space]const[space]std::string[space]&[space]iv,[space]const[space]std::string[space]&[space]key) { [space]mykey[space]=[space]"";
[space]if[space](iv.length()[space]<[space]key.length()) [space]{ [space][space]return; [space]}
[space]for[space](size_t[space]i[space]=[space]0[space];[space]i[space]!=[space]key.length()[space];[space]i++) [space]{ [space][space]char[space]c[space]=[space]iv[i][space]^[space]key[i];
[space][space]mykey.append(&c,[space]1); [space]} }
void[space]lk1_mutate_key(std::string[space]&[space]mykey,[space]const[space]size_t[space]i) { [space]size_t[space]val[space]=[space]0;
[space]for[space](size_t[space]k[space]=[space]0[space];[space]k[space]!=[space]mykey.length()[space];[space]k++) [space]{ [space][space]val[space]^=[space]mykey[k][space]^[space]k; [space]}
[space]mykey[i[space]%[space]mykey.length()][space]=[space]val[space]^[space]i[space]^[space](i[space]>>[space]8)[space]^[space](i[space]>>[space]16)[space]^[space](i[space]>>[space]24)[space]^[space](i[space]>>[space]32)[space]^[space](i[space]>>[space]40)[space]^[space](i[space]>>[space]48)[space]^[space](i[space]>>[space]56); }
void[space]lk1_encrypt(std::string[space]&[space]data,[space]const[space]std::string[space]&[space]iv,[space]const[space]std::string[space]&[space]key) { [space]std::string[space]mykey;
[space]lk1_create_key(mykey,[space]iv,[space]key);
[space]if[space](mykey.empty()) [space]{ [space][space]data[space]=[space]"";
[space][space]return; [space]}
[space]char[space]prev[space]=[space]0;
[space]for[space](size_t[space]i[space]=[space]0[space];[space]i[space]<[space]data.length()[space];[space]i++) [space]{ [space][space]char[space]k[space]=[space]mykey[i[space]%[space]mykey.length()][space]^[space]prev;
[space][space]prev[space]^=[space]data[i];
[space][space]data[i][space]^=[space]k;
[space][space]lk1_mutate_key(mykey,[space]i); [space]} }
void[space]lk1_decrypt(std::string[space]&[space]data,[space]const[space]std::string[space]&[space]iv,[space]const[space]std::string[space]&[space]key) { [space]std::string[space]mykey;
[space]lk1_create_key(mykey,[space]iv,[space]key);
[space]if[space](mykey.empty()) [space]{ [space][space]data[space]=[space]"";
[space][space]return; [space]}
[space]char[space]prev[space]=[space]0;
[space]for[space](size_t[space]i[space]=[space]0[space];[space]i[space]<[space]data.length()[space];[space]i++) [space]{ [space][space]data[i][space]^=[space]mykey[i[space]%[space]mykey.length()][space]^[space]prev;
[space][space]prev[space]^=[space]data[i];
[space][space]lk1_mutate_key(mykey,[space]i); [space]} }
|
|
|
| |
| 1 user reading this topic (1 Guest and 0 Anonymous)
|