Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a concrete instantiation of Rabin-Williams signatures.

Specifically:

  • The private key is 2 primes $p, q$.
  • The public key is their product $N = pq$ and is approximately 3072 bits long.
  • the hash function is Skein-512 with 3072 + 512 = 3584 bits output (Skein allows arbitrary output lengths).
  • The padding scheme is deterministic full-domain-hashing, using the 3072 low-order bits of the Skein output.
  • The two high-order bits of the Skein output, which are not otherwise used, are used to select which of the four square roots to output.

Example applications are CA signatures and distribution package manager signatures where signature verification speed is critical.

Questions:

  • Is Rabin-Williams with 3072 bit keys faster or slower to verify than EdDSA?
  • Is the scheme I gave secure? I think that it is an instantiation of a scheme that was proven secure in the random oracle model by Bernstein in this paper. While Skein is less used than other secure hash algorithms, it was an SHA-3 finalist and underwent a substantial amount of cryptanalysis.
share|improve this question
    
@downvoter why? – Demetri May 25 at 17:03
    
I'm following the description here as I am not familiar with RW. When you say that the padding scheme uses the 3072 low-order bits of the Skein output, what is the input? The message itself? – mikeazo May 25 at 17:47
    
Yes, the message is the Skein input. – Demetri May 25 at 17:51
    
Do you have a link to the mathematical description of RW that you are using? – mikeazo May 25 at 17:55
    
I am using the one in the Bernstein paper I linked to. – Demetri May 26 at 2:00

Rabin-Williams signature verification with 3072 bit keys is much faster than EdDSA signature verification of comparable security (when done in software). How much depends on care of coding, hardware, EdDSA parameters. Two data points:

  • in the eBATS benchmarks for a skylake CPU, ronald3072 signature verification (RSA with $e=3$ as an OpenSSL wrapper, by Bernstein) is nearly twice as fast as ed25519 (archetypal EdDSA carefully optimized by Bernstein); I'm too lazy to see if/when Montgomery arithmetic (which does not pay in the context) is used by OpenSSL RSA signature verification; but since there are at least two modular multiplications in that, versus one in RW, the later can only be faster.
  • in the Crypto++ benchmarks, RW 3072 verification can be extrapolated from RW 2048 verification times 2.25 (erring on the safe side), and is over 15 times faster than the fastest ECDSA signature verification (with pre-computation) quoted.

Even for an implementation using a $32\times32\to64$ multiplier, and classical algorithms, the modular multiplication dominating (properly coded) RW signature verification with 3072 bits key uses $k=96$ words, and about $2k^2$ (less than 20000) multiply-and-add. That can't be very long if coded carefully!


I think the theoretical principle of the scheme is right. Some details (like exactly what Full-Domain-Hashing is used, and perhaps additional constraints on primes) needs to be ironed out. And of course, the principle of rolling one's crypto is debatable (or just should be summarily rejected, in many real-life contexts).

As of implementation: the signature verification is reasonably easy to get right (as long as the correct number of redundancy bytes are checked), and is inherently immune to timing and other side-channel leakage (excluding fault injection), since nothing secret is involved. However lots of things can go wrong in signature generation, including side-channel (timing, power analysis..) and fault-injection attacks (against the later, at the very least, the signature should be verified independently of what generated it before being released).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.