Being Digital's Fortress

November 14, 2007 11:54 AM

Did anyone ever crack the Negroponte Code?

In 1995, long before One Laptop per Child, tech evangelist Nicholas Negroponte authored a book, Being Digital, that challenged readers to crack an "unbreakable" binary code of his own devising. Negroponte was so certain this code couldn't be broken that he offered a $100,000 prize out of his own pocket. (The offer was later revoked for legal reasons – details at the bottom of this ancient interview.)

Does anyone know the current status of Negroponte's challenge?

This was keeping me up last night.

posted by roger ackroyd to technology (8 comments total)

Well, if the key is truly random and as long as the message, then it is a one-time pad and really is 100% unbreakable without knowledge of the key. With $100,000 on the line, he'd be stupid to use anything else.
posted by indyz at 12:03 PM on November 14, 2007

Either it's a one-time-pad or Negroponte is an idiot.

Since determining whether it's really a OTP is probably harder than determining whether Negroponte is an idiot, that's the approach I'd use.
posted by Kadin2048 at 1:08 PM on November 14, 2007 [2 favorites has favorites]

Nonsense. Many sensible people think straight RSA with huge keys (not an RSA hybrid) will remain unbreakable as long as primes are a computationally hard problem (which, unless the NSA understands physics or math in ways we don't, it still is).
posted by phrontist at 2:37 PM on November 14, 2007

It sounds like he was trying to make a political point about the then-proposed Clipper chip, not come up with a new encryption algorithm. His remarks about "layering" and use of "unbreakable", as well as his statements here that the method does not need to be complex, all seem to me indicate that he was talking about using a one-time pad on the plaintext, as others have stated above, before submitting it to a Clipper chip. His point being that even once the NSA recovered the original "plaintext" of some Clipper-encrypted message through a back door, that text could be useless to them. The spine of his book allegedly illustrates this point.

How do you know the code was "of his own devising?" I don't get that explicitly from your article or the one I linked. If it was, it is important to note that the (presumably) unsolved state of this problem says absolutely nothing one way or another about the merits of his algorithm. Bruce Schneier puts it well here. For those same reasons, it's unlikely that anyone with real expertise has tried very hard to solve it.
posted by metric space at 3:50 PM on November 14, 2007 [1 favorite has favorites]

He also could have just made it random noise, which would be a sensible thing to do, if dishonest.
posted by blacklite at 10:04 PM on November 14, 2007

Metric Space: I don't remember much about the code besides the fact that it existed and seemed very interesting at the time – so I was probably mistaken when I said it was of Negroponte's own devising. The background information on the Clipper chip certainly gives me context for the challenge.

...and thanks for the Schneier link.
posted by roger ackroyd at 12:28 AM on November 15, 2007

thanks for the Schneier link

Sure, glad you liked it.

He also could have just made it random noise, which would be a sensible thing to do, if dishonest.

It's also interesting to note that under a one-time pad encryption, any solution of an appropriate length is feasible, since any key is possible. So in the absence of a third-party verifier a cheater could certainly encrypt a legitimate plaintext message. Then in the very unlikely event that the correct solution was somehow proposed, he or she could easily and plausibly deny its correctness by simply claiming that the original message was something else.
posted by metric space at 6:47 AM on November 15, 2007

If you like unsolved crypto challenges, there are several more still out there.
posted by LobsterMitten at 4:05 PM on November 15, 2007