private-attribution / ipa

A raw implementation of Interoperable Private Attribution
MIT License
41 stars 23 forks source link

Enforce index uniqueness inside the Generator struct #1185

Closed akoshelev closed 2 months ago

akoshelev commented 3 months ago

This is the first step to allow PRSS to generate only one part of randomness, shared with one helper. The motivating issue is #1029. To support that, we need to enforce uniqueness checks at the lower layer because each generator now can be called at different times.

This change moves the used variable to Generator struct. This required some rethinking of generate method parameter types - instead of raw u128, it now takes PrssIndexu128. Mainly for debugging purposes, to be able to print "index:offset" when a duplicate index is used.

codecov[bot] commented 3 months ago

Codecov Report

Attention: Patch coverage is 93.63636% with 7 lines in your changes missing coverage. Please review.

Project coverage is 92.07%. Comparing base (5f59526) to head (bec905f). Report is 7 commits behind head on main.

Files Patch % Lines
ipa-core/src/protocol/prss/mod.rs 91.78% 6 Missing :warning:
ipa-core/src/protocol/prss/crypto.rs 97.29% 1 Missing :warning:
Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #1185 +/- ## ========================================== + Coverage 92.04% 92.07% +0.02% ========================================== Files 196 196 Lines 29241 29318 +77 ========================================== + Hits 26916 26995 +79 + Misses 2325 2323 -2 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

akoshelev commented 2 months ago

the block limit for sequential generation is artificially reduced to 2^32. None of these seem like major issues.

I agree. After generating 2^32 values we are already at 50% chance of collision due to the birthday bound, so I don't see a lot of value trying to get above that limit.

I guess if there's a strong desire to maintain the u128 API to Generator for the sequential randomness case, there could be a wrapper around Generator that provides the same API and implements the used index tracking and PrssIndex128 conversion.

We could do that, although because of the RngCore interface, we can't fully leverage all 128 bits here and the struct guarantees the uniqueness of index used for PRSS itself

martinthomson commented 2 months ago

The birthday bound for AES applies at 2^64, not 2^32 and only if we are feeding in random values. We are essentially doing that because we don't use the PRP directly, but XOR in the counter. This is to give us what the paper describes as circular correlation resistance. Either way, we're a long way from hitting any birthday bounds.

akoshelev commented 2 months ago

The birthday bound for AES applies at 2^64,

Sequential randomness reduces the value received from the cipher to 8 bytes by truncation. So I think it still applies here

akoshelev commented 2 months ago

I am going to merge this change, if there are more comments here I'll address them in a follow up