Insights into Modern Cryptography

Cryptography, the science of secret communication, is the answer to this challenge. The etymology of the word “cryptography” comes from the Greek “crypto”, which means “hidden” or “secret”, and “Graphy”, which denotes a process or form of drawing, writing, or describing.

With the rise of online betting and internet security needs, cryptography has become a multi-faceted subject. Using encryption as a process or algorithm to make things secret is but one function of cryptography. Beyond that, cryptography must be able to protect against eavesdroppers, chosen plain text attacks and chosen cipher text attacks, as well as insure any number of the following:

Confidentiality: Defined as the intent to keep secret.

Integrity: A way to confirm the lack of corruption of data.

Authentication: A way to prove that the device with which you are communicating is actually the device it claims to be and not a third party attacker.

Authorization: The proper assignment of permission to do something.

Modern cryptography was developed after the 2^nd world war. In 1949, Claude Shannon conceptualized the information behind theoretic security. His basic idea was this: a cipher text should reveal no information about plain text. In mathematics, it is written this way:

Perfect Secrecy by Shannon

 ∀ messages m₀ and m₁ ϵ M (space of all messages) such as length(m₀) = length(m₁) and ∀ c ϵ C (space of all cipher texts)

Pr[E(k, m₀) = c] = Pr[E(k,m₁) = c]

where k is uniform in K (space of all the keys)

In other words, in a given a cipher text an attacker cannot tell if the encrypted message is m₀ or m₁ for all the possible m₀ and m₁ messages, so even the most powerful adversary learns nothing about plain text from cipher text and, therefore, no cipher text attack is possible.

In our digital world, cryptography is performed with computers. The XOR logic function is the basic building block of cryptographic algorithms due to an important property that is has, expressed by the following theorem:

If Y is a random variable over {0,1}ⁿ and X is an independent uniform variable on {0,1}ⁿ then Z = Y XOR X is a uniform variable on {0,1}ⁿ

This prevents frequency analysis that was the weakness of methods used until the mid 20^th century.

The One Time Pad Algorithm

The One Time Pad (OTP) is an algorithm that takes a message m and a key k (the lengths of m and k are equal) and XOR m and k. Because k is a uniform variable, Z is also a uniform variable and an eavesdropper cannot perform any cipher text attack. Unfortunately, to get perfect secrecy, the key must be longer than the message (|K| > |M|), which is close to impossible in practice. Indeed, if we get two encrypted messages with the same key k, XORing these two cipher texts come up with m₁ XOR m_2, and a simple statistics analysis on this result will allow for the discovery of a lot of information on the plain text.

To make OTP practical, the random key is replaced by a “pseudorandom” key with the following understanding: knowing all the previously generated keys, there is only a tiny probability (≤1/2⁸⁰) of discovering the new key.  Besides, instead of perfect equality used to describe the Shannon perfect secrecy, we say we have a semantic security if 2 cipher texts have indistinguishable distributions, so again we’re talking about probabilities. Key generation is the cornerstone of good security. As WEP protocol showed, a bad choice in the key destroys security.

WEP is insecure because the length of IV (Initial Vector) is 24 bits, which means that the same key is used about once every 16 million frames. Also, the keys are related; the key for frame 1 was 1||k, the key for frame #2 was 2||k. Furthermore, IV is reset to 0 after a power cycle, so an attacker could recover the ley after only 40,000 frames, which is completely unsecure in the climate of today. To overcome this weakness, in network traffic, a new key must be negotiated for every session. In modern stream ciphers a seed + a nonce (a non- repeating value for a given key) are used to generate the key and the pair (seed, nonce) is never used more than once. The most famous of these stream ciphers are RC4, Salsa or Sosemanuk.

Keep in mind that OTP is fine for communication inside a network but is not well suited for data storage. Indeed, OTP has no integrity because it is malleable—meaning that modification of cipher text is undetected and has a predictable impact on plain text.

Block Ciphers

Block ciphers are another approach to encryption. Their implementation is more complex and slower than stream ciphers, but they are more robust and able to solve challenges left by stream ciphers. Unlike stream ciphers, block ciphers are a fixed block of n bits that is scrambled to create a cipher text of n bits. When a message is less than n bits, it is necessary to pad the message to reach n bits. AES and RSA are the most common block cipher encryptions.

For block ciphers, 2 modes of operations are available: CBC (Cipher Block Chaining) mode and CTR (Counter) mode.  Each mode needs an IV (Initial Vector) to start encryption but then the implementation differs. The CBC mode has a serial implementation unlike the CTR mode that has a parallel implementation.

Here we have encryption with CBC mode: A random IV is chosen, then the output of each block is used to encrypt the next block.

Here we have encryption with CTR mode: F is a pseudorandom function and IV is random for every message and incremented for each block. F can be applied in parallel to each block.

All these methods are effective against eavesdroppers and confidentiality but none yet can assure integrity, authentication and protection against active attacks.

Message Authentication Code

Message integrity is based on MAC (Message Authentication Code). A tag is generated based on the message m and a key k. Once the receiver gets the message, he can perform a verify tag where the output is yes or no. MAC calculation uses a PRF (Pseudorandom Function), so an attacker cannot produce a valid tag for a new message. Integrity requires a secret key and does not have to be confused with a CRC (Cyclic Redundancy Code) that was designed to detect random, non-malicious errors.

Stream ciphers and block ciphers build confidentiality (in other words they are effective against eavesdropping but not against active attacks) and the MAC guarantees integrity but not confidentiality. But if MAC is performed on cipher text, we end up with an authenticated encryption. Attackers cannot create new cipher texts that decrypt properly. Integrity, authentication, and authorization can then be performed.

All these methods use the same key for the sender and the receiver and are called symmetric encryptions. We assumed keys were exchanged before communication started, but in the internet-connected world of today, many people must exchange data without knowing each other, and therefore cannot exchange keys first. Asymmetric encryption is the solution to this dilemma. The Diffie-Hellman protocol helps explain:

If p is a large prime number, g an integer in {1,…,p} and x is chosen randomly in {1,…, p-1}, knowing the result , there is no known efficient algorithm to calculate x. Then, with two numbers x and y, it is very easy to perform an exponential operation to end up with a key but very hard to reverse the operation to discover the key.

g^(x^y ) (mod p)=g^(y^x ) (mod p)= g^xy (mod p) = Key to use for encryption

If Alice and Bob want to share the key and there is an eavesdropper between them, the following steps are performed to share the key.

There are several Diffie-Hellman variants as well, like the resolution of an elliptic curve in the form of y² = x³ + ax + b.

In the end, despite all these efforts, there is no guaranteed way to securely communicate. The Shannon theorem demonstrates perfect security from a theoretical point of view, but practically speaking, side channel attacks can be very powerful. One of the best examples of a side channel attack occurred in 2013 when researchers cracked the world’s toughest encryption by listening to the high pitched sounds (10 to 150kHz) made by a computer CPU while decrypting a 4096-bit RSA algorithm. Daniel Genlin, Adi Shamir and Eran Tromer were able to craft a decrypting key using this type of unknown, which is impossible to predict.