Bruce Schneier
Schneier on Security
A blog covering security and security technology.
« Portrait of the Modern Terrorist as an Idiot | Main | Second Movie-Plot Threat Contest Winner »
June 14, 2007
Perpetual Doghouse: Meganet
I first wrote about Meganet in 1999, in a larger article on cryptographic snake-oil, and formally put them in the doghouse in 2003:
They build an alternate reality where every cryptographic algorithm has been broken, and the only thing left is their own system. "The weakening of public crypto systems commenced in 1997. First it was the 40-bit key, a few months later the 48-bit key, followed by the 56-bit key, and later the 512 bit has been broken..." What are they talking about? Would you trust a cryptographer who didn't know the difference between symmetric and public-key cryptography? "Our technology... is the only unbreakable encryption commercially available." The company's founder quoted in a news article: "All other encryption methods have been compromised in the last five to six years." Maybe in their alternate reality, but not in the one we live in.Their solution is to not encrypt data at all. "We believe there is one very simple rule in encryption: if someone can encrypt data, someone else will be able to decrypt it. The idea behind VME is that the data is not being encrypted nor transferred. And if it's not encrypted and not transferred, there is nothing to break. And if there's nothing to break, it's unbreakable." Ha ha; that's a joke. They really do encrypt data, but they call it something else.
Read the whole thing; it's pretty funny.
They're still around, and they're still touting their snake-oil "virtual matrix encryption." (The patent is finally public, and if someone can reverse-engineer the combination of patentese and gobbledygook into an algorithm, we can finally see how actually awful it really is.) The tech on their website is better than it was in 2003, but it's still pretty hokey.
Back in 2005, they got their product FIPS 140-1 certified (#505 on this page). The certification was for their AES implementation, but they're sneakily implying that VME was certified. From their website: "The Strength of a Megabit Encryption (VME). The Assurance of a 256 Bit Standard (AES). Both Technologies Combined in One Certified Module! FIPS 140-2 CERTIFICATE # 505."
Just goes to show that with a bit of sleight-of-hand you can get anything FIPS 140 certified.
Posted on June 14, 2007 at 1:05 PM • 29 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
Trevor • June 14, 2007 1:22 PM
Let me be the first to admit this post was over my head. I'm guessing you were targeting industry insiders, though, and not people like me, who have a more basic interest in security.
I did get the keywords though. Meganet=snake oil.
art • June 14, 2007 1:38 PM
From the abstract in the patent:
"Rather, the encrypted data consists of pointers to locations within a virtual matrix, a large (arbitrarily large), continuously-changing array of values." ... " 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."
Sounds like electronic book cypher to me.
derf • June 14, 2007 1:46 PM
I forget whose rule it was, but "any information put into a computer can be gotten back out given enough time, inspiration, and access".
Given infinite computing power and enough knowledge, any two-way algorithm CAN be broken by brute force.
This doesn't mean that Meganet's answer holds any water.
I'm guessing by what they have represented on their website: It *sounds* like you store your file with meganet. They take your file, encrypt it, then break it into chunks and put each chunk into a very large array (their website?). They create a "key" which is actually a group of pointers to your various data bits, encrypt it, then send you this key. Your software knows how to decrypt this key, get the data chunks from the array, reassemble them, then decrypt the file.
Neat idea, but I don't see it as any more unbreakable than anything else. In fact, since Meganet isn't guaranteed to exist, the file may no longer be available at some time in the future when you need it.
BLP • June 14, 2007 1:58 PM
@derf:
True, but the idea is that you just have a two hard drives full of identical random data, and then the data you transfer says:
Okay, we're making a 32k file:
The first 1k is Block 42.
The second 1k is Block 50.
The third 1k is Block 27.
etc.
It's pretty efficient in terms of data transfer, but not unbreakable.
BLP • June 14, 2007 2:02 PM
heh. Okay, not *quite* how I described it, as that would require approximately 2 x 10^300 gigs of storage...
32-bit chunks would require around 500MB of storage, which is a little more doable.
Alexandre Carmel-Veilleux • June 14, 2007 2:18 PM
Yet another OTP based algorythm that goes through some convoluted mean to permutate the pad between each use and to extend it to however long the file to encrypt is. They use PRNGs and 2048-bit of key material plus a file that is not generated with a PRNG but rather a mutually agreed upon (or worse, shipped with the software).
They claim their algorythm allows the user to set a date or range of dates during which the file is decryptable... This is done by trusting the RTC of the computer and putting the date or range of date in the *key* somehow.
The sheer number of places where random numbers are being used to do something with the implicit expectation that it will be regenratable by the recipient is incredible, if a number is predictable, why call it random? Are they using rand()?
I guess these guys have never heard of stream ciphers.
Nice quote:
"Most known encryption algorithms operate at the byte level. At the byte level, binary numbers are human intelligible. For example, a byte of a given value may represent a particular text character. Byte-level encryption is therefore susceptible to hacking. The present day security software, by contrast, employs as one of its modules a Bit Level Encryption (BLE) module. Using BLE, a byte is encrypted at the bit level. Since a bit is the smallest possible unit of digital information, by itself, a bit is meaningless. Bit Level Encryption is therefore substantially immune to the type of hacking to which byte level encryption is susceptible."
Adrian Sanabria • June 14, 2007 2:39 PM
And they reference you in the patent! What an honor, eh?
---------------------------------------------
Other References
Schneier, Applied Cryptography 2e, pp. 170-177, 1996.* .
Menezes, et al., Applied Cryptography, p. 172, 1996.* .
Bruce Schneier, Applied cryptography, 2e, John Wiley pp. 183-184, 1996..
Spider • June 14, 2007 3:04 PM
Bruce,
Looking at the website, they have an endorsement by a one
JAIME MILSTEIN, Ph. D., ExaGroup Consulting
take a look below
http://www.meganet.com/Technology/milstein.asp
Do you know any thing about him, or his qualifications to judge the cryptographic strength of the algorithm?
Max • June 14, 2007 3:34 PM
Once in 2002 their VME algorithm was reverse-engineered:
http://www.mail-archive.com/...
Brian • June 14, 2007 3:37 PM
Nice prizes for their hacker challenges. I wonder if these things are even legit.
I love their Patent... It's full of so many great ideas.
Method 1... Generating a random table, looking up data in it, and replacing the unencrypted data with a pointer into the random table. This is the inverse of standard table cyphers where you use the message as a pointer into the table of random data. But then they move one of the items in the table randomly afterward. (???)
Method 2... Subtracting something from both an encrypted and an unencrypted value so that a machine number representation limit is reached... I'm not sure what this is supposed to achieve...
Method 3... Using multiple encryption methods on the data including their method in method 1.
Method 4... Using a file as a communications key
Method 5... Using a session key to scramble a communications key.
Methods 6, 7, 8 and 9... Basically using a bitmask of a serial number to determine who can decrypt a message.
This seems rather pointless to me, but then what do I know.
Method 10... Using a random number to generate a random value which will then be XORed with the data. I am sure that nobody has ever thought of doing that before.
Method 11... Randomly choosing a different encryption method for each "data value".
Method 12... Multiplying one data value by one random number which has a "multiplicative inverse by modulo arithmetic" (It's more complicated than that, but that's the basic idea)
Method 13... Deriving a key from a date limit so that decryption can only be done if you know when it could be decrypted. Like 6-9, this is another WTF?
Method 14... Decryption of Method 13
Method 15... Using a local file on each computer as a key
Method 16... Using a local file that has another purpose as a key. Presumably using something like one of the windows DLLs.
It seems to me that this entire patent is either obvious, pointless, or worthless... Or some combination.
Z.
Joseph • June 14, 2007 4:13 PM
It's Homer Simpson's Company!
"Super Global Hyper Meganet"!
http://www.youtube.com/watch?v=euWniEVhJxk
No wonder they have crypto problems.
dragonfrog • June 14, 2007 4:14 PM
@ Brian
See the post above you - reading that suggests that the challenges were bogus - the posted challenge files, when decrypted with the given passphrases, yielded garbage...
Nick Johnson • June 14, 2007 4:20 PM
@BLP: And in such a scenario, how big would the pointers into the data have to be?
It's neither space-efficient nor hard to crack.
BLP • June 14, 2007 4:56 PM
@Nick:
I think I managed to describe a substitution cypher with a 32-bit (i.e., 4.2 billion letter) alphabet.
You actually would be using a 32-bit value to refer to each 32-bit value... so no, not at all space efficient.
And not a 500MB table, 16GB table to hold all 4.2 billion 32-bit values.
And being just a substitution cypher, falls prey to most of the classical attacks.
Even more reasons why people, like me, who don't know anything about crypto systems shouldn't design them.
sooth_sayer • June 14, 2007 5:09 PM
From their website
"Former CIA Director Woolsey Joins Meganet Board of Advisors. Company Debuts Bomb Jammer That Would Save Lives In Iraq. - Tuesday, March 07, 2006
WASHINGTON, March 7, 2006 – Today Saul Backal, CEO of Meganet Corporation, announced that former Director of Central Intelligence R. James Woolsey has joined the company's Board of Advisors.
“We are pleased that R. James Woolsey has joined the Meganet Board of Advisors,��? said Backal. “Mr. Woolsey brings a wealth of expertise and experience to our company.��?
Meganet Corporation is a privately-held information security ........."
....
What's going on here?
Scott • June 14, 2007 5:13 PM
I like the disclaimer on the certification listing:
"(When operated with the Microsoft® Base Cryptographic Provider validated to FIPS 140-1 under Certificate #238 operating in FIPS mode for the operating systems specified)"
From the security policy:
"The cryptographic module gains security functionality from the Microsoft Enhanced
Cryptographic Provider (MS CAPI RSAENH) module, FIPS 140-1 Certificate #238. The
module utilizes MS CAPI’s implementations of RSA for key wrapping, signing, and
verification, SHA-1 hashing, and key generation based on the FIPS 186-2 Appendix 3.1
with the SHA-based ‘G’ function."
So they don't implement much of the security covered by the FIPS mode of operations.
Worth nothing in the SP:
"The module supports the following Non-Approved FIPS algorithms:
• VME: VME is a Proprietary Encryption Algorithm. This algorithm is not used to fulfill any of the FIPS 140-2 requirements."
A fine example of gaming the system, thanks for the update, Bruce!
Scott • June 14, 2007 5:15 PM
Hm, I wrote "worth nothing" while I meant "worth noting", but maybe my typo was also correct.
Norp • June 14, 2007 8:43 PM
After a quick reading of the patent it appears that they are simply patenting repeated encryption with a stream cipher. I think my favorite part is that they take an entire branching flowchart that is seemingly designed for confusion (Figure 4) to cover
for k = 0 to max(131072, file length)
key[k] = rand()
The entire rest of the patent appears to cover generating an equivalent of X instances of the key[] array and then applying them in series. Also their combiner is consistently modular multiplication which is not bijective across all possible operands.
Unfortunately, they are largely inspecific about the RNG in use.
This design appears to coincide with the reverse-engineered design referenced by Max and published anonymously to Cypherpunks.
Alexandre Carmel-Veilleux • June 14, 2007 11:05 PM
The PRNG in the cypherpunks source code are painfully weak. They used a Linear congruential generators, in fact they lifted the code right out of "Numerical Recipes in C"...
"Method 16... Using a local file that has another purpose as a key. Presumably using something like one of the windows DLLs."
Great, just what we need -- "no you can't put on that Microsoft security patch, because it will render all our encrypted documents unreadable."
Jeesh.
~EdT.
Mike • June 15, 2007 9:35 AM
"Just goes to show that with a bit of sleight-of-hand you can get anything FIPS 140 certified."
Anybody got a cereal box decoder ring?
Rich • June 15, 2007 10:06 AM
Their website main page menu doesn't work in Firefox unless you block the Flash, as it covers the menu dropdowns.
Not their biggest faux pas, granted, but indicative.
Back in the 80's, I implemented encryption on the Commodore 64 using the computer's ROM as a one-time pad (it was 16kB big!). The password was used to compute a starting offset into the ROM, and the rest was simple XOR. (Hey, I was young and didn't have a clue. Give me a break.)
Just in case someone needs prior "art" (in the widest possible sense) to fight their patent. Not that my idea was terribly original anyway.
Stephen • June 16, 2007 3:44 AM
Their matrix encryption must be legit, since their flash animation includes raining kanji symbols as in The Matrix movie.
markm • June 18, 2007 12:46 PM
FP: That's not a "one time pad", because you wouldn't use it only one time. It is a book cypher. In the older (pencil and paper) version of book codes, each agent and the home office would keep a copy of some unexceptional published book, and words would be represented by page #, line #, word #. Usually some simple reformatting and encryption would follow so the transmitted message didn't look like just a list of number triplets.
Cracking a book code must be easier than many things government crackers have accomplished. The Venona decryptions, for instance (of a one-time pad that was used twice) must have been equivalent to reconstructing a completely random book from the encrypted messages. The best advice I can give you about trying to protect your secrets from a government agency is to use something much better than a homemade book code, and not attract so much attention they'll spend millions on decryption. OTOH, an amateur with limited resources might find a well-executed book code too difficult to be worth the effort - unless they can take a shortcut and identify the book by guessing and spying. So FP's greatest vulnerability to amateur crackers probably is that the "book" isn't hard to guess.
X the Unknown • June 18, 2007 1:25 PM
The general "sorta one-time-pad" approach of using vectors into a large "sorta random" data-set does have one advantage: when using it to encrypt data for personal use, it can be made to give a "plausible deniability" key.
The "real" key generates your desired data. The "fake" key works using the same algorithm, to generate a "harmless" dataset (say, the current Tax Code of the United States).
Now, if you are ever hauled into court about the purported contents of your encrypted file, they'll presumably have a harder time proving that "their" decryption is legitimate, since you have a perfectly good counter-example...
This clearly works with XORed OTPs - just have two different CD's that each "decode" the encrypted data differently. The advantage of th vectored-block approach is that the two OTPs are steganographically "hidden" within each other, so it isn't immediately obvious to everyone that there are two of them.
Of course, they will have actually extracted the key from a (probably warantless) keylogger, so the encoding wasn't the weakest link in the first place.
adam • June 20, 2007 3:12 PM
"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"
WOW 1,000,000 bits! That means it can't be cracked in less then 2^1,000,000 operations!
Let's see, what is that in years... take the number of operations, divide by a generous 10 trillion ops/sec, 3600 sec/hr, 24 hr/day, and 365.25 day/year ...
-->2**1e6/10e12/3600/24/365.25
ans =
Inf
INFINITY years! It's uncrackable!
Bob W. • June 30, 2007 10:10 PM
This is presumably the same Meganet which was awarded a $3.8 million no-bid contract by the US Department of Labor and then failed to deliver useful software. As noted on the Government Management subcommittee of the House Oversight Committee :
In February 2002, the Department of Labor awarded a sole-source contract to Meganet to purchase encryption and digital signature software and services. One year later, after spending $3.8 million, the Department determined that the Meganet products would not function properly and acquired similar products from another manufacturer. The Department of Labor Inspector General found “significant irregularities,��? including an apparent conflict of interest, in the award of a sole-source contract to Meganet, and that the decision to abandon the Meganet products and acquire new products was not supported by test results. The Inspector General concluded that the contract “was not properly awarded, modified, or managed."
Subscribe to comments on this entry
Post a comment
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.
|
| Subscribe |
Subscribe via Kindle |
| Blog Menu |
SearchPowered by DuckDuckGoBlog Home Page
Archives by Date2013 J F M A M
Tags  |
| Latest Book |
more books by Bruce Schneier |
Comments