Opened 4 years ago

Closed 4 years ago

#17783 closed enhancement (implemented)

Pull in a SHA-3 implementation.

Reported by: yawning Owned by: yawning
Priority: Medium Milestone: Tor: 0.2.8.x-final
Component: Core Tor/Tor Version: Tor: unspecified
Severity: Normal Keywords: tor-core crypto
Cc: Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

We'll need it sooner or later, particularly because SHAKE128/SHAKE256 are incredibly handy for what they do, and having a cryptographic hash that's immune to length extension attacks simplifies some of our constructs.

I have a modified version of keccak-tiny (https://github.com/coruus/keccak-tiny) that provides more familiar semantics that I can clean up for inclusion.

Child Tickets

Change History (13)

comment:1 Changed 4 years ago by nickm

sure, let's have a look. (Also as in intermediate step, please put your cleaned-up tweaked version on github so other folks can yoink it too?)

comment:2 Changed 4 years ago by yawning

https://github.com/Yawning/tor/compare/feature17783

I still need to add common/crypto.h wrappers for the XOFs (which is the main reason we should be looking at SHA-3 IMO), but this does the integration for SHA3-256/SHA3-512. Performance is slower than OpenSSL's optimized SHA-2 assembly, but it is message size dependent. Not something I'd use for a general purpose hash yet...

comment:3 Changed 4 years ago by yawning

The same branch now has wrappers for SHAKE256 that should be suitable for use.

comment:4 Changed 4 years ago by nickm

Reviewing...

Looking good!

  • first commit is a pure import; that's fine.
    • But I don't like the code duplication between keccak-tiny-unrolled.c and keccak-tiny.c. Keeping them in sync would seem to be annoyingly hard. Let's only maintain one. Which is the only-slightly-unrolled one, and how much better is the other one's performance?
  • second commit:
    • forks the api and makes the changes non-mergeable to upstream by introducing tor dependencies. I'm not 100% a fan of making the changes non-upstreamable; can we isolate our changes behind a set of #defines and some "keccak-tiny-private.h" file?
    • The correct use of KECCAK_{XOF,HASH}_DELIM and KECCAK_TARGET_TO_RATE in keccak_init, the fact that you need to init before you add bytes or finalize, and the fact that you need to finalize before you squeeze, should probably be documented. In fact, it might not be crazy to assert in the code that these requirements are met.
    • There should be a comment explaining that nobody should ever look at keccak_state's internals.
  • third commit (9edd9a8e2c2f283e7607e59524ffdf0b2ae51516):
    • The assertions about bit sizes are getting big; probably we should have a new inline function that takes a digest_algorithm_t and returns the size of its output.
    • I would like to see a more unit tests here. In particular, I would like to see:
      • more test vectors, including the empty vector, vectors exactly equal to one/two input block size, vectors equal to one/two input block sizes plus or minus one, a single-character input, and something with a NUL in the middle.
      • Although we don't do this with the other incremental digests, I'd like to see is do a pretty rigorous test on the incremental update function -- possibly randomized tests where we generate a big random buffer and add it incrementally in random-sized chunks and make sure we get the same output each time. (I think this is a good idea because in this case the incremental update code is our own.)
  • Fourth commit (the one to add xof):
    • Here you test the return value of keccak_init; in the previous commit you don't. Probably best to be consistent.


comment:5 Changed 4 years ago by nickm

Status: newneeds_revision

comment:6 Changed 4 years ago by nickm

Also see #17795 for a ticket about the unending expansion of digests_t.

comment:7 Changed 4 years ago by nickm

Also see #17796 for a ticket about memory efficiency. (Neither this nor #17795 needs to be solved before this ticket can bemerged.)

comment:8 in reply to:  4 Changed 4 years ago by yawning

Replying to nickm:
[snip]

  • first commit is a pure import; that's fine.
    • But I don't like the code duplication between keccak-tiny-unrolled.c and keccak-tiny.c. Keeping them in sync would seem to be annoyingly hard. Let's only maintain one. Which is the only-slightly-unrolled one, and how much better is the other one's performance?

The author recommends keccak-tiny-unrolled.c, I personally didn't find a huge difference between either, though I suspect this would be CPU/microarchitecture specific. For modern Intel, I suspect that the unrolled version doesn't fit in the LSD cache...

  • second commit:
    • forks the api and makes the changes non-mergeable to upstream by introducing tor dependencies. I'm not 100% a fan of making the changes non-upstreamable; can we isolate our changes behind a set of #defines and some "keccak-tiny-private.h" file?

I wasn't really planning on fighting to merge this upstream, but ok.

  • The correct use of KECCAK_{XOF,HASH}_DELIM and KECCAK_TARGET_TO_RATE in keccak_init, the fact that you need to init before you add bytes or finalize, and the fact that you need to finalize before you squeeze, should probably be documented. In fact, it might not be crazy to assert in the code that these requirements are met.

Ok.

  • There should be a comment explaining that nobody should ever look at keccak_state's internals.

Ok (though I do at one point in our XOF wrapper, I'll change that).

  • third commit (9edd9a8e2c2f283e7607e59524ffdf0b2ae51516):
    • The assertions about bit sizes are getting big; probably we should have a new inline function that takes a digest_algorithm_t and returns the size of its output.

Ok.

  • I would like to see a more unit tests here. In particular, I would like to see:
    • more test vectors, including the empty vector, vectors exactly equal to one/two input block size, vectors equal to one/two input block sizes plus or minus one, a single-character input, and something with a NUL in the middle.

Ok, for both SHA3-256 and 512?

  • Although we don't do this with the other incremental digests, I'd like to see is do a pretty rigorous test on the incremental update function -- possibly randomized tests where we generate a big random buffer and add it incrementally in random-sized chunks and make sure we get the same output each time. (I think this is a good idea because in this case the incremental update code is our own.)

Hm, ok.

  • Fourth commit (the one to add xof):
    • Here you test the return value of keccak_init; in the previous commit you don't. Probably best to be consistent.

Ok.

I'll make all the changes when I can hear myself think.

comment:9 Changed 4 years ago by nickm

also, compiler warning:

src/test/test_crypto.c:562:21: error: comparison of integers of different signs:
      'int' and 'unsigned long' [-Werror,-Wsign-compare]
  for (int i = 0; i < sizeof(msg); i++)
                  ~ ^ ~~~~~~~~~~~
src/test/test_crypto.c:564:21: error: comparison of integers of different signs:
      'int' and 'unsigned long' [-Werror,-Wsign-compare]
  for (int i = 0; i < sizeof(out); i++)
                  ~ ^ ~~~~~~~~~~~

comment:10 Changed 4 years ago by yawning

Checkpointing: https://github.com/Yawning/tor/compare/feature17783_take2
(nb: This may get rebased/tramped on/etc, probably not).

The incremental API is cleaner (IMO), and is self-contained without tor-isms in 1 commit so should be easy to upstream if so desired. There aren't huge changes to how it's used, though there's separate init calls (that take bits instead of target, yay) for use as a digest or XOF.

TODO:

  • more test vectors, including the empty vector, vectors exactly equal to one/two input block size, vectors equal to one/two input block sizes plus or minus one, a single-character input, and something with a NUL in the middle.
  • Although we don't do this with the other incremental digests, I'd like to see is do a pretty rigorous test on the incremental update function -- possibly randomized tests where we generate a big random buffer and add it incrementally in random-sized chunks and make sure we get the same output each time. (I think this is a good idea because in this case the incremental update code is our own.)

I even tested building it with clang in addition to GCC this time.

Last edited 4 years ago by yawning (previous) (diff)

comment:11 Changed 4 years ago by yawning

Just pushed an update that adds test vectors that cover most of the additional cases requested. I went for SHA3-256 rate, -1, +1 and SHA3-512 rate *2, -1, +1 in the interests of brevity. It should exercise the code around the boundary conditions sufficiently (SHA3-512 on it's own should cover everything since it's common code...).

I couldn't find a ShortMsgKAT with a NUL in it suitable for testing in the official test vectors, but I'll admit that I didn't look very hard (The test vectors specify n bit messages so there's lots that aren't usable).

comment:12 Changed 4 years ago by yawning

Status: needs_revisionneeds_review

Added the random large buffer incremental test with SHA3-512. Should be ready for review again.

comment:13 Changed 4 years ago by nickm

Resolution: implemented
Status: needs_reviewclosed

Merged, then twiddled include.am a bit to make sure we distribute the header files. Thanks!

Note: See TracTickets for help on using tickets.