Encrypt a message with hash function, shared symmetric key, but no cipher

I am very new to Crypto and need some clarification or input. The question is:

Suppose that Alice wants to encrypt a message for Bob, where the message consists of three plaintext blocks, $P_0$, $P_1$, and $P_2$ - Alice and Bob have access to a hash function and a shared symmetric key $K$, but no cipher is available. How can Alice securely encrypt the message so that Bob can decrypt it?

What I had came up with appears to work but seems way too complicated.

Alice can compute an HMAC using the hash function, message and key for integrity and send it to Bob like so:

• Let $M$ = the plaintext consisting of $p_0, p_1, p_2$,
• Let $B$ be the block length of hash in bytes,
• ipad = 0x36 repeated $B$ times,
• opad = ox5C repeated $B$ times.

Then the HMAC of $M$ is defined to be:

$$HMAC(M, K) = H(K \oplus opad, H(K \oplus ipad, M))$$

Since there is no cipher for the symmetric key, Alice can send Bob a public key where only she has the private key. From here she can send the ciphertext $C = [M]$. Alice to Bob and Bob can verify decrypting ${M}Alice = M$ and plugging it into $HMAC(M, K) = H(K \oplus opad, H(K \oplus ipad, M))$ is consistent with what Alice had originally sent.

First, is this a way to encrypt/decrypt a message? Second, is there an easier way? No cipher available means the message cannot simply be encrypted/decrypted with the symmetric key, correct?

• your solution uses a public key encryption scheme... are you sure this is allowed? Hint: HMAC is the right direction and you are not asked to guarantee authenticity / integrity of the data. Sep 23 '15 at 8:33
• Hint: the OTP is secure if it uses a shared secret random pad as wide as the plaintext. Can you use HMAC and K to build (a functional equivalent of) such pad?
– fgrieu
Sep 23 '15 at 8:46

There is a simpler way: implement a stream cipher using the hash function, and use that to encrypt the plaintext.

Probably the most used stream mode is counter (CTR) mode, which is normally defined for block ciphers. CTR mode works equally well with a PRF (MAC) as with a PRP (block cipher). It only uses the function as a one-way function; with a block cipher either the encrypt or decrypt direction (of the block cipher) is used.

The CTR mode for HMAC can be implemented as follows: $C_i = HMAC(k, {nonce} | {I2OS}(i, 4)) \oplus M_i$ where:

• $C$ is the ciphertext;
• $i$ designates the block;
• $k$ is the key;
• $nonce$ is a value that is changed for every ciphertext computation;
• $I2OS$ is a conversion method to convert an integer to a binary encoding and
• $M$ is the message to encrypt.

$I2OS$ is configured using a static size of - in this case - 4 bytes. The blocks have the same size as the hash output. For the last block only the leftmost bytes can be used.

The $nonce$ or IV could be a random value that sent with each ciphertext. In principle it can have any value as long as it is unique. It forms the counter value together with the encoded value of $i$.

Decryption is of course identical: $M_i = HMAC(k, {nonce} | {I2OS}(i, 4)) \oplus C_i$

Your scheme may work: basically you can perform $T=HMAC(K, K_{pub})$ and send $K_{pub}|T$. Then the receiver party knows that the public key is indeed from the sender, and they can use it to encrypt.

However:

• this still needs an encryption primitive, i.e. a cipher;
• this is an online protocol rather than direct encryption;
• this is probably not what was meant, as the split of the message $M$ into blocks indicates.
• How will Bob know what the value of nonce in order to decrypt? Sep 24 '15 at 7:52
• It's in there David: "... e.g. a random value send with each ciphertext." Most modes of operation have an IV/nonce as input, so handling would be identical to e.g. AES CTR mode. Sep 24 '15 at 11:02