Calculate delay difference

[weber-tsao]

Hello, after reading Appendix A in https://eprint.iacr.org/2021/555.pdf, I am wondering can you explain Theorem 1 to me with some examples? I am still confused after reading it

Some specific questions:

1. For pypuf, how is the delay difference calculated using Theorem 1? In the below image, you mentioned that we can get TT1 as a solution of an equation system, how is it done? And how is does Theorem 1 help pypuf to calculate the delay difference? ### Is it possible that you can give me an example?
   

2. The TT1 is precalculated when the puf is created in the in pypuf, is that correct? Otherwise, how does puf.val calculate delay difference when I only input one challenge while the TT1 in question 1 need more challenge to be derived? or is the pypuf not using the idea as the above image

3. I am also curious if the pypuf is not explicitly computed delay values, but compute weights. What does the weight relate to the actual physical delays? I think that is something to do with Theorem 1 as well

4. I also want to check that the challenge bit is the only thing we need to calculate the delay difference in pypuf and Theorem 1, is that correct?

5. Just to make sure, I think the pypuf is not using any real value of delay difference number to calculate the delay difference, is that correct?

Thank you for your help, I think I will have more questions on delay difference for pypuf

Also, I got a error when using XORFeedforwardpuf, do you have any idea on how to solve this?

[nils-wisiol]

1. pypuf computes the delay difference of the Arbiter PUF using weights instead of delays. Theorem 1 shows that this gives the same results as using delays, and hence using weights can also be called "using the additive delay model". The reason for using weights is that there are less parameters and performance is better. For an example, set n=2 or n=3 or n=4 and choose some easy values for TT1, TT2, ..., such as 1, 2, 3, and compute the equations given in Theorem 1.
2. TT1 isn't directly used in pypuf. Instead, weights are used. How the used weights relate to TT1 is covered by Theorem 1.
3. If you randomly choose 4n delays, let's say by creating a PUF circuit, then you can compute n+1 weights from these delays. With the n+1 weights, you can compute the additive delay model just like you can with the 4n delays, but faster.
4. To compute the delay difference, you need either the 4n delays and the challenge, or the n+1 weights and the challenge. In pypuf's ArbiterPUF and XORArbiterPUF, the weights are chosen randomly, the challenge is given by the user.
5. pypuf is using real numbers as weights ("real numbers" as in ℝ). If you're looking for values based on physical measurements, check out the datasets that are shipped with pypuf.

For your XORFeedForwardPUF, it seems that you are trying to have a feed-forward loop that feeds into the first stage of the PUF. Try using values larger than 0 instead.

[weber-tsao]

Thank you for the feedback. I learned a lot. But I still have 3 problems: (Most of them are about real-world puf's delay difference which is my biggest confusion currently)

1. From the above, my understanding is that in pypuf, the delay is randomly chosen when puf is created. After that, because we have challenge bits, and we know the delay, we can easily compute delay difference, is that correct?

2. If we consider a real-world PUF, we can not derive or gain the value of its delay difference, since we cannot get 4n delay like in pypuf. Am I right? Or there is a way to somehow get delay difference or similar thing on real-world puf?

3. From the previous email you sent me:
   
   Does that mean I can use it on the real-world puf? So I construct the equation like the above image, and provide enough challenge to get the TT1, TT2....... EX:
   DD([1,1]) = (TT1+TT2)-(BB1+BB2)
   DD([1,0]) = (TT1+TB2)-(BB1+BT2)
   DD([0,1]) = (TB1+BB2)-(BT1+TT2)
   DD([0,0]) = (TB1+BT2)-(BT1+TB2)

,then I can compute the delay difference, is this possible?

[nils-wisiol]

1. That's correct. The delay chosen by pypuf follow the distribution that was also seen in real-world by DV13.
2. If you can measure the delay difference at the output of the PUF, you can derive the 4n delays or the n+1 weights by solving a system of linear equations. If you can't measure the delay difference directly, you can measure the reliability instead. (Again, DV13).
3. Yes, with Theorem 1 you can convert from weights to delays and vice versa. But I'm not sure how this connects to a real-world PUF. (But see answer to question 2.)

[weber-tsao]

Thank you for your answer. For question 3, what I mean is can we get the delay difference in the real world and how hard is it to get the delay. Do you think it is hard to obtain in the real world, or it is possible and the details are in DV13?

[nils-wisiol]

The details are in DV13. The gist is, you query the PUF m times on the same challenge. Likely, it will not always return the same response. Depending on the stability of the response, you can estimate the delay difference that was produced by this challenge. The higher m, the better your estimate will be.

Details of this attack and how it can be done using pypuf are described in the docs, as I've told you in my earlier reply to #178.

[weber-tsao]

Thank you. After looking at the paper, I think it is possible to estimate delay difference for a real-world puf by stability when we can't measure the delay difference directly. However, the estimated delay difference is not 100% correct. Do you agree with that estimating real world puf is possible?

[nils-wisiol]

Yes, it is possible, as described in DV13, in the docs to pypuf, and in my comment above. The accuracy of the computed delay goes up with the number of measurements m, as written above. If you're looking for the internal parameters, you can solve the equation system as described in DV13 and the pypuf docs with least squares, so that the inaccuracy of the measurements doesn't matter.

[weber-tsao]

Thank you for the detailed explanation