Cryptography : is it me ???

[fullmetalcoder]

There are three conditions which must be met:

• the key must be random,
• the key must be used only once,
• the key must have the same length as the message

If all of them are met, this encryption scheme is unbreakable (as proved by Shannon), otherwise it's unsecure.

The first two conditions can be met with proper software. It only needs a random key generator owned by both sender and receiver and initialized with common data so that the sequence of random key is the same under both computers. I guess this can be done but then, then initial data with which the random key generator has been set up becomes the real key...

About the third condition : a key with the exact same length as the message sounds quite weird and even though Shannon used this assumption to prove th unbreakability I'm pretty sure that as long as the key is not fully-repeated (i.e. key.size() > message.size() / 2) the unbreakability remain or at least we're very close to it....

Besides, if the two first conditions are met, I don't think a mismatch of the third on make the encryption so weak. And, as wysota pointed out, the encrypted data doesn't need to be encrypted forever...

[jacek]

The first two conditions can be met with proper software. It only needs a random key generator owned by both sender and receiver and initialized with common data so that the sequence of random key is the same under both computers.

That's how stream ciphers work.

I must admit that I'm quite impressed.... Just for my information, how much time did it take to decrypt it???

I don't know exactly, but judging from the time of my posts it didn't take more than 30 minutes.

[fullmetalcoder]

That's how stream ciphers work.

...

Maybe you could be a little more precise... Any link?

[jacek]

Maybe you could be a little more precise... Any link?

http://en.wikipedia.org/wiki/Stream_cipher

Also check those books I've mentioned earlier.

[Brandybuck]

The cardinal rule of inventing new cryptographic algorithms is: Never "roll your own".

[wysota]

The first two conditions can be met with proper software. It only needs a random key generator owned by both sender and receiver and initialized with common data so that the sequence of random key is the same under both computers.

You see... there is no software that can generate real random numbers. As for using the key once - if you use ECB mode, you violate that rule on the very beginning.

About the third condition : a key with the exact same length as the message sounds quite weird and even though Shannon used this assumption to prove th unbreakability I'm pretty sure that as long as the key is not fully-repeated (i.e. key.size() > message.size() / 2) the unbreakability remain or at least we're very close to it....

If at least part of the key repeats, it means more than one message is encrypted with the same key, which may allow you to extract part of the original message, which might lead to compromising the whole message (often one only needs some part of the message).

Besides, if the two first conditions are met, I don't think a mismatch of the third on make the encryption so weak.

Actually, it's the most important of the three... The first two only make sure you end up with a good key (with an additional assumption that the cipher doesn't have weak keys).

And, as wysota pointed out, the encrypted data doesn't need to be encrypted forever...

That doesn't make a cipher strong. It only means the message is (or is not) protect "well enough for a particular need".

Next Sunday? Oh... sorry, I haven't noticed "next". :P

I was wondering why it takes you so long to answer the thread

The key is: ?10w?weak?

Seemed obvious the key would be 80 bit long "Just in case"...

Just to theorise - I don't know exactly how Jacek broke the key, but I can make a guess at possible ways of dealing with the situation.

Knowing the key is a multiple of 8bits, one had to checks ten possible lengths. Now we know that statistically the character "e" is the most common in english language, so it is most likely to receive collisions on it. Unfortunately use of C++ may change those statistics, so we have two possible ways of overcoming this.
1. gather own statistics of C++ code by counting the number of occurences of each character in a large C++ code (like Qt sources, although it lacks comments).
2. try to guess most popular characters - I'd say they are " " (space), ":" (colon), ";" (semicolon) and "{","}" (braces).

The longer the text, the more collisions one may expect. Furthermore if the message is a C++ sourcecode, it most probably begins with a hash (#) - like in "#ifndef ..." or with a slash (/) - marking the beginnning of a comment. This gives additional insights, allowing one to try to guess the first character of the key right away. Furthermore if the following characters are asterisks (in case of the comment), then we might guess the beginning of the message is "/********************". That gives us more than the key length, so xoring the beginning of the ciphertext with assumed plaintext we receive the key. The rest is just about verifying the key by decrypting the rest of the message.

So as you see, you might have compromised the key yourself here. Again, I don't know if that was the path Jacek took to decode the message, but it's a possible strategy.

Another approach would be to try to find collisions at each 10th character of the data - that's where the amount of text for analysis is vital.

[fullmetalcoder]

If at least part of the key repeats, it means more than one message is encrypted with the same key, which may allow you to extract part of the original message, which might lead to compromising the whole message (often one only needs some part of the message).

Actually, it's the most important of the three... The first two only make sure you end up with a good key (with an additional assumption that the cipher doesn't have weak keys).

OK. Does this mean that extending the key to make it as long as the message would do? I mean reusing the same key but shifted or semi-randomly bitmasked or anything else but in a way that's know to both encryption and decryption algorithm?

Seemed obvious the key would be 80 bit long "Just in case"...

I don't quite get you...

Just to theorise - I don't know exactly how Jacek broke the key, but I can make a guess at possible ways of dealing with the situation.

Knowing the key is a multiple of 8bits, one had to checks ten possible lengths. Now we know that statistically the character "e" is the most common in english language, so it is most likely to receive collisions on it. Unfortunately use of C++ may change those statistics, so we have two possible ways of overcoming this.
1. gather own statistics of C++ code by counting the number of occurences of each character in a large C++ code (like Qt sources, although it lacks comments).
2. try to guess most popular characters - I'd say they are " " (space), ":" (colon), ";" (semicolon) and "{","}" (braces).

The longer the text, the more collisions one may expect. Furthermore if the message is a C++ sourcecode, it most probably begins with a hash (#) - like in "#ifndef ..." or with a slash (/) - marking the beginnning of a comment. This gives additional insights, allowing one to try to guess the first character of the key right away. Furthermore if the following characters are asterisks (in case of the comment), then we might guess the beginning of the message is "/********************". That gives us more than the key length, so xoring the beginning of the ciphertext with assumed plaintext we receive the key. The rest is just about verifying the key by decrypting the rest of the message.

So as you see, you might have compromised the key yourself here. Again, I don't know if that was the path Jacek took to decode the message, but it's a possible strategy.

Another approach would be to try to find collisions at each 10th character of the data - that's where the amount of text for analysis is vital.

I know realize that the data itself was not very suited for XOR encoding...
Honestly Jacek, would you have done it so fast without knowing that it was C++ code???

[jacek]

I mean reusing the same key but shifted or semi-randomly bitmasked or anything else but in a way that's know to both encryption and decryption algorithm?

It could be enough.

I know realize that the data itself was not very suited for XOR encoding...

The problem is not with data, but with the method.

Honestly Jacek, would you have done it so fast without knowing that it was C++ code???

No.

[fullmetalcoder]

It could be enough.

I'll try this out then...

The problem is not with data, but with the method.

No.

Sounds like you're being a bit contradictory...

[jacek]

Sounds like you're being a bit contradictory...

Good cipher works on any data and it can withstand any kind of attack, including the known-plaintext one.

[wysota]

OK. Does this mean that extending the key to make it as long as the message would do? I mean reusing the same key but shifted or semi-randomly bitmasked or anything else but in a way that's know to both encryption and decryption algorithm?

If the message was long enough, that wouldn't have helped much. Knowing the pattern of masking bits or shifting one could still be able to find collisions, i.e. if you shift, you'll eventually get the original key again and it can happer faster when you use weak keys. For example if you rotated the key one bit to the right in each iteration, a weak key could be 1111 0000 1111 0000 - it repeats every half of its length (0101 0101 0101 0101 is even weaker).

So to be safe you need two things (at once):
- a good key
- a good cipher algorithm

[wysota]

@Fullmetacoder: Try breaking this one, it should take no longer than a few minutes to do it even if I don't tell you what kind of cipher it uses. The message is an abstract from this site.

NZ ZPRZXI VRRAMXVIMDOH VOY XDCRDOZOIH IVTMOU RVGI MO ILZ XDOIZHI ID LVKZ HDCZ FDGC DF XDCRAZIZOZHH - OD ADDHZ ZOYH, HIJWH VOY ODI NDGTMOU CZILDYH. MF ILZ FMOVA XDCRDOZOI MH AMCMIZY XDCRVGZY ID NLVI LVH WZZO YZXAVGZY MO ILZ RGDEZXI, ZPIGV XDYZ MGGZAZKVOI ID ILZ FJOXIMDOVAMIQ NLMXL MH RGDKMYZY MO ILZ FMOVA HDAJIMDO LVH ID WZ GZCDKZY.

ILZ XDYZ IVTMOU RVGI MO ILZ XDCRZIMIMDO HLDJAY WZ NZAA YZHMUOZY. QDJ HLDJAY RVQ VIIZOIMDO ID XAZVO MOIZGFVXZH, XDYZ GZJHZ, UZOZGMX HDAJIMDOH, YZHMUO RVIIZGOH VOY VAA DILZG ILMOUH ILVI CVTZ QDJG RGDEZXI AZHH ZGGDG-RGDOZ VOY ZVHMZG ID CVMOIVMO.

NZ ZPRZXI ILZ VRRAMXVIMDO DG XDCRDOZOI ID WZ WVHZY DO BI IZXLODADUQ. AMCMIMOU ZPIZGOVA AMWGVGMZH VOY VRRAMXVIMDOH OZZYZY ID JHZ ILZ RGDUGVC MH VYKMHZY, NLZGZ VRRAMXVWAZ (M.Z. NZ YDO'I ZPRZXI VO MYZ ID WZ V FJAAQ HZAF-XDOIVMOZY VRRAMXVIMDO, WJI NZ ZPRZXI V IZPI ZYMIDG ID YMHRAVQ IZPI JHMOU BI XAVHHZH VOY ODI ILMGY RVGIQ XDCRDOZOIH).

[fullmetalcoder]

If the message was long enough, that wouldn't have helped much. Knowing the pattern of masking bits or shifting one could still be able to find collisions, i.e. if you shift, you'll eventually get the original key again and it can happer faster when you use weak keys. For example if you rotated the key one bit to the right in each iteration, a weak key could be 1111 0000 1111 0000 - it repeats every half of its length (0101 0101 0101 0101 is even weaker).

When I mentioned predefined extension of the key to make it virtually as long as the message I had no precise idea but I'm now thinking about this concept : "the message is the key". My first approach is to keep the XOR block encryption but to avoid repeating the key by using the message as a key. The first block is encrypted with the key and then used as key to encrypt the next block and so on... This is not of course unbreakable but the first block can't be decrypted in any other way than brute-force search which makes the algorithm much stronger than the first one I proposed.

void encrypt(QByteArray& data, QByteArray& pass)
{
    int i = 0, e = data.size(), x = 0, m = pass.count();
    char c, *d = data.data(), *p = pass.data(), *b = new char [m];
 
    while ( i < e )
    {
        b[x] = d[i];
        d[i] ^= p[x];
 
        if ( !(x = (++i % m)) )
            qSwap(p, b);
    }
}
 
void decrypt(QByteArray& data, QByteArray& pass)
{
    int i = 0, e = data.size(), x = 0, m = pass.count();
    char c, *d = data.data(), *p = pass.data(), *b = new char [m];
 
    while ( i < e )
    {
        d[i] ^= p[x];
        b[x] = d[i];
 
        if ( !(x = (++i % m)) )
            qSwap(p, b);
    }
}

void encrypt(QByteArray& data, QByteArray& pass)
{
    int i = 0, e = data.size(), x = 0, m = pass.count();
    char c, *d = data.data(), *p = pass.data(), *b = new char [m];
    
    while ( i < e )
    {
        b[x] = d[i];
        d[i] ^= p[x];
        
        if ( !(x = (++i % m)) )
            qSwap(p, b);
    }
}

void decrypt(QByteArray& data, QByteArray& pass)
{
    int i = 0, e = data.size(), x = 0, m = pass.count();
    char c, *d = data.data(), *p = pass.data(), *b = new char [m];
    
    while ( i < e )
    {
        d[i] ^= p[x];
        b[x] = d[i];
        
        if ( !(x = (++i % m)) )
            qSwap(p, b);
    }
}

To copy to clipboard, switch view to plain text mode 

Further enhancement of this code could be :

• Compressing the data on-the-fly to reduce redundancy without increasing complexity (a simple RLE would be enough I think)
• Using tricks to make encryption a little more random. For instance XOR'ing with 0xff (one's complement) on some special occasions (data byte is even, or odd, or multiple of 3 or whatever...)

[wysota]

My first approach is to keep the XOR block encryption but to avoid repeating the key by using the message as a key. The first block is encrypted with the key and then used as key to encrypt the next block and so on...

Correct me if I'm wrong, but if the first ciphertext block is the key to the next, then all I have to do to break it is to use the previous block of ciphertext as the key for the next one. I won't be able to break the first block, but surely the rest will be deciphered in no time.

[fullmetalcoder]

Correct me if I'm wrong, but if the first ciphertext block is the key to the next, then all I have to do to break it is to use the previous block of ciphertext as the key for the next one. I won't be able to break the first block, but surely the rest will be deciphered in no time.

block1 ^ key => cypherblock1
block2 ^ block1 => cypherblock2
...

if, as you suggest, you do :
cypherblock2 ^ cypherblock1
<=> (block1 ^ key) ^ (block2 ^ block1)
<=> block2 ^ key

I don't see what is decrypted by doing so but maybe I missed something...

[wysota]

I thought you meant:
block1 ^ key => ciphertext1
block2 ^ ciphertext1 => ciphertext2

BTW. Your cipher is still weak. If you try to encrypt the sourcefile mentioned earlier, you'll notice that you expose some of the message (that in turn exposes the remaining part of the message, as the message itself is used as a key).

Known plaintext attack will expose the key immediately.

[fullmetalcoder]

BTW. Your cipher is still weak. If you try to encrypt the sourcefile mentioned earlier, you'll notice that you expose some of the message (that in turn exposes the remaining part of the message, as the message itself is used as a key).

That's why :

• The key is used only once and a new key is generated by the compression algorithm (though not in the code I posted...)
• It is highly recommended to use compression to prevent such exposition of the message that might endanger the key.

Also note that if you didn't have any hint about the content of the previous file the second remark would not be that crucial. To determine whether it is strong enough for my purpose (if I have to talk about cryptography in my paper it's better to present a decent algorithm... ) I'll put a new encrypted file on the same FTP ASAP so that you guys can crack it and tell me how hard it is...

Known plaintext attack will expose the key immediately.

I don't claim this method is perfect. As far as I'm concerned the risk of a plain text attack is about null because my data is randomly formatted (can be plain text, code, compressed odt, pictures, ...) and it is highly improbable that people wanting to decrypt it have more than a general idea of what it contains...

[wysota]

Try this one:

uint keygen(uint prevkey){
  int sum = 0;
  uint t = prevkey;
  for(int i=0;i<31;i++){
    if(t & 0x1) sum++;
    t >>= 1;
  }
  prevkey >>= 1;
  prevkey |= (sum & 0x1) << 31;
  return prevkey;
}

uint keygen(uint prevkey){
  int sum = 0;
  uint t = prevkey;
  for(int i=0;i<31;i++){
    if(t & 0x1) sum++;
    t >>= 1;
  }
  prevkey >>= 1;
  prevkey |= (sum & 0x1) << 31;
  return prevkey;
}

To copy to clipboard, switch view to plain text mode 

This generates iteration key. The cipher algorithm is the first you suggested - xoring plaintext with the key. The code above is a pseudo-random number generator that will generate pseudorandom keys based on the original key. You can obtain the same by doing srand(key) and then calling rand() - you'll also receive a stream of pseudorandom keys. The trick is that if you initialise the generator with the same seed, you'll receive the same result.

This should get you a decent cipher.

[fullmetalcoder]

Try this one:

uint keygen(uint prevkey){
  int sum = 0;
  uint t = prevkey;
  for(int i=0;i<31;i++){
    if(t & 0x1) sum++;
    t >>= 1;
  }
  prevkey >>= 1;
  prevkey |= (sum & 0x1) << 31;
  return prevkey;
}

uint keygen(uint prevkey){
  int sum = 0;
  uint t = prevkey;
  for(int i=0;i<31;i++){
    if(t & 0x1) sum++;
    t >>= 1;
  }
  prevkey >>= 1;
  prevkey |= (sum & 0x1) << 31;
  return prevkey;
}

To copy to clipboard, switch view to plain text mode 

This generates iteration key. The cipher algorithm is the first you suggested - xoring plaintext with the key. The code above is a pseudo-random number generator that will generate pseudorandom keys based on the original key. You can obtain the same by doing srand(key) and then calling rand() - you'll also receive a stream of pseudorandom keys. The trick is that if you initialise the generator with the same seed, you'll receive the same result.

This should get you a decent cipher.

There are many ways of generating pseudorandom integers and the one you suggest is probably as good as any other but the thing is that my algorithm uses passphrase which are sequences of ascii bytes longer than 4 bytes...

Another problem, appearing only when with using srtand() then rand() is that srand() might not lead to the same sequence of numbers, even if initialized with the same seed, under various computers (it's a matter of C runtime...)

[wysota]

but the thing is that my algorithm uses passphrase which are sequences of ascii bytes longer than 4 bytes...

But this is not a problem. You can extend the method to as many bytes as you want. You calculate the sum by iterating words, then you shift each word one bit to the right and set the oldest bit to the value of the youngest bit of the next older word. The oldest bit of the key is set based on the sum. For 32bit key I get about 2M different keys with this algorithm, allowing to safely encrypt about 8MB of data using distinct keys. Again, the cipher is vulnerable to the known plaintext attack if you're able to guess the beginning of the message (to get the first key used, so that you can generate the rest of the key stream). You can make it harder by using every n-th key from the stream (so "n" is also part of the key).

Another problem, appearing only when with using srtand() then rand() is that srand() might not lead to the same sequence of numbers, even if initialized with the same seed, under various computers (it's a matter of C runtime...)

It's not a matter of C runtime. rand() is always a pseudo-random generator. The same rand() implementation has to return the same stream for the same seed. Different implementations might return different streams though. I just wanted to show the principle, so that doesn't matter.