Suppose two parties want to communicate securely with each other (Bob and Alice) using a simple messaging system in English. There are approximately 180,000 currently used words in the English language.
Bob creates a random private key of 512 bits in length e.g.
Bob also chooses a random hash function from a group of hash functions that all output 512 bits. These could be SHA-2, Keccak, Grøstl, BLAKE, JH, Whirlpool and Skein hash functions.
Bob gives the key and chosen hashing method to Alice (either in person or using some other key exchange method).
Using a program and the dictionary of 180,000 words, Bob and Alice compute HMAC(key, word) for each word in the dictionary using the chosen hash function. Each person calculates this on their machine.
The values are stored in a lookup table with columns (id, word, hmac) in an indexed database on each person's machine. With a HMAC generation time of 23 milliseconds per word on a single core (reference machine: Core i5 @2.67GHz), this would take 69 minutes to construct a database of values given 180,000 words. Using all 4 cores, splitting up the work and using multithreaded programming this could be dropped to 17 minutes to generate the full database on each machine. This is a one-time generation, so no big deal.
Bob writes message to Alice.
For encryption, the program selects each plaintext word in the message, then looks up the corresponding HMAC hash value in the database then replaces the plaintext word with that hash value. A database lookup for each word and corresponding hash will be very fast in a modern, indexed database.
The hashes for each word are concatenated together so it is one full string of unintelligible text. This makes up the ciphertext.
A message authentication code is computed on the text using HMAC(key, ciphertext) and sent with the message e.g. ciphertext || MAC (concatenated).
Alice receives the encrypted message. Grabs the last 512 bits of the message which is the MAC. Then validates the MAC with her copy of the key and the hash algorithm using HMAC(key, ciphertext). Incorrect MACs mean the message is discarded immediately.
Alice's program breaks up the message into the hashed words as it knows each word was hashed into a fixed length 512 bit hash.
Alice's program looks up each hashed word in her database's dictionary of words to retrieve the corresponding plaintext word. The program assembles the message back to plaintext for her. This database lookup for each word and corresponding hash should also be very fast in a modern, indexed database.
The strength of the protocol relies on the difficulty in computing a pre-image of the HMAC hash of one of the hashed words to find the key. This would be 2512 for a standard computer using a brute force search or 2256 using Grover's algorithm.
There is also security in that the attacker does not know which hash function that was used by either party. They will have to try brute forcing using all available 512 bit hash algorithms.
All hashed words compute to the same length output e.g. 512 bit. This means shorter length words are indistinguishable from longer ones.
If the hashed output and MAC are concatenated as a single string and sent, then the output is indistinguishable from a random string.
Frequency analysis of the output might help determine simple words in the ciphertext such as 'the' etc if that word is repeated and sent multiple times. This isn't necessarily a problem as it's only a simple word and doesn't convey much meaning to the message. You can also avoid that by not using simple words at all in the message.
The message doesn't account for numbers or punctuation. Solution would be to send simple messages such as 'LEAVE MIDNIGHT' then any further sentences could be sent in another message. Also numbers could be expanded to their word equivalent e.g. '2' becomes 'TWO'.
The time to generate the dictionary of words/hashes can be time consuming. As mentioned it may only take 17 minutes using a fast computer and multithreaded program to create the dictionary on each computer. With a Core i7 or ever increasing speeds of computers it would be even faster. From there the same dictionary could be transferred to any other devices needing to communicate.
The encrypted output is much longer than the message itself. Not really a big deal considering today's networking and storage capabilities.
Assuming an attacker knew the protocol, they may be able to discern how many words were in the message based on the length of the ciphertext. This could be fixed by using padding words, and setting a fixed length message size.
Now I would appreciate some constructive feedback.
- Are there any similar encryption systems currently in use?
- What else could go wrong with the protocol?
- What are some more downsides and mitigations?
- What are some improvements that could be made?
Updates after feedback
After feedback regarding the scheme it is vulnerable to chosen-plaintext attack and frequency analysis of past messages unless each word is only ever used once. This is not particularly usable so I devised some changes.
A random nonce/IV is created for each message. This will be 512 bits and sent with the message. To encrypt, Bob computes HMAC(key, nonce || word) for each word in the message. || indicates concatenation. Encryption will be very fast and a lookup dictionary is no longer needed as it will change each message.
For decryption, Alice constructs a temporary dictionary using HMAC(key, nonce || word) for each word in the dictionary. Alice's program looks up each hashed word in her database's dictionary of words to retrieve the corresponding plaintext word. The program then reassembles the plaintext message.
Only disadvantage is that the decryption of each message will be slower. This could be made faster by using more powerful hardware, e.g. faster, more modern CPUs or multi-cpu/multi-core server system and splitting up the work for each core. Decryption time decreases with more powerful hardware. The scheme still maintains security in that it is very difficult (2512) for an attacker to find a pre-image and retrieve the original key especially when they don't know the exact hash algorithm that is being used. This would be ideal for organisations with dedicated hardware for sending and receiving messages.
For modern PCs at the moment it may be possible to reduce the output size of the hash algorithms e.g. 256 bit to decrease the decryption time for each message, while still maintaining a good security margin. Quantum cryptography would reduce that to 2128 to find a pre-image however which is still a long time even for an attacker with supercomputers. I would not lower the hash size below that.