Wireless communication method for secure side-channel signaling and authentication at the physical layer

Abstract

A method for wireless communication using a service side-channel signaling and authentication at the physical level. This method comprising the steps of creating at least one transmitting node and one receiving node within a wireless communication channel. Then choosing primary message and a secondary message and generating a valid transmission tag. Then superimposing the valid transmission tag and creating a set of secret codebooks in order to form a side-channel. Then applying key equivocation metric to measure key information leakage to an eavesdropper. Then transmitting said primary message and said secondary message. Then a receiver receiving said primary and said secondary messages detecting fingerprint estimating data combining a key set with the estimated data sending data and key set to a matrix to generate a secret codebook searching for valid tags authenticating and recovering side information.

Claims

1. A method for wireless communication using a service side-channel signaling and authentication at the physical level the method comprising the steps of: creating at least one transmitting node and one receiving node within a wireless communication channel; choosing primary message and a secondary message to be sent by a transmitter; generating a valid transmission tag to be sent by said transmitter; superimposing the valid transmission tag by said transmitter; creating a set of secret codebooks by said transmitter; forming a side-channel and applying key equivocation metric to measure key information leakage to an eves dropper by said transmitter; transmitting said primary message and said secondary message by said transmitter; receiving said primary and said secondary messages by a receiver; detecting fingerprint by said receiver; estimating data by said receiver; combining a key set with the estimated data by said receiver; sending data and key set to a matrix to generate a secret codebook by said receiver; searching for valid tags by said receiver; authenticating and recovering side information by said receiver.

2. The method of claim 1, wherein said secret codebooks are created from a random generator matrix made up of the valid tags of a standard codebook.

3. The method of claim 1, wherein generating valid transmission tags further comprises forming said valid transmission tags from originally generated data, generated side data and a key set combined together in a valid transmission tag generating matrix.

4. The method of claim 3, wherein superimposing said valid transmission tags further comprises using the generated transmission tags and the originally generated data to form a message wherein said valid transmission tags are superimposed.

5. The method of claim 1, wherein the step of detecting fingerprint further includes observing a threshold for changes.

6. The method of claim 5, wherein the step of observing a threshold further includes calculating appropriate threshold limits to prevent false alarms.

7. The method of claim 1, where the step of receiving further includes reconstructing a valid codebook from the obtained information in the side-channel message and a shared key.

8. The method of claim 1, wherein the step of authentication further comprises detecting a valid tag through observation.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The embodiments herein will be better understood from the following detailed description with reference to the drawings, in which:

(2) FIG. 1 is a schematic diagram representing the communication system with the authentication scheme of the present invention;

(3) FIG. 2 is a graphical diagram representing an increasing side channel rate;

(4) FIG. 3 is a graphical diagram representing side channel performance messages with and without error correction;

(5) FIG. 4 is a graphical diagram representing side channel performance that follows the packet success rate;

(6) FIG. 5 is a graphical diagram representing the key equivocation decreasing linearly with each of the adversary's observations;

(7) FIG. 6 is a graphical diagram representing performance vs security over side-channel success probability;

(8) FIG. 7 is a graphical diagram representing required tag length to achieve desired performance and remain below wall over required tag systems.

DETAILED DESCRIPTION

(9) Referring to FIG. 1 a system diagram of the multi-key physical layer fingerprinting framework (10) in accordance with the present invention is provided. A transmitter (12) and a receiver (14) are provided. Within the transmitter (12) we find means for generating data (16), a tag generator (18) a means for generating side-data (20) and a key set (22). All of these elements are combined with a method to superimpose (24) the information in a side-channel communication. The communication is transmitted by the transmitter (12) over a channel (26) where it may be exposed to an eavesdropper (eve) (28). The communication is received by the receiver (14) where the data is used to estimated data (32) along with a key set (34) to generate a secret codebook (36). The communication along with the information generated by the secret codebook generation (36) is then used to search for any valid tag (30), finally this information is used to authenticate and recover side information (38).

(10) A legitimate transmitter-receiver paid share the same set of secret keys that are used to enable authentication and transmit additional information over a side-channel. Prior to any public communication, the transmitter and receiver share a K-bit secret master key k that is chosen uniformly at random from K and represents their total shared secret bits. The primary message s is a length L vector of complex-valued iid symbols with zero mean and unit variance. The secondary message is represented by a uniformly chosen integer m{1, . . . , N.sub.k} which is used to determine a tag, t.sup.xmit, obtained from a tag generating function.
t.sup.xmit=g(s,m,k). (eq. 1)

(11) For a given s and k, the set of all txmit resulting from each m is called the valid tag codebook and is denoted as: T.sup.valid={t.sub.i.sup.valid}.sub.1iN.sub.k={g(s,k,m)}.sub.1mN.sub.k.

(12) We assume that txmit is of similar structure to s, i.e. it is also a length L vector of complex valued iid symbols with zero mean and unit variance, though possibly from a different distribution, or modulation type. This approach simplifies the receiver processing because s and txmit are symbol-synchronous, although more general fingerprint insertion methods are possible. The final symbol output x is given by scaling and summing the message and tag.
x=p.sub.ss+p.sub.tt.sup.xmit(eq. 2)

(13) The power is allocated between message and tag by p.sub.s and p.sub.t, whose values are non-negative real scalars that satisfy p.sub.s.sup.2+p.sub.s.sup.1=1. The final output vector, x, is therefore also of unit transmit power.

(14) The procedure for fingerprint embedding from the transmitter is as follows: 1. Choose primary message s and secondary message m. 2. Generate tag txmit using (1). 3. Superimpose tag using (2). 4. Transmit x.

(15) In this invention, two secret codebook construction techniques are considered for the tag generating function (1). In both cases, the construction of the codebook is aided by the use of cryptographic hash functions. The first codebook, called the standard secret codebook, is constructed by first partitioning the master key into N.sub.k smaller keys of identical length.sup.l. Denote this partitioned keys by Kvalid={k.sup.valid}.sub.1iN is where each sub-key is indexed by a different secondary message.

(16) Then, we assume that g(s, k, m)=g.sup.l(s, k.sup.valid), where g.sup.l(, ) is a deterministic function designed so that changes in the input(s) produce what appears to be unrelated (sometimes modeled as statistically independent) outputs. In this approach, k.sup.valid is chosen depending on m which facilitates the transfer of information through the side-channel. In practice, cryptographic hash functions are generally accepted as providing a good approximation to the desired g.sup.1(, ). When dealing with hash functions, the HMAC protocol [1] should be used to securely incorporate the key in order to avoid vulnerabilities such as length extension attacks. The codebook formed from the set of tags corresponding to each m is called the valid codebook for s. It should be noted that the original single key design of the framework in U.S. Pat. No. 9,161,214 B2 is obtained by setting N.sub.k=1 so that there is only one key and thus only one tag in the valid codebook.

(17) The second codebook construction, called the linear secret codebook approach, has similar structure to the first, but the master key is now broken down into log 2 Nk smaller keys, labeled the valid key set. We proceed by calculating a set of basis tags corresponding to each valid key using the same g.sup.1(, ) as the standard secret codebook approach. (Recall that previously, only a single tag is required to be calculated using the valid key associated with m). The final set of valid tags is then composed of all linear combinations of the basis tags. The final valid linear codebook is of size N.sub.k 1 after omitting the zero tag/codeword since it will be present in every linear codebook for any s and thus is not useful for authentication. Now, t.sup.xmit is selected from the codebook based on the secondary message from the range m{1, . . . , N.sub.k1}. The nice properties of g.sup.1(, ) and the fact that log 2 N.sub.kL guarantees that the codewords produced by the linear combinations will be unique with very high probability [2]. Simple ad hoc fixes can be employed if this is not the case. The secret linear coding scheme does not require any changes to the partitioned codebook procedure described in the preceding sections due to the pairwise independence of codewords. In fact, for a codebook of equal size, the performance between the two schemes will be identical.

(18) Alternate Description of Secret Linear Codebook

(19) The secret linear codebook can be alternatively interpreted as being constructed from a random generator matrix made up of the valid tags of the standard codebook. The transmitter chooses a length N.sub.k binary vector m with the zero vector excluded. The transmitted tag is then:

(20) $\begin{array}{cc}\begin{array}{c}{t}^{\mathrm{xmit}}=m\stackrel{\_}{G}\\ =\underset{j=1}{\overset{N_k}{.Math.}}{m}_j{t}_j^{\mathrm{valid}},\end{array}& \left(\mathrm{eq}.3\right)\end{array}$

(21) where m.sub.j is the j.sup.th bit of the binary vector m and t.sub.j.sup.valid is the j.sup.th row of the generator matrix

(22) $\begin{array}{cc}\stackrel{\_}{G}=\left[\begin{array}{c}{t}_1^{\mathrm{valid}}\\ t_2^{\mathrm{valid}}\\ \mathrm{.Math.}\\ t_{N_k}^{\mathrm{valid}}\end{array}\right],& \left(\mathrm{eq}.4\right)\end{array}$

(23) created using (1) for each key in K.sup.valid. Note that (3) is performed with binary vectors before being modulated to the complex symbols that are superimposed in (2). This formulation is equivalent to linear coding with a generator matrix, in this case t.sup.valid, whose rows are formed by the set of valid tags T valid. Procedure 2.

(24) TABLE-US-00001 Procedure 2 Secret Linear Codebook (Transmitter) 1: Choose primary message s and secondary message m. 2: Use (1) to generate t.sub.j.sup.valid for the rows of the generator matrix G in (4). 3: Generate tag using (3). 4: Modulate and superimpose tag using (2). 5: Transmit x.

(25) Channel Model

(26) The additive white Gaussian noise (AWGN) channel is considered for the present invention. The legitimate receiver and the adversary respectively observe
Y=x+W.sub.b(eq. 5)
Z=x+W.sub.e(eq. 6

(27) where W.sub.b (W.sub.e) is a vector of L random complex Gaussian noise samples, each with zero mean and variance .sup.2 (.sup.2).

(28) Receiver Processing

(29) The receiver observes Y through the AWGN channel in (5) and attempts to decode the primary message, determine its authenticity, and recover any side-channel information. It is assumed that tag power is small relative to the message power (p.sup.2p.sup.2), so the message can be decoded by ignoring the presence of the tag, but with a small performance penalty in bit error rate (BER) [3]. The primary message is observed at an SNR of

(30) $\frac{p_s^2}{p_t^2+{}_b^2}.$

(31) A residual is formed by removing 8, the estimated version of s, from Y to obtain,

(32) $\begin{array}{cc}R=\frac{1}{p_t}\left(Y-p_s\hat{s}\right)=\hat{t}+\frac{1}{p_t}{W}_b& \left(\mathrm{eq}.7\right)\end{array}$ where t{circumflex over ()} represents the unknown tag that was transmitted. The residual can then be tested for the presence of a valid tag by performing a hypothesis test as follows:

(33) $\begin{array}{cc}\{\begin{array}{cc}{H}_0& \mathrm{No}\mathrm{valid}\mathrm{tag}\mathrm{was}\mathrm{sent}\\ H_1& t_1^{v\mathrm{alid}}\mathrm{was}\mathrm{sent},m=1\\ & \mathrm{.Math.}\\ H_{N_k}& t_{N_k}^{v\mathrm{alid}}\mathrm{was}\mathrm{sent},m=N_k.\end{array}& \left(\mathrm{eq}.8\right)\end{array}$

(34) Essentially, the receiver reconstructs a valid codebook from the obtained s{circumflex over ()} and shared k, and then both decodes and determines the authenticity of t{circumflex over ()}. Note that because the legitimate transmitter and receiver agree upon K.sup.valid, they also agree upon T.sup.valid as long as s=s{circumflex over ()}. It is assumed in the subsequent analysis that the message is obtained without error. If the message is decoded in error, then authentication is highly likely to fail due to incorrect reconstruction of T valid, the valid codebook.

(35) Deciding H.sub.0 indicates that no valid tag was detected in Y. Deciding Hj(>0) indicates that the message is authentic and simultaneously determines the secondary message m. This conveys log 2 N.sub.k bits of information over the side-channel. A test statistic for each valid tag in the codebook is calculated using a bank of N.sub.k matched filters to resolve (8). The test statistic corresponding to t.sup.valid is
Z.sub.iZ.sub.i(R)=(R.sup.t.sup.valid.sub.i),(eq. 9)

(36) for i=1, . . . , N.sub.k, where () denotes real part of its argument and is the conjugate transpose. The hypothesis corresponding to the largest test statistic is chosen if it exceeds a threshold, r, that is calculated to limit a, the probability of type I error. The full decision process can be found in Procedure 3 where the threshold design is detailed in the subsequent section.

(37) Fingerprint Detection

(38) The detection threshold r changes for each observation because of the dependency of the codebook, T.sup.valid, on . This section provides the calculations necessary to design the threshold in Procedure 3 that limits the probability of false alarm to a. The false alarm rate allows the legitimate parties to limit the probability that a random tag is wrongly authenticated or that the wrong secondary message is decoded. Decreasing the false alarm rate better protects against impersonation attacks

(39) TABLE-US-00002 Procedure 3 Receiver's Hypothesis Test 1: Calculate test statistics {z.sub.1, z.sub.2, . . . , z.sub.N.sub.k} 2: Determine i = arg max.sub.1jN.sub.k.sup.z.sup.j 3: Calculate threshold 4: if z.sub.1 > then 5: Decide hypothesis H.sub.1 6: else 7: Decide hypothesis H.sub.0 8: end if

(40) and side-channel decoding errors, but decreases overall side-channel performance since the stricter test increases the probability of wrongly rejecting an authentic tag.

(41) Because the tags are generated using a cryptographic hash function, the tag/codewords in the codebook are essentially drawn uniformly at random. Thus, we model any particular codebook as an instance of the uniform random variable T.sup.valid={T.sup.valid.sub.1 . . . , T.sub.nk.sup.valid}. To reiterate the notation, we then take t.sup.valid={t.sup.valid.sub.1, . . . , t.sup.valid.sub.nk} to denote a particular realization of T.sup.valid.

(42) Distribution of Test Statistics {Z.sub.1, . . . , Z.sub.N.sub.k}

(43) We consider the distribution of the test statistics conditioned on each hypothesis. This allows us to calculate the appropriate thresholds to limit the false alarm probability.

(44) The i.sup.th test statistic conditioned on hypothesis H.sub.j being true is
Z.sub.i(R|H.sub.j)=({circumflex over (t)}.sup.t.sup.valid.sub.i|H.sub.j)+{tilde over (W)},(eq. 10)

(45) where

(46) $\tilde{W}=\frac{1}{P_t}\left(W^{}{t}_i^{\mathrm{valid}}\right)$
is a zero mean Gaussian random variable with approximate variance.sup.i

(47) ${}_{\tilde{w}}^2=\frac{1}{p_t^2}L{}_t^2{}_w^2.$
Thus, {tilde over (W)}(0,.sub.{tilde over (w)}.sup.2).

(48) We further expand (10), first for H.sub.0, and then for Hj(>0).

(49) When H.sub.0 is true, then an invalid tag was transmitted, i.e., t{circumflex over ()}T\t.sup.valid. For security, the number of valid tags comprises a very small subset of T, so that an adversary has a very low chance of picking a valid tag by chance. So, T\t.sup.valid. With L sufficiently large to apply the Central Limit Theorem, we have that R(t{circumflex over ()}t.sup.valid is normally distributed. Hence,

(50) $\begin{array}{cc}\begin{array}{c}{Z}_i\left(R|H_0\right)\left({\hat{t}}^{}{t}_i^{\mathrm{valid}}|\hat{t}\mathrm{��}\right)+\tilde{w}\\ ~\left(0,\frac{L}{2}{}_t^4+{}_{\tilde{w}}^2\right).\end{array}& \left(\mathrm{eq}.10\right)\left(\mathrm{eq}.11\right)\end{array}$

(51) When Hj(>0) is true, then it follows simply from (10) that

(52) $\begin{array}{cc}\begin{array}{c}{Z}_i\left(R|H_{j\left(>0\right)}\right)=\left({\hat{t}}^{}{t}_i^{\mathrm{valid}}|\hat{t}=t_j^{\mathrm{valid}}\right)+\tilde{w}\\ ~\left(\left(t_j^{{\mathrm{valid}}^{}}{t}_i^{\mathrm{valid}}\right),{}_{\tilde{w}}^2\right).\end{array}& \left(\mathrm{eq}.13\right)\end{array}$

(53) To interpret this, let us consider the cases where i=j and ij. When i=j, then

(54) 0$\left[\left(T_i^{{\mathrm{valid}}^{}}{T}_i^{\mathrm{valid}}\right)\right]=L{}_t^2$
because the tag symbols are iid. On the other hand, when ij, then

(55) $\left[\left(T_{j\left(i\right)}^{{\mathrm{valid}}^{}}{T}_i^{\mathrm{valid}}\right)\right]=0.$

(56) 2.6 Calculation of Thresholds {(.sub.1, . . . , .sub.Nk}

(57) For each message, N.sub.k thresholds are computed, each chosen to limit the probability of choosing one of the N.sub.k incorrect hypotheses to . More specifically, the thresholds for Hj(>0) limit side-channel decoding error while the threshold for H.sub.0 limits the incorrect acceptance of invalid tags. Conditioned on H.sub.j being true, the thresholds are calculated as

(58) $\begin{array}{cc}{}_i|H_{j\left(i\right)}=\underset{}{\min }s.t.Pr\left\{Z_i\left(R|H_j\right)>\right\}<.& \left(\mathrm{eq}.14\right)\end{array}$
for H.sub.j(>0) and

(59) $\begin{array}{cc}{}_i|H_0=\underset{}{\min }s.t.Pr\left\{Z_{\left(N_K\right)}>\right\}<.& \left(\mathrm{eq}.15\right)\end{array}$

(60) for H.sub.0 where Z(Nk) is the maximum test statistic. This is required to account for the fact that the test statistic under H.sub.0 is the maximum value produced by a random tag passing through N.sub.k matched filters. In particular, by considering the cases of H.sub.0 and Hj(>0), we have

(61) $\begin{array}{cc}{}_i|H_0={}^{-1}\left(\sqrt[N_k]{1-}\right)\sqrt{\frac{L}{2}{}_t^4+{}_{\tilde{w}}^2}& \left(\mathrm{eq}.17\right)\left(\mathrm{eq}.16\right)\\ {}_i|H_{\left(j>0\right)}={}^{-1}\left(1-\right){}_{\stackrel{}{w}}+\left(t_j^{{\mathrm{valid}}^{}}{t}_i^{\mathrm{valid}}\right)& \end{array}$

(62) where (16) is due to the maximum order statistic CDF under H.sub.0 being F.sub.Z

(63) ${}^{N_k}\left(\frac{z}{\sqrt{\frac{L}{2}{}_t^4+{}_{\tilde{w}}^2}}\right)$
where () is the standard normal CDF.

(64) Without any priors as to which hypothesis is more likely, we set the threshold .sub.i conservatively:

(65) $\begin{array}{cc}{}_i=\underset{ji}{\max }\left\{{}_i|H_j\right\}.& \left(\mathrm{eq}.18\right)\end{array}$

(66) .sub.ii is excluded from consideration because it does not correspond to a false detection event. One is not restricted to this choice of threshold. For example, one may assign more importance to the null hypothesis to lower the possibility of false authentication.

(67) Authentication Performance

(68) Authentication correctly occurs when 1) the transmitter transmits a message with a valid tag and 2) the receiver is able to detect a valid tag in their observation. That is, it occurs when the transmitter transmits t.sup.validt.sup.valid and the receiver decides t{circumflex over ()}t.sup.valid. However, because of the structure of the secret codebook (or rather, lack thereof) due to the use of cryptographic hash functions, mistaking one valid tag for another using Procedure 3 is extremely unlikely. Therefore, we instead focus on the case where the receiver is able to correctly detect the transmitted tag such that t{circumflex over ()}=t.sup.valid.

(69) Single Realization

(70) We first consider the probability of authentication for a particular set of valid tags t.sup.valid=

(71) {t.sup.valid, . . . , t.sup.valid}. Without loss of generality, let H.sub.I be true, i.e., t.sup.xmit=t.sup.valid. Then,

(72) $\begin{array}{cc}\begin{array}{c}\mathrm{Pr}\left[\mathrm{Decide}{H}_1|H_1,t^{\mathrm{valid}}\right]=\mathrm{Pr}[Z_1\left(R|H_1\right)>{}_1\mathrm{and}\\ Z_1\left(R|H_1\right)=\\ \underset{1i{N}_k}{\max }\left\{Z_i\left(R|H_1\right)\right\}{t}^{\mathrm{valid}}]\\ ={}_{{}_1}^{}Pr[Z_2\left(R|H_1\right)<z,\mathrm{.Math.},\\ Z_{N_k}\left(R|H_1\right)<z|t^{\mathrm{valid}}]\\ p_{Z_1\left(R|H_1\right)}\left(z\right)dz\end{array}& \left(\mathrm{eq}.19\right)\left(\mathrm{eq}.20\right)\end{array}$

(73) where pZ1(R|H1) is the probability density of Z.sub.1 under hypothesis H.sub.1 as given in (13). Note that conditioned on a particular set t.sup.valid, the test statistics are not independent. This can be easily seen by considering two valid tags that are highly correlated.

(74) Overall

(75) Now, the probability of authentication for a random secret codebook T.sup.valid is considered.

(76) $\begin{array}{cc}\begin{array}{c}\mathrm{Pr}\left[\mathrm{Decide}{H}_1|H_1\right]={T^{\mathrm{valid}}}_{}\left[\mathrm{Pr}\left[\mathrm{Decide}{H}_1|H_1,T^{\mathrm{valid}}\right]\right]\\ =\underset{i}{\overset{}{.Math.}}\mathrm{Pr}\left[\mathrm{Decide}{H}_1|H_1,T^{\mathrm{valid}}=t_i^{\mathrm{valid}}\right]\\ \mathrm{Pr}\left[T^{\mathrm{valid}}=t_i^{\mathrm{valid}}\right]\end{array}& \end{array}$

(77) Any realization of a secret codebook is modeled as equiprobable. By treating the set of valid tags as random, and conditioning on H.sub.1 being true, the following is noted:

(78) $Z_{1}N\left(L{}_t^2,{}_{\tilde{w}}^2\right)$$Z_{i\left(>1\right)}N\left(0,\frac{L}{2}{}_t^4+{}_{\tilde{w}}^2\right).$
This follows using the same analysis as presented in Section 2.5.1.

(79) {Z.sub.1, . . . , Z.sub.N.sub.k} are independent because they are based on independent tags.

(80) .sub.1|H.sub.0=.sub.1,0 is always a constant.

(81) 0${}_1|H_{j\left(>1\right)}N\left({}^{-1}\left(1-\right){}_{\tilde{w}},\frac{L}{2}{}_t^4\right).$
This follows by applying the Central Limit Theorem to the last term of equation 17

(82) {.sub.1|H.sub.j(=0, 1, . . . , N.sub.k.sub.)} are independent.

(83) {Z.sub.1, . . . , Z.sub.Nk} are independent because they are based on independent tags.

(84) .sub.1|H.sub.0=.sub.1,0 is always a constant.

(85) .sub.1|Hj(>1)N (.sup.1(1).sub.w{circumflex over ()}, .sup.L.sup.4). This follows by applying the Central Limit Theorem to

(86) The acceptance threshold for Z.sub.1 is .sub.1. Writing out (18) gives
.sub.1=max{.sub.1|H.sub.0,.sub.1|H.sub.2, . . . ,.sub.1|H.sub.N.sub.k}(eq. 21)

(87) (21) From the above properties of the conditional thresholds, it follows that the density of .sub.1 is:

(88) $\begin{array}{cc}{f}_{{}_1}\left(t\right)=\{\begin{array}{cc}\left(N_k-1\right)f_{{}_i|H_2}\left(t\right)Pr\left({}_1|H_2\right)<t^{N_k-2}& t>{}_{1,0}\\ {}_{-}^{{}_{1,0}}\left(N_k-1\right)f_{{}_i|H_2}\left(t\right)Pr\left({}_1|H_2\right)<t^{N_k-2}dt& t={}_{1,0}\\ 0& t<{}_{1,0}\end{array}& \left(\mathrm{eq}.22\right)\end{array}$

(89) Note that because of the null hypothesis, the .sub.1 cannot takes values below .sub.1,0.

(90) Note that because of the null hypothesis, the .sub.1 cannot takes values below .sub.1,0. The overall probability of authentication (cf. (19)) can now be calculated:

(91) $\begin{array}{cc}\begin{array}{c}\mathrm{Pr}\left[\mathrm{Decide}{H}_1|H_1\right]={\mathrm{��}}_{T^{\mathrm{valid}}}[\mathrm{Pr}[Z_1\left(R|H_1\right)>\\ Z_2\left(R|H_1\right),\mathrm{.Math.},Z_1\left(R|H_1\right)>\\ {}_1|T^{\mathrm{valid}}]]\\ ={}_{{}_{1,0}}^{}\mathrm{Pr}[Z_2\left(R|H_1\right)<\\ {z|T^{\mathrm{valid}}]}^{N_k-1}{F}_{{}_1}\left(z\right)p_{z_1\left(R|H_1,T^{\mathrm{valid}}\right)}\\ \left(z\right)dz\\ ={}_{{}_{1,0}}^{}{}^{N_k-1}\left(\frac{z}{\sqrt{\frac{L}{2}{}_t^4+{}_{\tilde{w}}^2}}\right)\\ \left(\frac{z-L{}_t^2}{{}_{\tilde{w}}}\right)F_{{}_1}\left(z\right)dz.\end{array}& \left(\mathrm{eq}.23\right)\left(\mathrm{eq}.24\right)\end{array}$

(92) Referring to FIG. 2, we see increasing the side channel rate, which requires an increase in key set size, requires a larger SNR to achieve the same performance. A linear codebook of equal size performs identically.

(93) 3.3 Simulation Results

(94) Monte Carlo simulations verify the mathematical analysis and depict the performance trade-offs of the proposed authentication scheme. We first present a scenario in which all primary messages are assumed to be decoded without error so that the secret codebook is reconstructed properly by the receiver. We then show the effect that message errors have on the authentication and side-channel performance. In this case, we allow error correction capabilities to better depict real world conditions. For all simulations, the message and tag symbols are chosen from a normalized 16QAM constellation and the side-channel communications false alarm rate is set to =10.sup.4. We vary the codebook size to show the trade-offs between rate and performance. The linear coding scheme achieves the same performance as a partitioned codebook of equal size as explained in Section 2.3, so we do not provide results for both codebook schemes since they are easily compared. For example, a linear code with N.sub.k=4 and a partitioned codebook with N.sub.k=16 will both have 16 pairwise independent codewords and thus will have the same side-channel performance, but will have differing effects on security which will be presented in Section 4.t

(95) FIG. 2 depicts the probability of successfully authenticating and decoding the secondary message when an error-free primary message is observed and a partitioned codebook is used. We use L=1024, 16QAM message and tag modulation, p.sup.2=0.001, and =10.sup.4. The master key k has =4096 bits and is partitioned in N.sub.k smaller keys. The decoding and authentication performance is determined by the codebook size, or number of keys; three cases are shown with N.sub.k=16, 64, 512 (N.sub.k=4, 6, 9 for a linear codebook). Notice that each smaller key will be larger when using the linear codebook scheme rather than the partitioned codebook scheme since fewer N.sub.k partitions are required to achieve the same rate and performance. The advantage of having larger keys will be further explored in Section 4. Increasing the rate of the side-channel requires more codewords, which requires more key choices, which then requires a better SNR to achieve the same performance. The plots show that the theoretical performance of (23) agree with the simulations.

(96) We now take message errors into account and simulate an error-correcting code in which messages with less than 10 bit errors per 512 bit block are perfectly recovered. The difference in performance is due to the receiver's inaccurate recreation of the codebook when incorrect messages are obtained. Due to the nature of hash functions, even a single bit error in the primary message will cause the receiver to construct a completely random and independent codebook. The authentication and side-channel performance with message errors is shown in FIG. 3. The performance changes as expected and all three cases with varying N.sub.k are clustered closer together due to complete codebook reconstruction failure when the primary message error correction code fails, which in this case requires 10 or more bit errors.

(97) Packet success rate (PSR), or the percentage of correctly received primary messages, is the limiting factor. The simulation parameters remain unchanged from the plots in FIG. 2 in which packets at the SNR required to perfectly recover the primary message are authenticated with high probability. Thus, the performance mirrors the PSR. FIG. 4 illustrates how the PSR upper bounds the performance in the case of message error correction. The side-channel success rate does not exceed the PSR for any N.sub.k.

(98) Referring to FIG. 3 we note side-channel performance with and without primary message error correction decoding

(99) Secrecy Analysis

(100) We now turn our attention to the secrecy of the system. We use the information-theoretic concept of equivocation to quantify the secrecy of the legitimate parties' key. We assume that the adversary does not know the shared key but has unlimited computational power and complete knowledge of the entire fingerprint embedding authentication process.

(101) Equivocation, or conditional entropy, is an information-theoretic metric that quantifies the amount of information one variable reveals about another [4]. The way in which equivocation of the secret key decreases as the adversary observes legitimate transmissions is considered. Entropy denoted H(X), is the amount of information contained in a realization of a random variable. Given the channel between the transmitted and adversary, the adversary's key equivocation can be calculated. This allows them to track the risk of key compromise and to refresh their key accordingly. For example, replacing.sup.2 k with another random K bit sequence will reset the adversary's key equivocation to .

(102) The adversary's key equivocation given an observation Z is

(103) $\begin{array}{cc}H\left(k|y,\right)=\underset{s\mathrm{��},t\mathrm{��}}{.Math.}p\left(s,t\right)H\left(k|s,t\right).& \left(\mathrm{eq}.25\right)\end{array}$

(104) The key equivocation is upper bounded by the entropy of the key, bits in this case, and can decrease with more observations. Conceptually, key equivocation arises when more than one key can produce the observed message/tag pairs. If the message and tag pair are observed without noise, nonzero key equivocation is unlikely to occur due to collision resistance in hash functions. The situation, however, is made more complicated when the tag is observed with noise (Section 4.1) and when multiple keys are used resulting in enhanced security for the legitimate parties (Section 4.2). Now referring to FIG. 4. the side-channel performance follows the packet success rate of the primary channel because of error-free primary messages are required for the receiver to accurately reconstruct the codebook.

(105) 4.1 Single Key Scheme

(106) We assume that the adversary is able to recover the message s without error from Z. The transmitter transmits the associated tag at low power so that the adversary makes the noisy estimate t{circumflex over ()}, just as the receiver does (see (7)). Suppose that the transmitter uses the same key and transmits n authenticated messages. The adversary then obtains the pairs (s.sup.i, t{circumflex over ()}.sup.i) for i=1, . . . , N.

(107) The adversary can create a super-tag estimate through concatenation:
{circumflex over (t)}={circumflex over (t)}.sup.1|{circumflex over (t)}.sup.2| . . . |{circumflex over (t)}.sup.N.(26)

(108) 2A challenge is communicating the new keys to both parties while keeping it hidden from the adversary. Using the side-channel for key updates may be an interesting topic of future research.

(109) With no penalty for computational complexity, they can create a noiseless super-tag for the observed messages
t.sub.j=t.sup.1|t.sup.2| . . . |t.sup.N=g(s.sup.1,k.sub.j)|g(s.sup.2,k.sub.j)| . . . |g(s.sup.N,k.sub.j).(27)

(110) for each possible key in k.sub.jK. The adversary can determine the set of most likely keys by comparing t with each t.sub.j using a metric such as Hamming distance.

(111) Using this approach, the adversary's single key equivocation after N observations can be approximated as [5],

(112) $\begin{array}{cc}H\left(k|Y^n;\right)\frac{.Math.\mathrm{��}.Math.}{{.Math.\mathrm{��}.Math.}^N}\underset{i=0}{\overset{N{\log }_2.Math.\mathrm{��}.Math.}{.Math.}}\left(\begin{array}{c}N{\log }_2.Math.\mathrm{��}.Math.\\ i\end{array}\right)H\left(\frac{{.Math.\mathrm{��}.Math.}^N}{.Math.\mathrm{��}.Math.}{p_e^i\left(1-p_e\right)}^{N{\log }_2\left|\mathrm{��}\right|-i}\right).& \left(\mathrm{eq}.28\right)\end{array}$

(113) where p.sub.e is the iid tag bit error probability and ={|T|, |K|, p.sub.e} are system parameters. Note that p.sub.e is generally high for the adversary, because by design the tag is inserted by the transmitter with low power resulting in a noisy tag estimate for the adversary. H(k|Y.sup.n; ) decreases linearly with N since each observation contributes the same expected amount of information.

(114) The adversary's impersonation attack success probability is lower bounded by P.sub.1min{, 2.sup.H(k|Y.sup.n.sup.;)} since they can always randomly select a key from her search space. If the legitimate users can perform a key update whenever 2.sup.H(k|Y.sup.n.sup.;) exceeds , then the adversary will theoretically not gain sufficient information to impersonate at a probability higher than using a randomly chosen tag.

(115) 4.2 Multiple Key Scheme

(116) We now consider the case where multiple keys are used for the side-channel communications as described in Section 2.3. The adversary can impersonate the legitimate transmitter upon obtaining any key from the valid set of keys Kvalid, defined in Section 2.1. However, the transmitter's use of multiple keys complicates the adversary's key inference. Previously in Section 4.1, the adversary always attributed their observations to the same, albeit unknown, key. With multiple keys being possible, the adversary must be able to attribute each observation to the correct key.

(117) In the following, we make a worst case assumption that the adversary can always attribute each observation to the valid key. Assuming that the transmitter chooses the keys uniformly at random, the adversary waits N.sub.k observations on average to infer knowledge about any particular key. Thus, the key equivocation of one key from the set of N.sub.k keys is,

(118) $\begin{array}{cc}H\left(k|Y^n;\right)\frac{.Math.\mathrm{��}.Math.}{{.Math.\mathrm{��}.Math.}^{\frac{N}{N_k}}}\underset{i=0}{\overset{\frac{N}{N_k}{\log }_2.Math.\mathrm{��}.Math.}{.Math.}}\left(\begin{array}{c}\frac{N}{N_k}{\log }_2.Math.\mathrm{��}.Math.\\ i\end{array}\right)H\left(\frac{{.Math.\mathrm{��}.Math.}^{\frac{N}{N_k}}}{.Math.\mathrm{��}.Math.}{p_e^i\left(1-p_e\right)}^{\frac{N}{N_k}{\log }_2.Math.\mathrm{��}.Math.-i}\right),& \left(\mathrm{eq}.29\right)\end{array}$

(119) which can be further simplified when each tag's bit error probability is iid, since the amount of information contributed by each bit of the tag would be the same. The simplification results in the following key equivocation formula,

(120) $\begin{array}{cc}H\left(k|Y^n;\right){\log }_2.Math.\mathrm{��}.Math.-\frac{n}{N_k}{\log }_2.Math.\mathrm{��}.Math.\left(1-\left(p_e\right)\right),& \left(\mathrm{eq}.30\right)\end{array}$

(121) where H(p)=p log 2 (p)(1p)log 2 (1p) is the binary entropy function. FIG. 5 shows that increasing N.sub.k requires the adversary to make more observations to infer the same amount of information about a key in .sup.valid. Since the adversary gathers information about independent key partitions, it will take more observations for 2.sup.H(k+Y.sup.n.sup.;) to exceed a for one of the keys.

(122) The same increase in key equivocation depicted in FIG. 5 can be achieved with a single key whose length is equal to the combined length of all N.sub.k keys. Each observed tag contributes the same amount of information about the group of keys. The main secrecy benefits of the multi-key scheme arise from computational security since the adversary's message-key attribution problem adds combinatorial complexity. Equation (30) gives a worst case scenario for the legitimate users when the adversary uses the above scheme assuming perfect key attribution. It is important to note that the main motivation for the multi-key scheme is to add a covert side-channel rather than add additional security, although it also adds computational complexity for the adversary. Referring to FIG. 5 we see the key equivocation decreases linearly with each of the adversary's observations. The equivocation for keys from larger key sets decreases much more slowly because it takes more observations for any specific key/tag to be repeated. The overall information being leaked is equivalent however.

(123) 4.3 Linear Codebook Scheme

(124) We now analyze the security of the secret linear codebook construction. For codebooks of equal size, the linear scheme requires fewer partitions of the master key k compared to the partition scheme. In this case, the adversary must obtain more secret bits in order to launch a successful impersonation attack since each key in Kvalid will be larger. If the linear combinations were performed at the key level rather than at the tag level, the adversary would be able to generate a valid tag by determining the linear combination that produced a tag and not the specific keys. Linearly combining at the tag level ensures that they must derive the exact keys used to produce an observed tag. The adversary's key inference complexity is greatly increased since they must attribute each observed tag to 2.sup.Nk possible key combinations instead of just N.sub.k.

(125) TABLE-US-00003 Secondary Key Attack Scheme Message Rate Usage Rate Resence Single Key (N.sub. = 1) 0 Partitioned (N.sub. 2) log.sub.2 (N.sub.) /N.sub. /N.sub. Linear (N.sub. 2) log.sub.2 (2.sup.N 1) /2 (Avg.) /N.sub. log.sub.2 (N.sub.) 1 /2 (Avg.) /log.sub.2 (N.sub.)

(126) Table 1: Secrecy and Rate Trade-Offs for 3 Key Usage Schemes

(127) (Schemes for using bits of secret key. Resilience is the amount of secret key that can be leaked before impersonation attacks are guaranteed to succeed. Detailed explanation of trade-offs presented in Section 4.4.)

(128) 4.4 Security and Side-Channel Rate Trade-Offs

(129) TABLE-US-00004 TABLE 1 Secrecy and Rate Trade-Offs For 3 Key Usage Schemes Secondary Key Attack Scheme Message Rate Usage Rate Resilence Single Key (N.sub. = 1) 0 Partitioned (N.sub. 2) log.sub.2 (N.sub.) /N.sub. /N.sub. Linear (N.sub. 2) log.sub.2 (2.sup.N 1) /2 (Avg.) /N.sub. log.sub.2 (N.sub.) 1 /2 (Avg.) /log.sub.2 (N.sub.)

(130) As the transmitter increases their tag power, they simultaneously increase the receiver's authentication and side-channel decoding success probability while undesirably leaking more key information to the adversary. This trade-off between side-channel success and the amount of information leak-age is depicted in FIG. 6 which plots (23) versus (29) over an SNR range of 4 to 14 dB for varying N.sub.k. We again use L=1024, 16QAM message and tag modulation, p.sup.2=0.001, and =10.sup.4. Since increasing the side-channel rate requires a higher tag power, more information is revealed through the tag for a given success probability. The method of generating authentication tags also impacts the trade-offs between side-channel rate and impersonation resistance. Table 1 details the major security and communication rate trade-offs of three explicit constructions using the fingerprint embedding framework.

(131) For N.sub.k=1, an adversary must obtain all K bits to guarantee success in an impersonation attack. This provides the legitimate users with the best protection, but restricts communication and requires the use of all of their secret information for each transmission. For N.sub.k2 without the linear coding, the adversary requires less secret information to attack, but now the transmitter can communicate log 2 N.sub.k bits of information using only /N.sub.k bits of the total secret key for each transmission. For N.sub.k2 with the linear coding, the adversary requires the same amount of information, but now log 2 2.sup.Nk1 bits can be communicated using on average /2 bits of the secret, assuming the secondary messages are chosen uniformly and randomly. This comes at the cost of degraded side-channel performance since the codebook size increases, although for low rate side-channel communications this impact may be negligible. Alternatively, the transmitter can achieve the same side-channel rate by constructing a linear code using fewer, but larger, partitions of the master key and thus obtaining better protection against impersonation attacks since the adversary will require more observations. The linear codebook scheme, however, uses, on average, more bits of the secret key k for each transmission than the partitioned codebook scheme.

(132) 5 Privacy Analysis

(133) Referring to FIG. 6 we note that more information is revealed about the key as the receiver's performance improves by increasing the side-channel SNR, i.e, allocating proportionality more power to tag. Now consider the scenario in which the adversary must make a decision whether a captured trans-mission from the transmitter contains an authenticating tag or not. By controlling the tag power, the legitimate users can force the adversary into a regime in which they cannot reliably detect the embedded tags which further confounds their ability to infer key information. The existence of an SNR wall can aid the legitimate users in concealing their superimposed authentication tags [6]. In this section, we consider the impact of an SNR wall on authentication, relate our framework to the assumptions of [6], and consider different operating regimes in the fingerprint embedding scheme.

(134) 5.1 Limits of a Radiometer Detector

(135) We assume the adversary knows the complete authentication scheme, including the tag power, but not the secret key. Since only one tag is sent with each transmission, the adversary's detection problem will be the same for both the single and multiple key cases. In either scenario, the transmitter wishes to determine the tag power, p.sub.t, and length, L, such that the receiver authenticates with high probability while the adversary detects the presence of the tag with arbitrarily low probability. The receiver and the adversary both face a detection problem. While the adversary is only differentiating between signal-plus-noise and noise (where we assume the adversary knows the digital constellations employed), the receiver must decide between N.sub.k+1 hypotheses. However, since the receiver has knowledge of the expected secret codebook, they can gain an advantage over the adversary.

(136) The advantage can be seen when considering a phenomenon, introduced in [6], known as an SNR wall. Detectors operating in an SNR regime below the SNR wall threshold will not be able to robustly detect the signal. This arises when a radiometer detector is used and there is uncertainty in the observed noise power. In this case, robustness is defined as the ability to achieve desired error performance for all possible noise powers in an uncertainty region.

(137) If the adversary's noise uncertainty lies in a range,

(138) ${}_e^2\left[\frac{1}{p}{}^2,{}^2\right]$
where .sup.2 is the nominal noise power, and they use a radiometer for detection, then an SNR wall exists and is given by

(139) $\begin{array}{cc}{\mathrm{SNR}}_{\mathrm{wall}}=\frac{{}^2-1}{}.& \left(\mathrm{eq}.31\right)\end{array}$

(140) Notice that the location of the wall is independent of the number of samples that the adversary observes. Further, the SNR wall is not applicable to the receiver, who uses a matched filter rather than a radiometer. If they know , the transmitter can choose a tag power allocation p.sup.2 to force the adversary's observations to be below the SNR wall using (31) assuming they also know the adversary's channel, or has knowledge of their channel statistics (see Section 5.2). Then, since sample length is independent of the wall, they can increase the tag length until the total tag energy is high enough to produce desired results in the receiver's matched filter test.

(141) FIG. 7 depicts an example of the number of tag symbols required to achieve desired authentication performance in the single key scheme while forcing The adversary to operate below the SNR wall for different side-channel success probabilities. The transmitter sets their tag power using (31), so that

(142) $\begin{array}{cc}{p}_t^2\frac{{}^2-1}{}{}_e^2.& \left(\mathrm{eq}.32\right)\end{array}$

(143) Then, for a given desired side-channel success probability of P.sub.A and false alarm, , the transmitter chooses a tag length, L, by solving [7, Equation 14] for L with the SNR set to the appropriate SNR.sub.wall to get

(144) 0$\begin{array}{cc}L={\left[\begin{array}{c}{}^{-1}\left(1-\right)\sqrt{\frac{1}{2}+\frac{1}{2}{\mathrm{SNR}}_{\mathrm{wall}}^{-1}}-\\ {}^{-1}\left(1-P_A\right)\sqrt{\frac{1}{2}{\mathrm{SNR}}_{\mathrm{wall}}^{-1}}\end{array}\right]}^2,& \left(\mathrm{eq}.33\right)\end{array}$

(145) for the single key case and by solving (23) for L in the multi-key case. The required tag length increases as PA increases and as the adversary's uncertainty, , decreases.

(146) 5.2 Estimating the Adversary's SNR Wall

(147) The theoretical analysis raises the question of how to obtain p, the parameter that characterizes the adversary's noise uncertainty, so that the transmitter can set their tag power and length accordingly. Without knowing p, the transmitter will be unable to compute the adversary's SNR wall and the required tag power to achieve desired performance. It is possible for the uncertainty to be lower bounded by taking note of the measurement inaccuracies in estimating the thermal noise variance in a receiver and propagation constants to obtain a lower bound for the adversary's SNR wall [8]. Using the bound, the transmitter can obtain a conservative estimate of the uncertainty and can design their system accordingly.

(148) Suppose that the transmitter wishes to estimate the adversary's SNR wall under a given prior on the fading coefficient of their channel. In this case, we consider a fading environment where the adversary's observation (6) now takes on the form
Z=Hx+W.sub.e.(eq. 34)

(149) For simplicity, we will assume a Rayleigh block-independent fading model in which each message will experience an independent zero-mean Gaussian distributed fade, h, with variance .sup.2. Now, the average SNR of the adversary's received tag will be .sup..sub.h=p.sup.2.sup.2/.sup.2. Therefore, the SNR for each message will be exponentially distributed as

(150) $\begin{array}{cc}P{}_h\left(x\right)=\left(\frac{1}{{\stackrel{}{}}_h}\right)e^{-x/{\stackrel{}{}}_h}.& \left(\mathrm{eq}.35\right)\end{array}$

(151) Given the distribution and its parameter .sup..sub.h, the tag power required to force the adversary's SNR to be below the SNR wall with a desired probability, , is

(152) $\begin{array}{cc}{p}_t^2-\frac{{}_e^2}{{}_h^2\ln \left(1-\right)}\left(\frac{{}^2-1}{}\right).& \left(\mathrm{eq}.36\right)\end{array}$

(153) 5.3 Optimal Detector with No Noise Uncertainty

(154) The radiometer detector and noise uncertainty provide an achievable operating point to limit the adversary's detection capabilities. When the restrictions are removed, however, and the adversary has the ability to design an optimal test with no noise uncertainty, theoretical guarantees of undetectable authentication are difficult to attain. An approach in [9] uses the total variation distance and Kullback-Leibler divergence to lower bound the sum of error probabilities for the optimal detector and states that covert communication with low probability of detection is possible. The rate of communications, however, approaches 0 as the message length tends towards infinity. In finite cases, it is stated that O(n) bits can be sent in n channel uses while limiting the sum of the type I and II errors of the adversary's detector to +1E for any arbitrary E where and are the type I and II errors of the detector, respectively.

(155) Using this analysis, the required tag power to achieve an E that satisfies +1E is

(156) $\begin{array}{cc}{p}_t^{2}2{}_e^2\sqrt{\frac{2}{n}}.& \left(\mathrm{eq}.37\right)\end{array}$

(157) Unlike with SNR walls, the result relies on the length of the transmitted message and, in practical scenarios we have considered, generally produces a tag power that is too low for successful authentication.

(158) Finally, this invention, an extension of the fingerprint embedding authentication scheme was presented and analyzed. By partitioning a shared key, two legitimate parties create a secret codebook that is used to both authenticate their communications and communicate additional side-channel information at minimal cost. The secret codebook construction schemes, most notably our novel secret linear code, allow the legitimate users to control the trade-offs in side-channel rate and secrecy. In particular, we applied the key equivocation metric to measure key information leakage to an eavesdropper over time, and we also showed how an SNR wall can be utilized to attain a degree of stealth when noise uncertainty is present in the eavesdroppers detector. The described trade-offs and analysis of authentication performance, side-channel rate, secrecy, and privacy provide users with the ability to design their system according to their system specifications and needs.

(159) The foregoing description of the specific embodiments will so fully reveal the general nature of the embodiments herein that others can, by applying current knowledge, readily modify and/or adapt for various applications such specific embodiments without departing from the generic concept, and, therefore, such adaptations and modifications should and are intended to be comprehended within the meaning and range of equivalents of the disclosed embodiments. It is to be understood that the phraseology or terminology employed herein is for the purpose of description and not of limitation. Therefore, while the embodiments herein have been described in terms of preferred embodiments, those skilled in the art will recognize that the embodiments herein can be practiced with modification within the spirit and scope of the appended claims.