Lattice Attack || Predicting MSB or LSB with a 4-bit Nonce

3 replies 126 views
orbit777Member
Posts: 9 · Reputation: 92
#1Aug 11, 2024, 07:33 AM
Lattice Attack || If I have a 4-bit nonce, can I guess the MSB or LSB of 'd'? Or if I know 4 bits of 'd', can I predict the nonce's MSB or LSB? Here's the deal. My private key is 0x2966130c44669056359323ed640f0d9458a0f82fe0328bdc8ee72599c3602dae and the public key is just private * G. The nonce is 0x1f18f5c6507511b559fb5e6d58b8af0fac075b922acab1acf3ca415de73a6282 and the message is 0x9765f3ff01c9a476a71d8ae8b452a876e0784a76526f46da7b2de5984f4bf851. After signing, I got: r = 0xd57a46d3672b3d428a5d8ccb91ced3400959127f76f15a7d99a1002e690dec20 s = 0x95e836298458e00a6f11e291cd7e45003b3ffd886a0048d52f9665a6a5603ad6 z = 0x9765f3ff01c9a476a71d8ae8b452a876e0784a76526f46da7b2de5984f4bf851. The public key is 0x30c7d40d49e6e639ef0a33229420fde736712073c1230513297a637207c54490 and 0x3331b0b1ef655e237bcc2e6f6664b6f1567a0696c6e7aad4b1d15507ef4f27e5. I only need one 4-bit signature to guess the MSB or LSB accurately. My English isn’t great, but I’m offering $1000 for help. Anyone out there tried this before? Puzzle 135: I have 30 vulnerable signatures and I know 4 bits, but I need 87 signatures to cover all cases. So, I'm using my 30 signatures to predict the other signatures' 4-bit MSB or LSB. I just want to use a single signature to guess the MSB or LSB accurately.
3 Reply Quote Share
orbit777Member
Posts: 9 · Reputation: 92
#2Aug 11, 2024, 08:25 AM
private  =  0x2966130c44669056359323ed640f0d9458a0f82fe0328bdc8ee72599c3602dae We can get LSB or MSB useing 128-bit nonce? pub       =  private*G nonce    =  0x1f18f5c6507511b559fb5e6d58b8af0fac075b922acab1acf3ca415de73a6282   I know 128 bit LSB in Nonce message=  0x9765f3ff01c9a476a71d8ae8b452a876e0784a76526f46da7b2de5984f4bf851 If Know nonce 128-bit LSB ,so we can get private key MSB 128-bit or LSB 128-bit ? useing only one signature ? any one help please any math formula ?
1 Reply Quote Share
ColdVaultMember
Posts: 19 · Reputation: 184
#3Aug 11, 2024, 09:30 AM
Mathematically Impossible for Hidden Number Problem you need 2 or more signatures if you know the 128 Bit of the Biased Nonce. There may  or may not be clever algorithms to brute-force this for the first 128 Bits
2 Reply Quote Share
paul.ninjaFull Member
Posts: 152 · Reputation: 539
#4Aug 11, 2024, 12:15 PM
You are mixing a few different attacks into one soup here, and the soup is starting to look radioactive, lol. For ECDSA you have s*k = z + r*d mod n. If you know the full k, the private key falls out instantly. If you only know 4 bits of k, you know basically nothing useful. You have 252 bits of fog left. That is not a lattice attack, that is asking the universe to autocomplete your homework. With 128 known bits it becomes more interesting, but still not "one signature and done" in the lattice sense. Lattice/HNP works because you collect many signatures from the same private key, each leaking a little bit about its nonce, then the repeated structure gives the lattice something to grab onto. One signature gives you one modular equation with two secrets dancing around in it. No grip. There is one caveat: with the public key and signature you can treat it like a partial discrete log problem against the nonce point, because r is the x-coordinate of kG. If you know half the nonce, then you reduced the search space a lot, and Pollard kangaroo / interval DLP style attacks become the right conversation. But that is not "predict MSB/LSB from 4 bits", and it is still not a cute Python loop unless your electricity is free and your calendar ends in the next century.  So for your $100 formula: if you have full nonce, use d = (s*k - z) * inverse(r, n) mod n. If you have only 4 bits, no formula saves you. If you have 128 bits from several signatures, then build the HNP lattice properly. If you have only one signature and only 4 known bits, go make coffee instead. It will produce better entropy.
0 Reply Quote Share

Related topics