Hash-Based Cipher

This is a symmetric encryption method based on a hash function h.

It's not particularly efficient, but it is easy to remember and implement.

The idea came after learning two concepts:

• stream ciphers
• Lamport signatures

Similar to how Lamport signatures use a hash function as the foundation for asymmetric signatures, Based Cipher tries to use a hash function as the foundation for symmetric encryption.

Each character in a plaintext str is encrypted like so:

cipher[i] = h(str[i] + i + key + nonce)

This maps each character to a ciphertext value. The mapping is different for each key, nonce and index.

Each component exists because:

• str[i] is the data to be encrypted
• i is relevant so two equal characters at different positions are not known to be equal from the ciphertext
• only actors who know key can produce and reproduce ciphertext
• nonce is relevant so two equal characters at same positions are not known to be equal from two different ciphertexts, it needs to be unique for each ciphertext

The nonce must be extractable from the ciphertext or communicated through another channel:

cipher[-1] = nonce

Therefore it should just be randomly generated and not reveal anything about anything.

But how can I decrypt? h is a one-way function.

Yes, but if you have the ciphertext and key:

• i is known
• key is known
• nonce is known
• cipher[i] is known

And while str[i] is technically unknown, it can only be one of 256 values (if the alphabet is bytes).

So, you can just try h(? + i + key + nonce) at most 256 times, until you get cipher[i].

And once you match cipher[i], you know what str[i] is.

Repeat that for each i and you'll get the plaintext.

relation to Lamport signatures

Lamport signatures create secret values and publish their hashes. Later, revealing one of the secret values proves knowledge of the secret key.

This cipher does something similar: instead of choosing between two possible secret values, it chooses between one secret value for each possible character.

For each position, the key and nonce create a mapping:

secret character -> hash value

The ciphertext value is the hash value corresponding to the actual character.

Decryption works by searching through the possible characters until finding the matching hash.

With a bit-based alphabet, this becomes even closer to Lamport signatures:

0 -> h(0 + i + key + nonce)
1 -> h(1 + i + key + nonce)

signed message / encrypted message

In Lamport signatures the message is known by both parties, the signer and the verifier.

In Based Cipher the message is known by the encrypter, not known by the decrypter initially.

secret key / domain

In Lamport signatures the secret is known by one party, the signer.

In Based Cipher, that secret is known (i.e. can be derived) by both parties, the encrypter and the decrypter. The secret is the domain of all hash input values i.e. hash inputs of all possible characters/bits.

The difference is that Lamport signatures store random secret values, while Based Cipher derives the possible values from the character, index, key, nonce.

public key / ciphertext

In Lamport signatures, the hash outputs of all secret values are the public key.

In Based Cipher, the ciphertext is a fraction of what the public key in Lamport signatures is. Only that fraction is published, and used by the decrypter to reproduce the message that was not known to him initially. In Based Cipher, what is not part of this fraction must remain secret. It must also remain secret, which fraction was published.

h requirements

h needs some properties:

• one-way
• avalanche effect
• collision resistant

If the input changes slightly, the output should change unpredictably.

If the output is large, the ciphertext will be very large. The ciphertext will always be quite a bit larger than the plaintext.

example

Let's say:

# nonce should be larger and doesn't have to be hexadecimal ASCII, this is just an example
nonce=$(</dev/urandom head -c 8 | xxd -p)
# key should also be much more secure
key=password123
# space separated characters, so we can use shell for loops
plaintext="h e l l o"

The following script prints the ciphertext to stdout.

echo $nonce
i=0
for str_i in $plaintext
do
	sha256sum <<<"$str_i $i $key $nonce"
	i=$(( $i + 1 ))
done

The ciphertext:

676af7cc8d0c0653
53a05dbfafe643b54e9650e643abb66496edf1ede586663d96e992b6d7d41667 *-
2d4e6396a4767761a204810571c11bb2177ae2f98ca8904674bd90967a80f995 *-
2986ad39d030223b5a0ea61992a62bcc1471fd23568edf6ac9edd4db920def58 *-
aeb25f6df961a4e8b20bfb48071849076a81ed9dae32cf151073a94ec8122331 *-
543fe09195ca4da20b96301b85df8efbde2503f9b58554b6a21fda7a734d6ac2 *-

Now, I won't write a shell script for decrypting - it would be much less tedious in a real programming language.

But just to illustrate, let's attempt to decrypt the fifth character:

$ sha256sum <<<"m 4 password123 676af7cc8d0c0653"
486539f9640623fc6b6e534898da1075d496ac897f25ae50428ce4b682b37e58 *-

$ sha256sum <<<"n 4 password123 676af7cc8d0c0653"
e99154b69ccef255c20c345457cded86066e71049cd912609a80c9ac857437d0 *-

$ sha256sum <<<"o 4 password123 676af7cc8d0c0653"
543fe09195ca4da20b96301b85df8efbde2503f9b58554b6a21fda7a734d6ac2 *-

Oh wow, we've seen 543fe091... before! str[4] must be 'o'.