kTimesG's 80-bit key challenge

October 16, 2024. kTimesG announced a side challenge in the BitcoinTalk thread of the b1000 puzzle. The deal: on November 1 at midnight UTC, a P2PKH address with 0.005 BTC and "an 80-bits secure private key". Plus the range to search. The winner only had to say which method broke it. And there was a line for everyone about to argue: "If your first instinct is to yell 'this is not a 80-bits secure private key', please note this competition is NOT for you."

How the 80-bit challenge works

80 bits in the middle of a 511-bit number

The range post went up at 00:01:53 UTC. It's not a range from 1 to 2^80:

minKey = 0x659756abf6c17ca70e0000000000000000000140be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
maxKey = 0x659756abf6c17ca70fffffffffffffffffffff40be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355

Both numbers are 511 bits long. They differ only in 80 contiguous bits, starting at bit 361. A number that big still works as a private key. It just wraps around the curve order n.

The trick is to move the unknown bits to the bottom. Subtract minKey·G from the public key. Multiply by the inverse of 2^361 mod n. What's left is an ordinary key between 1 and 2^80, and Kangaroo eats that in minutes. The answer, 0x2d56cbf370cbeef9e80a, goes back the same way. minKey | (k << 361), then mod n, gives b40e7d34…6be5fe56.

So yes, 80-bit secure. Some people in the thread still spent the day arguing it wasn't.

The public key only lived in the mempool

The address got two payments of 0.0025 BTC on October 28 and never spent. No spend, no public key, nothing to search with. The author promised to push a spend 20 to 28 hours after the range post. And the hint said where the hard part was: "The challenge involves correctly extracting pubkey from the raw TX, otherwise it's a no brainer."

So the real game was a race. Pull the public key out of the pending spend. Crack it. Replace the author's transaction with a higher fee, all before a block confirms it.

The author pushed right after a block, and the next one took 57 minutes. Plenty of time. albert0bsd posted the transformed public key minutes after the spend showed up. Still, nobody replaced it for 39 minutes. kTimesG wasn't impressed: "What if this was the real 80 bit puzzle being emptied, you'll never have 40 minutes." Etar's script had the key in 158 seconds and then crashed on the fee. Ouch.

The replacement landed in block 868480 at 00:37:21 UTC on November 2. 0.00495 BTC went to 14q4SoQwENXXzsVT3GMwDrDUGiW5QZeiDg. The author's own spend never confirmed, so the chain shows only the replacement.

What the kTimesG record carries

export const kTimesG80Bit = bitcoinPuzzle({
  id: "ktimesg/80_bit",
  address: p2pkh("1ECDLP8osCZHBB1LH5PVAUfFegeMgFb52q", "90b881be…8ba92a12"),
  sourceUrl: RANGE,
  startedAt: "2024-11-01 00:01:53",
  status: Status.Solved,
  pubkey: compressed("03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7"),
  key: hex("b40e7d34265ab9533a64622bd1a188fb8abb8829af545169abad49b46be5fe56"),
  prize: 0.005,
  hints: [/* the 80 contiguous bits, the range with its answer, the raw TX */],
  solvedAt: "2024-11-02 00:37:21",
  solveTime: 88528,
  transactions: [funding(/* … */), increase(/* … */), claim(/* … */)],
  solver: party(undefined, { addresses: ["14q4SoQwENXXzsVT3GMwDrDUGiW5QZeiDg"] }),
});

A 256-bit key and no bits

The key is the reduced one, the 256-bit number that actually signs for the address. It has no bits, on purpose. bits has to match the key's own length, and 80 is the width of the range, not the key. The range and the 511-bit form sit in the hints, where the author put them.

The range hint also carries the answer. Before anyone had the public key, the range post committed to the solve steps with a SHA-256, a6c39217…f0651db0. The steps came out after the claim. The record quotes their last lines: shift 361, the 80-bit key and the % that turns it into b40e7d34….

Started at the range, not at the funding

startedAt is the range post, not the funding four days earlier. The author did post the address on October 31, to show it wasn't a hoax. But without the range there was nothing to search. And without the pending spend, nothing to search with. So solveTime is 88,528 seconds, about 24.6 hours, and almost all of it was waiting for the spend.

A solver with an address and no name

opchecksig wrote later that the prize address is theirs. Kangaroo on an RTX 4070, 28 minutes. Nobody signed anything with that address though. So the record keeps the address and skips the name.

Keyed by the author

ktimesg/80_bit resolves as 80_bit or ktimesg/80_bit. The collection is named after kTimesG, not after this one challenge. If another one comes, it goes right next to this one.

The kTimesG puzzle records