Subsections

6. Authentication with partially secret key

In the previous chapter we assumed that Eve had no information on the secret key used in the authentication, i.e., to Eve the key was a random variable uniform over its whole range. As explained in Section 1.2 that is an unrealistic requirement in QKG. Information leakage in the quantum transmission phase is unavoidable but the damage can be reduced using privacy amplification. Through the privacy amplification process Eve's knowledge of the key is reduced, but not to exactly zero. As soon as the whole initial key is used Alice and Bob will have to start trusting authentication with a key that is not completely secret. This chapter deals with authentication with a partially secret key in general, while the next chapter puts the results into the context of QKG.

If Eve holds some information about the authentication key, her chance of forgery may be much higher for some messages than others. For example, imagine Alice and Bob are authenticating messages using the second hash family in Section 5.2. Remember that those hash functions works by applying a number of smaller hash functions, each hash function halving the length of the message. If Eve knows the first hash function with certainty but nothing else and sees a valid message/tag pair from Alice, she can divide the message into substrings and change each substring to another that yields the same hash after the first step. No matter what the other hash functions are, the fact that the internal state after the first step is the same guarantees that the same tag is produced. However, if she wants to forge another message she is not helped at all by knowing the first hash function. But that is a weak comfort for Alice and Bob. Their goal was for Bob to verify that exactly the message he received was sent by Alice. No matter how limited Eve's choices are when choosing a forged message, Alice and Bob have failed if Eve makes any undetected change to the message. To be on the safe side we will consider the possibility of Eve to make an undetected change at all, without being bothered with how happy she is with the choice of message.

6.1 Active and passive chance of forgery

Eve's main goal is to make Bob accept a fake message, but her secondary goal is to avoid raising suspicions if she fails. If she has the possibility to first perform passive eavesdropping on the message and tag sent by Alice, and then decide whether she will launch a full-fledged active attack and send a forged message to Bob, it makes sense to divide Eve's chance of forgery into a passive part and an active part.

We can number the different states that Eve may be in after the eavesdropping phase depending on what message/tag pair she sees, denote the probability that she is in state with $p_{i}^{\text{pas}}$ and the probability that an active attack succeeds if she chooses to launch one with $p_{i}^{\text{act}}$ . Her total chance of succeeding is

$\displaystyle p^{\text{tot}}= \sum_i p_{i}^{\text{pas}}p_{i}^{\text{act}}.$

(6.1)

As long as Eve stays passive she does not risk detection, but if she chooses to make an active attack the chance of success is $p_{i}^{\text{act}}$ depending on the state she is in. If she fails to guess the tag correctly she is detected when Bob notices that it does not match the message. We will see that this difference between Eve's total and active chance of forgery is especially important in QKG and in other scenarios where many messages are sent and Eve only needs to forge one of them.

If Eve just needs to forge one message from an infinite stream of messages, she will wait until she after the eavesdropping phase is in the state with highest probability to guess a correct tag. As long as the passive probability for that state is non-zero, the probability that she will sometime reach that state will go to 1 as the number of messages goes to infinity, and Eve's chance of having forged a message will approach $p_{\text{max}}^{\text{act}}$ . If $p_{\text{max}}^{\text{act}}$ is not acceptably small, Alice and Bob must be prepared for the day when Eve succeeds.

6.2 No message/tag pairs seen

Eve doesn't need to know the whole key to be able to forge a message without any risk of being discovered, even when she cannot see a valid message/tag pair. The key is always larger than the tag and Eve needs only as much information that is contained in the tag. In other words, there are many hash functions that takes a single message to the same tag, and if her uncertainty about the key just makes her incapable of knowing which of those hash functions is used she still knows the correct tag with certainty. On the other hand, any information that just helps her pinpoint the exact hash function within the subsets that maps her message to the same tags is quite worthless.

Fortunately for Eve, what is worthless key information when trying to forge one message need not be when trying to forge another. The first condition of definition 1 states that exactly $\nicefrac{\vert\mathscr{H}\vert}{\vert\mathscr{T}\vert}$ keys or hash functions take a single message to a single tag. The second condition implies that the grouping of keys is different for each message. A natural upper bound for Eve's active chance to forge any message is therefore the sum of probabilities for the $\nicefrac{\vert\mathscr{H}\vert}{\vert\mathscr{T}\vert}$ most probable keys. The min-entropy of the key, $H_\infty(K)$ , is the negative logarithm of the highest probability so if we let denote the key length in bits and the tag length, a somewhat looser but simpler bound is given by

$\displaystyle p_{\text{max}}^{\text{act}} \leq \frac{\vert\mathscr{H}\vert}{\vert\mathscr{T}\vert}2^{-H_\infty(K)} = 2^{l_K - H_\infty(K) - l_T }.$

(6.2)

If Eve knows nothing about the key her key (min-)entropy equals the size of the key and chance is bounded by $2^{-l_T}$ as expected.

6.3 Encrypted tags

The method of one-time pad encryption of the tag described in (5.4) makes authentication of a constant stream of messages cheap and works fine when completely secret one-time pads are available. However, when the one-time pads are not guaranteed to be completely secret, Eve will learn something about the hash function for each message/tag pair she sees. The information she has about the one-time pad will equal the knowledge she gains about when she sees and XOR .

If Eve is unlucky she will only gain information she already had. The exact knowledge of she gains depends not only on her exact knowledge of but also on , so it is very hard to put restrictions only on Eve's knowledge that guarantees that she does not learn anything new.

All Eve has to do to exploit this weakness is to passively eavesdrop the messages and the encrypted tags and combine that information with whatever she knows about the one-time pads until she has enough confidence in her knowledge of the hash function that she can mount an attack that succeeds with acceptable probability. In other words, her active chance of forgery will increase for (almost) each message/tag pair she sees if encrypted tags are used. Therefore, using the encrypted tags method is not advisable unless the one-time pads are known to be completely secret. Using the normal method of selecting a new hash function for each message does not share this problem.

6.4 A message/tag pair seen

If Eve sees a message/tag pair from Alice to Bob she is given information about the authentication key, and she will combine that information with whatever she knew about the key initially. We will call the initial key before she has seen the tag and the key it reduces to after the tag is revealed $K = K_0\vert _{T=t}$ .

The change of her uncertainty about the key when she sees the tag is quite simple. The $\nicefrac{\vert\mathscr{H}\vert}{\vert\mathscr{T}\vert}$ keys consistent with the message/tag pair seen are singled out and normalized and the rest are set to 0. A limit for the average Rényi entropy of order 1 or larger of the resulting key is given by theorem 3,

$\displaystyle E_{t\in R(T)}(H_\alpha(K_0\vert _{T=t})) \geq H_\alpha(K_0) - H_1(T) \geq H_\alpha(K_0) - l_T.$

(6.3)

This is only a limit on the expectation value of the entropy, and we have seen several examples of very misleading averages. Fortunately we also have some limits on the individual entropies. They cannot be negative and they cannot be larger than . These limits will of course apply to the average as well. Combining these limits yields

$\begin{displaymath}\begin{split}H_\alpha(K_0) - l_T \leq E(&H_\alpha(K))\leq l_K... ...\leq \phantom{E(}&H_\alpha(K)\phantom) \leq l_K-l_T \end{split}\end{displaymath}$

(6.4)

which gives some kind of picture of how the entropies of the final key are distributed. Note that $H_\alpha(K_0)$ typically will be pretty close to

unless Eve initially knew very much about the authentication key.

6.4.1 The problem

If Alice and Bob wish to authenticate a stream of messages and are concerned about Eve's chances to forge any message in the long run the average value doesn't matter much. The average entropy might give an idea of the total chance of forgery, but if she gets infinitely many opportunities for an attack, even if she only can make one active attack, only the minimum possible entropy matters.

As an example, suppose Eve receives information that makes one of the keys twice as likely as before, while all other keys still have the same probability as each other. That is, the initial key is the random variable $Q_{\vert\mathscr{H}\vert-1}^{\nicefrac2{\vert\mathscr{H}\vert}}$ . Since the highest probability has doubled, the min-entropy of the key is reduced by exactly 1 bit. When she sees a message/tag pair she will rule out all but the $\nicefrac{\vert\mathscr{H}\vert}{\vert\mathscr{T}\vert}$ keys consistent with the pair. If the more probable key is not among those, the entropy of the resulting key will be maximal, , since she has no information about those keys. If the more probable key is among those left, the new maximal probability is given by renormalizing the probability $\nicefrac2{\vert\mathscr{H}\vert}$ .

$\displaystyle \max_{k\in R(K)}P\left(K\!=\!k\right) = \frac{\frac2{\vert\mathsc... ...scr{T}\vert} - 1)} \approx 2\frac{\vert\mathscr{T}\vert}{\vert\mathscr{H}\vert}$

(6.5)

**Figure 6.1:** Eve can wait undetected until she knows she can make a successful attack.

The probability of the most likely key is still approximately twice as high as if Eve had no information at all, which like before means her min-entropy is reduced by 1 bit. Thus, in this case 1 bit of reduced min-entropy in the initial key gives Eve normally no information about the final key and sometimes approximately 1 bit of reduced min-entropy of the final key. The message in the message-tag pair does not matter in this case. Eve's maximum active chance of forgery is just doubled.

As another example, suppose Eve's knowledge of the initial key is that out of the $\vert\mathscr{H}\vert$ possible keys, she has a list of $\nicefrac{\vert\mathscr{H}\vert}{\vert\mathscr{T}\vert}-1$ keys that she knows are not the real one. Furthermore, all those keys select hash functions that take Alice's message to the same tag.

The entropy for this key is very close to the entropy of a completely unknown key, which is the same thing as the length of the key. Since the distribution is uniform the Rényi entropy does not depend on $\alpha$ so we have for any $\alpha$

$\begin{displaymath}\begin{split}l_K &- H_\alpha(K_0) = \log(\vert\mathscr{H}\ver... ...}\vert\ln(2)} < \frac1{\vert\mathscr{T}\vert\ln(2)} \end{split}\end{displaymath}$

(6.6)

which is pretty small. A realistic tag size might be 32 bits, which would mean that the entropy is reduced with less than four billionths of a bit. Nevertheless, if the tag Alice sends is the right one, Eve will know the key with total certainty and $H_\alpha(K)=0$ . The chance of that tag being the right one is just one in $\vert\mathscr{H}\vert-\nicefrac{\vert\mathscr{H}\vert}{\vert\mathscr{T}\vert}+1$ and for any other tag Eve has no use for her prior information, so the average entropy will still be very close to

, as is required by (6.4).

Eve's active chance of forgery is exactly 1 in this case. If the message is changed to one where the $\nicefrac{\vert\mathscr{H}\vert}{\vert\mathscr{T}\vert}-1$ keys with 0 probability instead are spread out as evenly as possible over the $\vert\mathscr{T}\vert$ tags, Eve's entropy for the final key is independent of both the tag and $\alpha$ and is bounded by

$\begin{displaymath}\begin{split}H_\alpha(K) \geq \log(\frac{\vert\mathscr{H}\ver... ... &> l_K - l_T - \frac1{\vert\mathscr{T}\vert\ln(2)} \end{split}\end{displaymath}$

(6.7)

which leaves her maximum active chance of forgery pretty much unaffected when Alice sends this particular message.

6.4.2 The solution

We have seen that simply sending a tag along with each message to prove authenticity does not work in the long run if Eve has a small but non-zero knowledge of the authentication key used. However, only minor adjustments are needed to make Eve's active chance of forgery equal to her passive chance, and therefore makes her chances of successful forgery before being detected equal to her maximum total chance of forgery.

One theoretical solution is for Alice and Bob to have synchronized clocks and agree before each message at which time the message should arrive. At that time Alice will send the message, wait for a time interval longer than the precisions of their clocks, and send the tag. Eve will not know if she will be able to forge a message/tag pair before she sees the real tag, but by then it will be too late to change the message. Keeping the clocks synchronized and agreeing upon fixed times for messages seem kind of problematic though, so this is probably not a good idea.

**Figure:** Two different solutions. In both versions Eve is forced to launch her attack before she knows if she will succeed and can therefore, with very high probability, never launch an attack undetected. $m_n\!\parallel\!s_n$ is the concatenation of the message and the salt.

A simpler solution that does not need clocks is for Alice to send the message to Bob, who replies with a random fix-sized temporary bit string, called the salt, which Eve must not be able to guess before she sees it. Alice calculates a tag based on the concatenation of the message and the salt and sends that tag to Bob. Before Eve has seen the tag she will not know if she will be able to forge a message/salt/tag triplet, and she will not see the tag before she sends the salt to Alice. Since she cannot send fake salt to Alice and be sure to get away with it before she has seen the real tag, she can either send the real message to Bob and fail but stay undetected or send Alice faked salt and Bob a faked message and with only a very small probability be able to send Bob the right tag. With almost certainty the tag she receives from Alice won't give her enough information so she will probably get caught. This solution requires slightly more time for Alice and Bob to communicate and, since the message to be authenticated now includes the salt, a slightly larger authentication key.

Authentication in quantum key growing