Not really TAI64N

Not really TAI64N

[Vlad Krasnov]

The WireGuard spec states that a timestamp used is TAI64N, however the wireguard-go implementation produces an invalid timestamp, because the Go function now.UnixNano() returns the total number of nanoseconds from epoch and truncated to 32bit, whereas TAI64N requires it to be in the range [0, 999999999].

Moreover the kernel implementation does not check if a timestamp is valid TAI64N at all, it simply checks that this is a monotonically increasing, 12 byte long, big endian number.

While this is probably not insecure, it goes against what is stated in the whitepaper.

Also, the function used for comparison is memcmp, non-constant time function, that shouldn’t be used in cryptographic context.

Cheers,
Vlad
_______________________________________________
WireGuard mailing list
WireGuard@lists.zx2c4.com
https://lists.zx2c4.com/mailman/listinfo/wireguard

Re: Not really TAI64N

[Jason A. Donenfeld]

Hi Vlad,

On Thu, Nov 8, 2018 at 3:54 AM Vlad Krasnov <vlad@cloudflare.com> wrote:
> The WireGuard spec states that a timestamp used is TAI64N, however the wireguard-go implementation produces an invalid timestamp, because the Go function now.UnixNano() returns the total number of nanoseconds from epoch and truncated to 32bit, whereas TAI64N requires it to be in the range [0, 999999999].

Good catch, thanks. Fixed here:
https://git.zx2c4.com/wireguard-go/commit/?id=4fd55daafe64f6101dde5c0a8a6887fef0ff0545

> Moreover the kernel implementation does not check if a timestamp is valid TAI64N at all, it simply checks that this is a monotonically increasing, 12 byte long, big endian number.
>
> While this is probably not insecure, it goes against what is stated in the whitepaper.

That's right, and by intention. The whitepaper *does* mention that:

"To prevent this, a 12-byte TAI64N [7] timestamp is included,
encrypted and authenticated, in the first message. The responder keeps
track of the greatest timestamp received per peer and discards packets
containing timestamps less than or equal to it. (In fact, it does not
even have to be an accurate timestamp; it simply must be a per-peer
monotonically increasing 96-bit number.)"

> Also, the function used for comparison is memcmp, non-constant time function, that shouldn’t be used in cryptographic context.

This is also mentioned in the whitepaper:

"From an implementation point of view, TAI64N [7] is very convenient
because it is big-endian, allowing comparisons between two 12-byte
timestamps to be done using standard memcmp()."

I realize of course this is vulnerable to timing inference, but I
disagree that this is a "cryptographic context" akin to the ordinary
situation where timing attacks are against secrets like hash results
or private keys. I had considered implementing this as a constant time
function, but I had a hard time coming up with scenarios in which:

- an attack would be possible; and
- it would gain the attacker a particularly useful piece of information.

You could argue that an attacker who has stolen a victim's private key
and has access to enough timing information on _other_ things
happening on the CPU (but not from any timing of a related response,
since there isn't one for handshakes with old timestamps) might be
able to construct packets to guess word-by-word the last time the
victim completed a handshake. But on the other hand, couldn't that
attacker instead just keep incrementing the counter second by second
until he does receive a response? This sounds far easier and doesn't
require timing inferences. Another attack might be that an attacker
who hasn't stolen a private key gets a hold of an old handshake
message. Then by somehow having timing information to _other_ things
happening on the CPU (but not through timing of any related response),
he gains some information about the timestamp ciphertext, perhaps by
virtue of already knowing through various means what the _current_
latest handshake is. But I'm not sure this is actually feasible and in
which circumstances that would actually crop up as a useful attack or
why an attacker would in the first place have limited information like
that.

I'm all ears if you can think of a clever situation that justifies
doing the comparison differently. I just haven't found one and neither
has anyone I've neurotically conversed with about this very issue. But
that doesn't mean it doesn't exist: perhaps you have something
specific in mind?

Regards,
Jason
_______________________________________________
WireGuard mailing list
WireGuard@lists.zx2c4.com
https://lists.zx2c4.com/mailman/listinfo/wireguard

Re: Not really TAI64N

[Vlad Krasnov]

> 
> That's right, and by intention. The whitepaper *does* mention that:
> 
> "To prevent this, a 12-byte TAI64N [7] timestamp is included,
> encrypted and authenticated, in the first message. The responder keeps
> track of the greatest timestamp received per peer and discards packets
> containing timestamps less than or equal to it. (In fact, it does not
> even have to be an accurate timestamp; it simply must be a per-peer
> monotonically increasing 96-bit number.)”
> 

Yes, I saw that in the paper, and having a monotonic 96-bit counter is perfectly fine. I guess the wording is not clear, and the codebase calls it TAI64N, which is confusing.

I only raised the issue because the name implies one thing, and the implementation does some other thing.

So calling tai64n.After implies you compare two valid tai64n timestamps, and not just two large big endian numbers.


>> Also, the function used for comparison is memcmp, non-constant time function, that shouldn’t be used in cryptographic context.
> 
> This is also mentioned in the whitepaper:
> 
> "From an implementation point of view, TAI64N [7] is very convenient
> because it is big-endian, allowing comparisons between two 12-byte
> timestamps to be done using standard memcmp().”
> 

Yes, it makes a lot of sense, and memcmp will rightfully distinguish two valid tai64 timestamps today.

But in theory values larger than 2^63 are reserved for possible future use, and then this assertion might become invalid.


> I realize of course this is vulnerable to timing inference, but I
> disagree that this is a "cryptographic context" akin to the ordinary
> situation where timing attacks are against secrets like hash results
> or private keys. I had considered implementing this as a constant time
> function, but I had a hard time coming up with scenarios in which:
> 
> - an attack would be possible; and
> - it would gain the attacker a particularly useful piece of information.

I can’t think of any too, but there is no real cost to it, in fact it would probably be faster than calling memcmp, so why not do it in constant time?

> 
> You could argue that an attacker who has stolen a victim's private key
> and has access to enough timing information on _other_ things
> happening on the CPU (but not from any timing of a related response,
> since there isn't one for handshakes with old timestamps) might be
> able to construct packets to guess word-by-word the last time the
> victim completed a handshake. But on the other hand, couldn't that
> attacker instead just keep incrementing the counter second by second
> until he does receive a response? This sounds far easier and doesn't
> require timing inferences. Another attack might be that an attacker
> who hasn't stolen a private key gets a hold of an old handshake
> message. Then by somehow having timing information to _other_ things
> happening on the CPU (but not through timing of any related response),
> he gains some information about the timestamp ciphertext, perhaps by
> virtue of already knowing through various means what the _current_
> latest handshake is. But I'm not sure this is actually feasible and in
> which circumstances that would actually crop up as a useful attack or
> why an attacker would in the first place have limited information like
> that.
> 
> I'm all ears if you can think of a clever situation that justifies
> doing the comparison differently. I just haven't found one and neither
> has anyone I've neurotically conversed with about this very issue. But
> that doesn't mean it doesn't exist: perhaps you have something
> specific in mind?
> 
> Regards,
> Jason

_______________________________________________
WireGuard mailing list
WireGuard@lists.zx2c4.com
https://lists.zx2c4.com/mailman/listinfo/wireguard