The principle of the stream cipher with examples in C #. From One-time pad to stream cipher based on hashf and CTR

In the course of the article, developing the idea of ​​"One-time Notepad", "invent" a stream cipher based on the hash function. We learn what Counter Mode Encryption CTR is.

Knowledge of the terms "hash function" and "One-time notebook" for reading is not necessary.

Disposable notebook

In "One-time Notepad" ciphertext is obtained by imposing a key on the plaintext. Overlaying can be done, for example, using bitwise XOR: each bit of plaintext XOR is followed by the corresponding (same in order) key bit.
')

Figure 1. Every bit of plaintext XOR is with the same key bit in order.

Accordingly, to decrypt, you need to XOR-write the ciphertext with the key.

var encoding = Encoding.GetEncoding(1251); var plainText = encoding.GetBytes("111111"); var key = encoding.GetBytes("123456"); // encrypt: key XOR plainText byte[] cipherText = new byte[plainText.Length]; new BitArray(key).Xor(new BitArray(plainText)) .CopyTo(cipherText,0); // decrypt: key XOR chipherText var decripted = new byte[cipherText.Length]; new BitArray(key).Xor(new BitArray(cipherText)) .CopyTo(decripted, 0); var decriptedStr = encoding.GetString(decripted);  1.    ,   ,       

The more random and unpredictable the key, the better, the harder it is to pick it up. For this "One-time Notepad" key must be random:

 var plainText = encoding.GetBytes("111111"); var key = new byte[6]; using (var randomGenerator = new RNGCryptoServiceProvider()) randomGenerator.GetBytes(key);  2.      

The key must be one-time

Obviously, the key length must be not less than the length of the text to be encrypted. If the key is shorter than the clear text, you can try to repeat it cyclically - Figure 2:


Figure 2. The key is shorter than the plaintext. Just repeat the key to cover all the encrypted text.

Key overlays on text are called gamming. In this terminology, the key of the “One-time Notepad” will be called the gamut.

An example of the method of cyclic overlay gamma

 //  XOR //    data    XOR, //   static IEnumerable<byte> XORStrimmed(byte[] gamma, IEnumerable<byte> data) { var gammaIndex = 0; foreach (var bb in data) { // XOR yield return (byte)(bb ^ gamma[gammaIndex]); if (gammaIndex < gamma.Length - 1) gammaIndex++; else gammaIndex = 0; } }  3.   XOR    

Let's see what happens if the text is longer than the key and we will simply repeat the gamma cyclically:

 var plainText = encoding.GetBytes("11111111111111111111111111111111111111111111111111"); var key = new byte[6]; using (var randomGenerator = new RNGCryptoServiceProvider()) randomGenerator.GetBytes(key); // encrypt: key XOR plainText var cipherText = XORStrimmed(key, plainText); // decrypt: key XOR chipherText var decripted = XORStrimmed(key, cipherText); var decriptedStr = encoding.GetString(decripted.ToArray());  4.       

You do not need to be a cryptographer to notice that the ciphertext was not very persistent (at least it is clear that the symbols in the plaintext are repeated):


Fig. 3. Ciphertext with a simple repetition of the gamma unstable

For the same reason, the notebook is called disposable - you cannot use the same key twice.

Such plaintext in the example is chosen for clarity. A good cipher, even for such a string, will produce a ciphertext without repeating patterns.

Stream cipher

As we have seen gamma should not be repeated. Every time the gamma ends for the next round, you need to somehow get a new gamma:


Figure 4. Every time the gamma ends, you need to make a new gamma. Each round has its own gamma.

We also know that gamma should not only not be repeated, but should also be as random as possible. However, if we generate a truly random gamut at each round, we will get a one-time notebook: the key will be the size of a ciphertext. This is not what we need.

We need a mechanism for generating a pseudo-random gamma, depending on the key. When decrypting, knowing the key, we should be able to generate the same gamma.


Figure 5. Stream cipher scheme

If our generator will make a pseudo-random gamut, depending on the key, for all plaintext, we will get a stream cipher.

Counter Mode Encryption CTR

Let's add picture 4: we need a function that will generate a gamma depending on the key and the round number:


Figure 6. Gamma for each round is made by a function depending on the key and the round number.

This is the Counter Mode Encryption CTR - the gamma generator receives a counter (counter) of the round at the input:


Figure 7. 3 rounds of stream cipher with Counter Mode Encryption CTR (except for one component, see below)

Hash function as gamma generator

A hash function is a function that converts plaintext into a pseudo-random sequence of a given length. Knowing the hash (the result of the hash function) it is impossible to recover the plaintext. Changing even one bit of cleartext results in a completely different, pseudo-random hash.

Those. we can use the hash function as a gamma generator:

Gamma Round = HASH (key + RoundIndex)

 private static IEnumerable<byte> XorCounterModeEncryptDecrypt(byte[] keyBytes, IEnumerable<byte> data) { if (keyBytes == null) throw new ArgumentNullException(nameof(keyBytes)); if (data == null) throw new ArgumentNullException(nameof(data)); int roundIndex = 0; byte[] roundGamma = null; int gammaIndex = 0; foreach (var d in data) { if (gammaIndex == 0) { // create gamma var counterBlock = keyBytes.Concat(BitConverter.GetBytes(roundIndex)).ToArray(); using (var sha = new SHA512Managed()) roundGamma = sha.ComputeHash(counterBlock); } yield return (byte)(d ^ roundGamma[gammaIndex]); if (gammaIndex < roundGamma.Length - 1) gammaIndex++; else { gammaIndex = 0; roundIndex++; } } // foreach }  5.   XOR,           

Usage example

 var plainText = encoding.GetBytes("11111111111111111111111111111111111111111111111111"); var key = encoding.GetBytes("1123456"); // encrypt: key XOR plainText var cipherText = XorCounterModeEncryptDecrypt(key, plainText); // decrypt: key XOR chipherText var decripted = XorCounterModeEncryptDecript(key, cipherText); var decriptedStr = encoding.GetString(decripted.ToArray());  6. /   Counter Mode Encryption   

Nonce, HMAC

The cipher implementation is not finished yet. In the current implementation, the same key with the same plaintext will always produce the same ciphertext. This is unacceptable: Imagine that the same encrypted commands “urgently sell bitcoins” are transmitted via a communication channel - this is a joke, but you get the idea.

So, one more requirement is added: each time during encryption, a different ciphertext should be obtained. In our case, this means that the gamma generator needs to be modified.

The problem is solved by the so-called Nonce:

• each time, during encryption, a random bit sequence is generated - Nonce
• Nonce is involved in the formation of gamma
• Gamma Round = HASH (Nonce + key + RoundIndex)
• Nonce is the same for all rounds.
• Nonce is distributed / stored with ciphertext. Those. Knowledge of Nonce, which was used to create a ciphertext, is not a secret.

Figure 8. 3 rounds of stream cipher with Counter Mode Encryption CTR with the addition of Nonce

HMAC is a way to add a dependency on a hash to some additional parameter. We achieved the same result (to make the cache dependent on several parameters) using concatenation. Those. logically

HASH (RoundIndex + key)

Same thing

HMAC (RoundIndex, key)

The conclusion is different, but logically the same thing.

 private static IEnumerable<byte> XorCounterModeEncryptDecrypt(byte[] keyBytes, byte[] nonceBytes, IEnumerable<byte> data) { if (keyBytes == null) throw new ArgumentNullException(nameof(keyBytes)); if (data == null) throw new ArgumentNullException(nameof(data)); if (nonceBytes == null) throw new ArgumentNullException(nameof(nonceBytes)); if (nonceBytes.Length < 4) throw new ArgumentOutOfRangeException(nameof(nonceBytes)); var nonce = new BitArray(nonceBytes); int roundIndex = 0; byte[] roundGamma = null; int gammaIndex = 0; foreach (var d in data) { if (gammaIndex == 0) { // create gamma // create counter block: Nonce + Counter // another way: Nonce XOR Counter (has some constraints) var counterBlock = nonceBytes.Concat(BitConverter.GetBytes(roundIndex)).ToArray(); using (var hmacSHA = new HMACSHA512(keyBytes)) roundGamma = hmacSHA.ComputeHash(counterBlock); } yield return (byte)(d ^ roundGamma[gammaIndex]); if (gammaIndex < roundGamma.Length - 1) gammaIndex++; else { gammaIndex = 0; roundIndex++; } } // foreach }  7.   XOR,          .  Nonce  HMAC 

 var plainText = encoding.GetBytes("11111111111111111111111111111111111111111111111111"); var key = encoding.GetBytes("1123456"); var nonce = new byte[4]; using (var randomGenerator = new RNGCryptoServiceProvider()) randomGenerator.GetBytes(nonce); // encrypt: key XOR plainText var cipherText = nonce.Concat( XorCounterModeEncryptDecrypt(key, nonce, plainText) ); // decript: key XOR chipherText var decripted = XorCounterModeEncryptDecrypt( keyBytes: key, nonceBytes: cipherText.Take(4).ToArray(), data: cipherText.Skip(4)); var decriptedStr = encoding.GetString(decripted.ToArray());  8.   

Algorithm

We briefly describe the resulting algorithm:

1. We make random nonce. One Nonce is used for all rounds.
2. For each round, we calculate a unique CounterBlock, which will be used to generate a gamma.
   
   CounterBlock = Nonce + Round Number
3. Generating gamma for the round
   
   Gamma = HMAC (CounterBlock, Key)
4. Putting Gamm on plain text with bitwise XOR
5. When the gamma ends, the next round begins. Increasing the number of round by 1 –that way the new round gets a new gamut

Disclaimer

The above bicycle is for educational purposes only. The idea of ​​using hash functions in stream ciphers is not new (see below). As far as I know there is no unequivocal opinion on the persistence of such schemes. Perhaps this question is simply not relevant - hashes work slower.

In defense of the idea, I will give a comment from the initial discussion on pgpru.com :
using a hash as a PRF to create a stream with which XOR data could be encrypted is not new.

For example, in the description of one of the SHA3 finalists, the hash function Skein (http://www.skein-hash.info/sites/default/files/skein1.3.pdf), a similar use-case is described in the PDF hash itself.

If you see an inaccuracy, a mistake - treat with understanding. I am not a cryptographist, I am engaged in information security only for applied purposes when developing projects, without exceeding the requirements for information security.

Links

GitHub StreamCipherOnHashAndCTRMode

Primary discussion on pgpru.com
Block cipher mode of operation
Implementing 5 modes of operation with a hash function
Information Theory and One-Time Notebook
Stream cipher