[Cryptography] Nu supr unbrakable cripto

[Bill Cox]

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.

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.

Feel free to try an crack this new algorithm.  More likely than not, I made
at least one mistake for you to catch :)

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:

def E(key, data):
    if key >= (1 << 256) or data >= (1 << 512):
        raise Exception("E input data too large")
    dlow = data & ((1<<256)-1)
    dhigh = data >> 256
    for i in range(4):
        dlow ^= H(key, dhigh)
        dhigh ^= H(key, dlow)
    dlow ^= H(key, dhigh)
    return (dhigh << 256) | dlow

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.

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:

def H(key, data):
    state = key << 256 | data
    for i in range(64):
        state = doRound(state)
    return state & ((1 << 256)-1)

def doRound(state):
    vlow = state & ((1 << 256)-1)
    vhigh = state >> 256
    vlow = (vlow*(vhigh | 1)) & ((1 << 256)-1)
    vhigh ^= vlow
    vlow = rotateBits(vlow, 39)
    vhigh = rotateBits(vhigh, 209)
    return (vhigh << 256) | vlow

def rotateBits(data, dist):
    return (data >> dist) | ((data & ((1<<256-dist)-1)) << (256-dist))

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.

Now we have a block cipher!  Let's try it in Python.  I added these lines
for the test:

data =
0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef
key = 0xaaaabbbbccccddddeeee
encData = E(key, data)
print "Encrypted data %x" % encData
decData = E(key, encData)
print "Decrypted data %x" % decData

When run, it prints:

Encrypted data
d530bb53e81b8fb8e61881d58fc1d5d1fbde89d408ed2798dc27e4987ce5b00fa35dc782d627c5dd06b1f87afb7c170a23b0cb30fdeebb6b15f5d67f2fbff724
Decrypted data
deadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef

How cool is that?

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:

def encryptFile(filename, key):
    if filename.endswith(".enc"):
        outFilename = filename[:-4]
        encrypting = False
    else:
        outFilename = filename + ".enc"
        encrypting = True
    with open(filename, "rb") as infile:
        with open(outFilename, "wb") as outfile:
            if encrypting:
                rndfile = Random.new()
                nonce = bytes2int(rndfile.read(32))
                outfile.write(int2bytes(nonce, 32))
            else:
                nonce = bytes2int(infile.read(32))
            key ^= nonce
            for data in blocksFromFile(infile):
                encData = E(key, data)
                outfile.write(int2bytes(encData, 64))
                key = (key + 1) & ((1 << 256)-1)

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

Python code, with goobered padding and no MAC, attached.

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151231/2c15ee04/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: nucrypto.py
Type: text/x-python
Size: 2428 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151231/2c15ee04/attachment.py>