Assertion `a->limbs + b->limbs <= 2*((256+(64 - 0)-1)/(64 - 0))+1' failed. #43

Hi,

I'm trying to write Rust (rust-lang.org) wrappers for this library. I'm not a cryptography expert and Rust is still under heavy development, so this might not be problem with a secp256k1 library itself, but when I'm giving random array as inputs like this (Rust syntax):

  #[test]                                                                                           
  fn sign_and_verify_fail() {                                                                       
      let s = Secp256k1::new();                                                                     

      let mut msg = Vec::from_elem(64, 0u8);                                                        
      let mut seckey = [0u8, ..32];                                                                 
      let mut nonce = [0u8, ..32];                                                                  
      rand::task_rng().fill_bytes(msg.as_mut_slice());                                              
      rand::task_rng().fill_bytes(nonce);                                                           
      rand::task_rng().fill_bytes(seckey);                                                          

      let pubkey = s.pubkey_create(seckey, false).unwrap();                                         
      let sig = s.sign(&msg, seckey, nonce).unwrap();                                               

      rand::task_rng().fill_bytes(msg.as_mut_slice());                                              
      assert_eq!(s.verify(msg, sig, pubkey), Ok(false));                                            
  } 

I'm getting assert abort:

secp256k1: src/num_gmp_impl.h:200: secp256k1_num_mul: Assertion `a->limbs + b->limbs <= 2*((256+(64 - 0)-1)/(64 - 0))+1' failed.

Generally, it seems the randomness of msg is triggering the problem. Are there some messages / private keys that are not valid? Is this assert ringing a bell what is possibly wrong?

secp256k1's order is 115792089237316195423570985008687907852837564279074904382605163141518161494337, which is slightly smaller than 2^256. A valid private key should be in the range 1 to the order. (However, I haven't checked that the private key is the source of your error).

It would be helpful if you could capture the inputs in a failure case (or post your complete rust code someplace so I could reproduce).

The message can only be 32 bytes. If it's larger, you need to hash it before passing in.

I did a dump of arrays:

msg:
[29, 43, 58, 27, 190, 113, 99, 144, 140, 147, 49, 159, 205, 130, 73, 25, 4, 247, 222, 238, 232, 32, 252, 208, 19, 229, 51, 100, 215, 127, 102, 39, 53, 218, 167, 244, 216, 50, 200, 229, 115, 214, 36, 91, 195, 167, 176, 159, 80, 143, 37, 170, 39, 97, 108, 174, 15, 93, 92, 46, 9, 123, 99, 19]
non:
[142, 145, 0, 2, 12, 122, 33, 14, 3, 87, 129, 205, 241, 47, 3, 63, 225, 234, 0, 128, 215, 216, 236, 67, 53, 191, 158, 194, 34, 141, 190, 10]
sec:
[174, 208, 0, 194, 217, 116, 26, 129, 129, 154, 241, 63, 101, 52, 22, 23, 233, 114, 13, 158, 149, 59, 27, 25, 211, 155, 207, 69, 214, 56, 7, 143]
secp256k1: src/num_gmp_impl.h:200: secp256k1_num_mul: Assertion `a->limbs + b->limbs <= 2*((256+(64 - 0)-1)/(64 - 0))+1' failed.

I'll publish the whole source once I have some more time.

@sipa: Thank you. That seems to be the problem.

As a post-issue: Shouldn't the API check that and return something? Or at least have an assert to fail with more clear message.

Agree, it should. Or at least it should be documented.

I actually remember reading about 32-byte limit somewhere and completely forgot about it, and it was not appearing anywhere I was looking at (main *.h file mostly).

While we're at it. How "slightly" is this order smaller than 2^256 (@gmaxwell comment) ? Should I validate for it somewhere?

The method to convert to a pubkey checks this and returns failure if it's invalid.

It's very unlikely that a random secret key will be out of range. (It's roughly 2^32 out of 2^256 that is out of range). Wrt to the message, I do worry that an unhashed message interface is a pretty big liability (E.g. sign 0).

Does signing zero filled message breaks or weakenes the security? I'm not sure if I understand.

Since I'm receiving so much support, there's one more thing that is unclear to me from the API. Does sizes of all the structures/arrays (compressed signatures, uncompressed signatures, public key, etc.) fixed? The API is not clear about it. Especially signature: is it 33/65 or can it be of any size? <= 72 is all I understood.

An ECDSA signature of zero can be trivially forged, just due to how the algebra works out ( r,s = pubkey.x,pubkey.x is a valid signature of 0). ECDSA should never be used without hashing the message. The libsecp256k1 interface doesn't, so that an application specific hash function can be used.

I'm not sure if I should open a new issue, but I can't get any more information on how to use compact signatures. My two last tests: https://github.com/dpc/bitcoin-secp256k1-rs/blob/master/src/secp256k1.rs#L352 are failing on Err(InvalidSignature) returned by s.verify.

#54 added input validation checks. Closing this; ping if you need it reopened.