1

At the moment I'm playing around with ECDSA. I know that I can retrieve the private key if the same K is used to sign two messages.

I tried to use this script: Ruby Script to crack the private key. But I'm always getting an error:

signature_der_string.rb:14:in `decode': null is wrong length (OpenSSL::ASN1::ASN1Error)

My signatures start with a leading 0. If I leave out the 0 I get a different error

`decode': too long (OpenSSL::ASN1::ASN1Error)

Can you help me what I'm doing wrong?

msghash1_hex = '4992c90022d12b85555493d3dcca55671b4047c1'

msghash2_hex = 'fced62bb70b5af004e8720342d036da02009e5e8'

sig1_hex = '436c79af2252b161af0b74e3eeb4064af334c483e8708fe709c46b1aa480fa49b017fb020fbc9717c6bf50ada23a820'

sig2_hex = '436c79af2252b161af0b74e3eeb4064af334c483e8708fe734065fe380b95c601f118c047976b3007831690806e10f4'

Community
  • 1
Peter234
  • 113
  • 1
  • 3
  • I'm pretty sure you're getting errors here because your ASN.1 encoding of the signature is broken (or non-existent). If you prepent zeroes, ASN.1 will decode this to 0-byte length and if you don't prepend anything it will take the first that seems appropriate which will trigger the other error. – SEJPM Jun 02 '16 at 19:28
  • I created the signature with ecdsa python library. signature = key.sign(b"Signature").encode("hex"). What should I do instead? – Peter234 Jun 02 '16 at 19:30
  • Also see: https://crypto.stackexchange.com/a/1797/23623 – SEJPM Jun 02 '16 at 19:33
  • ecdsa does not by default encode a signature in ASN.1 notation when using sign. It simply converts $r$ and $s$ to strings and and concatenates them. Source is in util.py. – puzzlepalace Jun 02 '16 at 19:39
  • Thanks! Makes sense to me... But how can I encode signature in ASN 1? Should I use openssl? – Peter234 Jun 02 '16 at 19:40
  • You can use sign(b'Signature', sigencode=ecdsa.util.sigencode_der) as stated in the README. – puzzlepalace Jun 02 '16 at 19:43
  • Thanks! I think got it. One last question. I couldn't find the solution on the internet... Can I convert an existing signature automatically? Without creating a new one? – Peter234 Jun 02 '16 at 20:04
  • I suppose you could use string_to_number and then sigencode_der from ecdsa's utils.py to do this. – puzzlepalace Jun 02 '16 at 20:42
  • I tried it with: ecdsa.der.encode_octet_string(b"signature"). But hexlify(signature) gives me b'04097369676e6174757265'..With a leading 0. Sorry for asking but I'm really trying to figure it out on my own...But I don't get any further. – Peter234 Jun 02 '16 at 20:55
  • Hexadecimal represents each byte with two hex digits (0-9a-f or 0-9A-F). Your sig?_hex strings are odd length which is just wrong; with a digit 0 preprended they are valid hex for 48 bytes which appears to be two chunks of 24 bytes for a 192-bit EC curve -- but not DER. The DER encoding of OCTET STRING starts with a byte 4, which is correctly shown in hex as 04. But the DER encoding of an ECDSA signature doesn't use any OCTET STRING, it uses a SEQUENCE of two INTEGERs. If DER is too hard for you, use the separate r,s approach in @PurpleK's answer. – dave_thompson_085 Jun 03 '16 at 02:00

1 Answers1

3

I have modified this Ruby script to not require public keys and to allow direct (r,s) input. Funnily enough, I stumbled on this thread (created two hours ago as of writing) on Google searching for the exact same problem. Note that I am using Secp192r1 (due to a CTF challenge), so feel free to modify that to your likings:

require 'ecdsa'

msghash1_hex = '000000000000000000000000000000000000000000000000'
msghash2_hex = '000000000000000000000000000000000000000000000000'

sig1 = ECDSA::Signature.new(0x000000000000000000000000000000000000000000000000, 0x222222222222222222222222222222222222222222222222)
sig2 = ECDSA::Signature.new(0x000000000000000000000000000000000000000000000000, 0x333333333333333333333333333333333333333333333333)

group = ECDSA::Group::Secp192r1

def hex_to_binary(str)
  str.scan(/../).map(&:hex).pack('C*')
end

msghash1 = hex_to_binary(msghash1_hex)
msghash2 = hex_to_binary(msghash2_hex)

r = sig1.r
puts 'sig r: %#x' % r
puts 'sig1 s: %#x' % sig1.s
puts 'sig2 s: %#x' % sig2.s

# Step 1: k = (z1 - z2)/(s1 - s2)
field = ECDSA::PrimeField.new(group.order)
z1 = ECDSA::Format::IntegerOctetString.decode(msghash1)
z2 = ECDSA::Format::IntegerOctetString.decode(msghash2)

k_candidates = [
  field.mod((z1 - z2) * field.inverse(sig1.s - sig2.s)),
  field.mod((z1 - z2) * field.inverse(sig1.s + sig2.s)),
  field.mod((z1 - z2) * field.inverse(-sig1.s - sig2.s)),
  field.mod((z1 - z2) * field.inverse(-sig1.s + sig2.s)),
]

private_key = nil
k_candidates.each do |k|
  private_key_maybe = field.mod(field.mod(sig1.s * k - z1) * field.inverse(r))
  puts 'Private key maybe: %#x' % private_key_maybe
  next
end

Signature.new(r,s) are the parameters above. msghash_hex is basically the hex version of your HASH(message) without 0x and with quotation marks around it to make it into a string to be processed later.

KelvZhan
  • 46
  • 3