Slashdot Mirror
Israeli Firm Claims Unbreakable Encryption
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 is uncrackable... but the "key" is the same size as all the data you'll ever want to send... but DAMN it works. =]
From the article:
"Most of the encryption community called our product snake oil," says Backal. "Everyone competed to throw stones at us and didn't bother trying to understand the product."
So, 1) They have an unbelievable claim (unbreakable encryption) and 2) the extremely knowledgeable encrypton community, who have much experience with breaking encryption, has seen their product and calls it snake oil.
It is snake oil. Move along.
I believe posters are recognized by their sig. So I made one.
> This isn't the first time someone's made this claim, or second, or third ...
And if this story gets reposted, it'll seem like a fourth!
Wonderful article, but how good is encryption when your fundamental flaw in data security is the people who use it?
Case in point: 128-bit SSL keys, MD5 hashed passwords on a system utilizing firewalls and a database whose data is encrypted by the super-uncrackable-key(tm)... owner connects to the site over the internet via telnet...
We should invent encrypted people. That way not only would data be safe, but it's so secure the guy next to you has no idea what you're talking about!
Sincerely,
-Matt
--- Need web hosting?
Which is unfortunately 2x the size of the original message.
Ho hum...
-- The universe began. Life started on a billion worlds...
-- Except on one where stupidity was there first.
With hardware. Geiger-Müller for example. Or measuring thermic movement of certain electrons.
Szo
Red Leader Standing By!
How can a deterministic computer create anything more then pseudorandom ?
By using lava lamps, of course
Jason
ProfQuotes
...Ask Kevin Mitnick - Part II.
Their glick is using a 1MB long key (4000 times longer than current encryption methods). They say it's going to be the strongest in the next 5-6 years.
The title "unbreakable" was created by the journalist (and it appears to have worked, they got a story in slashdod).
By using a non-software-based, outside source of entropy. Send up a weather baloon connected to your serial/parallel port. Retrieve real-time data, disgard a few of the most significant figures, and use the rest.
In other words, there are many ways.
Justin Dubs
Take input file and pipe it to dev/nul,
Take dev/random and pipe it to output file.
Guaranteed unbreakable encryption!
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
This is so incredible I just can't read anymore.
I haven't read the article (c'mon!) but I saw the mentions of VME, which...well... was broken.
It's snakeoil. Just marketing, no security. Move along. Nothing to see here.
Belief is the currency of delusion.
From the press release or whatever that is:
Even though this is probably bogus, the prize for breaking it looks interesting
You're ignoring the distinction between symmetric and asymmetric cryptography.
Symmetric cryptography uses only one key for encryption and decryption. For such a key, 256 bits is quite secure.
Asymmetric cryptography uses a public key for encryption and a different, private key for decryption. If using the RSA algorithm then yes, anything less than 1024 is insecure. (Elliptic Curve Cryptography is also asymmetric but is still strong at less than 1024 bits.)
Meganet's algorithm is symmetric.
Counterpane had a little blurb on their website about it... Crypto stuff
This may have been where the original "Snake Oil" comment came from.
I'm no elite cryptographer; I just try to be an educated user. I rely on people far smarter, and with far more expertise than I'll ever have in the field of cryptography to give me an idea of whether something is reasonably good. That said, even a rank amateur like myself can detect marketing-speak...
I have no authoritative expertise with which to judge encryption algorithms, but outrageous claims tend to speak for themselves... in a negative way.
Even if a man chops off your hand with a sword, you still have two nice, sharp bones to stick in his eyes.
First, let's consider the source of this article. Here is what Israel21c says about themselves.
"ISRAEL21c is a not-for-profit corporation organized under the laws of California that works with existing institutions and the media to inform Americans about 21st century Israel, its people, its institutions and its contributions to global society. ISRAEL21c creates, aggregates and broadly disseminates high-quality information to the American public about the Israel that exists beyond the pervasive imagery of conflict that characterizes so much of western media reporting. Our goal is to strengthen the vibrant and enduring partnership between the United States and Israel, and between Americans and Israelis."
Translation: They are a part of the American pro-Israel lobby, whose job it is to pull the blinkers over the eyes of Americans regarding whatever Israel is doing at the moment. In this case, they don't handle the Arab-Israeli conflict (they mention a sister org for that -- israelinsider). Rather, they propagandize for the Israeli high-tech industry, an industry largely created by American taxpayers and which directly competes with American companies. We won't talk about the underhanded way that came about.
So fair enough, they are pimping their nation's product. Let's look at what the article actually says, however.
"Meganet offers a patented non-linear data mapping technology, called VME (Virtual Matrix Encryption), that creates exceptionally random cipher text and combines it with a one million-bit key, which is unheard of in today's data security markets. Competing solutions offer a maximum of 256 bits."
Cut through the marketing bullshit, and this sounds like a variation on the old one-time pad. This isn't the first company to discover how wonderfully secure the one-time pad is. It it difficult to believe that this company has achieved a quantum leap in computer power such as would be necessary to support a one million bit key for any other kind of algorithm.
"All other encryption methods have been compromised in the last five to six years."
This is a quote from the founder of the company, a former IDF (Israeli Defense Force) tank commander. The statement is deceptive. Any form of encryption, OTHER THAN A ONE-TIME PAD, is susceptible to brute force attack if the key size is small enough. Some encryption methods, such as DES, are more vulnerable than others. PGP and GnuPG use default encryption that is pretty darn secure, and there hasn't been a successful cracking attempt a key of any reasonable size. The quote, by being deceptive, makes the product claims suspect.
"Backal stumbled onto the mathematical algorithm behind VMS when he was working as an engineer in the field of Wide Area Networking."
Highly unlikely story to begin with. One does not "stumble onto" mathematical algorithms -- not reliable ones, anyway. There is mention of a patent application, but no reference to any peer review. The fact that this company was ignored for two years is instructive -- if there was any substance to this, someone in the cryptography field would have taken a look at it. There is also the following:
"In an attempt to prove VME's strength, Meganet began offering prizes such as a Ferrari or $1m. to anyone who could break into a VME-protected file. So far, two million people have attempted to crack the code, but none have managed."
I try not to use bad language on public forums, but the most descriptive word I can come up with for this is "bullshit". If VME had ever put this out for that kind of money for a genuine trial, it would have been all over the Net. There is NO evidence I can discover that supports this claim. None. Nada. Zilch. This whole thing is really starting to smell bad.
The following two quotes give reason for pause as well.
"In November 1999, Meganet launched the company at the Comdex computer show in LA, California, hoping to attract corporate users. The company packed its 1,000 sq. ft booth with attractions, including a $1m. giveaway of Meganet software. Meganet proved a runaway success, and in the wake of the show it raised $5m. at a valuation of $50 to $60m. from new investors, most of them small, private investors. To date, the company has raised $10m., none of which comes from VCs."
"By December 2000, however, Meganet was in trouble. The company may have gained industry recognition, but it did not have sales. Nor could it raise money as the stock market had begun to crash."
You know what it means that money is raised from "small investors" without VC involvement? It generally means that you a dealing with a corporate con artist. I have some personal experience in dealing with a tech company that refused to take VC money. The reason for not raising money from VCs is simple. A venture capital firm will, on behalf of its funders, demand access to and a thorough review of the technology, something small investors aren't in a position to demand. If this was the real thing, there wouldn't be any need to hide the ball from the money guys. If you are a small investor, beware of companies that raise their money from small investors exclusively. It is a fundraising method that is the foundation of a great many frauds and impositions. If this is for real, somebody big would have invested -- but then, that might pose the same problem for the founder as having a VC involved, right?
Here is the part that worries me, however.
"Today, Meganet is rapidly becoming a significant US government vendor. Though it remains a small company, with just 25 employees, it won three out of four tenders released by the US government in this sector last year, beating giants like Verisign, RSA, Network Associates, Computer Associates, and IBM, to become sole-contractor on the projects."
Assuming this is true, it is disturbing. Let's look at what we have here. We have a former IDF officer who has come up with supposedly "unbreakable" encryption. It isn't peer reviewed, and he is apparently seeking security through obscurity (i.e. hides the ball) rather than publishing this wonder technology where others can take a look at it and see if there are any flaws. The company's R&D is in Israel, and when the company fails commercially, it starts getting U.S. Government contracts, presumably through the kinds of political connections that the America-Israel lobby (such as AIC and Israel21c) foster.
The Israelis have demonstrated that, despite the fact that the United States is their only real allies in the world, they won't hesitate to stab the Americans in the back when it serves Israeli interests. The Pollard spy case was only the tip of the iceberg for Israeli espionage in the US. Our own State Department has established that Israel has the most aggressive spying program in the U.S. of any ally, surpassing even such supposedly unfriendly nations as China. Remember the three Israelis in the van who were picked up by police after they were filmed cheering while the WTC collapsed? All former IDF members. They were released after a few weeks and rushed home, and the company they worked for simply disappeared.
I doubt VME has any wonder technology. I don't doubt that the Israeli intelligence apparatus would love to have us using their technology companies to protect our vital national secrets. Then they won't have a need for embarrassments like active intelligence agents in the US. They could simply download the information themselves, courtesy of our blindness in working with this somewhat unreliable ally.
Based on what I see in the article and the source, I wouldn't touch VME with a ten-foot pole.
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, 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.
i-name =twylite [http://public.xdi.org/=twylite], see idcommons.net
It's my girlfriend. Many men have tried, and to date none have been able to figure her out.
Bit pricy though.
This fpp.co.uk is David Irving's site. He is the guy who denies the holocaust. More on Mr.Irving: http://www.geocities.com/irving_challenger/
Have Linux installed at your place in Amsterdam, for cheap
There used to be a Windows program called "Unbreakable security" which, among other things, could encrypt a file and put it in self opening .exe file (you had to enter the password).
So I tried to crack the program and found out it was fairly easy to do (took me a few hours). But then I discovered that the program had a bug which caused the blank password to be accepted as valid password. So much about Unbreakable security.
here
The joy of this for me is that, in the end it really comes down to a 7 bit exhaust to get started decrypting, and after that it's just a matter of decrypting each intermediary key in turn.
Jedidiah
Craft Beer Programming T-shirts
Professional cryptographer Bruce Schneier used these guys as the exemplar for "Pseudo-mathematical gobbledygook" in the February 1999 issue of his monthly crypto-gram newsletter:
"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.
Ubi dubium ibi libertas: Where there is doubt, there is freedom.
I know what it is like to be misunderstood. I have this brilliant, gauranteed, money making scheme that no-one has faith in. If you send my £25 I will tell you all about it.
I love stacking my barbecues in the shed at the end of summer - you can't beat a bit of grill on grill action.
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.
Pathman, Free (as in GPL) 3D Pac Man
doesn't work. It just keeps going faster and faster."
It is the perennial cry of the snake oil crowd that the "establishment" won't take their claims seriously. It never, *ever* seems to occur to them that this is because their claims are *provably* whacko. Especially where purely mathmatical structures are concerned.
Most snake oil saleman didn't do very well in math at school, although this personal limitation has never seemed to stand in the way of their being able to seriously cook a set of books to display for the investors.
KFG
A deficiency of one-time-pad is a man-in-the-middle with plaintext known. Given the known plaintext he can solve for the key and then use it to substitute an identical-length message of his own choosing.
...") for the long-winded header. The tail disolves into noise, but that could be expected from a code-clerk (or machine) under attack, which might make a synchronization error in the key. For automated systems you can still spoof the checksum at the end even if you can't spoof the tail of the message. Tweak the protocol and you might, say, slip some malware's infection header into a known buffer-overflow bug behind a firewall.
This is a non-trivial problem, as the start of a message may be known to an attacker, in both manual systems (where messages often start out with stock stuff) and automated ones (where the start may be automated protocol headers or well-known payload starts, which is all he really wants to spoof). Further, the entire content may have been discovered by other means - means which still didn't give him the encryption key.
Substituting only the start can still spoof both manual and automated systems. With a manual system you can substitute a short, urgent message ("They're coming over the hill at us from the east armed with
A solution to that was proposed back in the '70s by (ahem) me: Use Gallois fields, TWICE as much one-time pad as message, and encrypt in small blocks by multiplying by the first block of key and adding the second. (You also discard any block of key that would result in a multiply-by-zero in the first step.)
For any product of N primes there is at least one gallois field, and two is prime, so there is at least one gallois field of 2^n members for any n, i.e. you can encrypt blocks of n bits for any value of n greater than 1. (For n=1 this degenerates to ordinary one-time pad, as the first block of key is always 1.)
Suppose you encrypt in 8-bit blocks. (What a coincidence!) Even if the man-in-the-middle knows the message, for each byte he can either leave it alone or make a random choice among the other possible bytes. He's reduced to a malicious noise-generator. (He can pick the worst spot(s) to inject noise, but that's the limit.)
I called this the "GLOPS" cycpher, by analogy with GLOPS codes (a term-of-art for codes composed of arbitrary pairings of typically 5-letter groups with messages). With a GLOPS code knowing "GLOPS" means "attack at dawn" doesn't tell you whether "GLOPT" means "attack at dusk", "send a gross of toilet paper", or anything else. Similarly, with a GLOPS cypher, knowing 0x33 means "A" in this position doesn't tell you anything about 0x34 (except that it isn't "A" - unlike a GLOPS code where GLOPT might ALSO mean "attack at dawn".)
Bantam Dominique roosters crow a four-note song. Once you've heard it as "Happy BIRTHday" you can't NOT hear it that way
This crypto scheme is weak and can be rapidly broken by a brute force approach. It requires a common private key sequence that is shared among multiple users of the software; each user uses this common key to encrypt messages along the matrix. Matrix values are shared amongst all users with a common "serial number prefix." The encrypted "message" that is created is not actually the message; it is a bit sequence that points at positions within the matrix. The software locates each bit position to give a readout of the character at that step. Although the matrix undergoes convolutions as decryption occurs, supposedly making it more "uncrackable," ultimately the reduction of this method requires re-use of a one-time pad (the "virtual matrix"). Reuse of a one-time pad turns an unbreakable encoding into something insecure and breakable. That is ultimately the largest weakness of this algorithm.
Here's the telling bit in the patent scheme (US 6,219,421):
"A message may be secured in accordance with various options specifying an intended audience, including "global," "specific" and "private" options. "Global" allows anyone having a copy of the data security software to decrypt the message providing that person has the correct keys and is able to supply parameters matching those with which the message was secured. "Group" allows the possibility of successful decryption by any of a number of users within a group identified by its members having copies of the software program with a common prefix. "specific" allows only a user having a particular numbered copy of the software program to decrypt. Finally, "private" allows decryption only by the same software copy used to secure the message originally. Without the correct keys and parameters, it is impossible for the message to be unlocked. The present invention further enhances security by allowing definition of a date range where the data can be decrypted correctly, hence preventing lengthy efforts to break the code by brute computational force."
... but the opinions of the New York Times editorial staff certainly are. :)
What is being advertised here is not unbreakable in the sense used by most mathematician or serious cryptographers. (When a cryptographer says unbreakable, s/he means that the system is secure even against an adversary with unlimited computing power.)
Ideal use of a one time pad does have this property. There was a nice breakthrough in the EuroCrypt conference last year, where it was shown that one can obtain similar behavior even with keys that are shorter than the message to be encrypted, as long as the messages that you wish to encrypt are fairly random.
In any case, if you'd like to really understand what is going on here, for goodness' sake don't bother with Schneier's book; have a look at Goldreich's, "Foundations of Cryptography".
These guys are crack smokers, especially Saul Backal. They tried to sell the company I was working on at the time on this VME bullshit. (I have an unopened copy if anybody wants it . . .)
Maybe they came up with something, maybe they didn't. After meeting him and going through their presentation and watching him stumble over some basic questions, I will never trust that company. Some memorable things from that meeting: Bruce Schneier doesn't know what he is talking about. We don't need peer review to know our algorithm is secure. No you can't analyze the source or the algorithm.
For those who may not know, the measure of a truly secure algorithm is that it is secure even when the algorithm is known.
-b
Ron had had a fax from the inventors claiming that the scheme had been endorsed by several well known names in the crypto world who I won't mention for reasons that will become apparent including one of my collegues on a Web standards board.
There wasn't enough information in the press release to determine whether the scheme was bogus so I did the obvious thing and called up one of the people who was alledged to endorse it. Turned out that he did nothing of the sort, he thought it was snake oil but had been asked a different question, who should he talk to to get it adopted as a standard. The snake oil peddlers had then approached Ron saying that 'S. recommended that he talk to them', cleraly implying that S. recommended the scheme.
This matrix scheme looks very much like Power One Time Pad, it has the same million bit key. According to the patent application the scheme appears to be a variant of the playfair cipher which was cracked in WWI.
The competition means absolutely nothing. Any scheme can be made uncrackable if it uses a key length that is greater or equal to the amount of data encrypted. The point is that such schemes are almost completely useless.
The claimed $1 million prize is not convincing experience has shown that companies that make such offers rarely pay them out even if the scheme is broken. In short the actual value of the prize is:
Amount x Probability of Payment x Probability of cracking - cost of time.
The challenge is in any case over. I can't find out how long the challenge was offered for.
As I said before, I can set the rules for a competition so that the competition is unwinnable even though the cipher is broken.
For example consider creating a cipher using the declaration of independence which for the sake of argument we will consider to be perfectly random (it is not). The cipher consists of choosing a random starting point in the declaration and then XORing the plaintext with the declaration to create the ciphertext. I can generate one unbreakable ciphertext simply by making the plaintext shorter than the declaration.
I note that the current challenge text is distributed in a 53Kb Zip file, that would be 424,000 bits or so, considerably less than the alleged million bit key. Give me a few hundred Mb of ciphertext however and we might have a contest.
The wierd thing is the claim to have a contract with the department of Labor to supply an encryption scheme that is not endorsed by NIST. That would appear to breach several procurement guidlines. Also I can't find any record of any contract of that type on the Department of Labor site.
Looking for an Information Security student project suggestion?
Try http://dotcrimeManifesto.com/