Welcome Guest [Log In] [Register]
Welcome to Crypto. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
Stream ciphers
Topic Started: Feb 13 2014, 06:22 PM (223 Views)
encrypted
Just registered
[ * ]
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
Edited by encrypted, Feb 13 2014, 07:42 PM.
Offline Profile Quote Post Goto Top
 
mok-kong shen
NSA worthy
[ *  *  *  *  *  * ]
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.)
Offline Profile Quote Post Goto Top
 
encrypted
Just registered
[ * ]
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.
Offline Profile Quote Post Goto Top
 
mok-kong shen
NSA worthy
[ *  *  *  *  *  * ]
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/
Offline Profile Quote Post Goto Top
 
encrypted
Just registered
[ * ]
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]}
}
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
« Previous Topic · General · Next Topic »
Add Reply