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

'unbreakable' encryption

[gatekeep]

Anything which can be decrypted is going to be breakable. It may take a good deal of effort, but I don't believe there's any such thing as 'unbreakable' encryption. After all, the data has to be decryptable at some point or it's useless.

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 doubt it

[Waffle Iron]

... equations sent with an initial (proprietary) exchange which takes place when users connect to an equipped server.

Otherwise known as the encryption key? That's hardly a one-time-pad.

Re:I doubt it

[Hater's Leaving, The]

Kinda sorta.

A one-type pad could be considered encryption key too though. The difference is that the theoretical kolmogorov complexity of a OTP is at least its own length.

If this nonsense can have it's 'pad generation algorithm' transmitted in b bits, then its kolmogorov complexity is at most b bits.

And if the algorithm is transmitted using a secure channel then the 'pad' is no more secure than that initial channel.

It's like the other old con - you can't use the tail end of a one-time pad to send the next whole one-time pad, no matter what they tell you.

So yes, you're right, the thing's just oozing bogons[*], and is fuxored from the start.

THL
[* The elementary particle of bogosity]

Sounds fishy to me

[happyhippy]

"We've found an electronic way of handling those complex keys, and of regenerating them dynamically so that lists of keys don't have to be stored anywhere," Mr. Kassam said. Its still going to be a matter of cracking what equations make the keys. And seeing everyone who uses these equations once someone has a good deal of these, everyones security is fux0red.

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!"

Re:nonsense

[MindStalker]

Because a computer can't truly think of a random number, if you have two identical computers and you ask them for a random number and give them the same "seed" they will produce the same number. If you feed them no seed at all if you boot the computer and ask for a list of numbers, it will be the same list everytime you reboot. The computer is just installed with a device to generate this sequence of numbers, it has no way to be original. When you need to create a truly random number, which is often important in encryption, you need a random seed, often things like keyboard input, mouse movements, and network traffic is used together to create this seed. Anyways, this program once it creates this random number has to send it back to the server for the server to be able to decrypt the messages. There is no secure way to do this except for using another encyption method, which makes this encyption method just as breakable as any other if you can get the random number, or the seed. But this company says that the encryption is absolutly secure, which it is, but the key for the encyption isn't secure. So effectivly they are hiding behind semantics

Re:nonsense

[egomaniac]

Clarification -- a whole book of codes is transmitted at once. Then you use each code once.

This is actually a lot better than it might sound, because you only have to worry about super-secure physical transit once, and then you get N opportunities to send completely unbreakable messages over whatever insecure channels you want. They could be announced on the nightly news if you wanted, and they would be completely and totally secure as long as nobody had your codebook.

(How can you prove they are "completely and totally" secure? Surely you can just brute-force a one-time pad? ... Well, no. Say the pad is 500 characters long, and you transmit cyphertext <= 500 characters. In the absence of the pad, you would have to try each and every possible pad ... which gives you each and every possible message. There are as many potential plaintexts as there are possible pads, and a huge number of them would be comprehensible, plain English. Comprehensible, plain English with absolutely no relation to the cyphertext, but you get the point.

There is no way to determine that "WE ATTACK AT DAWN" is the *true* plaintext, and not just some random coincidence that resulted from a certain choice of potential pad.)

Author should be ashamed

[tomstdenis]

Note to author: If you are not in the know, don't write as if you are.

First off, the OTP is completely 100% unbreakable [in theory]. Even with infinite time an OTP is unbreakable.

No symmetric key system, even a really super-duper one can get that type of security. I mean sure, you could make it require 2^1000 time, but that isn't unbreakable. That is "not likely to be breakable", a strong difference.

Second, this is not the first company todo so. In fact the sci.crypt snake oil journal is full of similar companies. Any company that cites "unbreakable" and "OTP" when talking about their inhouse crypto is very suspect. Real credible companies don't play on such naive terms. RSA for example will play on the reliability of the code more than they will about the breakability of their ciphers they use [e.g. RC5/DES/AES]

Third, if it is not a OTP then its not a OTP. These "OTP-like" and "pseudo-OTP" phrases you read here and there are meaningless. Either its an OTP or it isn't. There is no half-way inbetween.

Fourth, as I read it you download a program that generates a stream? This is nothing new. What the heck do they think a stream cipher is [re: a block cipher in CTR mode is a good candidate]. What they don't say is if you make a 1000-bit pad with a stream cipher you're not supposed to think of that as a 1000-bit key for a message as in you have 1000 bits of entropy. If you use a 64-bit key to seed a cipher to make 1000-bits for a 1000-bit message than the key is still only 64-bits and you just stretched the entropy over 1000-bits.

e.g.

Entropy In >= Entropy Out

Fifth, everyone please laugh at the shameful cloakware people. Shameful! www.cloakware.com, they are an even bigger canadian joke.

Tom

Re:The Past

[merlin_jim]

I have two things to say:

1024 bit, while not unbreakable, is still unbreakable in the lifetime of the universe. I have no doubt methodologies and processes will be developped in the future that will change this, but as of right now, for all intents and purposes, it's unbreakable

Secondly, many parts of quantum mechanical behaviour *are* random, especially at macroscopic scales. For example, when a particular radioactive isotope chooses to decay is completely random; I've seen military random number generators that depend on this or similar effects to create truly random number.

But, no purely software random number generator will ever even come close to approaching randomness.

Take a secure method and add multiple weaknesses..

[Jelloman]

I'm no encryption expert but this whole thing looks pretty pathetic to me.

• "...anyone who logs on through a Web browser or Internet link will automatically be given an encrypted connection. A small 4- to 10-kilobit file, a bit like a Web cookie, is loaded into the client computer's memory."
  So the program is transmitted through breakable encryption.
  
• "The file contains a program to generate random encryption keys, so that the keys themselves don't have to be sent over the network connection."
  So the keys are generated using a pseudo-random number generator, which makes them quite guessable.
  
• "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..."
  Then the key is transmitted over the network via breakable encryption, which they just said they wouldn't have to do.

Very likely just rubbish

[tempmpi]

The file contains a program to generate random encryption keys, so that the keys themselves don't have to be sent over the network connection

Working OTP encryption requires the random numbers to be truely random, a computer programm can't do that. You need a source of randomness in the computer like the user or a special hardware random generator. The user isn't a solution for random numbers for OTP because you need a lot of random numbers and the user will have to type or move his mouse for a very long time until he has produced enough random numbers for a OTP encryption of a short file.

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 it sends back to the client, and then the key is destroyed and a new one is created.

Here the real problem of it. OTP encryption is only secure if no one can get his hand on the One Time Pad. If the OTP is transmitted over the internet, someone could easily get the OTP. If it is transmitted using a "secure process". The encryption is only as save as this "secure process". If this process is breakable, the whole encryption is breakable.

The "secure process" is also only known to Prescient. Everyone knows that "Security through Obscurity" doesn't work.

Re:Can't anyone use their heads at /. ????

[Silver222]

On the other hand, some might say stories like this are a damn good reason not to subscribe. I read the National Enquirer in the line at the supermarket, but I don't buy it.

Re:The Past

[Hater's Leaving, The]

However, the one time pad is simply a method of transporting a secure channel through time...

In order to have a one time pad, and be perfectly, provably, secure, you must at some point earlier in time (maybe face to face in a secret bunker, where there are no bugs or cameras or tempest devices etc.) have had a secure channel over which to transmit and receive the pad.

The pad lets you transport that secrecy to another point in time. However, you must have had the secure channel in the first place. Are you sure that bunker is as secret as you think it is?

So yes, it's mathematically proven, but it's often very hard to set up in practice, because the preconditions are strict.

THL.

Re:OTP can be broken, given the right circumstance

[plam]

No, this is incorrect. OTP is secure in the following fashion:

Consider aaaaa as an OTP encryption of something. Then, hello and quack are equally good decryptions, and there's nothing that tells you what the original message was.

"One time pad"+modifications ISN'T A ONE TIME PAD

[IvyMike]

Dear Slashdot editors: A one-time pad is provably unbreakable provided you meet the very strict, precise definitions for what a one-time pad is.

Once you make the slightest change, it's no longer a "one-time pad", it's "a new unproven proprietary crypto system." There are NO exceptions to this rule. Any time you post a story that says, "Company X has a one-time pad system that is different than other one-time systems", they don't really have a one-time pad system, and you're just promoting their snake-oil for them. The OTP unbreakability is a mathematical proof, and you can't change the axioms and just claim the proof still holds!

Seriously, NO exceptions. Don't be tempted by their fancy footwork and wiley ways; they're trying to fool you

Can a company come up with a new cryptosystem that's cool? Yes, but they'll have to do a lot of hard work to prove it. This doesn't meet that standard.

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.

Flat out lies

[Alsee]

The company is flat out lying. Or incompetent. They are *NOT* using one-time-pads, and they are *NOT* using a Vernam Cipher. If they were, then yes, it would be unbreakable encryption. But they aren't. They are generating a sequence of psudo-random numbers. Just like any streaming cypher. Generating a list of numbers and calling it a "pad" does not make a bit of difference.

Either (A) they do not understand cryptography, or (B) they are intenionally lying about their cryptography. Either case is a good reason not to trust their cryptography.

-

Re:The Past

[Anonymous Coward]

>>You can determine the 'random' output of any process by knowing the algorithm and all of the seed values.

Not true as quantum mechanics is truely random. And before anyone tries to say "it appears random becouse you don't know the initial state" I say that experiments contradict that point of view.

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.
  

Re:WRONG

[Sycraft-fu]

Doesn't matter, it's STILL 100% secure (again assuming the pad is truly random). The thing is you just DON'T KNOW what it is that I'm trying to say in the message. Even if you can guess, it doesn't help you. You don't know what is plausable or not ebcause you don't know what I'm trying to say. IF you did, you wouldn't need it decrypted. Even if you have a general idea, it doesn't buy you anything. Suppose you know I'm going to tell the guy on teh other end to meet me at certian coordiantes. Fine, you don't know how I chose to phrase that, so you have nowhere to start in the decoding. However for argument's sake say you even know the exact for of teh message. You know I will write it like this:

"I will meet you at the folowing location: XXX XX by XXX XX" where the Xs are the degrees and minutes of the two coridnates. Still buys you nothing, you can decode those into any combination of cordinates you want and yuo have no way of knowing which one is correct.

The problem is with a one time pad, like the orignal poster indicated, literally ANYTHING within that space is possable and since it is truly random (if done right) you just can't know when you have the right answer. You might decode something that you belive to be perfectly correct, it looks totally plausable, and still be dead wrong. You'd do just as well guessing at random with messages the same length as the encrypted document.

Further, you have no way of knowing or being able to tell if what I send was in the form you expected. Maybe it's all BinHExed, maybe it's gziped, maybe it's ROT-15'd. You just can't know.

If you want to try it I'd be happy to generate you a message encrypted with a one time pad and you can try to crack it. I'll even be generous and tell you the prices format it's in and tell you what the topic is. You'll still never crack it, and that's more information than you'd normally have when dealing with a message so encrypted.

Other classic sign I missed

[billstewart]

Oh, yeah - "We've found an electronic way of handling those complex keys, and of regenerating them dynamically so that lists of keys don't have to be stored anywhere," Mr. Kassam said. If you can regenerate the pad of keys, you have no way to limit it to one-time use. With a conventional silk or flash-paper pad distributed by spies with briefcases handcuffed to their wrists, once you use a page of the pad, you burn it so nobody can regenerate it again. Otherwise, somebody else can also regenerate the key and crack your message.

And I didn't bother pointing out that because these folks have no clue what a mathematical proof is, they didn't bother showing how their system preserves the properties of a OTP algorithm.