Cryptography : is it me ???

[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.

[Brandybuck]

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

[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.

[fullmetalcoder]

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).

Interesting. There's a thing I always wanted to know about shifts in C++... What asm instructions are used? In z80 for example (whic is the only assembly language I know) there are many different shift/rotate instructions. Some that preserve the content of the byte whatever happens, some that set "new" bits to the content of the "carry flag" which is affected by other operations, including shifts...

You can make it harder by using every n-th key from the stream (so "n" is also part of the key).

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.

Yes but each C run time (VS / MinGW / GCC / ..) may have a different generator... If so the rand() function is not affordable...

[wysota]

Some that preserve the content of the byte whatever happens, some that set "new" bits to the content of the "carry flag" which is affected by other operations, including shifts...

Bit shifting operator from C/C++ fills the oldest/youngest bits with zeros. In assembly it also depends on little/big endianness and some other things (like the register used).

If you use subsequent keys, compromising one of them allows the attacker to generate all the remaining keys. If you use every nth key instead (and hide the "n" from the attacker), then it makes it harder for the attacker to break the key (he/she needs to break two blocks). If you extend the idea by using some S-block to pseudo-randomise the "n", you'll make the key even safer.

Yes but each C run time (VS / MinGW / GCC / ..) may have a different generator... If so the rand() function is not affordable...

I didn't say to actually use rand() in a cipher, I said it performs the same task as the function I implemented.

[fullmetalcoder]

Bit shifting operator from C/C++ fills the oldest/youngest bits with zeros. In assembly it also depends on little/big endianness and some other things (like the register used).

Good to know...

If you use subsequent keys, compromising one of them allows the attacker to generate all the remaining keys. If you use every nth key instead (and hide the "n" from the attacker), then it makes it harder for the attacker to break the key (he/she needs to break two blocks). If you extend the idea by using some S-block to pseudo-randomise the "n", you'll make the key even safer.

It's a good idea but how do we compute the "n"??? If it's generated from the first key or the first unencrypted block or anything like that it does not provide any security enhancement except if you consider that the attacker ignore the algorithm used but in this case he doesn't stand a chance to break the message... BTW what is a "S-block" ???

[wysota]

It's a good idea but how do we compute the "n"???

S-box will handle that.

If it's generated from the first key or the first unencrypted block or anything like that it does not provide any security enhancement except if you consider that the attacker ignore the algorithm used but in this case he doesn't stand a chance to break the message...

No, it's not "generated" from key, it's part of the key. Consider the key to be made of two parts - one is the S-box number used and the other is the seed for the key stream generator.

BTW what is a "S-block" ???

Eem... sorry, should be S-box

Generally the idea is that n changes every block and you don't know which S-box is used, so you can't follow the pattern - you have to check every S-box. The larger the number of S-boxes, the better the security. Additionally you can introduce another level - switch S-boxes during computation.

Of course all that makes the cipher quite computation intensive and hard to implement in hardware.

[jacek]

Bit shifting operator from C/C++ fills the oldest/youngest bits with zeros.

Are you sure?

#include <iostream>
#include <iomanip>
#include <limits>
 
template< class T >
void print( const char * l, T v )
{
   std::cout << l
             << std::hex
             << std::showbase
             << std::internal
             << std::setw(10)
             << std::setfill('0')
             << v
             << std::endl;
}
 
int main()
{
   int a = 1;
   unsigned int b = 1;
   int c = -1;
   unsigned int d = std::numeric_limits< unsigned int >::max();
 
   print( "a  = ", a );
   print( "a' = ", a << 1 );
 
   print( "b  = ", b );
   print( "b' = ", b << 1 );
 
   print( "c  = ", c );
   print( "c' = ", c >> 1 );
 
   print( "d  = ", d );
   print( "d' = ", d >> 1 );
 
   return 0;
}

#include <iostream>
#include <iomanip>
#include <limits>

template< class T >
void print( const char * l, T v )
{
   std::cout << l
             << std::hex
             << std::showbase
             << std::internal
             << std::setw(10)
             << std::setfill('0')
             << v
             << std::endl;
}

int main()
{
   int a = 1;
   unsigned int b = 1;
   int c = -1;
   unsigned int d = std::numeric_limits< unsigned int >::max();

   print( "a  = ", a );
   print( "a' = ", a << 1 );

   print( "b  = ", b );
   print( "b' = ", b << 1 );

   print( "c  = ", c );
   print( "c' = ", c >> 1 );

   print( "d  = ", d );
   print( "d' = ", d >> 1 );

   return 0;
}

To copy to clipboard, switch view to plain text mode 

Output:

$ ./a.out
a = 0x00000001
a' = 0x00000002
b = 0x00000001
b' = 0x00000002
c = 0xffffffff
c' = 0xffffffff
d = 0xffffffff
d' = 0x7fffffff

There are two right shift operators: logical and arithmetical (the latter replicates the sign bit).

[wysota]

I was shifting an unsigned integer, so it didn't matter But yes, you're right - the sign has to prevail.

[fullmetalcoder]

No, it's not "generated" from key, it's part of the key. Consider the key to be made of two parts - one is the S-box number used and the other is the seed for the key stream generator.

Generally the idea is that n changes every block and you don't know which S-box is used, so you can't follow the pattern - you have to check every S-box. The larger the number of S-boxes, the better the security. Additionally you can introduce another level - switch S-boxes during computation.

Of course all that makes the cipher quite computation intensive and hard to implement in hardware.

My goal here is not to obtain the most secure algorithm ever... I need something simple and fast enough to be describe as an appendix of my paper... I can't afford a long and complicated stuff because it is not a paper on computer science in particular but on math in general and even if I was free to choose any math-related topic there are some limits...

So here comes the fun. The link below points to a XOR encrypted version of my paper in its current state. I use the last version of the algorithm I proposed so all you have to do is to break the first block. However there are some difficulties :

• AFAIK the only way to break it is a brute-force attack or a stunning luck...
• The key is rather big say between 15 and 25 chars => 120 and 200 bits => quite a number of possibilities...
• The input data is compressed due to the file format used (a "all-in one" document with text formatting and embedded images...)

However you have some insights : it's written in english, it deals with "algorithms", "computational complexity", "cryptography", ...

The encrypted file!

Good luck to the ones who won't be able to resist and attempt to crack it!

P.S : if you managed to break the code may you take a look at it and report mistakes in the content or the expression (english is not my native language...)