English French
A better approach would be to authenticate Alice without storing her password in clear on Bob's computer. For this, Alice computes a `hash chain` as proposed by Lamport in [Lamport1981]_. A hash chain is a sequence of applications of a hash function (`H`) on an input string. If Alice's password is `P`, then her 10 steps hash chain is : :math:`H(H(H(H(H(H(H(H(H(H(P))))))))))`. The result of this hash chain will be stored on Bob's computer together with the value `10`. This number is the maximum number of remaining authentications for Alice on Bob's computer. To authenticate Alice, Bob sends the remaining number of authentications, i.e. `10` in this example. Since Alice knows her password, `P`, she can compute :math:`H^9(P)=H(H(H(H(H(H(H(H(H(P)))))))))` and send this information to Bob. Bob computes the hash of the value received from Alice (:math:`H(H^9(P))`) and verifies that this value is equal to the value stored in his database. It then decrements the number of authorized authentications and stores :math:`H^9(P)` in his database. Bob is now ready for the next authentication of Alice. When the number of authorized authentications reaches zero, the hash chain needs to be reinitialized. If Eve captures :math:`(H^n(P))`, she cannot use it to authenticate herself as Alice on Bob's computer because Bob will have decremented its number of authorized authentications. Furthermore, given that hash functions are not invertible, Eve cannot compute :math:`H^{n-1}(P)` from :math:`H^{n}(P)`.
`A cryptographic algorithm should be secure even if the attacker knows everything about the system, except one parameter known as the secret key.`
A detailed explanation of the ECC cryptosystems is outside the scope of this e-book. A simple introduction may be found on `Andrea Corbellini's blog <http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/>`_. There have been deployments of ECC recently because ECC schemes usually require shorter keys than RSA and consume less CPU.
A detailed explanation of the operation of the RSA algorithm is outside the scope of this e-book. Various tutorials such as the `RSA page <https://en.wikipedia.org/wiki/RSA_(cryptosystem)>`_ on wikipedia provide examples and tutorial information.
A drawback of this approach is that Bob is forced to perform two public key computations : one encryption to send the random nonce to Alice and one decryption to recover the nonce encrypted by Alice. If these computations are costly from a CPU viewpoint, this creates a risk of Denial of Service Attacks were attackers could try to access Bob's computer and force it to perform such costly computations. Bob is more at risk than Alice in this situation and he should not perform complex operations before being sure that he is talking with Alice. An alternative is shown in the time sequence diagram below.
AES is widely used as of this writing, but other secret key encryption schemes continue to appear. ChaCha20, proposed by D. Bernstein is now used by several internet protocols :rfc:`7539`. A detailed discussion of encryption schemes is outside the scope of this book. We will consider encryption schemes as black boxes whose operation depends on a single key. A detailed overview of several of these schemes may be found in [MVV2011]_.
AES or the Advanced Encryption Standard is an encryption scheme that was designed by the Belgian cryptographers Joan Daemen and Vincent Rijmen in 2001 [DR2002]_. This algorithm has been standardized by the U.S. National Institute of Standards and Technology (NIST). It is now used by a wide range of applications and various hardware and software implementations exist. Many microprocessors include special instructions that ease the implementation of AES. AES divides the message to be encrypted in blocks of 128 bits and uses keys of length 128, 192 or 256 bits. The block size and the key length are important parameters of an encryption scheme. The block size indicates the smallest message that can be encrypted and forces the sender to divide each message in blocks of the supported size. If the message is larger than an integer number of blocks, then the message must be padded before being encrypted and this padding must be removed after decryption. The key size indicates the resistance of the encryption scheme against brute force attacks, i.e. attacks where the attacker tries all possible keys to find the correct one.
agree on a way to encrypt the messages that they will exchange
a hash of the entire file signed with Ted's private key
Alice and Bob are the first names that are used in examples for security techniques. They first appeared in a seminal paper by Diffie and Hellman [DH1976]_. Since then, Alice and Bob are the most frequently used names to represent the users who interact with a network. Other characters such as Eve or Mallory have been added over the years. We will explain their respective roles later.
Alice and Bob have agreed on the secret information :math:`3` without having sent it explicitly through the network. If the integers used are large enough and have good properties, then even Eve who can capture all the messages sent by Alice and Bob cannot recover the secret key that they have exchanged. There is no formal proof of the security of the algorithm, but mathematicians have tried to solve similar problems with integers during centuries without finding an efficient algorithm. As long as the integers that are used are random and large enough, the only possible attack for Eve is to test all possible integers that could have been chosen by Alice and Bob. This is computationally very expensive. This algorithm is widely used in security protocols to agree on a secret key.
Alice checks the signature (with :math:`Bob_{pub}`) and the certificate and computes :math:`S_{A}=B^{a} \mod p`
Alice chooses a secret integer and sends :math:`A= g^{a} \mod p` to Mallory
Alice chooses a secret integer : :math:`a=8` and sends :math:`A= g^{a} \mod p= 5^{8} \mod 23=16` to Bob
Alice chooses a secret integer : :math:`a` and sends :math:`A= g^{a} \mod p` to Bob
Alice computes :math:`S_{A}=B^{a} \mod p= 21^{8} \mod 23=3`
Alice computes :math:`S_{A}=M^{a} \mod p` and uses this key to communicate with Mallory (acting as Bob)
Alice selects a random integer, :math:`a` and sends :math:`A=g^{a} \mod p` to Bob
Alice sends her random nonce, :math:`R2`. Bob signs :math:`R2` and sends his nonce : :math:`R1`. Alice signs :math:`R1` and both are authenticated.
A naive approach would be to rely on hash functions. Since hash functions are non-invertible, Alice and Bob could decide to use them to exchange Alice's password in a secure manner. Then, Alice could be authenticated by using the following exchange.