Cryptography: the study of the techniques to allow secure communication and data storage in the presence of adversaries.
Cryptoanalysis: how to break cryptographic algorithms
Criptology: union of cryptography and cryptoanalysis
Cryptography brings together the fields of mathematics, computer science, and electrical engineering and it’s used in many applications such as secure communication, secure storage, secure computation, and secure identification. It provides (accordingly to the CIA triad) many important features such as:
Confidentiality: Ensuring that the information is only accessible to those who are authorized to access it.
Integrity: Ensuring that the information has not been altered by unauthorized parties.
Authenticity: Ensuring that the information is from the expected source.
Non-repudiation: Ensuring that the sender cannot deny sending the information.
Freshness: Ensuring that the information is recent.
And many more advanced features like proof of knowledge, proofs of computation, and zero-knowledge proofs.
History of Cryptography
Cryptography, derived from the ancient Greek words “kryptós” (meaning “hidden”) and “gráphein” (meaning “to write”), is the study of techniques used to ensure secure communication. Its purpose is to allow only the intended sender and recipient of a message to view its contents. In ancient times, reading and writing were themselves secretive practices. As society evolved, the need for secret writing led to the development of cryptography.
One early example is the “scytale”, a method that was relatively easy to break: the message, written on a stripe of paper (or leather) is wrapped on a shaped stick, making it hard to read. The trusted element in this case was the physical stick itself. Cryptography became a necessity and was primarily used for military purposes. Notable early studies in this field were conducted by Gabriele de Lavinde and Leonardo da Vinci, with the latter’s famous mirror writing. However, cryptography was not yet treated as a formalized science and remained largely military-focused. Luigi Sacco, an Italian army general, wrote one of the last non-formalized books on cryptography.
The formalization of cryptography emerged out of the need during World War 2, where it played a crucial role in the war efforts. Winston Churchill himself credited cryptoanalysis for the victory. As the UK relied on imports and Germany had conquered most of Europe, the US attempted to send aid via ships. However, these ships were consistently targeted by German submarines. The submarines had to resurface to refill, making them vulnerable to attacks. This critical information was transmitted encrypted within the German army using the Enigma cipher, one of the last non-formalized encryption systems. Alan Turing worked on breaking the Enigma cipher to determine its key in a deterministic way, leading to the creation of the Bombe machine. This marked the birth of computing machines and the formalization of cryptography.
a cryptosystem is a system that takes a message (plaintext) as input and transforms it into a ciphertext using a reversible function, often with the use of a key.
The only difference between Shannon’s definition and the current one is the use of the term “text”, which has been replaced by “strings of bits” in modern cryptography.
Cryptography and Cryptosystems
Before starting to talk about cryptography, we need to define some useful terms:
Definitions
Plain space: the set of all possible messages written in a natural way by human/machine. Usually , where is the length of the message
Cipher space: the set of all possible ciphertexts . Usually , the length is not necessarily the same as (ciphertexts can be longer than plaintexts, ).
Key space: the set of all possible keys. Usually, keys with special formats are derived from bitstrings of length .
Encryption function.
Decryption function.
For all we need such that .
The goal of cryptography is to prevent anyone not authorized from being able to read and understand data. Possible attackers models are:
The attacker simply eavesdrops on the communication channel; this kind of attack is usually called ciphertext-only attack.
The attacker knows a set of possible plaintexts, but not the corresponding ciphertexts
The attacker may tamper with the data and observe the reactions of a decryption-capable entity
The problem of cryptography and cryptosystems is to allow the communication between two elements that want to communicate over anuntrusted channel (e.g. internet), that is to say there is a threat agent that wants to read the exchanged elements.
The problem is thus guaranteeing confidentiality and integrity.
Definitions
Confidentiality making sure that message exchanged via an untrusted channel is encrypted, impossible for anyone to read except for the authorized people, so only the receiver must be able to read the message
Integrity: making sure that other people do not tamper the message and that, should the message be tampered, the receiver can detect the modification (insertion/deletion/replacement/…): this means that a tampered message is not decrypted correctly (e.g. is corrupted) and the receiver can not read it; so, the message must not be modified during transmission, the receiver must be able to verify its integrity
Kerckhoffs’ Principle
Kerckhoffs’ principle states that the security of a cryptosystem relies uniquely on the secrecy of the key, never on the secrecy of the algorithm, which must be known, even to the attacker. This principle is also valid in security, which must be based on transparency, rather than secrecy. The reason why it is important for the algorithms to be known is that a public algorithm can be tested and analyzed by anyone: anyone can find and report vulnerabilities, so that they can be solved and their number is lowered. In fact, there is no way to prove the robustness of an algorithm, except for trying to break it. Because of this, design and approval of a cryptographic algorithms require years. This means that:
The system must be practically, if not mathematically, unbreakable.
The system should be possible to make it public, even to the enemy.
The key should be communicable and retainable without the help of written notes, and changeable or modifiable at the discretion of the correspondents.
The system should be applicable to telegraphic communications.
The system should be portable, and its use should not require more than one person.
Finally, the system should be easy to use, requiring neither mental strain nor the knowledge of a long series of rules.
These are the concepts upon which the security of a cryptosystem relies.
One of the issues considered by Shannon in its formalization is the existence of a perfect cipher, one that can not be broken regardless of the effort: to answer this question he applied distribution of probability to each exchanged message, this defining:
is the probability of observing message ; in other words, the probability of observing the plaintext
: given ciphertext observed, it’s the probability that the message (plaintext) is
Definition
We define a perfectly secure cipher as a cipher where, for all and ,
In other words, seeing a ciphertext gives us no information on what the plaintext corresponding to could be.
Shannon concluded that a cipher is the perfect one if and only if, that is to say: even if the ciphertext is observed, it does not leak any secret about the message. Even by knowing it, it is not possible to retrieve the message, unless it is known already, so it is impossible to retrieve the key by simply analyzing the ciphertext. This means that the cipher provides the attacker with no information about the plaintext, nor about the key.
Shannon Theorem
Shannon Theorem
Any symmetric cipher with is perfectly secure if and only if every key is used with probability and a unique key maps a given plaintext into a given ciphertext:
Shannon Theorem represents another property that characterizes perfect ciphers; according to Shannon’s formalization, in a perfect cipher the number of keys must be greater than or equal to the number of possible messages: . This means that the cardinality of the set of keys must be greater than or equal to the cardinality of messages, . This theorem has two important and practical consequences:
In a perfect cipher the key must not be reused: a different key must be used for each message
In a perfect cipher the length of the key must be equal to that of the message to encrypt
This property was demonstrated by reduction to absurdity and can be summarized as follows:
must be at least as large as :
For each , there is one ciphertext for each key
If , the number of ciphertexts for each message would be smaller than
Thus, given , this means that there are values in that cannot correspond to some of the values in
This is absurd by definition of perfect cipher
One-Time Pad
From a practical perspective, saying that a perfect cipher has the above mentioned property, means that for a 1 kB message, the key has to be equal to (or greater than) 1 kB as well and can never be re-used. In real life, a perfect cipher does exist: it is called One Time Pad, whose main characteristics are:
XOR of a message and a random key , that is pre-shared, consumed while writing and can not be re-used (re-using the same key implies leaking some information that a hacker could exploit to obtain the message)
Perfect cipher, because it satisfies the condition
Minimal cipher, because
ptx: this is secretkey: xvhe uw nopgdz---------------------ctx: qcpw co fsrxhs
However, in real life, it is terribly inconvenient and only used in special settings, such as war or diplomatic contexts, where this kind of encryption is affordable.
In general, real world algorithms, except for One Time Pad, are imperfect and can thus be broken, because they do not satisfy the condition , which implies that the key has to be re-used many times. Re-using the same key many times means that each<ciphertext, plaintext>couple will leak some information that the hacker can exploit: if the hacker is able to analyze many ciphertexts, since the same key is used more than once, by inferring some regularities in the plaintext, the attacker can retrieve some information about the key.
Imperfections and Brute Force
In real life algorithms the same key is re-used more than once: this is why algorithms are not perfect, furthermore the key is the only unknown thing (the algorithm must be known).
At this point, the attacker, in order to break the algorithm, has to find the key, and all real world algorithms are vulnerable to brute-force attacks, which means trying all possible keys until a well-formed output is found: this is not a smart attack though.
Perfect ciphers are not vulnerable to brute force, because of the minimal property: having means that trying all possible combinations of the key will result into obtaining every possible combination of the plaintext, which are all equally likely.
Cryptoanalysis: Breaking Ciphers
Brute-force is the upper bound to the robustness of an algorithm, it is the worst case scenario to apply (most time-consuming method) in order to break an algorithm, because each possible combination must be tried: it basically measures the time needed to break any non-perfect algorithm.
Info
A real cryptosystem (algorithm) is broken if there is a way to break it that is faster than brute forcing. Some types of attacks are:
Ciphertext attack: the analyst only has ciphertexts and has to analyze the statistical distribution of the elements in the ciphertext, until a pattern is found
Known plaintext attack: the analyst has a set of pairs plain-ciphertext
Chosen plaintext attack: the analyst can choose plaintexts and generate their respective ciphertexts, by doing so they can analyze the correlation between different plain- and ciphertexts, carrying out the so-called linear differential cryptoanalysis
To move from the first to the third type, more information is required: in the ciphertext attack only ciphertext is needed, while in chosen plaintext some device that emulates the behavior of the system is needed too, therefore the first method should be used first.
Building a cipher so that a successful attack is also able to solve a hard computational problem efficiently is the goal of modern cryptography. This is done by:
solving a generic nonlinear Boolean simultaneous equation set
factoring large integers: if and are two large primes, computing is easy, but given , finding and is hard (basically, you have to try all primes until you get to the smaller between and )
finding discrete logarithms: if then . Given , it’s easy to compute , but knowing , it’s difficult to find .
decoding a random code.
Success
The goal is to avoid assumptions and prove an exponential lower bound for the time taken to solve a hard problem, which has an efficiently verifiable solution. This would shift from a computational security assumption to a theorem and prove as a corollary.
To create a computational security cipher we have to:
Define the ideal attacker behavior.
Assume a given computational problem is hard.
Prove that any non-ideal attacker solves the hard problem.
The attacker is represented as a program able to call given libraries that implement the cipher at hand, and the security property is defined as answering to a given question. The attacker wins the game if it breaks the security property more often than what is possible through a random guess.
Example
A ZIP-compressed le encrypted with a secret 4-bytes key is given. According to Kerckhoffs’ principle, the algorithm must not be secret, in fact it computes .
K(hex) = AA BB CC DDM(hex) = 50 4B 03 04 BA DA 55 55 ...xorC(hex) = FA F0 CF D9 10 61 99 88
Is it possible to recover the key without brute forcing? Let’s see what happens step by step:
By analyzing the algorithm it’s possible to see that it is not perfect, since the key is re-used. In fact the key is 4 B long, while the ZIP file is way bigger (): this means that the key has to cover the entire length of the file.
Since the algorithm is not perfect it is surely possible to brute force it: XOR function is reversible, therefore . As a consequence the attacker can try to brute force every possible key, until they output a well formed ZIP file (not corrupted)
This algorithm can actually be broken faster than by using brute force, by simply knowing XOR is reversible and a ZIP file is being encrypted.
In Unix-like systems a Magic number is given at the beginning of the header of a file (first bytes of every file) to define the type of the file. All ZIP files have the same magic number (PK\x03\x04), which is 4 B long: this means that the attacker knows both the ciphertext and the first 4 B of the plaintext.
At this point the attacker only has to take the first 4 B of the ciphertext, xor it with the first 4 B of a plain text (known because the file is a ZIP) and obtain the key. This is a known plaintext attack: a ciphertext and one corresponding plaintext are give, additionally xor function’s properties are used.
(Non) Successful Attacks
Security of a cryptosystem relies on the strength of the algorithm and its ability to withstand attacks. To determine the robustness of an algorithm, it is necessary to attempt to break it. The process of breaking an algorithm is faster and more effective when the algorithm is public and can be tested by a wide range of experts.
When evaluating the robustness of an algorithm, it is important to consider the time required to break it and the strength of the attack employed. For example, if brute forcing the algorithm takes two years, but another type of attack can break it in two days less, the algorithm is still considered robust. However, if an attack can break the algorithm in just one day while brute forcing would take 100 years, then the algorithm is truly broken.
The impact of an attack on the algorithm’s security depends on the value of the asset being protected. In some cases, an attack may not be sufficient to consider the algorithm broken. It is crucial to assess the level of protection and encryption needed for the specific asset in question.
Encryption and Confidentiality
Symmetric Encryption Algorithms
Definition
A symmetric encryption algorithm is a function that takes a plaintext and a key and returns a ciphertext .
The decryption function takes a ciphertext and a key and returns the original plaintext .
The key is shared between the sender and the receiver and independent from the plaintext and the chosen algorithm.
Symmetric Encryption is also referred to as secret/shared key encryption, since its basic idea is that a key is used to both encrypt plaintext into ciphertext and decrypt ciphertext into plaintext. Symmetric Encryption only guarantees confidentiality (integrity is not guaranteed).
Let’s consider its functioning. Alice and Bob want to communicate over an untrusted channel, Alice uses a symmetric encryption function by using a single secret key to encrypt the message and generate the ciphertext in order to send it to Bob. Bob will use the same key to decrypt the message. By analyzing this scenario, it’s clear that the main problem of symmetric encryption algorithm is that since a shared secret (key) is used, a way must be found to exchange the key between the two entities that are trying to communicate. The key can not be transmitted via the same channel through which the message is transmitted, otherwise the attacker will find both key and message and decrypt it (the algorithm is known). Another trusted channel is needed to transmit the key.
Trusted Channels
Suppose to be exchanging a secret (encrypted) email with a friend. The message will be encrypted (with the key) and sent. To exchange the key (so that the receiver can decrypt and read the message) some methods can be used:
exchange via person (off-band), physically: of course not feasible if the person is far away
exchange via phone-call, fax, sms: these channels are not really secret, they are considered trusted if an attacker that can read the emails, but not sms or phone calls is considered; in other word these are trusted if the considered threat agent is assumed to only have access to one channel
Still, to exchange the key, an alternative trusted channel must be found, which is a huge problem, also referred to as Key Management Problem.
The first factor of this problem is finding a trusted channel that can be used to exchange the key, the second one is related to the fact that it is not scalable. If entities want to communicate by using a symmetric encryption algorithm, almost keys are needed. This means that when adding/removing someone these keys all have to be shared. The same key can not be used for all entities, because if we did so leaking a single key would compromise the entire system (considering the people involved as trusted elements). To guarantee confidentiality and integrity between all couples of people, almost keys must be shared for each entity.
In general, it’s possible to define symmetric encryption algorithms as a cocktail of substitution and transposition: modern symmetric ciphers mix these properties, and some of them are:
Substitution involves replacing each byte with another one, similar to the Caesar cipher. However, this method is limited and weak because patterns and frequencies of letters can still be observed in both the plaintext and ciphertext. To improve upon monoalphabetic ciphers, polyalphabetic ciphers use multiple alphabets mapped by a key. This makes repetition and structure less visible.
Transposition involves swapping the values of specific bits. The plaintext is typically arranged in rows and read in columns, with the key determining the number of rows and columns. The dimensions of the matrix should be close to the length of the message. While repetition and structure are not easily visible, brute force attacks can still be attempted by trying different combinations of rows and columns. However, this requires computational effort and testing all possible structures.
Cryptographically Safe Pseudorandom Number Generators
We want to use a finite-length key and a OTP cipher (also known as Vernam cipher), but we need to “expand” the key. We assume that the attacker can only perform computations.
Definition
A CSPRNG is a deterministic function whose output cannot be distinguished from a uniform random sampling of in where is the CSPRNG stretch.
In practice, we have only candidate CSPRNGs, and building a CSPRNG from scratch is possible, but not efficient. Due to the lack of proof that a function exists and the existence of a CSPRNG implies , CSPRNGs are practically built with another building block: PseudoRandom Permutations (PRPs) defined starting from PseudoRandom Functions (PRFs).
Definition
Consider the set , a uniformly randomly sampled can be encoded by a entries table, each entry out bit wide. .
Random Functions (RFs) and Pseudorandom Functions (PRFs)
It’s uniquely identified by the value of the seed, it is not possible to tell apart in from a RF, and it’s a permutation of all the possible strings. It facts on a block of bits outputs another one of the same size, the output “looks unrelated” to the input, and its action is fully identified by the seed (useful to think of the seed as a key).
Real-world PRPs are the outcome of public contests because no formally proven PRP exists yet. The typical construction is to:
compute a small bijective Boolean function of input and key,
compute again between the previous output and the key,
and repeat until you’re satisfied.
Modern PRPs are the outcome of public contests and cryptanalytic techniques provide ways to detect biases in their outputs.
Concrete PRPs go by the historical name of block ciphers and are considered broken if, with less than operations, they can be told apart from a PRP via deriving the input corresponding to an output without the key, deriving the key identifying the PRP, or identifying non-uniformities in their outputs.
The key length is chosen to be large enough so that computing guesses is not practically feasible. The key space is generally measured in bits, so the attack time is exponential on the number of bits. We need to balance the computational effort of the attacker with the length of the key.
Data Encryption Standard (DES)
DES was an algorithm developed by IBM and selected after a competition to encrypt communication in a network. It underwent three years of testing against attacks and became a US standard in 1976. The core functionality of DES is an S-Box (substitution box), and its key is 56 bits long, resulting in a keyspace of .
The original design had a 128-bit key, but the NSA collaborated with IBM and suggested a 64-bit key with 56 random bits and 8 bits for even check. After this modification, the algorithm was accepted.
In the 1980s, differential cryptanalysis was discovered, along with advanced techniques to break algorithms. In 1993, it was revealed that the original S-boxes designed by IBM would be vulnerable to differential cryptanalysis, while the one proposed by the NSA was not. This raised suspicions that the NSA may have been aware of differential cryptanalysis before it was introduced. Rumors circulated that the NSA wanted to weaken DES by requesting a shorter key, as they believed a 128-bit key was unnecessary at the time due to the lack of computational power to brute force it. Their goal was to make DES lighter while still being resistant to differential cryptanalysis.
However, DES was eventually broken in 1997, twenty years after its release. It wasn’t until 2001 that the Advanced Encryption Standard (AES) became a standard, but DES remained in use during the transition period from 1997 to 2001.
Standard Encryption and Brute Forcing
Nowadays, the Data Encryption Standard (DES) is no longer used, not because of any new attacks that have emerged in recent years, but because it is relatively easy to brute force.
NOTE
The strength of an encryption algorithm is determined by the length of its keyspace, which refers to the number of possible keys. Brute force attacks require trying up to different keys to find the correct one. Increasing the length of the key by just one bit doubles the time required to brute force the algorithm, as the time needed is an exponential function of the number of bits.
In the case of DES, a standard block of 56 bits is used for the key, and simply adding more bits is not possible. To increase the key length, the block must be multiplied, such as in the case of triple DES which uses a key length of 3 times the standard length. Finding the right balance between the computational power required and the key length is crucial.
To analyze this trade-off, the keyspace vs. time for brute forcing curve must be examined. The graph shows that the slope of the line is proportional to the power of the attacker. Even with improvements in computational power, the shape of the curve remains relatively unchanged, unless a fully functioning quantum computer is developed in the near future. As of now, quantum computers are still far from being a reality, so the current curve represents the state of the art.
Example
Common key lengths include 56, 64, 128, and 256 bits. Brute forcing a 56-bit key may only take a few minutes, while a 64-bit key would require almost 100 years. Moving on to 128 and 256 bits, the time needed increases to years (about the age of the universe) and years respectively.
These values are considered sufficient to keep a secret, as long as the encryption algorithm is strong enough.
In conclusion, when evaluating the key length, it is important to find a balance between the number of bits and the computational power required. However, if the algorithm is strong enough, a key length of 128 bits is generally considered sufficient.
It is important to note that attackers will typically target the weakest part of the system, such as the human element, rather than attempting to directly attack the strongest element, unless it is known to be vulnerable.
Asymmetric Encryption Algorithms
Definition
An asymmetric encryption algorithm is a function that takes a plaintext and a public key and returns a ciphertext .
The decryption function takes a ciphertext and a private key and returns the original plaintext . The public key is shared with everyone, while the private key is kept secret.
Such algorithms guarantee confidentiality and more. In 1997, Diffie and Hellman introduced the concept of using two keys, where what is encrypted with can only be decrypted by , and vice versa. Additionally, even if the keys are related, one cannot be derived from the other. This approach, known as asymmetric encryption or public key cryptography, solves key management issues by providing each entity with a key pair: a public key and a private key. The public key can be shared openly, even on untrusted channels, as it can only be used to encrypt messages that can be decrypted with the corresponding private key.
For example, if Alice wants to communicate with Bob, she can use Bob’s public key to encrypt the message, ensuring that only Bob can read it using his private key. The mathematics behind this algorithm relies on a one-way function with a trapdoor, which is easy to compute in one direction but extremely difficult to invert. While symmetric encryption algorithms also utilize such functions, asymmetric encryption algorithms are more computationally intensive and solve scalability and key management problems. Therefore, it is common to use both symmetric and asymmetric algorithms together, leveraging public key cryptography to exchange keys used for symmetric encryption.
Let’s delve into the functioning of asymmetric encryption algorithms. In a scenario where Alice and Bob want to communicate over an untrusted channel, they do not need to share a secret key. Instead, each entity creates their own pair of private and public keys. The public keys are shared openly, as they do not need to be kept secret. The security of the algorithm relies on the private key, which must remain confidential to ensure message decryption only by the key’s owner. It is crucial to trust that the person using the private key is indeed Bob or Alice, as the confidentiality of the message depends on it. Authentication is provided when encrypting a message with the private key, as it proves that the message originated from the owner of that specific key.
NOTE
If Alice were to encrypt a message with her own private key, anyone could decrypt it using her public key, compromising confidentiality. In this case, the encryption serves as a form of authentication, indicating that the message came from the owner of the private key.
Some common asymmetric encryption algorithms include Diffie-Hellman and RSA.
Diffie-Hellman Exchange
This is not really an asymmetric encryption algorithm: it is an exchange, an algorithm used by entities to agree on a secret over an insecure channel. It exploits the use of a public and private key, but it is just a way to agree on a secret.
The easiest way to understand how it works is to consider a classroom full of people, where two people want to exchange a secret: after their conversation they will be the only ones knowing the secret. Diffie-Hellman allows entities to exchange messages over an untrusted channel, so that in the entities only the two entities actually involved in the exchange will know the secret.
As a one-way trapdoor function it exploits an old mathematical problem: the discrete logarithm:
If then
Given it is easy to compute , but knowing it is extremely difficult (computationally intensive) to compute
This is a crucial difference with respect to symmetric algorithm: computing is extremely difficult in the sense that brute force is required over all the possible values of . In this context brute forcing assumes a slightly different meaning: when referring to symmetric encryption algorithms brute forcing means trying all possible combinations in order to discover the key, while in this case a mathematical problem must be solved, which is eventually faster than actual brute forcing.
Example
Let’s pick prime, primitive root of public, where a primitive root is a number such that raising it to the power of any number between 1 and , each number between 1 and is obtained
Consider: 3 is a primary root of 7 (Diffie-Hellman exchange still works without the primary root property, however by respecting this condition it is guaranteed that the maximum number of possible keys will be obtained: the algorithm is more robust)
Let
The entities A and B that want to exchange the message will independently and secretly choose their own private key, by selecting a number between 1 and : the chosen number is the private key and must remain secret,
They will also compute independently their own public key : and
A and B must now exchange their public keys
At this point, both A and B can compute, thanks to mathematical computations, a shared secret K:
Anyone can have the public key, but without the private one it is impossible to decrypt the message, especially on a larger scale with longer keys.
RSA
It exploits, like any other asymmetric encryption algorithm, a one-way trapdoor function known as the factorization of prime numbers. In this case, if we have two large prime numbers, and , computing their product, , is easy. However, given , it is extremely difficult to determine the values of and . This problem, known as the quadratic sieve field, can only be solved by trying all primes until the smaller of the two factors is found.
Interestingly, the factorization problem and the discrete logarithm problem share similarities and have similar functionalities. If one of these problems were to be solved, it is likely that the other would also be broken, as they are mathematically related. The only category of asymmetric encryption algorithms that is independent of this problem is ECC (Elliptic Curve Cryptography), which is why current standards are shifting towards its direction.
To break RSA, an attacker would need to obtain the prime factors, and , given the value of . This factorization task has an exponential complexity with respect to the number of bits in . From an encryption perspective, the computation time for RSA grows linearly with the number of bits in . Therefore, there is a trade-off between the time needed to factorize and the key length.
Warning
The mechanisms used by processors to compute exponentials are slower compared to other computations. As a result, asymmetric encryption algorithms are generally more computationally intensive than symmetric ones.
While it has been demonstrated that a 512-bit RSA key can be factored within 4 hours on EC2, there is currently no practical demonstration of factoring anything larger than 700 bits. Therefore, keys longer than 1024 bits are considered safe, with typical choices being 2048 or 4096 bits.
The length of a key in symmetric encryption algorithms, which is measured in bits, represents the number of decryption attempts needed to break the key ( attempts). On the other hand, in asymmetric encryption algorithms, the key length represents the number of key-breaking attempts required to reverse the one-way trapdoor function.
Reversing a function is faster than brute force, which is why asymmetric encryption algorithms require longer keys to maintain the same level of security. This difference in key lengths has significant implications when comparing different algorithms.
In summary, symmetric encryption algorithms can be compared based on key lengths alone, while asymmetric encryption algorithms cannot be directly compared based on key lengths unless they are based on the same function. It is important to note that asymmetric and symmetric encryption algorithms should never be directly compared based on key lengths alone.
Summary
Symmetric
Asymmetric
Time Complexity
Typically
Typically to
Use Case
Suitable for large amounts of data, given the scalability (i.e. time complexity) of symmetric algorithms.
Suitable for small amounts of data. Often used for secure key exchange (of symmetric keys).
Same private key must be shared between all encrypting/decrypting parties.
Public key can be openly shared, making key distribution easier.
Key Length
Shorter (e.g. 128 or 256-bit AES)
Longer (e.g. 2048 or 4096-bit for RSA)
Symmetric Encryption Algorithms
Algorithm
Key Size
Block Size
Strengths
Weaknesses
One-Way Trapdoor Function
AES
128, 192, 256 bits
128 bits
Strong security, fast, widely adopted
Requires secure key distribution
Substitution-permutation network
DES
56 bits
64 bits
Simplicity, fast
Weak security, vulnerable to brute-force attacks
Feistel network
3DES
112 or 168 bits
64 bits
Improved security over DES
Slower than DES and AES
Feistel network
Blowfish
32-448 bits
64 bits
Fast, flexible key size
Not as widely adopted
Feistel network
Asymmetric Encryption Algorithms
Algorithm
Key Size
Strengths
Weaknesses
One-Way Trapdoor Function
RSA
1024-4096 bits
High security, widely adopted
Slow, large key sizes
Integer factorization
ECC
160-521 bits
High security with smaller key sizes, efficient
More complex implementation
Elliptic curve discrete logarithm problem
DSA
1024-3072 bits
High security, digital signatures
Relatively slow
Discrete logarithm problem
Diffie-Hellman
Variable
Secure key exchange
Susceptible to man-in-the-middle attacks
Discrete logarithm problem
Key Comparison Points
Problem Addressed (One-Way Trapdoor Function):
Symmetric Encryption: Uses simple one-way functions like substitution-permutation or Feistel networks. The security depends on the secrecy of a single key.
Asymmetric Encryption: Utilizes more complex mathematical problems such as integer factorization (RSA) or elliptic curve discrete logarithms (ECC). These algorithms involve a pair of keys (public and private) and are designed so that the private key cannot be feasibly deduced from the public key.
Key Size:
Symmetric Encryption: Generally smaller key sizes compared to asymmetric encryption, but requires secure key distribution.
Asymmetric Encryption: Larger key sizes provide equivalent security due to the complexity of the underlying mathematical problems.
Strengths and Weaknesses:
Symmetric algorithms are typically faster and more efficient for large amounts of data but face challenges in key distribution.
Asymmetric algorithms, while slower and more computationally intensive, offer advantages in secure key exchange and digital signatures.
Hash Functions and Integrity
Message Authentication Codes (MACs)
Add a small piece of information (TAG) allowing the receiver to verify the integrity of the message. Adding it to the plaintext is not a good idea, because during the encryption the MAC will be encrypted as well, so the receiver will not be able to verify it.
Definition
A MAC is constituted by a pair of algorithms:
: computes the tag of a string using a key.
: verifies the tag of a string using a key.
The ideal attacker model knows as many message-tag pairs as he wants, but he cannot forge a valid tag for a message for which he doesn’t know it already. Forgery also includes tag splicing from valid messages.
The tag creating entity and the verifying entity must both know the same secret key. The tag verifier is able to create a valid tag too, and there goes the non-repudiation property.
The MAC can be built using PRFs, and the tag can be computed as the last block of a block cipher encryption of the message. The tag is then sent to the receiver, who can verify the integrity of the message by computing the tag again and comparing it with the received tag. The CBC-MAC is secure for prefix-free messages, because the attacker cannot forge a valid tag for a message for which he doesn’t know the tag already.
MAC has several usage scenarios, like cookies, where the server sends a cookie to the client, and the client sends it back to the server. The server can verify the integrity of the cookie by computing the tag and comparing it with the received tag.
Testing the integrity of a file requires us to compare it bit-by-bit with an intact copy or read it entirely to compute a MAC. It would be fantastic to test only short, fixed length strings independently from the file size, representing the file itself, but there is a lower bound to the number of bits to encode a given content without information loss.
Hash Functions
Definition
A cryptographic hash is a function for which the following problems are computationally hard:
Given , it is hard to find (first preimage resistance).
Given and , it is hard to find such that (second preimage resistance).
It is hard to find two distinct strings and such that (collision resistance).
The ideal behavior of a concrete cryptographic hash function is that:
finding first preimages takes hash computations guessing .
finding second preimages takes hash computations guessing .
finding collisions takes hash computations
The output bitstring of an hash function is called digest.
The hash function is a function that maps arbitrary-length input on fixed length output . The output is usually way smaller than the output: the codomain is thus smaller than the domain. In fact, the domain elements’ structure is fixed: it might be e.g. a fixed-length string. This property has a huge impact on hash functions’ functioning: it allows collisions.
A collision happens when two inputs have the same output. This is of course bad: in general a good hash function must be resistant to collisions, and collisions must be difficult to obtain. However, hash function’s output must not be random, otherwise it will not be possible to check integrity. From a formal point of view, a good hash function satisfies three properties:
Preimage attack resistance : it must be computationally not feasible to find an input such that , where is a specific hash. An hash function is vulnerable to preimage attack if it is easy to find an input that generates a specific output.
Second preimage attack resistance : it must be computationally not feasible to find a second input such that, given a different input , , they have the same hash.
Collision resistance : it must be computationally not feasible to find a couple of inputs such that .
Preimage and Second preimage attacks are similar: in fact, if a way is found to perform a preimage attack, then it is surely possible to perform the second preimage. However, it does not work the other way round: it could be possible to find two inputs with the same hash without actually reversing the function. In general: the first attack implies the second, but not viceversa.
Also collision attacks look similar to second preimage ones, however they are in fact very different: in the second type the purpose is to find an input whose hash is equal to that of another given input; while in the third type the purpose is to find two random inputs with the same hash (there is no given input). In general, it is easier to find a couple of values that have the same hash, than finding an input that outputs the same value as another fixed input.
A hash algorithm can not be collision free, because of how it is defined: the only property that can be looked for in such an algorithm is to be collision-resistent. It must be hard for an attacker to voluntarily find a collision. It is in general, easier to find a random collision than finding a collision with a fixed value. Therefore a hash function should not be (easily) reversible.
SHA-2 is currently the standard hash function because no robust attack has been found against it. Previous standards, such as MD5 and SHA-1, have been deemed insecure. MD5 is considered cryptographically broken and unsuitable for further use due to multiple successful collision attacks. SHA-1 has been considered insecure since 2005 and in 2017, a collision attack was successfully performed against it, making it even more vulnerable. These attacks pose a significant security risk as they can make it impossible for a computer to differentiate between two files with the same hash, potentially allowing tampered files to go undetected.
Hash functions are widely used in backup and version control systems, as well as for ensuring the integrity of HTTPS certificates and digital signatures. While the SHA-1 attack is not easy to execute and requires significant computational power, its feasibility has been demonstrated. In comparison to brute force attacks, the SHA-1 collision attack is significantly faster, highlighting the vulnerability of the algorithm. Despite the possibility of brute-forcing hash functions, they generally provide fast and efficient computation of the output for a given input, making them valuable for ensuring data integrity.
Example
To check whether two elements (e.g. two images) are equal or not, one can compute their hash functions and compare the outputs (hash values). Two images may look exactly the same, but applying a hash function to both of them and compare the results might reveal that the outputs are different because one has been tampered (e.g. 1 pixel was changed). The same applies to two strings: if a single byte is different, the hash function’s output will change.
Attacks to Hash Functions
All attacks are related to the properties hash functions must satisfy. An attack is successful when the time to perform it significantly reduced with respect to previous attacks or brute-forcing time. However, that does not necessarily mean that the cryptosystem is broken: the system is broken if the complexity is hugely reduced and the attack is thus easy to perform.
Arbitrary collision or (1st or 2nd) preimage attack
In such attacks, the hash function is broken when, given a specific hash , the attacker can find so that (or equivalently, given a specific input , the attacker can find such that and ) in less time than what brute forcing it would require. If the attack reduces the time to break the hash function, it is broken. But, how long does it take for a brute force attack to obtain an arbitrary collision?
Hash functions usually generate -sized hash. Supposing that the inputs are chosen randomly and that the function is very good and robust (so that the output is as random as the input), the function will, in total, output possible hash values (hash of bytes). On average, a random collision is obtained in cases. This attack is more powerful.
Simplified collision attack
In this case the hash function is broken if the attacker can generate colliding couples (couples such that ) faster than brute forcing. This is easier to obtain: random collisions can happen in cases, because of the so-called birthday paradox.
Digital Signature and Confidentiality, Integrity, Authentication
Definition
A digital signature is a pair of algorithms:
: computes the signature of a message using a private key .
: verifies the signature of a message using a public key .
When a private key is used to encrypt a message, it provides a form of authentication. However, if the goal is only to guarantee message authentication and not confidentiality, there is an issue when the message is very large. It needs to be encrypted with an asymmetric encryption function, which is slow and computationally intensive.
To provide authentication in a faster way without using an asymmetric encryption function, the plaintext can be hashed and then encrypted with the user’s private key. The encrypted hash is sent over an untrusted channel, allowing the recipient to decrypt it with the sender’s public key. Meanwhile, the plaintext message is also sent over the same untrusted channel. Upon receiving the message, the recipient computes the hash and checks if it matches the previously received hash. If they are equal, integrity is preserved; otherwise, the message was tampered with. This method guarantees integrity, but not confidentiality.
A digital signature is the asymmetric encryption of the hash of the plaintext. If the plaintext is corrupted during transmission, the two hash values will not be the same. However, digital signatures only guarantee that the message (or its hash) was encrypted with a certain key, not the identity of the user using that key. Therefore, trust boundaries are shifted when considering digital signatures, and a way to verify the identity associated with a specific private key must be found.
Public key exchange can be done out of band or by utilizing a Public Key Infrastructure (PKI), which associates a key pair with an identity on a wider scale. This ensures that a specific public key belongs to a particular user. The PKI uses a trusted third party called a certification authority (CA) to digitally sign certificates that bind an identity to a public key. The CA computes the hash of the file, encrypts it with its private key, and sends both the digital signature and the certificate to the entity that requested it.
To verify the validity of a digital certificate, the CA’s public key must be obtained to check its hash. However, the CA’s public key is contained in another digital certificate signed by another CA. This creates a chain of certificates that could continue indefinitely. At some point, a trusted root CA must be found to establish trust in the entire chain. The root CA uses a self-signed certificate and is a trusted element that cannot be verified. The certification chain stops when a trusted root CA, trusted by the system, is encountered.
If a non-trusted authority is added to the certificate chain, the entire system is compromised, not because of the root CA itself, but because of the entity that allowed the non-trusted CA in the chain. The chain is built on both a geographical and a topic basis, and when a CA is trusted, all the ones depending on it are trusted as well. The root CA’s identity cannot be stolen as only the root CA itself has its private key. However, a way to distribute this trusted element must be found, often by using a de facto standard, such as a CA already installed in a certain system or browser.
Digital certificates and signatures allow for the verification of both the integrity and authentication of a received file. If the verification fails, it indicates that the file was compromised by an attacker or due to an error. Revoking digital signatures is not possible since they are the result of a computation made on the document itself. However, digital certificates can be revoked by utilizing Certificate Revocation Lists (CRLs) stored online. The challenge with CRLs is that they cannot be verified offline. CRLs are also signed by CAs for verification.
When using digital certificates, it is crucial to follow the verification sequence to avoid vulnerabilities. This sequence includes validating the signature of the document, checking if the public key matches the one on the certificate, verifying if the certificate belongs to the subject, validating the entire certification chain up to the root, ensuring the root certificate is trusted, and determining if the certificate is a CRL and how to obtain it if offline. Missing any of these steps can lead to vulnerabilities.
The Italian digital signatures framework
It was one of the first digital signature frameworks introduced in the EU in 1997. The current European digital signature framework was inspired by the Italian one. The Italian framework initially consisted of a list of screened Certification Authorities (CAs) that were analyzed by the Italian government. Only CAs that met certain requirements were accepted, resulting in around 10 selected CAs. Each selected CA created their own digital signature application, which served as the trusted element for users to sign their documents. This meant that each CA had to contain their own CA as the trusted element.
From a cryptographic perspective, all Italian signature standards used strong and unbroken cryptographic algorithms, which was a positive aspect of the framework. However, vulnerabilities emerged due to the decentralized nature of the applications developed by each CA. While the algorithms themselves were strong, the individual CA applications had design and development flaws. These applications, which contained the trusted element, allowed users to digitally sign documents.
A digital signature is stronger than a handwritten signature as it is tied to the content and cannot be forged unless the algorithm is broken. Unlike a written signature, a digital signature is the result of a complex computation that depends on the document being signed. However, since digital signatures are the result of a computation, if someone is able to produce a fake one, it cannot be distinguished from a real one. Therefore, if the application that produces digital signatures can be attacked, fake digital signatures can be produced.
Two notable bugs emerged in the Italian digital signatures framework:
Fields of Pain: This bug, discovered in 2002, affected many CA software applications. These applications allowed the signing of Word documents that contained dynamic fields (macros) without warning.
Macros are pieces of code inside a text document that can execute different functions when the document is opened. The problem was that the hash of a file containing macros would always produce the same hash, even if the visualized content changed when the document was opened.
Initially considered a feature, this behavior was later addressed by Microsoft through a patch that disabled macros via API. Today, if a user wants to digitally sign a document with a macro, a warning will appear. However, the issue goes beyond macros and highlights the importance of signing what is seen and agreeing on the document format for digital signatures.
Firma&Cifra: This bug, reported anonymously in 2012, allowed the creation and verification of a signature with a fake certificate, which is the worst-case scenario. Again, no cryptographic algorithm was broken, and the issue did not lie in the cryptographic algorithm itself. The problem arose from the possibility of creating two different documents with the same hash. To verify a signature, the author’s digital certificates and the certification chain are needed, which should be checked online. However, offline verification is also necessary, requiring everything to be included in a PKCS (in this case, PKCS#7). The issue with Firma&Cifra was that it did not properly verify the PKCS#7, allowing the inclusion of unverified certificates in the secured storage area. This made it possible to generate a fake certificate, fake user certificate, and sign a document with them, all included in the PKCS#7. The Firma&Cifra application would accept these inputs without proper verification. Once again, the reaction to this issue was that it was all done “by design.”
In both cases, the vulnerabilities were not related to the cryptographic part but rather implementation problems or issues with the document format.
The entire PRF is described by the value of the seed that cannot be told apart from a random
