Israeli Firm Claims Unbreakable Encryption 728
Several readers have pointed to an Israeli company's claim of achieving unbreakable encryption. The linked article reports this claim uncritically. Do you think there's such a thing as unbreakable encryption? This isn't the first time someone's made this claim, or second, or third ...
One Time Pad (Score:5, Informative)
Practically unbreakable (Score:2, Informative)
It's not theoretically unbreakable, just practically unbreakable with today's technology.
Re:Exceptionally random cipher text (Score:5, Informative)
Szo
Hmm, questions... (Score:2, Informative)
(Congrats and Kudos to them if they pulled it off, but I remain skeptical as always until I see some full-on analysis from experts in the field, not a brochure-derived article)
VME was broken (Score:5, Informative)
I haven't read the article (c'mon!) but I saw the mentions of VME, which...well... was broken [google.com].
It's snakeoil. Just marketing, no security. Move along. Nothing to see here.
Re:Nope (Score:3, Informative)
Unbreakable encryption is quantum encryption.
Re:VME was broken (Score:2, Informative)
Okay, that was just the decryptor, but IIRC it was broken (found weak) also elsewhere in sci.crypt. Bruce Schneier mentions them back in 1999... in his snakeoil column.
Re:One Time Pad (Score:5, Informative)
You CAN NOT use the same pad more than once. Hence the name "One-time" pads. Here's why:
Here are two messages, encrypted with the same pad:
cyphertext1 = plaintext1 + one-time-pad
cyphertext2 = plaintext2 + one-time-pad
For short:
c1 = p1 + otp
c2 = p2 + otp
Now, I get ahold of both cyphertexts, and I suspect, or guess, that they were encrypted with the same key.
(c2 - c1) = (p2 + otp) - (p1 + otp)
(c2 - c1) = (p2 - p1)
So, now, the "enemy" has a new set of numbers, obtained by the subtraction of the two cyphertexts, and this result is also the subtraction of the two plaintexts as the one-time-pads cancelled out.
A message that is simply the difference between two plaintext messages is trivially crackable via statistical analysis.
Anyone who enjoys encryption theory and a good yarn should go pick up a copy of Neal Stephenson's Cryptonomicon. It is one of the best book I have ever read.
Justin Dubs
Re:One Time Pad (Score:5, Informative)
Problem (1) is really hard to do well. And, no, a cheap soundcard is not the answer
Re:old news (Score:1, Informative)
Re:This is the dumbest thing I've read in a long t (Score:5, Informative)
In Applied Cryptography, Schneier has a lovely explanation of why you can't brute force a 256 bit key. IIRC it comes down to there not being enough quantums (of time) between now and the end of the universe to check every possible key if every atom can perform on calculation per quantum. He also explains why its not physically feasable to brute force a 128 bit keyspace.
So what is comes down to is this: either you find a weakness in the algorithm, or work on quantum computing until it can brute force huge keyspaces outside the normal constraints of physics. Until then, 128 bits is enough (for symmetric crypto).
Actually reading the Meganet site is laughable. They attribute stolen credit card details to poor or broken cryptography (reality: this data isn't kept encrypted on the site host, because the security architecture of most sites sucks).
The algorithm they claim is uncrackable is based on a random "matrix", which is derived from a "file of any size that is available ..." on both sending and receiving computers. So there IS secret data that must be transferred (or else that file is public, even worse). According to the code available here [google.com], the values aren't even vaguely random - just do lots of XORs using bits from your "secret file".
Meganet tries to justify its claims by pointing to multiple encryption. Big news guys: the size of the keyspace determines security, not the number of times you encrypt with the same key. At best multiple encryption makes it take longer to brute force the keyspace. It doesn't add security. Period.
Apart from that this matrix is used as a lookup table. That means that it has all of the problems of a one time pad, without the benefits. As soon as you use any block of values from the matrix again, you have information that you can use to attack the encryption.
It may be true that noone has broken this algorithm. I've written crypto algorithms that noone has broken ... because I've never published them, and noone has had an interest in breaking them. That doesn't make them secure. Cryptographic security is achieved using simple algorithms that can be proven, using mathematical theory, not attested to by supposition and lame tests.
Non (simply) n-time-pad (Score:2, Informative)
From the patent:
So, it would _seem_ a bit like:
1. build matrix:
A B C
D E F
G H I
2. to cipher up the letter F which is at row 2, col 3 send (2,3).
3. mutate matrix, goto 2
So the real "crypto" lies in the mutation of the matrix... how that is done is not described... maybe it's just x-or'ed onto itself or whatnot.
The way the key is found has nothing to do with the value of the crypto, so don't even begin to critisize how easy it must be for an attacker to guess which file is being used as key.
Beware of David Irving (Score:5, Informative)
Re:One Time Pad (Score:5, Informative)
That's a book cipher, and it's not a one time pad. There's a lot of structure in your pad material.
No, the problem is still the random source. If you have two sources that produce the same key stream they are not "random" in the sense that we mean. And if you distribute (broadcast) the pad, then you have the key distribution problem again.
Not to say that book ciphers cannot (and have not) been used to good effect. But one-time-pads they're not.
Snake oil since 1999 (Score:5, Informative)
"The base of VME is a Virtual Matrix, a matrix of binary values which is infinity in size in theory and therefore have no redundant value. The data to be encrypted is compared to the data in the Virtual Matrix. Once a match is found, a set of pointers that indicate how to navigate inside the Virtual Matrix is created. That set of pointers (which is worthless unless pointing to the right Virtual Matrix) is then further encrypted in dozens other algorithms in different stages to create an avalanche effect. The result is an encrypted file that even if decrypted is completely meaningless since the decrypted data is not the actual data but rather a set of pointers. Considering that each session of VME has a unique different Virtual Matrix and that the data pattern within the Virtual Matrix is completely random and non-redundant, there is no way to derive the data out of the pointer set." This makes no sense, even to an expert.
Re:One Time Pad (Score:3, Informative)
1) The generation of the pads.
The article says "Meganet offers a patented non-linear data mapping technology, called VME (Virtual Matrix Encryption), that creates exceptionally random cipher text". So this is how the "onetime pad" is generated, and this has always turned out to have a weakness. "Real" onetime pads are generated by random natural processes, such as cosmic rays, not from a mathematical seed.
Re:If the Israelies Have it.... (Score:1, Informative)
Well yes they are basically the same, didn't you know Israel is supposed to be the land of the Jews ? Want to move to Israel and buy some land there ? Good luck if you're not a Jew. It is a racist country, and Jews themselves don't deny it, that's one the reason it was created.
Re:My unbreakable encryption scheme (Score:3, Informative)
If I recall correctly, it was actually first deciphered by the agents of the Technical Office in Stockholm, Sweden and, neutral as Sweden was, leaked to the U.S.
Re:Consider the source--analyze the claims too. (Score:2, Informative)
While I agree with everything else you said, I remember about this particular instance of "please do our job for us": It WAS all over the net about two years ago except there wasn't a "one million dollar price" (but there was a Ferrari). Of course, it make everybody laugh at the time as well except a few scientists in the fields who where pretty much annoyed over the fact that not only did they more or less publically accused them of being incompetents, but they also didn't provide the testers with:
1/ The algorythm used.
2/ Anything but the cyphertext.
Failing to provide any of these would have disqualified the "trial" as to being a test of the algorythm efficiency so failing both speaks for the effort the company make in helping peer review.
The patent claim (Score:2, Informative)
A data security method and apparatus that provides an exceptional degree of security at low computational cost. The data security arrangement differs from known data security measures in several fundamental aspects. Most notably, the content of the message is not sent with the encrypted data. Rather, the encrypted data consists of pointers to locations within a virtual matrix, a large (arbitrarily large), continuously-changing array of values. The encryption technique is therefore referred to as Virtual Matrix Encryption. Furthermore, the data security arrangement uses a very large key of one million bits or more which creates a level of security much higher than any other existing method. The key is not transferred but is instead created from a file of any size that is available on both a computer used to send a secure message and a computer used to receive a secure message. The term Virtual Key Cryptographic as used herein to refer to techniques in which a key is recreated at a remote location from an electronic file without any transmission of the key itself. The file may be a system file, a file downloaded from the Internet, etc. A smaller, transaction-specific key, e.g., a 2,048 bit key, is sent end-to-end and is used in conjunction with the very large key to avoid a security hazard in instances where the same file is used repeatedly to create the very large key.
The patent [uspto.gov]Meganet's Algorithm (Score:2, Informative)
The flaw is that the starting "matrix" must be shared. It's essentially a symmetric key or shared secret algorithm, with the disadvantage being that the shared secret is overtly large. Example entropy sources to reconstruct the matrix suggested in the patent include "system files" or "files downloaded from the Internet".
Thus, it is impossible for the algorithm to be stronger than the method relied on to reconstruct the matrix at the receiving end. A file is most likely to be used to do this, so breaking an instance of ciphertext is likely to be an exercise in guessing which file(s) available to the receiving computer would be used to construct the decryption matrix.
If one has available a secure means to share the matrix construction file(s), one could presumably forego the VME encryption altogether and use the same means to pass the message itself.
The algorithm is designed to do nothing but encrypt or decrypt an arbitrary number of bytes. It does not address key exchange. If an implementation contains any other weaknesses through oversight, such as not padding plaintext to a sufficiently large block and passing any check information out of band to detect transmission errors, compromise could occur through those weaknesses.
Doesn't anyone here read Cryptogram? (Score:3, Informative)
http://www.counterpane.com/crypto-gram-9902.html [counterpane.com]
I think we can file this under "snake oil".
I would like to see this undergo a peer review... (Score:3, Informative)
However, strong peer review and research though can give very strong motivation as to why a certain algorithm is computationally intractable (making the encryption scheme practically unbreakable).
Before I could ever trust some new-fangled encryption scheme, I think I would like to see the company submitting REAL detailed articles of mathematics and techniques to appropriate research conferences and have the whole algorithm and math undergo the process of peer review. Its just too easy to fuck up encryption and to think something REALLY REALLY hard to compute isn't in reality a lot easier than it seems.
Key size, addendum (Score:5, Informative)
Symmetrical cryptography does not depend on any specific properties of the numbers selected as the key of the cryptosystem. Therefore a 128 bit key can assume 2^128 different values and, as some other poster pointed out, there is not enough energy in the universe to overcome the background radiation as many times as it would take to count to 2^128, let alone try and brute force the cypher.
Asymmetric cryptography on the other hand derives its features from mathematical properties of some of the numbers used. For example, some systems require the a product of large prime numbers, or discrete logarithms etc. This means that, for example in RSA, you cannot use all of the 2^128 values of a 128 bit key.
Most systems in use today are so-called hybrid systems, using both asymmetric and symmetric cryptography. Since a cryptosystem is as strong as its weakest link, you need to increase the asymmetric keysize to be at least as difficult to break as the symmetric part. Given the current knowledge of factoring algorithms and the like, you need at least a1024 to 2048 bit RSA key to stack up against a 128 bit symmetrical key.
Re:Sounds good... (Score:2, Informative)
Just torture/blackmail the people with the keys.
Re:Oh Good... (Score:3, Informative)
Warning Sign #1: Pseudo-mathematical gobbledygook.
Meganet has a beauty on their Web site: "The base of VME is a Virtual Matrix, a matrix of binary values which is infinity in size in theory and therefore have no redundant value. The data to be encrypted is compared to the data in the Virtual Matrix. Once a match is found, a set of pointers that indicate how to navigate inside the Virtual Matrix is created. That set of pointers (which is worthless unless pointing to the right Virtual Matrix) is then further encrypted in dozens other algorithms in different stages to create an avalanche effect. The result is an encrypted file that even if decrypted is completely meaningless since the decrypted data is not the actual data but rather a set of pointers. Considering that each session of VME has a unique different Virtual Matrix and that the data pattern within the Virtual Matrix is completely random and non-redundant, there is no way to derive the data out of the pointer set." This makes no sense, even to an expert.
Warning Sign #5: Ridiculous key lengths.
Meganet takes the ridiculous a step further : "1 million bit symmetric keys -- The market offer's [sic] 40-160 bit only!!"
Longer key lengths are better, but only up to a point. AES will have 128-bit, 192-bit, and 256-bit key lengths. This is far longer than needed for the foreseeable future. In fact, we cannot even imagine a world where 256-bit brute force searches are possible. It requires some fundamental breakthroughs in physics and our understanding of the universe. For public-key cryptography, 2048-bit keys have same sort of property; longer is meaningless.
Warning Sign #8: Security proofs.
There are two kinds of snake-oil proofs. The first are real mathematical proofs that don't say anything about real security. The second are fake proofs. Meganet claims to have a proof that their VME algorithm is as secure as a one-time pad. Their "proof" is to explain how a one-time pad works, add the magic spell "VME has the same phenomenon behavior patterns, hence proves to be equally strong and unbreakable as OTP," and then give the results of some statistical tests. This is not a proof. It isn't even close.
Investment sink been around since 1997 (Score:2, Informative)
Curiously, all of their challenges are over before ever appearing on their website...
Re:Exceptionally random cipher text (Score:3, Informative)
As a consequence you cannot get high rates and there is some structure in the output. What is wrong with using a 50 cent Zener Diode? Or a 1 Euro fast noisy OpAMP with amplification 100 and grounded input? Both produce high quality random noise, first case electrons jumping the PN-wall, second case electrons moving around (termal noise).
Time for googling, people. (Score:3, Informative)
cut and paste the links.) Google for
'meganet', 'encryption', and 'doghouse'
and you'll find two Doghouse entries for these
guys on Cryptogram. One makes fun of their
product; the other for them changing their
name in response to the first entry.
Re:One Time Pad - randomness... (Score:2, Informative)
- dave f.
I invented unbreakable encryption once... (Score:3, Informative)
It turns out if you have a key, you can just guess at it, and eventually break it... I just went to the source of the problem... the key. If you don't have a key, you can't break it. Unfortunately, as it turns out, you can't decrypt it either.
Seriously thhough:
It probably is theoretically possible despite what you may see on here to make an unbreakable encryption. The only problem with this is that it can only be used on data less than the key size(AKA one time pad) and random data(AKA data of an unknown format). If you can accomplish either these two, I don't think anyone will be able to break it. The problem is: With a one time pad, it's pretty much the same as carrying the data to the other end; data is useless unless someone can understand it.
I've always wanted to start a cryto challenge of a crypto that had no signature and was of nearly random data. The problem is, computers are not that great at pattern matching, and won't be able to find a good pattern in your data format to begin with. This is compounded with no verification that the key you used is valid. In theory, you could get anything out of the decryption if it weren't for that pesky external signature. Remove those, and it could decrypt to just about anything the same length.
In a nutshell, if you had the perfect compression (theoretically impossible) it would be impossible to break your encryption (if you didn't have a signature or hash for verification). Now if only compression was encryption oriented (no predictable bits... thus not perfect), we would be all set. If you researched enough, you may be able to make it very hard to predict bits in compression.
Most encryption in the past has been broken by the redundancy of the data (Signatures, statistics, etc.) so that you know if you have the right key (the signature matches, the MD5 matches, or it looks like the target language). If it's impossible to know if you have decrypted the message, it's impossible to break.
Re:Nope (Score:3, Informative)