One-Time Pad Encryption With No Pad?

thepooleboy writes: "The Globe and Mail has an article about a Toronto area company that has perfected 'Unbreakable Encryption' using the Vernam Cipher." The idea is to use as a one-time pad a large number generated by equations sent with an initial (proprietary) exchange which takes place when users connect to an equipped server. Since real one-time pads' numbers are by definition random and known in advance to both sender and receiver, though, the company seems to be playing fast-and-loose with their terms.

Comments

Re:'unbreakable' encryption

[kolding]

Actually, a correctly used one-time pad is unbreakable. The true randomness of the pad cannot be calculated, and if it's never reused, you have no clues as to how to calculate the encryption.

However, this scheme isn't a one-time pad. It's a function, with parameters encrypted with a standard encryption algorithm. If you break the algorithm used to exchange the parameters, you've broken the whole code. It's certainly no better than anything else out there.

I think we've been here

[fm6]

equations sent with an initial (proprietary) exchange

Since the exchange software is closed source, how are we supposed to know if it's secure? It's probably some silly gimmick that will be broken by the first hacker who fiddles with it.

Attempts to get around the fundamental limits of data encryption (and data compression, and a lot of other software fundamentals) remind me of all the pointless efforts to build a Perpetual Motion Machine. "Yeah, the smart guys say energy is "conserved", but anybody with any common sense can see if you just tweak this gearbox this way..."

nonsense

[egomaniac]

They have a program which generates new keys for each subsequent transaction, and they claim that this counts as a "one-time pad".

Nonsense -- a one-time pad is only secure because there is provably no way to figure out the keys without a copy of the codebook (assuming they were generated through appropriate random means).

As long as a program is producing the keys, they will exist in a particular sequence. All you need to do is figure out at which point in the random sequence you are, and then you can generate the rest of the sequence easily, allowing you to eavedrop on the conversation.

Admittedly, the article was fluff, but key-hopping doesn't significantly increase the difficulty of breaking encryption. Unless there is something else behind this that I'm missing, this is another "Compress random data by 99%! For real this time!"

WEBSITE LINK

[drDugan]

finding their website was non trivial on google

its here

http://www.prescient.net/

A vernam cipher IS unbreakable

[dwbryson]

no, a vernam cipher is the only form of unbreakable encryption. It happens like this: you have a stream of extremely random bits. And you have to make sure they are really really random, no pseudo random number generators. Say it's coming from a satelite up in space that measures radioactive particles(this was proposed in a paper not too long ago). Now the satellite streams these bits down to earth, so anybody can access them. Alice and Bob want to communicate securely over an insecure channel. So the agree on a series of bits to encrypt with. This can be anything from "every other bit" to a large polynomial function that says which bits to use. So every bit the function designates as an encrypted bit is used to XOR any message Alice and Bob use to communitacte. So, Alice computes bit random bit number x to encrypt bit y. She does XOR(x,y)->c and sends it to Bob. Bob also has this formula and performs the calculation to find which bit number x to use, then performs XOR(c,x)->y. The key is keeping the bit number function secret. Now, why is this secure? because anybody listening on the channel doesn't know the function(hopefully) and if your bits are truely random there is *no* way to distinguish whether any given bit can be 0 or 1. Try all the combinations for 0 or 1 in the message you want, but every permutation you want will look like the correct decryption.

"Unbreakable" is to "encryption", as...

[volpe]

..."unsinkable" is to "ship"

Re:*scoffs* 'unbreakable' encryption

[Citizen of Earth]

The client generates a series of random numbers to use as an encryption key. This is number is exchanged with the server through a secure process known only to Prescient, the server uses it to encrypt any information

Ha! The fools! Just send your message through this secure process. No need for the one-time-pad nonsense! QED.

Re:WRONG

[swillden]

Given infinite time, a monkey will eventually bang out the contents of the OTP.

Sure. The question is: How will you know it when you see it?

The monkey will bang out every possible n-bit sequence. Applying them all to the n-bit encrypted message will give you every possible n-bit message. So you'll get all of the following:

• ATTACK AT DAWN
• ATTACK AT NOON
• EAT MY DORITOS
• LICK MY PENCIL
• I BROKE AN OTP
• ...

So, how, exactly, will you know when you've found *the* message?

That's why an OTP is provably unbreakable. Because every pad is equiprobable. And that's why no algorithmically-generated pseudo-random sequence can be used for a one-time pad.

Wrong.

[rjh]

Ummmm... comparing asymmetric encryption to symmetric encryption (of which a one-time pad is a subset) with key-lengths is like comparing apples to oranges.

This much is right.

In asymmetric encryption, your security is in your keyspace... every bit doubles the time to search the keyspace.

This much is nowhere near right. According to our best estimates at the present time, it'll take on the order of 2**80 operations to factor out RSA-1024. It'll take on the order of 2**128 operations to factor out RSA-3072.

Adding two thousand bits doesn't increase the difficulty by 2**2048... only 2**48. Asymmetric crypto does not double in difficulty with each added bit.

In symmetric encryption, security is all about the keys; symmetric encryption is so easy to do that you can try millions of keys a second, as opposed to thousands or hundreds, so you HAVE to have a big keyspace.

This is not correct. In fact, it's downright astonishingly wrong. The problem is you're assuming symmetric and conventional, non-ECC asymmetric keyspaces are both flat (they're not). But if they were flat, then asymmetric crypto would have a keyspace multiple orders of magnitude larger. Which is the opposite of what you're asserting here.

Conventional, non-ECC asymmetric keys are so huge because most of the keys are weak. Let's compare DES to RSA. Is 0xFA810DD0 a legitimate 64-bit DES key? Yes. (Note: DES only uses 56 of those bits for key material; the other 8 are used for parity.) Is 0xFA810DD0 a legitimate 64-bit RSA key? No. Why? Because 0xFA810DD0 is an even number, which makes it much, much easier to factor.

Conventional, non-ECC asymmetric keyspaces are so huge partially (not exclusively) because most of the keys in that keyspace are unusable. Symmetric keyspaces are so small partially (not exclusively) because most of the keys in that keyspace are usable.

A keyspace in which all (or the overwhelming majority of) keys possess equal strength is called a "flat" keyspace. A keyspace in which some keys are stronger or weaker is... well, non-flat.

But, most symmetric encryption algorithms allow you to get it partly right; if the key is partly right, you get a partly decoded message, so the search algorithm is linear instead of exponential.

This is so wrong that it staggers the imagination. Claude Shannon established some principles back in the 1940s which still guide cipher development today. One of these is called the avalanche effect. The idea behind the avalanche effect is that a single one-bit error, anywhere in the enciphering/deciphering process, will affect the output of half the bits in the entire e/d process.

Go ahead. Use Blowfish with a 40-bit key. (There are lots of Blowfish implementations out there; if you want one, email me and I'll send you one.) Encrypt it with one 40-bit key, and then decrypt it with a key that's only one bit different. You'll get absolute, total, gibberish. You'll get gibberish because Blowfish is a well-designed cipher and avalanches properly.

But wait--it gets even worse. Only a chump runs a cipher in electronic codebook mode. Usually, ciphers are run in a block-chaining mode, where every subsequent block gets XORed with the prior block. So if you have a one-bit error in your process, that will affect half the bits of the block... which then create errors in half the bits of the next block... which avalanche... which propagate their error forwards, on and on and on... etcetera.

You get the idea.

(All of the above information can be found in either Bruce Schneier's Applied Cryptography, 2nd Ed or Menezes, Oorschot and Vanstone's Handbook of Applied Cryptography.)

Classic Snake Oil with = ~20-bit key

[billstewart]

This product has pretty much all the signs of the classic snake oil psuedo-one-time-pad, except that if you can believe their white paper, it's weaker than most snake oil products. Here are some of the issues:

• It's a proprietary secret algorithm they made up themselves. That's a bad sign already, because people who know the crypto community know that they have to be able to publish their algorithm and have it examined by (other) experts to have any credibility, and they know that any computer program can be reverse-engineered so the algorithm will leak out anyway, and anybody who doesn't know the crypto community well enough to know this hasn't read much of anything in the real literature, doesn't know the well-known attacks, much less the sneaky ones, and is probably reinventing yet another flat tire.
  
  
• They worked on it for four years before it was ready for public use. Since it hasn't been peer-reviewed, it's *still* not ready for public use. :-) And they say it's "considered to be the best in the world", but since they're the only ones who've seen the algorithms, they must be the one considering it the best in the world, and as we'll see below, their taste in such matters is pretty questionable.
  
  
• While grammar flames are normally considered tacky, if you can't get the syntax right in the English grammar in your press release, much less make the contents intelligible, and your crack team of engineers who've labored over this for four years can't hire somebody who *does* speak English to proof-read their press-release, I'm skeptical that they've done any better on either the syntax, structure, or quality-assurance for their programs. All your bits are belong to us! If they were from Montreal and not Toronto, you could at least blame it on Babelfish or something, but they've apparently had to do their own babbling.
  
  
• Their PR says it doesn't use an algorithm, and then talks about the computer programs that produce it. "E2Sec is not structured and uses no algorithms, therefore unbreakable" That doesn't mean that it doesn't have a mathematical structure - it only means that they're not mathematicians, don't understand the structures, and aren't very good at algorithms, therefore it should be easily breakable. That also strongly implies that, since they don't know algorithms or structure, they're not only bad at math but also not very good at programming, so the implementation has a much higher chance of being cracked without even bothering to crack their incompetent algorithm.
  
  
• They provide several examples of cyphertext (and the plaintext) and invite the public to break the algorithm using that, as a demonstration of their confidence that it's unbreakable. This approach is widely disparaged by the community - if they had any confidence, they'd not only publish the algorithm and invite cracking, they'd also pay some well-known cryptographer or cryptographers to analyze it for them, rather than hoping that either they'll get serious attention for free, or if they're a little brighter than that, only get unskilled amateurs trying to crack it because it's ignored by skilled professionals, leaving them free to say "See, nobody's cracked it in the TWO WHOLE WEEKS it was on the net! It must be UNBREAKABLE!!!!"
  
  
• They provide a "proof", which apparently was copied or translated by somebody who doesn't speak Mathematics, and leaves out the definitions of the critical functions and the lengths of variables but makes vigorous assertions that it demonstrates unbreakability within a person's given lifetime. The only way I can see that their assertion is true is if what they mean is "You won't be able to figure the precise values out in your lifetime because we've underdetermined our example" :-)"
  
  
• They assert that competing systems usually only provide 128-bit security, but theirs provides 5000-10000-bit security, because that's roughly the sizes of encryption programs they pass between client and server. Yes, that's an upper bound on the possible complexity, but most of those bits are the expression of the program, not the key itself.
  
• They pass their session encryption-pseudocode programs around using any conventional browser. This means that either it's all public, or that it's only protected by the 40-bit or 128-bit crypto used by the browser, so not only do they possibly have zero bits of strength in their own system, you might as well use your browser's encryption instead, because you can *i* get 128-bit crypto for free.
  
  
• "The core code is dynamically generated at install time from a random selection of over a million unique and distinct pseudo-code each capable of generating millions of server-based code." Unfortunately, in contexts that are clearly mathematically clueless, it's difficult to evaluate whether "over a million" means "20 bits" or "more than 5" or "billions and billions" or "oh, wow, man, that's really complicated-looking!". But if we take them at face value, they are at least *saying* that it's really about a 20-bit algorithm. It's possible that when you look at the algorithm closely that the 20 bits condense to much fewer than that, or that it's really a lot stronger than their clueless press-release (excuse me, they called this a "technology white paper", didn't they) writer says it is, but it's a good hint that it might be around 20 bits strong.
  
  
• Their algorithm uses "random numbers" and that they're "uniform". They don't talk about how they're generated, or how long they are. Typical random-number generation subroutines useful for game-playing or user interface decorations are linear congruential generators that are either ~16-bit or ~32-bit integers, and often the 16 bits are really just 15 bits. So maybe their 20-bit strength is really only 15. Of course, they also don't say anything about how the generator is seeded, so there's no way to tell if they've done that properly - it may be that their 15 bits of security falls apart after receiving two blocks of a message if they've done it sufficiently badly.
  
  
• In addition to using random numbers of undefined quality, they also refer to using "undeterministic keys". Aside from non-deterministic constructs in English grammar, it's hard to tell if they're referring to the presumed-poor-quality random numbers they use in other parts of the program or if they're doing some kind of hardware-generated randomness, e.g. having the user wave a mouse around. But if they are, the values from that randomness can't be generated identically by the recipient of a message, so they need to be passed in the aforementioned messages, where an eavesdropper can snag them, so the strength, if any, isn't helpful.