<div dir="ltr">We see these posted on this list often, to the annoyance of some, but to some of us they are fun to analyze and crack.  If you are one of the readers who find this annoying, please skip this thread.<div><br></div><div>On this post, I just want to demonstrate to those of us who are not crypto experts what real crypto people already know: that making unbreakable symetric key crypto is trivial.  Any decent crypto hacker should be able to do it.  While making an unbreakable symmetric key algorithm is trivial, it is very difficult to design one that is _useful_.  It also turns out to be very hard to get all the details right, such as counter-mode encrypt-then-mac, and implementing side-channel resistance.  Further, it is extremely difficult to design a new useful public key crypto system, which I wont even touch here.</div><div><br></div><div>Feel free to try an crack this new algorithm.  More likely than not, I made at least one mistake for you to catch :)</div><div><br></div><div>The basic strategy is to create a crypto grade hash function, and then turn that into a crypto-grade symmetric-key encryption algorithm.  Let's call this new hash function H, and the new encryption algorithm E.  E will be a block-based cipher.  The key will be 256 bits and the data will be 512 bits.  H will take a "key" and "data", both 256 bits, and in theory return a "compressed" 256 bit cryptographic-grade hash of them.  Given H, we create E like this:</div><div><br></div><div><div><div>def E(key, data):</div><div>    if key >= (1 << 256) or data >= (1 << 512):</div><div>        raise Exception("E input data too large")</div><div>    dlow = data & ((1<<256)-1)</div><div>    dhigh = data >> 256</div><div>    for i in range(4):</div><div>        dlow ^= H(key, dhigh)</div><div>        dhigh ^= H(key, dlow)</div><div>    dlow ^= H(key, dhigh)</div><div>    return (dhigh << 256) | dlow</div></div></div><div><br></div><div>Assuming H acts as an ideal cryptographic hash function, then after the first iteration of the for loop, the output is scrambled beyond recognition.  However, at that point, the output is "malleable", meaning that an attacker can flip bits of the dhigh output, and the same bits of the dhigh input will be flipped when decrypted.  This gives an attacker too much control, so we need at least one more iteration, and just to be paranoid, I did 4, though I think technically only 2 are required.  The last XOR is just to make this function the inverse of itself so that I do not need a separate encrypt and decrypt function.</div><div><br></div><div>Next, we need a super-duper hash function H.  All that is required is mixing bits back and forth like above, but this time instead of a key, we need to use three primitives which when mixed are difficult to mathematically analyze:  ADD, ROTATE, and XOR, sometimes called ARX.  I used multiplication rather than ADD, but it doesn't really matter since multiplication is just a bunch of additions.  Designing this well is an art because it has to map very well to the SIMD units on modern processors, and mix bits quickly.  In my case, I simply do a large number of rounds.  Is it enough?  Probably, but a proof of this is beyond my skill currently.  "Proving" this is enough is basically a matter of asking the world's best crypto experts to analyze it for days.  Here's my super-duper hash function, which I simply conjecture is secure enough, based on my using many rounds of ARX:</div><div><br></div><div><div>def H(key, data):</div><div>    state = key << 256 | data</div><div>    for i in range(64):</div><div>        state = doRound(state)</div><div>    return state & ((1 << 256)-1)</div></div><div><br></div><div><div>def doRound(state):</div><div>    vlow = state & ((1 << 256)-1)</div><div>    vhigh = state >> 256</div><div>    vlow = (vlow*(vhigh | 1)) & ((1 << 256)-1)</div><div>    vhigh ^= vlow</div><div>    vlow = rotateBits(vlow, 39)</div><div>    vhigh = rotateBits(vhigh, 209)</div><div>    return (vhigh << 256) | vlow</div><div><br></div><div>def rotateBits(data, dist):</div><div>    return (data >> dist) | ((data & ((1<<256-dist)-1)) << (256-dist))</div></div><div><br></div><div>The "round" function has a multiplication, XOR, and rotation, so it's probably good enough if iterated enough.  Doing it only 64 times might be too few, but with the multiplication instead of an addition, I suspect this mixing is enough.  There are two things to note about this hash function.  First, the doRound function is reversible.  This means that given the output of doRound, we can always compute what the input must have been.  This property insures that all 64 calls to doRound result in a 1-to-1 permutation of possible inputs to outputs.  No "entropy" is lost.  The only non-reversible step is the last step, where we return the low 256 bits of state.</div><div><br></div><div>Now we have a block cipher!  Let's try it in Python.  I added these lines for the test:</div><div><br></div><div><div>data = 0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef</div><div>key = 0xaaaabbbbccccddddeeee</div><div>encData = E(key, data)</div><div>print "Encrypted data %x" % encData</div><div>decData = E(key, encData)</div><div>print "Decrypted data %x" % decData</div></div><div><br></div><div>When run, it prints:</div><div><br></div><div><div>Encrypted data d530bb53e81b8fb8e61881d58fc1d5d1fbde89d408ed2798dc27e4987ce5b00fa35dc782d627c5dd06b1f87afb7c170a23b0cb30fdeebb6b15f5d67f2fbff724</div><div>Decrypted data deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef</div></div><div><br></div><div>How cool is that?</div><div><br></div><div>So, are we done?  Not really.  A block cipher can only encrypt a block at a time, and it doesn't even do that properly yet.  For example, any 0 data will always encrypt to the same output for any given key.  If we know that a file is mostly 512-bit blocks of 0's, we can figure out where the 512-bit 0 blocks are in the the file by looking at the encrypted data.  To avoid this, we need to encrypt the file in "counter mode", meaning we add 1 to the key each time we encrypt a block.  Also, we don't want the same file to be encrypted the same way twice, because that let's an attacker compare your encrypted file to a database of encrypted files he has, and unless your file is unique, he will figure out your data.  We need a "nonce" to fix this, which is a long random value that we mix in somehow to make each encrypted version of the same file unique.  Here's an example counter-mode encryption function:</div><div><br></div><div><div>def encryptFile(filename, key):</div><div>    if filename.endswith(".enc"):</div><div>        outFilename = filename[:-4]</div><div>        encrypting = False</div><div>    else:</div><div>        outFilename = filename + ".enc"</div><div>        encrypting = True</div><div>    with open(filename, "rb") as infile:</div><div>        with open(outFilename, "wb") as outfile:</div><div>            if encrypting:</div><div>                rndfile = Random.new()</div><div>                nonce = bytes2int(rndfile.read(32))</div><div>                outfile.write(int2bytes(nonce, 32))</div><div>            else:</div><div>                nonce = bytes2int(infile.read(32))</div><div>            key ^= nonce</div><div>            for data in blocksFromFile(infile):</div><div>                encData = E(key, data)</div><div>                outfile.write(int2bytes(encData, 64))</div><div>                key = (key + 1) & ((1 << 256)-1)</div></div><div><br></div><div>This has one significant error still: I did not deal with padding the last block, and the last block will be decrypted incorrectly.  I'm too lazy at the moment to fix it :)  Also, even with the nonce and counter mode, we have no data integrity check.  We should MAC the encrypted data so that we can verify the file has not been modified.  Otherwise, counter mode is just not good enough.  But... this is enough for a fun quick hack for today :)</div><div><br></div><div>Python code, with goobered padding and no MAC, attached.</div><div><br></div><div>Bill</div></div>