SHA-based encryption function in Python

[Bryan Olson]

Paul Rubin wrote:

 > ARGGH!  I knew about that before too, but forgot about it while writing
 > the code.

I figured you were testing us.

 > I will replace SHA(block) with SHA(key + block) and release
 > a new version tonight, with the MAC improved too.  Sound ok?


Let me see if I understand.  We start with a shared secret key called
"key", which may be of any length.  Each message requires it's own nonce
of 16 bytes.

 From this we form a session encrption key, called "enc_key" as:

     enc_key = _hash("enc" + key + nonce)

Now we need to intialize the variable "seed", and we need a new way
to do it.  Perhaps:

     seed = _hash("seed" + enc_key)

Then we form the running key, called "xkey", which is a list of
20-byte blocks.

     xkey = []
     for i in range(n_blocks_needed):
         seed = _hash(enc_key + seed)
         xkey.append(seed)

The ciphertext is the exclusive or of the plaintext and the running key.
The nonce travels with the ciphertext.


Now I have a few suggestions.

The system presents a cipher, a MAC, key derivations, and formats. I
think these should be defined individually.  I agree with defining how
to encrypt-and-sign with a master key, but I think the smaller elements
should also be defined and exposed on their own.

I would separate the IV from the ciphertext, and make computing the MAC
a separate function.  I see no need to include the nonce in computing
the auth_key. In some protocols, such as SSL/TLS, we would send a stream
in many sections.

Here's a candidate reference implementation.  Each function does one
thing that I believe should be individually defined.  The code is
written for lucidity and simplicity, not speed. I'm using Paul Rubin's
latest (at the time of this writing) MAC, but really I recommend going
with HMAC.


########################################################

import sha

class CryptError(Exception): pass

MACLEN = 8
IVLEN = 16


def session_cipher(enc_key, text):
     seed = _hash("seed" + enc_key)
     result_text = []
     while text:
         (block, text) = (text[:20], text[20:])
         seed = _hash(enc_key + seed)
         block = _xor_strings(block, seed[:len(block)])
         result_text.append(block)
     return "".join(result_text)


def session_sign(auth_key, text):
     k1 = _hash('auth1' + auth_key)
     k2 = _hash('auth2' + auth_key)
     return _hash(k1 + _hash(k2 + text))[:MACLEN]


def derive_enc_key(master_key, nonce):
     assert len(nonce) == IVLEN
     return _hash('enc' + master_key + nonce)


def derive_auth_key(master_key):
     return _hash('auth' + master_key)


def encipher(master_key, plaintext):
     nonce = _generate_nonce_somehow(master_key + plaintext)
     enc_key = derive_enc_key(master_key, nonce)
     return (nonce, session_cipher(enc_key, plaintext))


def decipher(master_key, nonce, ciphertext):
     enc_key = derive_enc_key(master_key, nonce)
     return session_cipher(enc_key, ciphertext)


def sign(master_key, text):
     session_key = derive_auth_key(master_key)
     return session_sign(session_key, text)


def verify(master_key, text, signature):
     if sign(master_key, text) != signature:
         raise CryptError, "invalid key or ciphertext"


def encipher_and_sign(master_key, plaintext):
     (nonce, ciphertext) = encipher(master_key, plaintext)
     signature = sign(master_key, ciphertext)
     return (nonce, ciphertext, signature)


def verify_and_decipher(master_key, nonce, ciphertext, signature):
     verify(master_key, ciphertext, signature)
     return decipher(master_key, nonce, ciphertext)


#############################################################
#   Utility functions

def _hash(x):
     return sha.new(x).digest()

def _xor_strings(s1, s2):
     return "".join(map(lambda x, y: chr(ord(x) ^ ord(y)), s1, s2))

_state = ""
def _generate_nonce_somehow(entropy=""):
     global _state
     import time
     _state = _hash(`time.time()` + _state + entropy)
     return _state[:IVLEN]


#############################################################
#   Not a great test but....

if __name__ == "__main__":
     master_key = "Big time secret key"
     plaintext = "No matter what happens, somebody just knew it would."
     nonce, ciphertext, sig = encipher_and_sign(master_key, plaintext)
     deciphertext = verify_and_decipher(master_key, nonce, ciphertext, sig)
     print deciphertext
     assert(deciphertext == plaintext), "Darn, it failed."