Fix: os2ip not compatible with RFC specification

[LucasAschenbach]

trafficstars

Description

The current implementation of hash_to_field, specifically os2ip, is not compatible with the official RFC specification (4.2, p. 12). This pull request updates the implementation of os2ip to be in line with the specification.

Type of change

There are two issues in the current implementation.

1. The input bytes are being converted to dynamic length hex coding, preventing the result-update logic from being called in cases where there is an uneven number of byte values < 16. As a result, the returned field element will be 0 with probability 1/2.

https://github.com/lambdaclass/lambdaworks/blob/f6dda1c526c49a33809684c44a948e20dadf5a78/crypto/src/hash/hash_to_field.rs#L47

The updated version adds leading zeros to the encoding to guarantee a length of 2 chars per byte.

https://github.com/LucasAschenbach/lambdaworks/blob/41a570ea09b59ef40cd328436d5e1db4b78b315c/crypto/src/hash/hash_to_field.rs#L47

2. The current implementation assumes the number of bytes to be divisible by N * 16 which is generally not the case. The remainder is being discarded.

https://github.com/lambdaclass/lambdaworks/blob/f6dda1c526c49a33809684c44a948e20dadf5a78/crypto/src/hash/hash_to_field.rs#L48

To include the remainder bytes, the result-update logic is now called one more time when the last byte has been processed.

https://github.com/LucasAschenbach/lambdaworks/blob/41a570ea09b59ef40cd328436d5e1db4b78b315c/crypto/src/hash/hash_to_field.rs#L48

• [ ] New feature
• [x] Bug fix
• [ ] Optimization

Checklist

• [ ] Linked to Github Issue
• [ ] Unit tests added
• [ ] This change requires new documentation.
  • [ ] Documentation has been added/updated.
• [ ] This change is an Optimization
  • [ ] Benchmarks added/run

[codecov-commenter]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 71.99%. Comparing base (f6dda1c) to head (41a570e). Report is 16 commits behind head on main.

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #870      +/-   ##
==========================================
- Coverage   72.28%   71.99%   -0.30%     
==========================================
  Files         149      149              
  Lines       33823    33325     -498     
==========================================
- Hits        24450    23991     -459     
+ Misses       9373     9334      -39     

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

[Oppen]

I smell many more problems in the original code. build_two_to_the_nth does nothing close to what the comment says it does (it builds the equivalent to 0x111...11112 for a FieldElement, which is precisely NOT a power of 2). os2ip itself seems like a case of premature optimization that both has no benchmark to back it up and misses the point by using format! in the main loop, which causes allocations and drops at every iteration, just to presumably avoid calling cios too often. The link documenting hash_to_field is also dead, so it seems fake? Can't know, I may check with webarchive. The tests also essentially don't test a lot. They check that if you pass the same value you get the same result, which is, uh, something.

All that said, thanks for the fix, it seems like the only correct bit in the file 🙃

I'd much rather try to make a more proper fix for the whole and add a co-authored-by for you, for finding and fixing this part. Unless you want to fix the other issues as well. A quick fix for build_two_to_the_nth is to change the '1' in the string to 'f'. Even then, all the code is more complicated than it needs to be.

[Oppen]

Only snapshot: https://web.archive.org/web/20230618021320/https://www.ietf.org/id/draft-irtf-cfrg-hash-to-curve-16.html#name-hashing-to-a-finite-field

This was short-lived. Odd.

[diegokingston]

This PR is stale, so I am closing it