|
Title: Getting key from duplicate r Post by: bitdrain on November 09, 2024, 04:31:37 PM Hi,
I was studying the old vulnerability that was introduced by reusing a same R when signing with the same key. I am able to proof this works for a large set of examples. However, I have these 2 example transactions: fae3e414425f008196f9127a01dcea59e22ab66768ce5bcb4aba260993494de1 ab1deb8544de4bb1d3319e67b1bfc354601406d4a00ecbe8cbdd7674f96e9699 that both have spent from 14tVK2JhEPsZEL7yYzMNXDYQ6dG3FnzzEY with exactly the same R value. I get z1 and z2 in the same way (using the unlock script instead of signature and putting scripts of irrelevant inputs to 0 length). the resulting values I get are: r :9ac20335eb38768d2052be1dbbc3c8f6178407458e51e6b4ad22f1d91758895b s1 : 2da94e7cb83e17d307d46c80df4f3315b17af13c4a04ef352495f1442562a290 s2 : 43273c2390b15bbe7e4d38559b1d4e6c0d63aad2c586652ec423d851df065271 z1 : 068fbde1dd7e06f4e88ae63a50f8ee07eff41c4b9586cbef1235b83281ab145d z2 : 015b14bdc6f69058bfa8dcdc0e8bcd1fc87f4303804f200bfa6aadf627a8d5f6 This however does not result (doing inverse((r*(s2-s1)),p)) in the private key linked to 14tVK2JhEPsZEL7yYzMNXDYQ6dG3FnzzEY. I'm curious as to why this example deviates from the rest and does not work as expected. I assume my math is wrong somewhere, but since it works for many other cases I'm a bit confused and especially curious if someone knows if my values are correct here or what obvious things I could be missing. Title: Re: Getting key from duplicate r Post by: nc50lc on November 10, 2024, 09:27:23 AM -snip- and especially curious if someone knows if my values are correct here or what obvious things I could be missing. All seem good except the R value is missing its first byte 0x00.Based from the signature, its length should be 33 bytes which includes the omitted 0x00 on its front. By the way, I didn't computed the private key, I just pointed out the missing byte. Title: Re: Getting key from duplicate r Post by: bitdrain on November 10, 2024, 10:17:30 AM All seem good except the R value is missing its first byte 0x00. Thanks for pointing this out, I left it out here but it was present. For the calculated key, these leading zeroes don't not seem to matter though. So it must be something else. Title: Re: Getting key from duplicate r Post by: hexan123 on November 10, 2024, 07:56:14 PM R: 009ac20335eb38768d2052be1dbbc3c8f6178407458e51e6b4ad22f1d91758895b
S1: 16c91427cb20a7321029c311e757dfee67f5e3f9bad23266fad8bf8aaf5cac01 Z1: e69364d551385880ddbb19338b633e2d6c17f1922817b3e3776851780b6aacb5 S2: 43273c2390b15bbe7e4d38559b1d4e6c0d63aad2c586652ec423d851df065271 Z2: 015b14bdc6f69058bfa8dcdc0e8bcd1fc87f4303804f200bfa6aadf627a8d5f6 PubKey: 036ee29b13e9d9f060d078bdcee464cb21aeafe5b5bc15206c5fa3c62f882c97c9 Title: Re: Getting key from duplicate r Post by: amaclin1 on November 10, 2024, 10:57:33 PM Code: const MyKey32 R ( QByteArray::fromHex( "9ac20335eb38768d2052be1dbbc3c8f6178407458e51e6b4ad22f1d91758895b" ) ); ....aaaaaaand the result is "9674578d05e0bc65284cc4db99420957858e1f57505baebb1d0d3e0d25957b7c" hint: try to use ( ORDER - S1 ) instead of S1 Title: Re: Getting key from duplicate r Post by: bitdrain on November 11, 2024, 09:30:08 AM hint: try to use ( ORDER - S1 ) instead of S1 oh that's it indeed! Thanks. So I understand now we take the inverse of S1 in this case, but is there a general rule as to when this happens? Is this when S goes beyond some boundary? Title: Re: Getting key from duplicate r Post by: cyberzzz on November 11, 2024, 12:34:44 PM #Python3
from fastecdsa.curve import secp256k1 from fastecdsa.point import Point def extended_gcd(aa, bb): lastremainder, remainder = abs(aa), abs(bb) x, lastx, y, lasty = 0, 1, 1, 0 while remainder: lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder) x, lastx = lastx - quotient*x, x y, lasty = lasty - quotient*y, y return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1) def modinv(a, m): g, x, y = extended_gcd(a, m) if g != 1: raise ValueError return x % m def sqrt_mod(a, p): if pow(a, (p - 1) // 2, p) != 1: raise ValueError(f"No square root exists for {a} modulo {p}") if p % 4 == 3: return pow(a, (p + 1) // 4, p) raise ValueError("Cannot find square root for this modulus with current method") def pub2point(pub_hex): x = int(pub_hex[2:66], 16) if len(pub_hex) < 70: prefix = int(pub_hex[:2], 16) y_square = (x**3 + secp256k1.a * x + secp256k1.b) % secp256k1.p y = sqrt_mod(y_square, secp256k1.p) if (y % 2 == 0 and prefix == 3) or (y % 2 == 1 and prefix == 2): y = secp256k1.p - y else: y = int(pub_hex[66:], 16) return Point(x, y, curve=secp256k1) Q = "034903acabebcd2185bd64afa44632af51813c4ef25d34b3310d0018271c73f122" Q = pub2point(Q) n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 G = secp256k1.G r = 0x9ac20335eb38768d2052be1dbbc3c8f6178407458e51e6b4ad22f1d91758895b s2 = 0x2da94e7cb83e17d307d46c80df4f3315b17af13c4a04ef352495f1442562a290 z2 = 0x68fbde1dd7e06f4e88ae63a50f8ee07eff41c4b9586cbef1235b83281ab145d s1 = 0x43273c2390b15bbe7e4d38559b1d4e6c0d63aad2c586652ec423d851df065271 z1 = 0x15b14bdc6f69058bfa8dcdc0e8bcd1fc87f4303804f200bfa6aadf627a8d5f6 try: doubler1 = ((z2 * s1 - z1 * s2) * modinv(r * (s2 - s1), n)) % n doubler2 = ((z2 * (-s1) - z1 * s2) * modinv(r * (s2 + s1), n)) % n if Q == doubler1 * G: print(f"Double R : ( X = 0x{hex(doubler1)[2:].zfill(64)} )") else: print(f"Double R : ( X = 0x{hex(doubler2)[2:].zfill(64)} )") except ValueError as e: print(f"An error occurred in modular inversion: {e}") Title: Re: Getting key from duplicate r Post by: COBRAS on November 20, 2024, 06:01:43 AM #Python3 from fastecdsa.curve import secp256k1 from fastecdsa.point import Point def extended_gcd(aa, bb): lastremainder, remainder = abs(aa), abs(bb) x, lastx, y, lasty = 0, 1, 1, 0 while remainder: lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder) x, lastx = lastx - quotient*x, x y, lasty = lasty - quotient*y, y return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1) def modinv(a, m): g, x, y = extended_gcd(a, m) if g != 1: raise ValueError return x % m def sqrt_mod(a, p): if pow(a, (p - 1) // 2, p) != 1: raise ValueError(f"No square root exists for {a} modulo {p}") if p % 4 == 3: return pow(a, (p + 1) // 4, p) raise ValueError("Cannot find square root for this modulus with current method") def pub2point(pub_hex): x = int(pub_hex[2:66], 16) if len(pub_hex) < 70: prefix = int(pub_hex[:2], 16) y_square = (x**3 + secp256k1.a * x + secp256k1.b) % secp256k1.p y = sqrt_mod(y_square, secp256k1.p) if (y % 2 == 0 and prefix == 3) or (y % 2 == 1 and prefix == 2): y = secp256k1.p - y else: y = int(pub_hex[66:], 16) return Point(x, y, curve=secp256k1) Q = "034903acabebcd2185bd64afa44632af51813c4ef25d34b3310d0018271c73f122" Q = pub2point(Q) n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 G = secp256k1.G r = 0x9ac20335eb38768d2052be1dbbc3c8f6178407458e51e6b4ad22f1d91758895b s2 = 0x2da94e7cb83e17d307d46c80df4f3315b17af13c4a04ef352495f1442562a290 z2 = 0x68fbde1dd7e06f4e88ae63a50f8ee07eff41c4b9586cbef1235b83281ab145d s1 = 0x43273c2390b15bbe7e4d38559b1d4e6c0d63aad2c586652ec423d851df065271 z1 = 0x15b14bdc6f69058bfa8dcdc0e8bcd1fc87f4303804f200bfa6aadf627a8d5f6 try: doubler1 = ((z2 * s1 - z1 * s2) * modinv(r * (s2 - s1), n)) % n doubler2 = ((z2 * (-s1) - z1 * s2) * modinv(r * (s2 + s1), n)) % n if Q == doubler1 * G: print(f"Double R : ( X = 0x{hex(doubler1)[2:].zfill(64)} )") else: print(f"Double R : ( X = 0x{hex(doubler2)[2:].zfill(64)} )") except ValueError as e: print(f"An error occurred in modular inversion: {e}") Hi can you modyfy r,ang get r,s,z, for same pubkey ? |