The Security Underpinnnings of Cryptography
Nice article on some of the security assumptions we rely on in cryptographic algorithms.
Comments
Chris S • November 24, 2014 3:30 PM
Clearly, security relies on the increasing power of n.
(“underpinnnings”)
Anura • November 24, 2014 3:46 PM
It’s no secret that every single algorithm that we have is “secure” because we don’t know of a way to break it. The reality is that unless we can prove that P != NP (I would knock out a proof over the long weekend, but I’m going to play video games and drink alcohol instead), and then find algorithms with mathematical proofs of security (e.g. we need to prove that no matter what advances we have in the future it’s mathematically impossible to find an algorithm, quantum or otherwise, that can deterministically recover the key in faster than 2128 operations for a sufficiently large key).
Anura • November 24, 2014 3:47 PM
… then we cannot prove that algorithm is actually secure from future advances.
Crack this • November 24, 2014 5:45 PM
Don’t you really need crypto only during transit? Is there any way to crack physical isolation?
Barbie thinks not:
http://www.tinyurl.com/BarbieKnowsSecurity
Clive Robinson • November 24, 2014 5:48 PM
@ Anura,
I’m reminded of the old saw of “In theory it’s secure, but in practice…”
It’s certainly true of AES and the rules of the competition NIST hatched up guided by the NSA, with the result that nearly all the early implementations of AES had gaping side channels leaking information that allowed relativly easy key recovery.
The problem with mathmatical proofs is the limits on what they can actualy prove caused by the scope of the underlying assumptions. If the assumptions are incorrect or incomplete then the resulting proof will be limited accordingly. And realisticaly I don’t believe we even know a fraction of what we need to know, nor I suspect we ever will. After all “define random” in a meaningful and usefull way without slipping into the physics of “many worlds”, “multiverse” or delightfully named “Swiss Cheese” model, along with a side order of “string theory” (all of which to an outsider sounds like those “natural philosophers” have way to much pizza in their diet 😉
The thing is mathmatics is not reality, it’s a tool to help us understand the reality of what we can observe, and if we don’t or cann’t make the right observations the answers it will give us are constrained by the limits of those preceding observations.
There is a saw that you occasionaly hear about learning physics, “You get told a succession of lies, each one closer to the truth without actually getting there”, which is in reality more about the models we build than what is real.
We also make unobjective assumptions about knowledge which boils down to the fact we are more likely to believe something if it looks beautiful or elegant than not. Which whilst apparently being a “good razor” to the truth nobody can give a non arm waving reason why it should be so (which leads to the “looking on the face of God” and similar comments).
But the opposit to “theory and practice” might also be considered to hold. In cryptography we get told about the OTP (and similar) being the only provably secure ciphers. But it fails theoreticaly if it can be shown that “random” or “non determanistic” are as some belive false concepts… However theoreticaly secure or not the OTP will remain as usefull in the practical sense irrespective of if “non determanistic” is a true or false construct. Which is why we have the notion of Crypto Secure Pseudo Random Number Generators, which fall back not on theoretical security but practical security due to the work factor involved.
Which brings us to an interesting observation, the likes of the NSA, GCHQ, et al don’t tend to use crypto they don’t know how to break. There are various reasons quoted by outsiders which may or may not be true, the most usuall being the “known strength” criteria, which is you only trust secrets of a known usefull life to certain grades of cipher. That is battlefields generaly only have secrets that last for very short durations as “first contact with the enemy” gives away position, strength and intention and other tactical information very rapidly. Thus ease of use is of more importance tacticaly than security, is the argument.
However “ease of use -v- security” for even short lived secrets does not realy apply in the modern era where micro computers do the “heavy lift” thus make most crypto systems as easy to use as required irrespective of the cipher complexity or strength.
So why do the likes of the crypto agencies still stick with the idea? Well one explanation is down to “the enemy knows the system”, that is tactical and even strategic cipher systems get lost / stolen in one way or another so why reveal your “best systems” to the enemy? Well that sort of fails to the “security by obscurity” observation, so is there a deeper underlying reason? To which the answer is almost certainly yes as I have outlined in the past.
Thus to some people “proof of insecurity in a non obvious form” might be more important than any “proof of security” to the likes of the NSA, GCHQ, et al.
Daniel • November 24, 2014 6:26 PM
Clive writes, “the thing is mathmatics is not reality, it’s a tool to help us understand the reality”
Math is a language describing reality from the perspective of discreet symbols.
“and if we don’t or can’t make the right observations the answers it will give us are constrained by the limits of those preceding observations.”
A monk asked Joshu, a Chinese Zen master: “Has a dog Buddha-nature or not?”
Anura • November 24, 2014 6:48 PM
@Clive Robinson
You’re absolutely right, I wasn’t addressing side channels – aka “All bets (proofs) are off” – which basically are impossible to fully protect 100% against. Even a simple ARX cipher implemented in hardware might theoretically be vulnerable to side channels, even if we could prove mathematically that it can’t be broken with a chosen plaintext attack in a feasible amount of time.
However, the main point I was making is that we can’t even prove that there does not exist an O(n^k) algorithm that can break an n-bit RSA key (or insert algorithm here) unless we can prove P!=NP. So even without side-channels everything that we know, we don’t really know.
For now, our best bet is complexity at the algorithm level and simplicity at the implementation level. I played around with a design that used a 4×4 matrix in the ring of integers modulo 2^64 for non-linearity in GF(2), using xor for key mixing and rotation so it would achieve diffusion. It tweaked the key schedule with a counter and IV so that every block was encrypted differently. I don’t propose my exact cipher as I did it just for fun (and it was slow), not as a serious proposal, but I think a similar model where it’s implemented without array lookups or branching, just basic assembly instructions, and where every block is encrypted with a different permutation of the key would be something to consider. You can also use it as a stream cipher, in which it has the property where two different blocks can theoretically encrypt to the same value, which is true of a truly random stream but not a block cipher in counter mode.
Ben K • November 24, 2014 9:28 PM
One of the annoyances of provably security cryptography is that it is based on asymptotic analysis, which hides constant factors. It is possible to have a cryptosystem that is provably secure, but which in practice will only be secure for impractically large parameters. Worse, sometimes it is not even clear how to pick parameter sizes — even if a system reduces to a hard problem, you might need much larger problem instances to achieve a comparable security level. The Blum-Blum-Shub PRNG is an example of this — it reduces to the QR problem, but requires significantly larger parameter sizes than would be hard for the QR problem itself.
If you ever want a challenging weekend project, try to work out how to make something like PGP that uses only provably secure constructions, with concrete parameters (if you are a glutton for punishment, do this without relying on the random oracle model or the ideal cipher model).
anonymous • November 24, 2014 11:59 PM
Clive Robinson • November 24, 2014 5:48 PM : “The thing is mathmatics is not reality, it’s a tool to help us understand the reality of what we can observe”
Three statisticians go duck hunting. A duck flies up from the brush. The first statistician shoots too high and misses. The second statistician shoots too low and misses.
As the duck flies away unharmed, the third statistician excitedly shouts “We got it!”
Clive Robinson • November 25, 2014 3:44 AM
@ Anonymous,
An observation, why are such jokes always about “three xxxx”?
For instance,
Q : Why do lecturers go around in threes at The London School of Economics?
A : Easy, one who can read, one who can write, and the third to look after the two intellectuals…
Wael • November 25, 2014 5:33 AM
@Clive Robinson,
An observation, why are such jokes always about “three xxxx”?
Intresting observation! Maybe two is too little and more than three is boring. Or perhaps because ‘3’ is a random unpredictable prime number, also used in Three wishes jokes. Or because it’s 3:33 AM my time 😉
The system on https://www.wuala.com/freemovequantumexchange also supports Unconditional Secure Schemes, see eg. https://www.wuala.com/FreemoveQuantumExchange/Aspects/Security/Programs/SourceCodingExamples for an example proof.
The only necessary additional hardware is one public True Quantum Server, see eg. https://qrng.physik.hu-berlin.de/
Since november 2010 already 1.1 PetaByte True Quantum Randomness has already been delivered.
thevoid • November 25, 2014 7:41 AM
@Clive
i think three is a special number. thruout history it has always been
considered magical eg the trinity (which predates christianity). a three
sided object is the smallest to enclose space (triangle). generally things
balance better with 3 legs. the universe has three spatial dimensions. etc.
tesla was also obsessed with it (he had to perform every task in multiples
of three). he believed if you could figure out the riddle of ‘3’ (and 6 and
9) you would understand the mysteries of the universe. i could probably go
on, there is much more i am not remembering presently..
though this is somewhat aside, you can structure space in triangles instead
of squares.
three also seems to be where our ability to completely grasp something
breaks down ie the three-body problem. where reality intrudes upon our
oversimplifications..
wumpus • November 25, 2014 8:14 AM
“Some of the security assumptions”. Basically the math assumptions. Because they are reasonably good. Of course, then there are the “implementation assumptions” that would make the paper a wee too long (Bruce has published at least two? books on the subject). I still think the assumption “we have a random number generator” is one to consider on the mathematical side, since it is a fundamental assumption of the algorithm and regularly botched in practice.
@Crack this:
Had that been an actual page from the now-notorious Barbie book it would be a really tough criticism. The book was published in 2010, the same year that Stuxnet was discovered. It wasn’t till this year that badUSB was disclosed. Blaming Barbie for out of date information would be like me attacking this blog because my 1st edition Applied Cryptography book recommends the IDEAL cipher. Physical disconnection still remains an incredibly strong tool, and probably more than enough for anyone who gets there computer information from Barbie.
Anura • November 25, 2014 1:54 PM
@Clive/Wael/anonymous/Others
Sometimes it’s two:
Two perfectly rational perfectly informed individuals walk into a bar…
Wael • November 26, 2014 2:23 AM
@Anura,
Sometimes it’s two
Sometimes! The funnier ones are three, though 🙂
Anura • November 26, 2014 3:28 AM
I don’t know about that. Two men walk into a bar; you’d think the second one would have ducked.
Scott Ferguson • November 26, 2014 7:47 AM
@Clive Robinson
<
blockquote>An observation, why are such jokes always about “three xxxx”?
<
blockquote>
I once read that there are only three jokes, annoyingly the author never said what Chaplin considered those three jokes to be. It took me years to figure out what I believe the answer was (presupposing Chaplin wasn’t joking). Apropos of your question – I suspect the answer is that after the first two we detect a pattern, having done so we relax slightly. When we hear the third it’s not a part of the expected pattern, so we receive a little shock – which accentuates the effect of the joke.
The joke itself is one or more of the three jokes, all forms of “shocks”:-
- witty – takes a little gymnastics to “get” i.e. huh? concern we don’t understand it, then relief when we do. We tell ourselves the teller is clever, but actually tell ourselves we are
- unexpected – the WTF shock of being startled (a little scare thrill)
- momentary empathy (phew! glad that wasn’t me the piano fell on – for a moment I was in that blokes, now flattened, shoes)
A similar “humour accentuating” device that works in the same manner (progressive pattern then surprise), might be the rythymic equivalent e.g. shave and a haircut (dah-di-di-dah-di, di-dit).
Well… you asked (and these are just my “wild” theories)
Kind regards
David Leppik • November 26, 2014 10:26 AM
@Clive:
The number three shows up everywhere in stories. Three pigs, three wishes, three brothers on a quest, etc. I present three (!) hypotheses:
-
It’s a pattern of western storytelling, so well-established that breaking it would be distracting.
-
It’s based on innate properties of how the mind processes linguistic/narrative information. Three is a magic number for digesting information.
-
It’s a logical progression, which has as much to do with psychology as logic. The first one establishes a pattern, the second one establishes that it is a pattern (and not just a one-off event), and the third one provides resolution by breaking the pattern.
Wael • November 26, 2014 11:45 AM
@Anura,
[…] would have ducked.
Okay, I stand corrected… It made me laugh 🙂
In that case, “one” is also OK. What did the termite ask the customers when it stepped into a bar?
Is the bartender here?
Scott Ferguson • November 26, 2014 6:38 PM
The number three shows up everywhere in stories.
It could be said that the number seven shows up everywhere in stories. And it would also be true.
1. It’s a pattern of western storytelling, so well-established that breaking it would be distracting.
It’s a pattern of western humour. Create a list of classical western storytellers and look at the “number patterns” they employ. Likewise myths. Like “the age at which major rockstars die” it’s only true if confirmation bias is conflated with deductive logic.
I “suspect” three is prominent number in the history of some religions though.
2. It’s based on innate properties of how the mind processes linguistic/narrative information. Three is a magic number for digesting information.
I suspect you are referring to Herbert Simon‘s belief that three is the “ideal base” for chunking. However there are differing views (and possible cultural influences), 4 is often proposed as a significant number when remembering letters and numbers (chunking), Miller proposed between 5 and 9. “Meaningful” chunks are different – though Simon didn’t “believe” so.
3. It’s a logical progression, which has as much to do with psychology as logic. The first one establishes a pattern, the second one establishes that it is a pattern (and not just a one-off event), and the third one provides resolution by breaking the pattern.
I agree with that theory – (obviously), though I’d add that it also involves physiology.
Kind regards
Wael • November 26, 2014 7:34 PM
@Scott Ferguson,
It’s a pattern of western humour
Not just Western! It’s a pattern in humor.
Mike Amling • November 26, 2014 10:32 PM
Arg! The authors, whom I respect and who should know better, repeat what I call the most widespread myth in cryptography: “… d is an inverse of the exponent e modulo phi(N)”, for RSA. In fact, d may or may not be an inverse of e modulo phi(N), but d must be an inverse of e modulo lambda(N).
Justin • November 26, 2014 11:09 PM
@ Mike Amling
You are talking about the < a href=”http://en.wikipedia.org/wiki/Carmichael_function”>Carmichael function, no doubt. That is interesting, because if N=pq where p and q are distinct odd primes, (as in RSA,) then lambda(N)=lcm(p-1,q-1) and if ed===1 (mod lambda(N)) then of course that would work.
So p and q should be chosen so that if possible (p-1)/2 and (q-1)/2 are relatively prime…
Scott Ferguson • November 27, 2014 12:38 AM
Not just Western! It’s a pattern in humor.
Thanks Wael – I know next to nothing about Asian, South American, or African[2] humour (lacking fluency in the languages), and if you have any references I’d be very grateful[1]. Certainly it’s common pattern throughout “Western” countries. Given my previously stated “belief” about the psychological/physiological reason it’s used in humour it seems reasonable that it would extend to the entire world – but without personal experience I was/am reluctant to propose that.
Kind regards
[1] I’m fascinated by human biases/suggestibility. (pun intended)
[2] The “call and response” in “two bits”/”shave and a haircut” is very similar to that used in much African music I’ve heard, and few Mexicans would be unfamiliar with it. (dah-di-di-dah-di, di-dit) will usually get a strong response ;p.
Wael • November 27, 2014 3:05 AM
@Scott Ferguson,
and if you have any references I’d be very grateful
Your wish is my command!
I’ll give you some examples that you maybe familiar with:
Arabian nights. The Genie and the three wishes? I know of no western Genies 😉 The word is actually of Arabic origins</>
And here are some jokes with “3”… I am sure other cultures and civilizations have similar “stories”
Speaking of Genies, maybe I’ll get to share the “long story” I talked about almost a year ago here
Clive Robinson • November 27, 2014 7:16 AM
With regards “three”,
It’s also the smallest number of objects you can have in a “Rock / Paper / scissors” game.
And perhaps more appropriate for security, the minimum number of “secret sharers” for which “deniability” for leaking exists.
Oddly we talk of “squaring the circle” when it should be triangaling –if such a word exists– the circle for the minimum number of sides.
Mind you just for fun there is a three dimensional shape that exactly fits a square or triangular or circular hole. Which makes me try and think what a four hole / dimensional object would look like, then the headache starts 🙁
David • February 1, 2015 11:52 AM
Nice article on some of the security assumptions. Website and credit card security are major concerns for businesses around the world. It appears to be a cat and mouse game with seo experts and website developers implementing the latest and greatest security protections for their clients, while at the same time, there are people on the other side of the globe trying to hack into our websites.
Always good to read what others assumption on security are.
David
Subscribe to comments on this entry
Leave a comment
Sidebar photo of Bruce Schneier by Joe MacInnis.
bitstrong • November 24, 2014 2:45 PM
Neal Koblitz also wrote a paper back before that titled “The Uneasy Relationship between Mathematics and Cryptography” which ignited a ferocious debate. He is also credited with co-development of Elliptic Curve cryptography. But if you ask him, you will find he really gets excited about an organization he and his wife established to educate poor kids in Central America, especially girls.