2
$\begingroup$

I'm guessing that the message must conform to 256 bits but I was not able to find documentation of any message length limits.

$\endgroup$
3
$\begingroup$

The first step of ECDSA (and most signature mechanisms in actual use) is hashing the message, both in signature production and verification. The result of this hash is then truncated to fit the group size; that's truncated to 255-bit for secp256k1.

Hence what limits the size of the message to be signed is the limit built into the hash, typically due to a fixed-size counter. That limit is usually $2^{64}-1$ bit (e.g. for SHA-256, typically used for secp256k1) or more (e.g. $2^{128}-1$ bit for SHA-512 or SHA-512/256, which would be usable as a substitute for SHA-256 with secp256k1).

$2^{64}-1$ bit is just shy of 2 exbibyte and >2.3 exabyte (several days worth of the current mobile traffic worldwide per this source). This is not a practical issue with usual hashes, which are sequential: hashing that at a rate of $10^9$ blocks of 512-bit per second (much more than anything a single sequential device currently achieves) would require more than a year. For hashing real large messages, we need a parallelizable hash, typically a hash tree. It would also be a good idea to sign subtrees of manageable size, to avoid storing exabytes of data only to find afterwards that it does not check.


Some APIs to ECDSA expect the hash to be done externally, and typically start at the truncation step. Technically, they do not fully implement ECDSA. For secp256k1, such API would probably process the low-order 255-bit of their pre-hashed message input. For signature production at least, it is important (prudent and perhaps essential) to only allow a hash (PRF secure in the ROM) to be fed there, as it is necessary for conformance, is an assumption in ECSDA security proofs/arguments, and doing otherwise at least allows existential forgery (perhaps worse).

Further, some APIs to ECDSA signature production take as input the random they use to sign (or the generator they use to generate that). It is then essential to only allow that input to be (or yield, for a generator) a random secret exclusively used for that purpose and a single signature; doing otherwise would jeopardize the confidentiality of the private key.

$\endgroup$
  • $\begingroup$ No sarcasm here but when you say, "The first step of ECDSA (and most signature mechanisms in actual use) is hashing the message" is that due to a limitation in the signature scheme of only being able to sign a message of a certain length or is hashing the message an input requirement of the scheme regardless of the message length? Following Paar's book, "Understanding Cryptography", it seems like the motivation for using a hash in a signature is because of some limitation in the size of the message when it comes to the signature process and is this the case in ECDSA? $\endgroup$ – JohnGalt May 13 '18 at 14:09
  • 1
    $\begingroup$ @JohnGalt Hashing is an integral part of a signature scheme to provide any security. $\endgroup$ – Squeamish Ossifrage May 14 '18 at 2:06
  • 1
    $\begingroup$ Might be worth pointing out that it would be foolish to design a system that requires a verifier to be able to store two exabytes of garbage before it can decide to discard the garbage. If messages can be that long, you're probably doing something wrong. (On the other hand, it is also dangerous for verifiers to operate on partially verified messages broken into chunks—but the problem remains that having an exabyte of instructions to act on atomically is asking for trouble.) $\endgroup$ – Squeamish Ossifrage May 14 '18 at 2:09
  • 1
    $\begingroup$ @fgrieu I'm realizing that what I was asking was why are hashes necessary using EC or really any scheme (although the answer is probably different depending upon the scheme). Instead I tried to ask a question that presupposed a message limit size as the reason. In the end you answered the question I asked and I'm marking it answered, so thank you. I'm going to review all of the comments and do a search to determine whether I should ask the broader question. $\endgroup$ – JohnGalt May 14 '18 at 13:54
  • 2
    $\begingroup$ @JohnGalt A general heuristic is that the fancy math often has highly structured corner cases that could be efficiently exploited for forgery if the attacker could force a message to fall into those corner cases, e.g. the extreme cases of integer cubes in RSA or a zero scalar in ECDSA. Using a hash renders negligible the probability that even an intelligent attacker can fabricate a message that falls into those corner cases. $\endgroup$ – Squeamish Ossifrage May 14 '18 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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