1
$\begingroup$

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'

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SEJPM Jun 2 '16 at 19:28
  • $\begingroup$ I created the signature with ecdsa python library. signature = key.sign(b"Signature").encode("hex"). What should I do instead? $\endgroup$ – Peter234 Jun 2 '16 at 19:30
  • $\begingroup$ Also see: crypto.stackexchange.com/a/1797/23623 $\endgroup$ – SEJPM Jun 2 '16 at 19:33
  • $\begingroup$ 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. $\endgroup$ – puzzlepalace Jun 2 '16 at 19:39
  • $\begingroup$ Thanks! Makes sense to me... But how can I encode signature in ASN 1? Should I use openssl? $\endgroup$ – Peter234 Jun 2 '16 at 19:40
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your code... Solved my problem no. Maybe you should delete it if its part of a CTF challenge not to spoil others... $\endgroup$ – Peter234 Jun 3 '16 at 4:35
  • $\begingroup$ If it solved your problem, please mark it as an answer. I will not be removing this answer as it would be selfish, and this is simply an adaptation of existing PoC code. Anybody with little Ruby knowledge can easily modify the PoC code you linked so it makes no difference. $\endgroup$ – KelvZhan Jun 3 '16 at 12:27

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