back to article We need to talk about mathematical backdoors in encryption algorithms

Security researchers regularly set out to find implementation problems in cryptographic algorithms, but not enough effort is going towards the search for mathematical backdoors, two cryptography professors have argued. Governments and intelligence agencies strive to control and bypass or circumvent cryptographic protection of …

This is why you have to know your threat model. I understand and accept that much of what I consider "encrypted" in my daily internet use, from SSL to something like Signal even, is probably not secure from a determined state actor who is targeting my traffic. There is mathematics knowledge in the Cryptonomicon of the U.S. Intel agencies that has never been revealed and likely only shared maybe with the U.K. given the nature of the relationship there since WWII efforts to defeat encryption.

The resistance to end to end encryption by these entities means they likely can't decrypt en masse probably because of processing requirements, but if you are a target they can spend a little processor time on, assume they have some of these tricks buried in the algorithms to ensure they can reverse most commercially available implementations.

I assume also that other nation-states have similar if not equal capabilities, although they probably have less leverage to incorporate such backdoors into commercial products than the U.S. since the game was pretty much invented here.

19
2
Anonymous Coward

OK, so let's assume I know my threat model.

Now I'm passing encrypted data but the algorithm has got a back-door (mathematical in the is case). Surly the main problem is that once the "key" leaks from government then my messages are no longer secure.

It doesn't matter what the back-door mechanism is, once it becomes known it will be exploited and the exploits will become common place... or have I missed something?

21
0
Silver badge

It is more likely that a deliberate weakness in the algorithm makes it easier ie practical for a nation state to crack rather than just a magic backdoor key that decrypts all the data.

20
1
Silver badge
Black Helicopters

The resistance to end to end encryption by these entities

The resistance to end to end encryption by these entities would be there regardless of whether they can easily intercept & decrypt en masse. A couple of reasons come to mind, and I'm sure there are others:

1. Intercepting & decrypting en masse would be even easier with official backdoors.

2. Dropping opposition to end-to-end encryption would let everyone know you can already intercept & decrypt en masse.

14
0
Black Helicopters

Re: The resistance to end to end encryption by these entities

Exactly. That's why the likes of UK Gov greet about how unfair it is that ordinary folks use cryption like WhatsApp. Because WhatsApp is already well rogered.

6
0
Anonymous Coward

This is why you have to know your threat model. I understand and accept that much of what I consider "encrypted" in my daily internet use, from SSL to something like Signal even, is probably not secure from a determined state actor who is targeting my traffic

Here's a fun question: why would you trust a FreeSSL cert when generation and root cert is in the hands of a US company? Yet they are *everywhere*. Well done..

10
3
Anonymous Coward

Re: fun question

Using FreeSSL or any other CA doesn’t expose your private key, so encryption is unaffected.

Where your choice of CA matters is around trust - will the CA issue a certificate to a third party that allows the third party to impersonate you? HSTS/certificate pinning helps to address this.

8
0
Anonymous Coward

OpenBSD

This makes me wonder if the standard version of OpenBSD is still restricted for usage in the USA?

and in answering my own question:

from the website - https://www.openbsd.org/cvsync.html - and at the very bottom of this link.

"IMPORTANT NOTE: There are a few issues relating to cryptographic software that everyone should be aware of:

The OpenBSD sources are from Canada. As researched by a Canadian individual and as described in the Export Control list of Canada, it is legal to export crypto software from Canada to the world.

However, if you are outside the USA or Canada, you should not fetch the cryptographic sections of the OpenBSD sources from a CVSync server located in the USA. The files in question are...

src/kerberosIV/*

src/kerberosV/*

src/lib/libdes/*

src/lib/libc/crypt/crypt.c

src/lib/libc/crypt/morecrypt.c

src/sys/crypto

src/sys/netinet

src/usr.sbin/afs/src/rxkad/*

Because of the USA ITAR munitions list, crypto software may only be exported to Canada from the USA."

5
0
Anonymous Coward

Whilst it is certainly an interesting piece that has been presented I have to wonder how long it will be before such back-doors, if they exist, become known? If they are there then I would expect that at some point someone gains a conscience and releases the information. It's not like you need to extract reams of data like Snowden, you simply have to publicise "algorithm XYZ has a known exploitable weakness ABC built in". In the end it does seem that all information wishes to be free.

1
0
Anonymous Coward

Re Fun question

Ref Fun Question:

Lots of websites don't use encryption to encrypt, they use it to avoid being demoted/flagged by Google and the other browser manufacturers. Some that do use it for encryption use it only to demonstrate good practice to their customers and to avoid falling prey to the non-state eavesdropper which is fair enough.

I'm not advocating 'casual' use of encryption here (selection / configuration of ciphers, operational management) but there are myriad reasons people use encryption that are not driven by threat modelling, paranoia or distrust in government.

0
0

National products

So what does the UK use? I'd like to know what to recommend instead of AES.

Edit: found it, it's AES

https://www.ncsc.gov.uk/guidance/tls-external-facing-services#profiles

Ha

13
2
Anonymous Coward

Re: National products

@cbars

I suggest you go spend some time in the company of Mr Google before making such stupidly misinformed comments.

What does the UK government use ?

Well, for stuff up to RESTRICTED marking (i.e. annoying if it became public, but not the end of the world), UK gov can use whatever they like, and AES just happens to be handy.

For stuff beyond RESTRICTED that would cause serious headaches if it became public, UK government has a range of secret-squirrel algorithms developed by the great minds of the doughnut-shaped mathematicians.

7
4
Silver badge

Re: National products

"RESTRICTED"? That dates you.

4
1
Anonymous Coward

Re: National products

Well at least I know there is more to UK government encryption than meets the eye.

I can't believe you seriously thought they used AES ... haha !

1
2

Re: National products

Hi A.C.

Bit rude.

Note the "ha" at the end of my post. Think about it for a second.... cool, so we understand each other :)

Chill out, you are a grown human, after all. Me and DuckDuckGo are good friends, and his dad is bigger than your dad.

7
1
Silver badge

Re: National products

In some HMG departments, the Weather forecast is 'restricted' even though it is publicly available.

Those departments classify everything because it creates jobs for the great and worthy.

4
0
Silver badge

Re: National products

When I read

Serious countries (USA, UK, Germany, France) do not use foreign algorithms for high-security needs. They mandatorily have to use national products and standards (from the algorithm to its implementation),” he added.

I wondered whether they use these mysterious other algorithms because they are

1. Stronger, or

2. They have a known flaw in them allowing the country's spy agency to be able to track and decrypt information being leaked to the enemy.

There are valid reasons for both.

3
0
Silver badge
Big Brother

turning it up to 11

So could you not use double pass encryption using algorithms from two (or more) different geo-political blocs (obvs not two that both mandate ROT13...)?

Semi-serious question.

24
1
Silver badge

Re: turning it up to 11

Difficult to say, but based on what we know of chaining hashing algorithms, you may end up with a counterintuitive result of making it easier to crack your ciphertext rather than harder since most encryption works on similar fundamental principles that can result in common modes of exploitation. Even the one-time pad has its weaknesses. They could intercept your pad or determine where the ciphertext is being transmitted and mess with it to de-synchronize you.

14
2
Silver badge

Re: turning it up to 11

"based on what we know of chaining hashing algorithms, you may end up with a counterintuitive result of making it easier to crack your ciphertext"

Nevertheless it's something the theoreticians should be looking at.

The critical point could be key exchange algorithms. It's not going to help if you have a very strong message encryption based on chaining algorithms from multiple sources if the key exchange is vulnerable.

10
0

Useful contribution by Mr Filiol... but I'm sure that safe backdoors could be put into crypto if we just use the right hashtags...

Can I take up my seat in the house of commons now? Or did I prove myself over-qualified by getting his name right?

25
0
Silver badge
Joke

Or did I prove myself over-qualified by getting his name right?

Your application for a seat has been rejected on the grounds that you listened to an expert who is not just clearly an expert but also clearly foreign.

24
0
Meh

Bank Vault locks - cardboard doors

Perhaps the cryptographic equivalent of bank vault locks can be got through by the tiny elite likely to be in the know, but why would anyone bother most of the time ?

Those who hold such high value secrets (i.e. knowledge of algorithm weaknesses) where these exist will want to use them very infrequently and against only the highest value targets for fear of disclosure through honeypot techniques and well tuned intrusion detection systems. It's all basic spy craft - those with high value sources protect these as much as they can which means most who could usefully know are denied access, information gained from these sources has to be very carefully guarded and sanitised prior to declassification and use, and the more use that is made will increase the probability that this kind of source gets disclosed sooner rather than later.

Everything else will involve getting through the cardboard doors - the very many and various implementation weaknesses against which very few systems are likely to be properly protected. So I don't think I'll be rolling my own crypto or combining multiple forms of it or engaging in other obscurity exercises likely to fail when I'm not yet doing the thousand other things I'd have to do (including knowing all my chip technologies and binary device drivers and system software) to avoid the cardboard doors.

The targets I have to defend just aren't valuable enough for me to worry about algorithms no-one has yet discovered unsafe despite large prizes for effective attacks being on offer for those who try to discover these backdoors.

9
1
Silver badge

Re: Bank Vault locks - cardboard doors

The problem is that those who hold the high value secrets might know this but their bosses have a timeline of the next prime ministers questions.

Would it be worth risking a backdoor into AES to get some dirt on the EU Brexit negotators? What about on the DUP - that should be worth a £Bn. Or the 11 rebel MPs ?

7
0

Re: Bank Vault locks - cardboard doors

"The problem is that those who hold the high value secrets might know this but their bosses have a timeline of the next prime ministers questions."

This is probably why those in the know seem unlikely to want to include politicians within their inner circle.

8
0

Backdoors

If there are backdoors put in, who will hold the backdoor keys? Even the NSA has leaks.

10
0
Silver badge

Re: Backdoors

But not necessarily at the top levels, unless you can prove otherwise.

2
2

Re: Backdoors

A leak is a leak is a leak - who cares what level it originates from?

1
1
Silver badge

Re: Backdoors

It determines the sensitivity of the intel which leaks (and by extension how paranoid they are about it). The difference between interfering with routine operations and possibly triggering World War III.

1
0
Black Helicopters

Re: Backdoors

"Even the NSA has leaks."

The likes of the NSA and GCHQ will have millions of secrets - and yet how often are there actual leaks? Next to never. People who apply for these jobs like keeping secrets - they like operating in a grey area of moral ambiguity. These organisations screen people to ensure the likelyhood of those they employ becoming a whistleblower are tiny.

And when leaks do occur - it tends to have life changing consequences for the leaker - think Manning and Snowden.

0
0

This post has been deleted by its author

This post has been deleted by its author

Silver badge

Slightly more complicated as far as AES is concerned

AES is a result of an open competition and was not designed in USA. It was designed in Belgium. While it is theoretically possible that the two cryptography researchers who came up with it are a NSA plant and it has an existing hole, I find this idea a bit too far fetched. Very far fetched. In fact so far fetched that whoever came up with needs to share what they are smoking.

AES and its standardization process, however, are one of the exceptions on the cryptography scene. It happened during a short lull in-between the insanity storms. We have regressed since and quite a bit almost back to the days of the Clipper chip adn 40 bit export level DES.

I suspect the next candidate will be purely USA-based and will follow the same design pattern as the elliptic RNG and several other interesting NSA-advised NIST ideas which appeared after AES.

25
0

This post has been deleted by its author

Silver badge

Re: Slightly more complicated as far as AES is concerned

> known weakness in one of the S-Boxes in AES - this information is a while back and cannot recall the details.

that's the first time I hear this...

> I also recall someone stating that there is a vulnerability when using 256bit keys as opposed to 128bit keys ?

that's a related-key vulnerability (it's easier to perform for AES-256 than it is for AES-128), if your keys come from a PRF (as they do in S/MIME, TLS and IPsec, among others), it's only of academic importance

> With the recent BGP event, perhaps this is an indicator that our security is not as good as we believe ?

BGP has no security, the problem is that it was designed at the time when it was not a problem, the world changed around it - but it's a problem as well known as the lack of security in HTTP

5
0
Silver badge

Re: Slightly more complicated as far as AES is concerned

Weaknesses is too strong a word. Noone has (publicly admitted to) found an exploit, but the simplicity of theb fact that all the keys from all the rounds are derived from the single initial key is incredibly trivial and therefore can feel too good to be true.

As an aside, this is one of the more accessible ways to explain AES.

3
0

This post has been deleted by its author

Anonymous Coward

Hmmmmm

The lack of anyone currently plugging BitCoin (other cryptocurrencies are available) to note this speaks volumes ...

2
0
Silver badge

The problem is normal, human paranoia and the for some value of normal urge to control others and/or monitor everything. We (the people) want our comms to be secure and private. Government has decided that because they can, everything should be slurped and stored "just in case". Some of it gets processed but most comms are just stored or so we've been told.

There is two inherent issues thought... the old "if you have done nothing wrong, nothing to fear".. which is bull since everyone has done at least one or two things wrong. The other is the old "give me five lines and I'll find something to hang you with" thing. Do we want to continue living in the shadow of this? Or do we (here in the States) wish to continue to exercise our Constitutional rights to free and unfettered speech?

I do believe that many of us are paranoid about comms for very valid reasons given the nature of governments (all of them) of late. And then there's the crims and financial gain....

9
0
Anonymous Coward

AES Backdoor...

AES has a back door of sorts. AES was chosen over, say, Blowfish because AES is easier to implement in IoT (wasn't called that back then, but that is the idea). This is public knowledge.

Well, NSA has its own fabs and can make billions of AES decryptors, so you know the routine.

You don't need an idiot Filiol backdoor, just one that the NSA can use. In BEA-1 case, once you know the backdoor, for all intents and purposes the algorithm is broken; the break is simply too easy to implement.

The main problem with Filiol et al premise is that they want a COMMON backdoor that is "easy" to use. This is logically equivalent to a promiscuous key-- once known, game over. There is no magic backdoor method in mathematics that is going to let Joe Plod read encrypted data easily yet prevents Jane Cracker from doing the same once the secret is out.

5
12

This post has been deleted by its author

This post has been deleted by its author

Anonymous Coward

Re: AES Backdoor...

Yes, Reijndael was chosen for AES after an open competition (unless you believe in a Dutch conspiracy) as the best fast secure symmetric algo. You can find all the candidates and the analysis online. Not all processors have AES-specific instructions but there are a lot of MCUs that have them. ECIES is an asymmetric scheme, a very different fish. There are MCUs available for that now. What you will find is ECIES used as an AES key-transport mechanism. And yes, ECC is preferred over RSA in small devices.

4
2

Re: AES Backdoor...

"The main problem with Filiol et al premise is that they want a COMMON backdoor that is "easy" to use"

No. Filiol does not want that. He created a backdoor that is undetected by all current crypto validation tests, then asked "how do you know your current crypto algorithm does not already contain a similar thing?"

23
0

This post has been deleted by its author

Re: AES Backdoor...

I thought that AES was chosen since it was the best performance vs security, but was not chosen to be implemented on small devices due to its low processing requirement.

......

I seem to recall that Elliptic Curve encryption is the chosen encryption for small devices since it is relatively secure and requires minimal processing to encrypt.

AES = symmetric cipher (would use just a single key for encryption and decryption)

Elliptic Curve =assymmetric cipher (uses 2 keys, a private and a public key)

Wonder why you mixed and compared both when they're not the same.

2
0
Silver badge

Re: AES Backdoor...

Question - given the amount of, predominantly US designed, chips containing AES-NI style encryption assisting circuitry is it possible that AES is secure but Intel have kindly implemented the instruction set in such a way to given their buddies at the NSA a leg-up? The management chip and all its flaws also smacks of a helping hand.

1
0
Anonymous Coward

Re: AES Backdoor...

Flemish, not Dutch.

2
0
Anonymous Coward

As I understand it and let me know if I'm wrong.

In crypto the key changes so to have a master key it would also need a part that is always the same which then makes the crypto easy to break because when you initialise the crypto the same key would always be present and mathematically linked to the other key reducing the number of options for that key.

1
5
Anonymous Coward

Thanks for the down votes without explaining why I was wrong.

So I looked up AES myself and rather than as I believed the key rotates between users the key stays the same and shuffles the data round based on the encryption key with the number of shuffles depending on the bit value for the key. That makes sense as to why it's difficult to crack but doesn't explain why it's not difficult to put a back door in? It also makes detecting the backdoor technically impossible as it would be the same process as trying to get the key in the first place so without it being leaked you wouldn't and couldn't know.

So my next question is why can't you use rotating keys where it transforms with each transfer of data and the previous key is used to determine that transformation? Not only would you need to crack the original key but you would need every piece of data between the start and finish to decrypt it all.

Again, if I'm wrong then please discuss as I'm trying to learn. Thanks.

0
1

Page:

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Forums

Biting the hand that feeds IT © 1998–2018