Exit Zen
53
../../principles/security.rst:545
English
To authenticate herself, Alice sends her user identifier to Bob. Bob replies with a random number as a challenge to verify that Alice knows the shared secret (i.e. her password). Alice replies with the result of the computation of a hash function (e.g. SHA-1) over a string that is the concatenation between the random number chosen by Bob and Alice's password. The random number chosen by Bob is often called a `nonce` since this is a number that should only be used once. Bob performs the same computation locally and can check the message returned by Alice. This type of authentication scheme has been used in various protocols. It prevents replay attacks. If Eve captures the messages exchanged by Alice and Bob, she cannot recover Alice's password from the messages exchanged since hash functions are non-invertible. Furthermore, she cannot replay the hashed value since Bob will always send a different nonce.
0/9150 · 915
54
../../principles/security.rst:559
English
Unfortunately, this solution forces Bob to store Alice's password in clear. Any breach in the security of Bob's computer would reveal Alice's password. Such breaches unfortunately occur and some of them have led to the dissemination of millions of passwords.
0/2580 · 258
55
../../principles/security.rst:571
English
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)`.
0/15040 · 1504
56
../../principles/security.rst:593
English
The two protocols above prevent eavesdropping attacks, but not man-in-the-middle attacks. If Mallory can intercept the messages sent by Alice, he could force her to reveal :math:`H^n(P)` and then use this information to authenticate as Alice on Bob's computer. In practice, hash chains should only be used when the communicating users know that there cannot be any man-in-the-middle on their communication.
0/4060 · 406
57
../../principles/security.rst:600
English
Public key cryptography provides another possibility to allow Alice to authenticate herself on Bob's computer. Assume again that Alice and Bob know each other from previous encounters. Alice knows Bob's public key (:math:`Bob_{pub}`) and Bob also knows Alice's key (:math:`Alice_{pub}`). To authenticate herself, Alice could send her user identifier. Bob would reply with a random number encrypted with Alice's public key : :math:`E_p(Alice_{pub},R)`. Alice can decrypt this message to recover `R` and sends :math:`E_p(Bob_{pub},R)`. Bob decrypts the nonce and confirms that Alice knows :math:`Alice_{priv}`. If an eavesdropper captures the messages exchanged, he cannot recover the value `R` which could be used as a key to encrypt the information with a secret key algorithm. This is illustrated in the time sequence diagram below.
0/8330 · 833
58
../../principles/security.rst:634
English
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.
0/6060 · 606
59
../../principles/security.rst:664
English
Here, Bob simply sends a random nonce to Alice and verifies her signature. Since the random nonce and the signature could be captured by an eavesdropper, they cannot be used as a secret key to encrypt further data. However Bob could propose a secret key and send it encrypted with Alice's public key in response to the signed nonce that he received.
0/3490 · 349
60
../../principles/security.rst:671
English
The solution described above works provided that Bob and Alice know their respective public keys before communicating. Otherwise, the protocol is not secure against man-in-the-middle attackers. Consider Mallory sitting in the middle between Alice and Bob and assume that neither Alice nor Bob knows the other's public key.
0/3220 · 322
61
../../principles/security.rst:705
English
In the above example, Alice sends her public key, (:math:`Alice_{pub}`), in her first message together with her identity. Mallory intercepts the message and replaces Alice's key with his own key, (:math:`Mallory_{pub}`). Bob replies with a nonce, `R`. Alice then signs the random nonce to prove that she knows :math:`Alice_{priv}`. Mallory discards the information and instead computes :math:`E_p(Mallory_{priv},R)`. Bob now thinks that he is discussing with Alice while Mallory sits in the middle.
0/4980 · 498
62
../../principles/security.rst:714
English
There are situations where symmetric authentication is required. In this case, each user must perform some computation with his/her private key. A possible exchange is the following. Alice sends her certificate to Bob. Bob replies with a nonce, :math:`R1`, and provides his certificate. Alice encrypts :math:`R1` with her private key and generates a nonce, :math:`R2`. Bob verifies Alice's computation and encrypts :math:`R2` with his private key. Alice verifies the computation and both have been authenticated.
0/5120 · 512
63
../../principles/security.rst:747
English
The protocol described above works, but it takes a long time for Bob to authenticate Alice and for Alice to authenticate Bob. A faster authentication could be the following.
0/1730 · 173
64
../../principles/security.rst:771
English
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.
0/1470 · 147
65
../../principles/security.rst:775
English
Now consider that Mallory wants to be authenticated as Alice. The above protocol has a subtle flaw that could be exploited by Mallory. This flaw can be exploited if Alice and Bob can act as both client and server. Knowing this, Mallory could operate as follows. Mallory starts an authentication with Bob faking himself as Alice. He sends a first message to Bob including Alice's identity.
0/3880 · 388
66
../../principles/security.rst:799
English
In this exchange, Bob authenticates himself by signing the :math:`RA` nonce that was sent by Mallory. Now, to authenticate as Alice, Mallory needs to compute the signature of nonce :math:`RB` with Alice's private key. Mallory does not know Alice's key, but he could exploit the protocol to force Alice to perform the required computation. For this, Mallory can start an authentication to Alice as shown below.
0/4090 · 409
67
../../principles/security.rst:822
English
In this example, Mallory has forced Alice to compute :math:`E_p(Alice_{priv},RB)` which is the information required to finalize the first exchange and be authenticated as Alice. This illustrates a common problem with authentication schemes when the same information can be used for different purposes. The problem comes from the fact that Alice agrees to compute her signature on a nonce chosen by Bob (and relayed by Mallory). This problem occurs if the nonce is a simple integer without any structure. If the nonce includes some structure such as some information about Alice and Bob's identities or even a single bit indicating whether the nonce was chosen by a user acting as a client (i.e. starting the authentication) or as a server, then the protocol is not vulnerable anymore.
0/7840 · 784
68
../../principles/security.rst:837
English
To cope with some of the above mentioned problems, public-key cryptography is usually combined with certificates. A `certificate` is a data structure that includes a signature from a trusted third party. A simple explanation of the utilization of certificates is to consider that Alice and Bob both know Ted. Ted is trusted by these two users and both have stored Ted's public key : :math:`Ted_{pub}`. Since they both know Ted's key, he can issue certificates. A certificate is mainly a cryptographic link between the identity of a user and his/her public key. Such a certificate can be computed in different ways. A simple solution is for Ted to generate a file that contains the following information for each certified user :
0/7280 · 728
69
../../principles/security.rst:849
English
his/her identity
0/160 · 16
70
../../principles/security.rst:850
English
his/her public key
0/180 · 18
71
../../principles/security.rst:851
English
a hash of the entire file signed with Ted's private key
0/550 · 55
72
../../principles/security.rst:853
English
Then, knowing Ted's public key, anyone can verify the validity of a certificate. When a user sends his/her public key, he/she must also attach the certificate to prove the link between his/her identity and the public key. In practice, certificates are more complex than this. Certificates will often be used to authenticate the server and sometimes to authenticate the client.
0/3760 · 376