Feeds

back to article Your encrypted files are 'exponentially easier' to crack, warn MIT boffins

Encryption systems may be a lot less secure than we thought, according to new research into the maths underpinning today's cryptography. Boffins in the US and Ireland have managed to poke holes in modern information theory, an area of mathematics used to prove the strength of cryptographic systems before they are trusted and …

COMMENTS

This topic is closed for new posts.

Page:

Compression

Would then a compression algorithm alleviate this weakness, and a perfect compression completely remove it? (The idea here being that compression increases entropy and if perfect up to one)

10
0
Silver badge

Re: Compression

There's no way to completely eliminate the weaknesses inherent in encryption schemes, assuming you want someone, including yourself to be able to read it again. All of encryption is not based around 'unbreakable' but around 'really, really, really time consuming to break'.

Just like any other aspect of security, there is no end game, or perfect, final solution, you only try to keep everything moving forward. As ways to increase decryption speeds of one method are found, another method will have to be developed.

7
2
Silver badge
Paris Hilton

Re: Compression

Or you could just XOR your text exhibiting the correlations with a good PRNG, with the seed the first 4 byte. Then everything hinges on the goodness of the PRNG but assuming it is pretty good, any correlations left will be epsilon-.ific. Actually, isn't that being done anyway?

3
4

Re: Compression

(Sorry, wordy.)

Actually, to increase entropy on a bit of data one would decompress it.

That is, you have 4 kilobytes of data, send 8 kilobytes after encryption. One way of doing this is to cut down on the alphabet used, sending data as fake genome information GATC and so forth or just send as Hex code, the less letters in the alphabet the longer the word size.

Of course this schema is just an add on to existing encypherment; the problem being as I see it is we have simplified the number of actual gross methods.

What happens, I wonder, when a machine runs across some new method?

3
3
Silver badge

@Destroy

So the seed is in the first four bytes? Well then anybody who sees the start of the stream and knows the number of bytes transmitted can decrypt it.

One Time Pads only truly work if they are one time.

1
2

Re: Compression

Compression has been part of the attacks on HTTPS - http://www.theregister.co.uk/2013/08/02/breach_crypto_attack/

0
0
Bronze badge

Re: Compression

"good PRNG"

If it's a pseudo-random number generator, then its output isn't random! That's the very definition of the "pseudo" part of it. That's why a certain brand of Las Vegas blackjack machines was cracked. You want an output that looks as if it is totally random, for a non-random input. Say you have a camera focused on a busy street. Each frame, you XOR the bytes, and that's your new random number. There's no predictable algorithm generating the raw numbers, so the output is random. A pseudo-random number generator uses an algorithm, so the sequence repeats at an interval. That's what makes it pseudo-random.

That's why a plain-text attack is so brutal on encrypted text. Once you get a guess on that key, you narrow your search down until you've got it. We won't need quantum computers to break encryption because we'll have cheap CUDA and Adapteva machines to try out absolute gobs of keys.

4
3
Silver badge
Holmes

Re: @Destroy

> So the seed is in the first four bytes?

Yes, but you don't care about that - because you just want to randomize before encryption. Regeneration of the PRNG stream is of no use to the attacker.

Indeed, I remember some 3DES stream cypher doing exactly that. A long time ago.

3
0
Silver badge
Headmaster

Re: Compression

> Compression has been part of the attacks on HTTPS

On the PROTOCOL. Jeez...

1
0
Silver badge
Headmaster

Re: Compression

> If it's a pseudo-random number generator, then its output isn't random!

Imagine that ... I KNOW THAT. And the good thing is ... it doesn't matter.

> We won't need quantum computers to break encryption because we'll have cheap CUDA and Adapteva machines to try out absolute gobs of keys.

The former are needed for RSA breakage. Your classical parallel processing ain't useful for that. And here we are talking about symmetric crypto.

2
1
Silver badge

Re: Compression

> Actually, to increase entropy on a bit of data one would decompress it.

That sounds like Monty Python's Troupe attacking the Castle of Louis de Lombard.

Just no.

1
0

Re: Compression

All legacy zip files I believe start with the same tree letters "pkz" so that should make it even easier to decrypt

0
0
Silver badge

Re: Compression

There's a neat trick you can do to securely encrypt your messages permanently. First bring up Word and select New Document. Now copy paste (CTRL C) your message into the new document. Then select all the text you want to make secret. Time to find the box called "font" (this might take a while as microsoft have recently hidden away all the controls in ribbons for security). Now use the dropdown in the font box to pick the security option called "wingdings" (or if you want more security, wingdings3). Now save the document to a .doc file. This .doc file is now unreadable/encrypted. You can encrypt a message of any length using this technique.

The only downside is if the NSA have access to Microsoft Word they will be able to decrypt your .doc file. Given recent revelations we have to assume the NSA might indeed have access to Microsoft Word. The only solution is to take a screen copy of your encypted message and paste it into mspaint and save it into .bmp encrypted format. The NSA won't be able to decrypt it now because there is no font box in mspaint (well there is, but microsoft have locked it down to prevent it being used in this way).

If you want to use this technique and are using Linux you will first need to upgrade to Windows Vista or above.

20
6

Re: Compression

I think you are missing the point. Sure, the encrypted data looks like noise. But the *unencrypted* data never looks like noise. Therefore, you can throw away all partial decrypts that look too much like noise as soon as you see it is the case. An encryption scheme is an invertible function, but much effort has been spent looking at the qualities of the right side. But one can trim the set of functions based on the qualities of the left side, also.

3
1
Bronze badge

Re: Compression

As some people have pointed out, compression might actually be a bad thing. An All-or-Nothing Transform (AONT) on the data would mitigate against this attack because as the name suggests the attacker gains nothing from being able to "probably" figure out correlations for small parts of the message.

1
0
Bronze badge
Devil

Re: Compression

RE Don Jefe.

AFAIK the one time pad is uncrackable. But that doesn't really count as "compression/encryption". So I'm not complaining, just being a pain in the... ;)

1
0
Silver badge

One time pad

The beauty is that a message encoded with a load contains not just any message, but every message. You can (and agencies do) transmit the encoded message via short wave radio with the whole world listening in, with the wrong pad they get the wrong message but would never even know it was.

It's actually very revealing to do a proper wartime one time pad encypherment - you can make a pad pair with a set of dice and a lot of patience. Once you do it yourself by hand you see how perfect the encryption is, and why. The reason doing it electronically is less perfect is because you have to share the pads securely at some point, and to do that instead of using impossible to break encryption, we use hard to break encryption.

5
0
Bronze badge

Re: Compression

"Say you have a camera focused on a busy street. Each frame, you XOR the bytes, and that's your new random number. There's no predictable algorithm generating the raw numbers, so the output is random"

Until you put a black back over it and you get a string of 1's.

2
0
Bronze badge
Happy

Re: Compression

Just in case anyone reading through doesn't know: random.org "offers true random numbers to anyone on the Internet". Probably not useful if you're doing frequent encryption, but worth knowing about, even if only for the good ideas about generation of randomness.

2
0
Bronze badge
Happy

Re: Wingding encryption

Ho, ho, yus. V. funny, and funnier because it's already been done, in public, and by people who should really have known better:

SCO further obfuscated the code on this slide by switching it to a Greek font, but that was easily undone. It's entertaining that the SCO folks had no clue that the font-change could be so easily reversed. I'm glad they don't work on my computer security :-)

Source: Analysis of SCO's Las Vegas Slide Show [freerepublic.com, 2003].

4
0
Silver badge

Re: @Destroy

So you're saying randomize and then encrypt normally? (I assumed it was just a dumb OTP encryption scheme.) But it still adds no extra security.

Without your scheme:

1. guess key K

2. attempt decrypt using K.

With your scheme:

1. guess key K.

2. decrypt first four bytes using K, seed PRNG with them.

3. attempt decrypt using K, remembering to xor the bytes with output of PRNG.

Essentially you have replaced encryption function E(xi) with a new function:

E'(xi) = E(xi) xor PRNG(i)

As far as I can see, it doesn't provide any additional protection against brute force attacks. It would provide protection against weaknesses in the encryption - e.g. if the algorithm performs badly when handed a string of zeros.

1
1
Anonymous Coward

Re: @Destroy

There is no need to keep the seed/nonce/IV secret. This should be additional bytes added to the start of your ciphertext, not the first bytes of the ciphertext.

0
1
Black Helicopters

Re: random.org

Who in their right mind would trust random numbers from a complete stranger sent over the net? Even if the site is genuine, how do you know you've not been spoofed by a man in the middle attack? Sure, it's fine for picking your lottery ticket numbers, but not for anything you want to be secure.

5
0
Anonymous Coward

@ Brewster's Angle Grinder Re: @Destroy

As far as I can see, it doesn't provide any additional protection against brute force attacks. It would provide protection against weaknesses in the encryption - e.g. if the algorithm performs badly when handed a string of zeros.

Exactly.. and since the article is about an analytical attack, not key guessing, Destroy All Monster's PRNG suggestion seems perfectly reasonable. In fact, "XOR against a good PRNG" is pretty much a synonym of "encrypt by stream cipher". Not really practical on a block device of course but on a block device any of the decent chaining modes should be employed and will be delivering exactly the same effect anyway.

Until very recently there hasn't been a trustworthy stream cipher but for the kind of pre-encryption suggested I'd imagine even the crappy oldies like Mersenne Twister or Blum Blum Shub should be more than adequate for any conceivable amount of data. For the truly paranoid, there's suddenly an embarrassment ( http://www.ecrypt.eu.org/stream/ ) of high quality stream ciphers to choose from - all designed to deliver ciphertext indistinguishable from true randomness... but as properly applied block ciphers also produce pseudorandom ciphertext such a block cipher would serve just as well as a stream cipher. So this latest scare is another great ad for TrueCrypt and cipher cascades in general: The first cipher serving as the pseudorandomiser which feeds unpredictable pseudorandom cleartext to the second cipher... and on again to the third if required. The first layer of encryption might be "exponentially easier" to attack but to deploy that attack you'd have to get through one or two layers of what is effectively encrypted randomness. Unless you believe in the "evil cipher" bogey man, of course. ;)

2
1
Silver badge

Re: Compression

"All of encryption is not based around 'unbreakable' but around 'really, really, really time consuming to break'."

Mm. at some level you are simply setting random monkeys to write Shakespeare..if your private and unshared secret is as bog as the data itself, or bigger.

And you might never know that what you had in fact decrypted was in fact the original encryption.

For example you might encrypt a plain text message that in itself was an encrypted message. The NSA would stop right there, thinking the job was in fact done.

the deficiencies of most encryptions systems are that they are public private key, and the encryption algorithms are known.

Encrypting your own hard disk using the entire work of 'jude the Obscure' as a key, and an algorithm of your own fiendish devising, would challenge a lot more.

Plug in the memory stick on which algo and key are held, and the computer works. remove it, and its disk is a a jumble of meaningless noise.

0
3
Black Helicopters

Re: Compression

But how do you know that the NSA or GCHQ dosn't monitor all the results random.org generates?

1
0
Anonymous Coward

Re: Compression

But how do you know that the NSA or GCHQ dosn't monitor all the results random.org generates?

It's "protected" by https, so yes, NSA, GCHQ, etc are obviously decrypting and storing it all in case anyone's stupid enough to use it for anything interesting.

0
0
Anonymous Coward

Re: Compression

Anyone know what's happened to http://entropykey.co.uk/ ?

:(

0
0
Silver badge

Re: Compression

Correct. This is why gpg and any serious encryption software includes a compression stage before the encryption - though it's not a very good one, it doesn't have to be.

0
0
Silver badge

Re: But the *unencrypted* data never looks like noise.

So, make the unencrypted data look more like noise before you encrypt it.

Maybe something along the lines of XOR each byte and append that as salt after the data byte. Add more random salt to the noisified file. Then encrypt the data.

0
0
Anonymous Coward

Re: random.org

You can buy your own high speed hardware device for generating true random numbers for only about 1000 Euro !

0
0
Thumb Up

Re: Compression

@nomnomnom

Post of the week!

0
1
Bronze badge

Re: Compression

There's no predictable algorithm generating the raw numbers, so the output is random.

"Predictability" (by which I would assume you mean deterministic behaviour) and randomness are two completely different qualities. A data source may be inherently nondeterministic but not random at all. To qualify as random any value in the target domain must be as likely an output as any other - if there is any weighting or bias in the output it is not random. A lot of real-world systems have been compromised by this very implied assumption - it's unpredictable, therefore it's random. Carry on spouting basic mantras if you want, but yes, "good" PRNGs - that is statistically tested, qualified PRNGs are frequently better for many applications than half-assed attempts at true randomness implemented by those without a firm grasp of even the basics.

2
1

Re: Compression

"Predictability" (by which I would assume you mean deterministic behaviour) and randomness are two completely different qualities... To qualify as random any value in the target domain must be as likely an output as any other - if there is any weighting or bias in the output it is not random. A lot of real-world systems have been compromised by this very implied assumption - it's unpredictable, therefore it's random.

Right on. I've long believed that most modern security flaws are not down to lack of thought or effort but lack of study or lack of knowledge. People spend 10 minutes studying this stuff and imagine themselves to be some kind of expert and begin to spout fundamentally flawed premises and if they were absolute truths. History is littered with examples of how non-random systems have been broken - it was essentially this very issue of a slight bias (not encoding a letter to its original value) that allowed even Enigma to be broken.

1
0

This post has been deleted by its author

Anonymous Coward

Encryption

Does not exist, when is this going to sync in? if it did it would be made illegal or forced to shut down...

3
4
Silver badge

Breaking messages 101

What the OP is probably talking about is the tendency of people to send things like WORD documents through an encryption stream.

WORD documents are FULL of predictable and repetitive bit strings and characters. They include large amounts of macro data and formatting information, all in standard positions. It's child's play to decrypt something if you have most of the plaintext immediately available.

If you are doing encryption properly, you have a code officer who knows these things, and who formats the messages accordingly before transmission. It helps if you use very short message strings and make extensive use of codewords. The military and FCO don't do this for fun, you know.

Sometimes when I am asked to implement a 'really strong' crypto system which I know will be used to send standard emails and documents I wonder if I should tell the client this. And then I think, 'Why bother his head over it? " I'm not being paid to do his risk analysis as well.....

10
2

Re: Breaking messages 101

Very much the reason that Enigma was breakable in practice, unnecessary volumes of traffic and the sending of stereotyped or guessable message content. I mean, sending the daily met reports on the same machines and with the same settings as strategic information...

6
0
Silver badge

Time to get the old enigma machine out again?

This time with 20 wheels.

0
0

70 Years Too Late?

Haven't we known this for a long time? Knowing, or at least being able to narrow down, part of the plain text is how lots of wartime messages were broken.

4
0
Facepalm

Re: 70 Years Too Late?

exactly, how this is noteworthy is beyond me

known plain text attacks are known about for nearly a century now, currently cryptographers are working to make the ciphers secure in situations where the attacker has full control over part of the ciphertext!

0
0
Anonymous Coward

Re: 70 Years Too Late?

This isn't about known plaintext attacks it's about cryptanalysis targeting poor entropy of the cleartext... and yes, it's ancient news that poor entropy of the cleartext makes such attacks feasible but that isn't what's being suggested here. What's being suggested appears to be that such attacks are significantly MORE feasible than some cryptographers previously thought because those cryptographers may have misunderstood or misapplied the theory used to calculate those feasibilities.

Oh and yes again, it's precisely because these attacks *are* so well known and understood that encryption *does* often begin with an initial compression pass to improve the entropy density of the cleartext. Just as suggested above.

1
0
Roo
Silver badge

Ah well

... There goes the neighbourhood ... Could be time to buy shares in Alcan. :P

1
0

I just fail to see how this can not be easily alleviated by a XOR pass with a good prng with the seed as the first bytes in the stream to encrypt, then you would get a stream to encrypt that is close to perfect from an entropy point of view.

2
2
Silver badge

Bletchley broke Fish because the generated XOR data combined with German text showed up statistical profiles they could exploit.

If you send the seed in the stream then the attacker will be able to deduce the XOR stream from the seed, after which they can attack the next layer of the jigsaw.

2
1
Hoe
Happy

Who needs easy to crack?

It would probably be easier to find the NSA's backdoor!

3
0
Silver badge

Re: Who needs easy to crack?

I doubt they have a backdoor. A fire escape or two maybe and possibly an underground car park with elevator.

1
0
Silver badge

Fundamentally insecure

My research into what I call 'Data Packaging' leads me to believe that the universe of numbers that are likely to be used for these things is much, much smaller than you would expect from the number of nominal bits. As a matter of fact, the problem appears to be near intractably difficult. I found this early on and actually registered a domain name whose only purpose was to supply 'good' numbers to support encryption more than a decade ago.

A key that is hundreds of bits long has no realistic chance of being from a truly random sampling of that space unless the process used to get the number is intensive.

0
2
Anonymous Coward

I am not a cryptographer but...

I would have thought a 'good' encryption does multiple passes for precisely this reason. After the first pass entropy must be pretty much optimal.

1
0
Silver badge

Re: I am not a cryptographer but...

It can be counterintuitive. A double pass of ROT-13 for instance gives you cleartext again. Multiple passes of Caesar cyphers don't add any more complexity than a single pass.

4
1

Page:

This topic is closed for new posts.