This white paper describes our current position on quantum key distribution (QKD). QKD is an approach to key distribution that relies on the properties of quantum mechanics to
provide security.
…
For all the practical, business and security reasons given above, at this point in time we:
do not endorse QKD for any government or military applications
advise against replacing any existing public key solutions with QKD for commercial applications
The UK should continue its research and development of QKD systems. But this should be balanced by a growing body of practical QKD vulnerability research, and accompanied by the
development of methods for quantifying and validating the security claims of real-world QKD systems. Responsible innovation should be accompanied by independent validation.
…
Wise words from the NCSC here:while QKD continues to depend upon conventional components that often lack battle-testing they may have vulnerabilities. Furthermore, current
implementations of quantum cryptography fail to address the bigger and harder problems of authentication and identity – key distribution, while not perfectly solved, is still
something that we understand very well… and many real-world attacks target other parts of the process (which QKD does not seek to solve).
There comes a time when people at a technical conference like this need something more relaxing. A change of pace. A shift of style. To put aside all that work stuff and think of
something refreshingly different.
So let’s talk about coding theory. There are perhaps some of you here tonight who are not experts in coding theory, but rather have been dragged here kicking and screaming. So I
thought it would be a good idea if I gave you a sort of instant, five minute graduate course in coding theory.
Coding theorists are concerned with two things. Firstly and most importantly they are concerned with the private lives of two people called Alice and Bob. In theory papers, whenever a
coding theorist wants to describe a transaction between two parties he doesn’t call then A and B. No. For some longstanding traditional reason he calls them Alice and Bob.
Now there are hundreds of papers written about Alice and Bob. Over the years Alice and Bob have tried to defraud insurance companies, they’ve played poker for high stakes by mail, and
they’ve exchanged secret messages over tapped telephones.
If we put together all the little details from here and there, snippets from lots of papers, we get a fascinating picture of their lives. This may be the first time a definitive
biography of Alice and Bob has been given.
In papers written by American authors Bob is frequently selling stock to speculators. From the number of stock market deals Bob is involved in we infer that he is probably a
stockbroker. However from his concern about eavesdropping he is probably active in some subversive enterprise as well. And from the number of times Alice tries to buy stock from him
we infer she is probably a speculator. Alice is also concerned that her financial dealings with Bob are not brought to the attention of her husband. So Bob is a subversive stockbroker
and Alice is a two-timing speculator.
But Alice has a number of serious problems. She and Bob only get to talk by telephone or by electronic mail. In the country where they live the telephone service is very expensive.
And Alice and Bob are cheapskates. So the first thing Alice must do is MINIMIZE THE COST OF THE PHONE CALL.
The telephone is also very noisy. Often the interference is so bad that Alice and Bob can hardly hear each other. On top of that Alice and Bob have very powerful enemies. One of their
enemies is the Tax Authority. Another is the Secret Police. This is a pity, since their favorite topics of discussion are tax frauds and overthrowing the government.
These enemies have almost unlimited resources. They always listen in to telephone conversations between Alice and Bob. And these enemies are very sneaky. One of their favorite tricks
is to telephone Alice and pretend to be Bob.
Well, you think, so all Alice has to do is listen very carefully to be sure she recognizes Bob’s voice. But no. You see Alice has never met Bob. She has no idea what his voice sounds
like.
So you see Alice has a whole bunch of problems to face. Oh yes, and there is one more thing I forgot so say – Alice doesn’t trust Bob. We don’t know why she doesn’t trust him, but at
some time in the past there has been an incident.
Now most people in Alice’s position would give up. Not Alice. She has courage which can only be described as awesome. Against all odds, over a noisy telephone line, tapped by the tax
authorities and the secret police, Alice will happily attempt, with someone she doesn’t trust, whom she cannot hear clearly, and who is probably someone else, to fiddle her tax
returns and to organize a coup d’etat, while at the same time minimizing the cost of the phone call.
A coding theorist is someone who doesn’t think Alice is crazy.
…
I’ve always been a fan of the “expanded universe” of cyptography placeholders Alice & Bob, and this humorous speech –
partially-reproduced here – is a great example of Alice & Bob headcanon at its best.
A few days ago, Ange Albertini retweteed an tweet from 2013
asking for a document that shows its own MD5 or SHA1 hash.
Later, he named such a document an hashquine, which seems to be appropriate: in computing, a quine is a program that prints its own source code when run.
Now, creating a program that prints its own hash is not that difficult, as several ways can be used to retrieve its source code before computing the hash (the second method does not
work for compiled programs):
Reading its source or compiled code (e.g. from disk);
Using the same technique as in a quine to get the source code.
However, conventional documents such as images are likely not to be Turing-complete, so computing their hash is not possible directly. Instead, it is possible to leverage hash
collisions to perform the trick.
This is the method that I used to create the following GIF
MD5 hashquine:
Once I managed to do create it, I figured out that it was not the first GIF MD5 hashquine ever
made, since spq beat me to it.
I will take that opportunity to look at how that one was done, and highlight the differences.
Finally, my code is on Github, so if you want to create your own gif md5 hashquine, you could easily start from there!
Creating a GIF MD5 hashquine
To create the hasquine, the two following ressources were used exhaustively:
The hashclash / fastcoll software to generate MD5 collisions with a chosen prefix;
We say that MD5 is obsolete because one of the properties of a cryptographic
hash function is that it should not be possible to find two messages with the same hash.
Today, two practical attacks can be performed on MD5:
Given a prefix P, find two messages M1 and M2 such as md5(P || M1) and md5(P || M2) are equal (||
denotes concatenation);
Given two prefixes P1 and P2, find two messages M1 and M2 such as md5(M1 || P1) and md5(M2 || P2) are
equal.
To the best of my knowledge, attack 1 needs a few seconds on a regular computer, whereas attack 2 needs a greater deal of ressources (especially, time). We will use attack 1 in the following.
Please also note that we are not able (yet), given a MD5 hash H, to find a message M such as md5(M) is
H. So creating a GIF displaying a fixed MD5 hash and then bruteforcing some bytes
to append at the end until the MD5 is the one displayed is not possible.
Overview
The GIF file format does not allow to perform arbitrary computations. So we can not ask the software used to display the image to
compute the MD5. Instead, we will rely on MD5 collisions.
First, we will create an animated GIF. The first frame is not interesting, since it’s only displaying the background. The second frame
will display a 0 at the position of the first character of the hash. The third frame will display a 1 at that same position. And so on and so forth.
In other words, we will have a GIF file that displays all 16 possibles characters for each single character of the MD5 “output”.
If we allow the GIF to loop, it would look like this:
Now, the idea is, for each character, to comment out each frame but the one corresponding to the target hash. Then, if we don’t allow the GIF to loop, it will end displaying the target MD5 hash, which is what we want.
To do so, we will, for each possible character of the MD5 hash, generate a MD5 collision at some place in
the GIF. That’s 16×32=512 collisions to be generated, but we average 3.5 seconds per collision on our computer so it
should run under 30 minutes.
Once this is done, we will have a valid GIF file. We can compute its hash: it will not change from that point.
Now that we have the hash, for each possible character of the MD5 hash, we will chose one or the other collision “block” previously computed. In
one case, the character will be displayed, on the other it will be commented out. Because we replace some part of the GIF file with
the specific collision “block” previously computed at that very same place, the MD5 hash of the GIF file will not change.
All what is left to do is to figure out how to insert the collision “blocks” in the GIF file (they look mostly random), so that:
It is a valid GIF file;
Using one “block” displays the corresponding character at the right position, but using the other “block” will not display it.
I will detail the process for one character.
Example for one character
Let’s look at the part of the generated GIF file responsible for displaying (or not) the character 7 at the first
position of the MD5 hash.
The figure below shows the relevant hexdump displaying side by side the two possible choices for the collision block (click to display in full size):
The collision “block” is displayed in bold (from 0x1b00 to 0x1b80), with the changing bytes written in red.
In the GIF file formats, comments are defined as followed:
They start with the two bytes 21fe (written in white over dark green background);
Then, an arbitrary number of sub-blocks are present;
The first byte (in black over a dark green background) describes the length of the sub-block data;
Then the sub-block data (in black over a light green background);
When a sub-block of size 0 is reached, it is the end of the comment.
The other colours in the image above represent other GIF blocks:
In purple, the graphics control extension, starting a frame and specifying the duration of the frame;
In light blue, the image descriptor, specifying the size and position of the frame;
In various shades of red, the image data (just as for comments, it can be composed of sub-blocks).
To create this part of the GIF, I considered the following:
The collision “block” should start at a multiple of 64 bytes from the beginning of the file, so I use comments to pad accordingly.
The fastcoll software generating a MD5 collision seems to always create two outputs where the bytes in position 123 are
different. As a result, I end the comment sub-block just before that position, so that this byte gives the size of the next comment sub-block.
For one chosen collision “block” (on the left), the byte in position 123 starts a new comment sub-block that skips over the GIF
frame of the character, up to the start of a new comment sub-block which is used as padding to align the next collision “block”.
For the other chosen collision “block” (on the right), the byte in position 123 creates a new comment sub-block which is shorter in that case. Following it, I end the comment, add
the frame displaying the character of the MD5 hash at the right position, and finally start a new comment up to the comment sub-block used as
padding for the next collision “block”.
All things considered, it is not that difficult, but many things must be considered at the same time so it is not easy to explain. I hope that the image above with the various colours
helps to understand.
Final thoughts
Once all this has been done, we have a proper GIF displaying its own MD5 hash! It is composed of
one frame for the background, plus 32 frames for each character of the MD5 hash.
To speed-up the displaying of the hash, we can add to the process a little bit of bruteforcing so that some characters of the hash will be the one we want.
I fixed 6 characters, which does not add much computations to create the GIF. Feel free to add more if needed.
Of course, the initial image (the background) should have those fixed characters in it. I chose the characters d5 and dead as shown in the image below, so
that this speed-up is not obvious!
That makes a total of 28 frames. At 20ms per frame, displaying the hash takes a little over half a second.
Analysis of a GIF MD5 hashquine
Since I found out that an other GIF MD5 hashquine has been created before mine once I finished
creating one, I thought it may be interesting to compare the two independent creations.
The first noticeable thing is that 7-digits displays have been used. This is an interesting trade-off:
On the plus side, this means that only 7×32=224 MD5 collisions are needed (instead of 16×32=512), which should make
the generation of the GIF more than twice as fast, and the image size smaller (84Ko versus 152Ko, but I also chose to feature my
avatar and some text).
However, there is a total of 68 GIF frames instead of 28, so the GIF takes more
time to load: 1.34 seconds versus 0.54 seconds.
Now, as you can see when loading the GIF file, a hash of 32 8 characters is first displayed, then each segment needed to
be turned off is hidden. This is done by displaying a black square on top. Indeed, if we paint the background white, the final image looks like this:
My guess is that it was easier to do so, because there was no need to handle all 16 possible characters. Instead, only a black square was needed.
Also, the size (in bytes) of the black square (42 bytes) is smaller than my characters (58 to 84 bytes), meaning that it is more likely to fit. Indeed, I needed to consider the case
in my code where I don’t have enough space and need to generate an other collision.
Other than that, the method is almost identical: the only difference I noticed is that spq used two sub-block comments or collision alignment and skipping over the collision bytes,
whereas I used only one.
For reference, here is an example of a black square skipped over:
And here is another black square that is displayed in the GIF:
Conclusion
Hashquines are fun! Many thanks to Ange Albertini for the challenge, you made me dive into the GIF file format, which I probably
wouldn’t have done otherwise.
And of course, well done to spq for creating the first known GIF MD5 hashquine!
It’s a common complaint that cryptography is too hard for regular people to understand – and that all our current cryptographically secure applications are designed for cyborgs and
not humans. While…
It’s a common complaint that cryptography is too hard for regular people to understand – and that all our current cryptographically secure applications are designed for cyborgs and
not humans. While the latter charge may well be correct, I argue that the former most certainly isn’t, because we have been teaching children the basic security principles behind
asymmetric cryptography for probably thousands of years.
What am I talking about? A fairly tail called Rumplestiltskin, which is actually about bitcoin!
You probably heard this fairly tale as a child – but let me refresh your memory.
There is a miller, who drunkenly brags that is daughter can spin straw into gold.
probably, he was posting about his half baked cryptocurrency ideas on
bitcointalk, and creating money “gold” from pointless work “spinning straw” sounds A LOT like bitcoin mining.
Anyway, the king is very impressed with his story.
the king is a venture capitalist?
And wants to see a demonstration, oh and if it doesn’t work he will cut off both their heads.
I have not heard about venture capitalists being quite this evil, but it seems some of them are into this
medieval stuff
Of course, the miller and his daughter don’t actually have the ability to create gold by magic, so they are in big trouble! but just then a magic imp appears.
a hacker, who understands cryptography
The imp says he can spin straw into gold, but for a price: the daughter’s first born child.
in the modern version he wants her naked selfies
It’s a terrible deal, but the alternative is death, so they reluctantly accept. The imp spins straw into gold in 3 increasingly dramatic episodes.
The kind is satisified, and marries the daughter, making her queen.
their startup is aquired
One year later, the first child is born. The imp returns demanding his prize. Because they love their baby, the King and Queen pleads with the imp to get out of the deal. They offer
him all their riches, but the imp is not interested! Desperately, they ask is there any other way? any at all? The imp replies, “Of course not! not unless you can guess my True
Name”
the true name is actually his private key. If they can guess that, the hacker looses his magical power over them
“Okay I will try and guess your name” says the Queen. The imp just laughs! “you’ll never guess it!” “but I’ll give you three days to try!”
The imp skips off into the forrest, and the queen trys to think of his name for 3 days… but can’t figure it out.
The queen trys to brute force his private key. but there is not enough compute in the entire kingdom!
But then, the a messenger is travelling through the forrest, and he happens past a strange little man, dancing around a camp fire, singing:
ha ha ha! te he he! they’ll never guess my private key! just three days! not enough to begin, to guess my name is rumplestiltskin!
Being a messenger, he had a good memory for things he heard. When he arrived back at the castle, he mentioned the curious story to the queen.
the hacker had been careless with his private key
When the imp arrived in the morning, the queen greeted him by name. He was furious! He stamped his foot so hard the ground split open and then he fell into the gaping hole, never to
be seen again. The king, queen, baby lived happily ever after, etc, etc.
they stole all his bitcoin
The simularities between this fairly tale and cryptography is uncanny. It has proof of work, it has private keys, it has an attempted brute force attack, and a successful (if
accidental) end point attack. The essential point about your private key is captured successfully: the source of your magic is just a hard to guess secret, and that it’s easy to
have a hard to guess name, but what gets you in the end is some work around when they steal your key some other way. This is the most important thing.
It’s not a talisman that can be physically protected, or an inate power you are born with – it’s just a name, but it must be an ungessable name, so the weirder the better.
“rumplestiltskin” is the german name for this story, which became wildly known in english after the brothers grim published their collection of folktales in the early 19th century,
but according to
wikipedia there are versions of this story throughout the europe, and the concept that knowing the true name of a magical creature give one power over it is common in mythology
around the world.
How did the ancients come up with a children’s story that quite accurately (and amusingly) explains some of the important things about asymettric cryptography, and yet we moderns
did not figure out the math that makes this possible this until the 1970’s?
Since the villian of the story is magical, really they have chosen any mechanism for the imps magic, why his name? Is this just a coincidence, or was there inspiration?
The astute reader has probably already guessed, but I think the simplest (and most fun) explaination is the best: extraterrestials with advanced cryptosystems visited earth
during prehistory, and early humans didn’t really understand how their “magic” worked, but got the basic idea
Yesterday, a hacker pulled off the second biggest heist in the history of digital currencies.
Around 12:00 PST, an unknown attacker exploited a critical flaw in the Parity multi-signature wallet on the Ethereum network, draining three massive wallets of over $31,000,000 worth
of Ether in a matter of minutes. Given a couple more hours, the hacker could’ve made off with over $180,000,000 from vulnerable wallets.
In this post I’ll explain why quantum computers are useless to find hash function collisions, and how we can leverage this powerlessness to build post-quantum signature
schemes. I’ll then describe a quantum computing model that you can try at home, and one where hash function collisions are easy to find…
In common slang, FTW is an acronym “for the win” and while that’s appropriate here, I think a better expansion is “for the world.”
We’re pleased to announce that we have sponsored the development of TLS 1.3 in OpenSSL. As it is one of the most widely-used TLS libraries, it is a good investment for the overall
health and security of the Internet, so that everyone is able to deploy TLS 1.3 as soon as possible…
All secure crypto on the Internet assumes that the DNS lookup from names to IP addresses are insecure. Securing those DNS lookups therefore enables no meaningful security. DNSSEC does
make some attacks against insecure sites harder. But it doesn’t make those attacks infeasible, so sites still need to adopt secure transports like TLS. With TLS properly
configured, DNSSEC adds nothing…
As the days get longer and the weather gets better, woodland trails and city alleyways alike begin to more-frequently see a particular brand of explorer. Clutching GPS devices (or,
increasingly, mid- to high-end mobile phones), these satellite-guided adventurers shy away from normal people, whom they call “muggles”. Outwardly, this is out of concern for the
continuity of their tiny treasure, but as often as not, it’s because geocachers – and
especially urban geocachers, who often don’t even have the excuse of “getting some fresh air” to justify their hobby – are likely to be seen as a little odd., “You do what
for a hobby? Find lost lunchboxes?”
There’s a “hidden in plain sight” urban geocache in this picture. Can you spot it? (probably not, at this resolution)
I’ve written plenty about geocaching already, but the only important thing to know for this particular anecdote is
how geocaches are rated to indicate how hard they are. There are two scales, each scored from one to five “stars”. The first scale is difficulty, which is
about how challenging the geocache is to find – a 1-star rating means that it’s in plain sight, not camouflaged, etc., while higher ratings might mean that it’s
well-concealed, tiny, disguised as something else, or requires that you solve a puzzle in order to determine where it is. The second scale is terrain, which is about how
challenging the geocache is to get to. A 1-star rating is typically accessible by wheelchair – you certainly don’t need to leave paved roads and footpaths to get it;
higher ratings might mean steep gradients, tree climbing, long hikes, and so on. The highest terrain ratings often mean that specialised skills or equipment are required (for example,
rock climbing gear or a scuba tank).
There it is: that capsule, magnetically-attached to the girder that supports the bridge, is the geocache.
As you can imagine, caches with a 5-star “terrain” rating are rarer, and are especially uncommon in built-up areas. Half-way up cliffs… deep inside caves… miles out to sea: these are
the places you’d expect to see geocaches with the highest level of “terrain” score. So imagine my surprise when I discover GC13WZQ (“Swing Lower”), a geocache with a 1-star “difficulty” rating but a 5-star “terrain” rating, just
a few minutes walk from Oxford City Centre. In the seven years this cache has been in place, it had seen fewer than 110 successful visitors: contrast to its neighbour, GCK57Z (“Swing Low”) – a virtual cache less than 10 metres away – which has seen about six
times as many visits in only 3 years longer. This, I thought, was a cache I had to see.
OxfordLad (who took this photo), and other geocachers claimed that, since early 2014, the cache was made entirely inaccessible by the boarding-up of the sides of the bridge.
Folks recently attempting to find the geocache had reported (OxfordLad, izybuzyfingers, twitcher50) that it had been made inaccessible by the recent addition of boards and barbed wire
to the edges of the bridge. Counter-arguments were raised (sandvika, Mad H@ter) to show that this didn’t make the cache inaccessible; it merely made it
accessible only by boat, which had already been suggested in the “attributes” for the cache.
Only an idiot would attempt a ‘requires boat’ geocache without a boat. Right?
I’m not a believer in the idea that any particular geocache can only be found one particular way. Also: I don’t have a boat. So I decided to make an expedition to
“Swing Lower” my own damn way. Approaching the bridge under which the cache is located, I immediately saw the boards and barbed wire that had been reported by those that had attempted
it earlier in the year. But as I would soon discover, anybody who was put off by a little bit of plywood and the risk of damp feet really wasn’t built of the right stuff to be able to
do what was required next. Put simply: boards and barbed wire are the least of your problems when you’re hunting for GC13WZQ.
It’s not the most conventional way to cross a bridge, I’ll admit.
The bigger challenge was getting to the cache once underneath the bridge. I discovered (perhaps with a little
inspiration from “Jackhuber”) that it was possible to brace myself against a pair of the beams that run the length of the bridge and – facing down – shuffle sideways to get to the
centre of the bridge. I felt acutely aware of the fact that until I got over the central channel, the depth of the water might not be enough to break my fall (especially if I slipped
and fell head-first), but was reassured by the fact that I’d brought fellow ‘cacher and coworker kateevery and she was ready, perhaps not to swim out and get me but at least to call 999, should
the need arise.
This is how Freddie Mercury holds a geocache.
So there you go. To all of you wusses for whom “there are boards and barbed wire in the way” was an excuse: you hadn’t even begun to face the challenge of “Swing Lower”.
I’ve written up a Batman-themed
description of the expedition as part of my log report.
Can you make out the coordinates in this image? No? Maybe it’d help if you looked at geo.danq.me.
This conveniently coincides with the week that I launched my new collection of puzzle geocaches, the Oxford
Steganography Series – four geocaches (GC54F78,
GC54F7B, GC54F7J, GC54F7N) whose coordinates are concealed within images or text, each of which contains a transparency film
that can be used (I made a video showing how) to
determine the coordinates of a fifth, bonus cache.
I’m reasonably pleased with the series, and I’ve been enjoying reading the reports of the ‘cachers who’ve been out hunting for them, so far.
I’m looking for an extension that will automatically redirect-to-HTTPS for particular domains, e.g. to ensure that I’m using the secure version of Wikipedia, etc., whenever I go
there. The HTTPS Everywhere plugin from the EFF does this for Firefox and Chrome; what can I do to make this work in Opera?
The explosion of smartphone ownership over the last decade has put powerful multi-function computers into the pockets of almost
half of us. But despite the fact that the average smartphone contains at least as much personally-identifiable information as its owner keeps on their home
computer (or in dead-tree form) at their house – and is significantly more-prone to
opportunistic theft – many users put significantly less effort into protecting their mobile’s data than they do the data they keep at home.
Too late, little Nokia E7: I’ve got physical access to you now.
I have friends who religiously protect their laptops and pendrives with TrueCrypt, axCrypt, or similar, but still carry around an unencrypted mobile phone. What we’re talking about here is a device that contains all of the contact
details for you and everybody you know, as well as potentially copies of all of your emails and text messages, call histories, magic cookies for social networks and other services, saved passwords, your browsing history (some people would say that’s the
most-incriminating thing on their phone!), authentication apps, photos, videos… more than enough information for an attacker to pursue a highly-targeted identity theft or
phishing attack.
Android pattern lock: no encryption, significantly less-random than an equivalent-length PIN, and easily broken by a determined attacker.
“Pattern lock” is popular because it’s fast and convenient. It might be good enough to stop your kids from using your phone without your permission (unless they’re smart enough to do
some reverse smudge engineering: looking for the smear-marks made by your fingers as you unlock the device; and let’s face
it, they probably are), but it doesn’t stand up to much more than that. Furthermore, gesture unlock solutions dramatically reduce the number of permutations, because you can’t repeat a
digit: so much so, that you can easily perform a rainbow table attack on the SHA1 hash to
reverse-engineer somebody’s gesture. Even if Android applied a per-device psuedorandom salt to the gesture pattern (they don’t, so you can download a prefab table), it doesn’t take long
to generate an SHA1 lookup of just 895,824 codes (maybe Android should have listened to Coda Hale’s advice and used BCrypt, or else something better still).
An encrypted iPhone can be configured to resist brute-force attacks by wiping the phone after repeated failures, which replaces one security fault (brute-force weakness) with another
(a denial of service attack that’s so easy that your friends can do it by accident).
These attacks, though (and the iPhone isn’t bulletproof, either), are all rather academic, because they are
trumped by the universal rule that once an
attacker has physical access to your device, it is compromised. This is fundamentally the way in which mobile security should be considered to be equivalent to computer security.
All of the characteristics distinct to mobile devices (portability, ubiquity, processing power, etc.) are weaknesses, and that’s why smartphones deserve at least
as much protection as desktop computers protecting the same data. Mobile-specific features like “remote wipe” are worth having, but can’t be relied upon alone – a wily attacker
could easily keep your phone in a lead box or otherwise disable its connectivity features until it’s cracked.
The bottom line: if the attacker gets hold of your phone, you’re only as safe as your encryption.
The only answer is to encrypt your device (with a good password). Having to tap in a PIN or password may be less-convenient than just “swipe to unlock”, but it gives
you a system that will resist even the most-thorough efforts to break it, given physical access (last year’s
iPhone 4 vulnerability notwithstanding).
It’s still not perfect – especially here in the UK, where the RIPA can be used (and has been used) to force key surrender. What we really need is meaningful, usable
“whole system” mobile encryption with plausible deniability. But so long as you’re only afraid of identity thieves and phishing scammers, and not
being forced to give up your password by law or under duress, then it’s “good enough”.
Of course, it’s only any use if it’s enabled before your phone gets stolen! Like backups, security is one of those things that everybody should make a habit of thinking
about. Go encrypt your smartphone; it’s remarkably easy –
This blog post is about password security. If you don’t run a website and you just want to know what you should do to protect yourself, jump to the
end.
I’d like to tell you a story about a place called Internetland. Internetland is a little bit like the town or country that you live in, but there’s one really important difference: in
Internetland, everybody is afflicted with an unusual disorder called prosopagnosia, or “face-blindness”. This means that, no matter how hard they try, the inhabitants of Internetland
can’t recognise each other by looking at one another: it’s almost as if everybody was wearing masks, all the time.
Denied the ability to recognise one another on sight, the people of Internetland have to say out loud who they are when they want to be identified. As I’m sure you can imagine, it’d be
very easy for people to pretend to be one another, if they wanted. There are a few different ways that the inhabitants get around that problem, but the most-common way is that people
agree on and remember passwords to show that they really are who they claim to be.
Alice’s Antiques
Alice runs an antiques store in Internetland. She likes to be able to give each customer a personalised service, so she invites her visitors to identify themselves, if they like, when
they come up to the checkout. Having them on file means that she can contact them about special offers that might interest them, and she can keep a record of their address so that the
customer doesn’t have to tell her every time that they want a piece of furniture delivered to their house.
Some of Alice’s Antiques’ antiques.
One day, Bob came by. He found a nice desk and went to the checkout to pay for it.
“Hi,” said Alice, “Have you shopped here before?” Remember that even if he’d visited just yesterday, she wouldn’t remember him, so crippling is her face-blindness.
“No,” replied Bob, “First time.”
“Okay then,” Alice went on, “Would you like to check out ‘as a guest’, or would you like to set up an account so that I’ll remember you next time?”
Bob opted to set up an account: it’d only take a few minutes, Alice promised, and would allow him to check out faster in future. Alice gave Bob a form to fill in:
Bob filled in the form with his name, a password, and his address. He ticked the box to agree that Alice could send him a copy of her catalogue.
Alice took the form and put it into her filing cabinet.
The following week, Bob came by Alice’s Antiques again. When he got to the checkout, Alice again asked him if he’d shopped there before.
“Yes, I’ve been here before,” said Bob, “It’s me: Bob!”
Alice turned to her filing cabinet and pulled out Bob’s file. This might sound like a lot of work, but the people of Internetland are very fast at sorting through filing cabinets, and
can usually find what they’re looking for in less than a second. Alice found Bob’s file and, looking at it, challenged Bob to prove his identity:
“If you’re really Bob – tell me your password!”
“It’s swordfish1,” came the reply.
Alice checked the form and, sure, that was the password that Bob chose when he registered, so now she knew that it really was him. When he asked for a set of
chairs he’d found to be delivered, Alice was able to simply ask, “You want that delivered to 1 Fisherman’s Wharf, right?”, and Bob just nodded. Simple!
Evil Eve
That night, a burglar called Eve broke into Alice’s shop by picking the lock on the door (Alice never left money in the till, so she didn’t think it was worthwhile buying a very good
lock). Creeping through the shadows, Eve opened up the filing cabinet and copied out all of the information on all of the files. Then, she slipped back out, locking the door behind her.
Alice’s shop has CCTV – virtually all shops in Internetland do – but because it wasn’t obvious that there had been a break-in, Alice didn’t bother to check the recording.
Alice has CCTV, but she only checks the recording if it’s obvious that something has happened.
Now Eve has lots of names and passwords, so it’s easy for her to pretend to be other Internetlanders. You see: most people living in Internetland use the same password at most or all of
the places they visit. So Eve can go to any of the other shops that Bob buys from, or the clubs he’s part of, or even to his bank… and they’ll believe that she’s really him.
One of Eve’s favourite tricks is to impersonate her victim and send letters to their friends. Eve might pretend to be Bob, for example, and send a letter to his friend Charlie. The
letter might say that Bob’s short on cash, and ask if Charlie can lend him some: and if Charlie follows the instructions (after all, Charlie trusts Bob!), he’ll end up having his money
stolen by Eve! That dirty little rotter.
So it’s not just Bob who suffers for Alice’s break-in, but Charlie, too.
Bob Thinks He’s Clever
Bob thinks he’s cleverer than most people, though. Rather than use the same password everywhere he goes, he has three different passwords. The first one is his “really secure” one: it’s
a good password, and he’s proud of it. He only uses it when he talks to his bank, the tax man, and his credit card company – the stuff he thinks is really important. Then
he’s got a second password that he uses when he goes shopping, and for the clubs he joins. A third password, which he’s been using for years, he reserves for places that demand that he
chooses a password, but where he doesn’t expect to go back to: sometimes he joins in with Internetland debates and uses this password to identify himself.
Bob’s password list. Don’t tell anybody I showed you it: Bob’ll kill me.
Bob’s approach was cleverer than most of the inhabitants of Internetland, but it wasn’t as clever as he thought. Eve had gotten his medium-security password, and this was enough to
persuade the Post Office to let her read Bob’s mail. Once she was able to do this, she went on to tell Bob’s credit card company that Bob had forgotten his password, so they sent him a
new one… which she was able to read. She was then able to use this new password to tell the credit card company that Bob had moved house, and that he’d lost his card. The credit card
company promptly sent out a new card… to Eve’s address. Now Eve was able to steal all of Bob’s money. “Muhahaha!” chortled Eve, evilly.
But even if Bob hadn’t made the mistake of using his “medium-security” password at the Post Office, Eve could have tried a different approach: Eve would have pretended to be Alice, and
asked Bob for his password. Bob would of course have responded, saying “It’s ‘swordfish1’.”
Then Eve would have done something sneaky: she’d have lied and said that was wrong. Bob would be confused, but he’d probably just think to himself, “Oh, I must have given Alice a
different password.”
“It must be ‘haddock’, then,” Bob would say.
“Nope; wrong again,” Eve would say, all the while pretending to be Alice.
“Surely it’s not ‘h@mm3rHead!’, is it?” Bob would try, one last time. And now Eve would have all of Bob’s passwords, and Bob would just be left confused.
Good Versus Eve
What went wrong in Internetland this week? Well, a few things did:
Alice didn’t look after her filing cabinet
For starters, Alice should have realised that the value of the information in her filing cabinet was worth at least as much as money would be, to the right kind of burglar. It was easy
for her to be complacent, because it wasn’t her identity that was most at risk, but that of her customers. Alice should have planned her security in line with that realisation:
there’s no 100% certain way of stopping Eve from breaking in, but Alice should have done more to make it harder for Eve (a proper lock, and perhaps a separate, second lock on the filing
cabinet), and should have made it so that Eve’s break-in was likely to be noticed (perhaps skimming through the security tapes every morning, or installing motion sensors).
But the bigger mistake that Alice made was that she kept Bob’s password in a format that Eve could read. Alice knew perfectly well that Bob would probably be using the same password in
other places, and so to protect him she ought to have kept his password encrypted in a way that would make it virtually impossible for Eve to read it. This, in combination with an
effort to insist that her customers used good, strong passwords, could have completely foiled Eve’s efforts, even if she had managed to get past the locks and CCTV un-noticed.
Here in the real world: Some of Alice’s mistakes are not too dissimilar to the recently-publicised mistakes made by LinkedIn, eHarmony, and LastFM. While
these three giants did encrypt the passwords of their users, they did so inadequately (using mechanisms not designed for passwords, by using outdated
and insecure mechanisms, and by failing to protect stolen passwords from bulk-decryption). By the way: if you have an account with any
of these providers, you ought to change your password, and also change your password anywhere else that uses the same password… and if this includes your email, change it everywhere
else, too.
Bob should have used different passwords everywhere he went
Good passwords should be long (8 characters should be an absolute minimum, now, and Bob really ought to start leaning towards 12), complex (not based on a word in any dictionary, and
made of a mixture of numbers, letters, and other characters), and not related to you (dates of birth, names of children, and the like are way out). Bob had probably heard
all of that a hundred times.
But good passwords should also be unique. You shouldn’t ever use the same password in two different places. This was Bob’s mistake, and it’s the mistake of almost everybody
else in Internetland, too. What Bob probably didn’t know was that there are tools that could have helped him to have a different password for everybody he talked to, yet still
been easier than remembering the three passwords he already remembered.
Here in the real world: There are some really useful tools to help you, too. Here are some of them:
LastPass helps you generate secure passwords, then stores encrypted versions of them on the Internet so that you can get at them
from anywhere. After a short learning curve, it’s ludicrously easy to use. It’s free for most users, or there are advanced options for paid subscribers.
KeePass does a similar thing, but it’s open source. However, it doesn’t store your encrypted passwords online (which you might
consider to be an advantage), so you have to carry a pen drive around or use a plugin to add this functionality.
SuperGenPass provides a super-lightweight approach to web browser password generation/storing. It’s easy to understand and
makes it simple to generate different passwords for every site you use, without having to remember all of those different passwords!
One approach for folks who like to “roll their own” is simply to put a spreadsheet or a text file into a TrueCrypt (or
similar) encrypted volume, which you can carry around on your pendrive. Just decrypt and read, wherever you are.
Another “manual” approach is simply to use a “master password” everywhere, prefixed or suffixed with a (say) 4-5 character modifier, that you vary from site to site. Keep your
modifiers on a Post-It note in your wallet, and back it up by taking a picture of it with your mobile phone. So maybe your Skype suffix is “8Am2%”, so when you log into Skype you type
in your master password, plus that suffix. Easy enough that you can do it even without a computer, and secure enough for most people.
A few months ago, I spent one lunchtime writing a One-Time Pad Encryption/Decryption Engine in
Javascript. I’d meant to blog about it at the time, but I forgot, but I came across it again today and thought it was cool enough to share with you all.
If you already appreciate why that’s cool, go play with it. If you don’t, allow me to explain.
What is a One-Time Pad and why is it awesome?
One-time pads are a form of cryptography which are simple enough to do by hand (you don’t need a computer, but it helps), versatile enough to transport any message, and – this is the
clever part – completely unbreakable.
Yes, completely unbreakable. It doesn’t matter if you have a billion supercomputers and a billion years, a one-time pad is mathematically sound. So long as it’s used properly,
it’s unbreakable, but it’s the difficulty and discipline required in using them properly – as well as difficulties in finding secure ways to share keys over long distances – that makes
them impractical for widespread use.
They did, however, see a lot of use in espionage during the Second World War and the Cold War, and continue to be used today for some diplomatic messages, as well as occasionally by
particularly paranoid civilians.
So what’s the story?
You’re probably familiar with the concept of a Caesar Cipher – you may have
even played with them as a child – which is perhaps most-often seen nowadays in the form of ROT13.
Put simply, a caesar cipher “rotates” letters through the alphabet, so perhaps A becomes B, B becomes C, C becomes D, and so on (in this example, Z would become A). So my message “IF
YOU READ THIS YOU ARE GAY” becomes “JG ZPV SFBE UIJT ZPV BSF HBZ”. I can send that message to you, having already agreed with you the code, and you can roll each letter back by one (so
A becomes Z, B becomes A, etc.), to get back the original message.
This is fundamentally flawed and offer no real security at all, of course. But suppose we made a couple of enhancements to our plain old Caesar Cipher. First, let’s add some punctuation
to our alphabet (space, full stop, comma – we’ll treat these as letters in their own right which come after ‘Z’). Then, instead of rotating each letter in our message the same number of
steps around, we’ll vary it. So let’s agree that the first letter will rotate 3 places, the second by 18, and the third by 11: then the fourth by 3 again, the fifth by 18, the sixth by
11, and so on. If we encode the same message now, we get:
I becomes L (rotated by 3)
F becomes X (rotated by 18)
[space] becomes I (rotated by 11)
Y becomes a comma (,)
And so on. Suddenly that’s a lot more secure than our plain old Caesar Cipher! Congratulations: you just invented the Vigenère Cipher. Unfortunately for you, it’s almost 500 years old already. Even more unfortunately, it’s still not very secure.
It’s fine for passing notes in class, but it won’t do for sending orders to your agent on the other side of the Iron Curtain!
How is a One-Time Pad different?
The “key” to the cipher we used above is 3, 18, 11, and the problem is that the key ends up being re-used (repeated) throughout the course of the message. If the message was the word
“ELF” (encrypted to “HAQ”), and we agreed never to use that same key again, then anybody who intercepted the message – even if they knew we were using a Vigenère Cipher – wouldn’t know
what we’d said, except to say that it had three or fewer letters. We could equally have said “MAN” (using the key 8, 17, 8), “EAT” (using the key 0, 17, 14), or “EGG” (using the key 0,
23, 1). If we ever used the same key – 3, 18, 11 – again, our code would become vulnerable to frequency analysis, which is a technique for working out what the key might be based on the likelyhood of particular letters or
words (especially common ones) being used in combination.
It’s pretty easy to see how to fix this: all you have to do is to choose a key that is at least as long as the message you want to encrypt, and never reuse the key.
This is how a one-time pad works. Suppose you and I agree a series of numbers, like this: 64191 25746 89891 93406 33604 89879. You keep a copy, and I keep a copy, and we never
tell anybody else those numbers, or the order in which they appear.
When I want to send you a message, I first convert that message into a series of numbers, using a codebook or codetable. In the example codetable below – which has been optimised for
the English language – the most-commonly used letters are represented by one digit each, while less-frequently used numbers are represented by two digits. So the message “STEAL THE
PANTIES” becomes 82832 17890 83752 80148 33282. It’s important to remember that this still isn’t encrypted; it’s just encoded: turned into a format suitable for encryption.
If we often talk about “panties” in our messages (and who doesn’t?), we might add that word to our codebook to make it faster to write: for example, we might assign it the code “11” –
in the table above, the prefix “99” means “look it up in the codebook”, so instead of writing “panties” as “80148 33282”, we’d write it as “9911” – cold war spies had whole dictionaries
of most-common words assigned to numbers to make them shorter to write out! That makes our message: 82832 17890 83752 99110. In this particular implementation, we add a padding zero to
make it up to a nice round block of five digits.
Next, we encrypt the message using our pre-arranged secret key, 64191 25746 89891 93406 33604 89879. To do this, we just take each digit in the message and add it to each digit in the
key, ignoring any “tens” column. So 8 plus 6 is (1)4, 2 plus 4 is 6, 8 plus 1 is 9, and so on, to get our encrypted message.
All you have to do to decode it is run the whole thing backwards. From each digit in the message, deduct the corresponding value in the key – if you get any negative numbers, just add
10 to them so that they’re not negative any more. Then run the resulting encoded number through your codebook to get back the secret message.
In practice, using a codebook is optional, but very-highly recommended. In the basic codebook I’ve provided with my implementation, the word “condition” goes down from being
“71547 23833 54” to just “99114 7”. A well-designed codebook will contain not only common words in your language, but anticipated words for the things that you expect to talk about in
your messages (like “MISSION”, “CAPTURED”, and – of course – “PANTIES”).
Messages encrypted using one-time pads are so secure that it’s safe to send the message itself completely in the clear, which is exactly what we used to do. Especially during the cold
war, but still today (and increasingly), governments have been able to communicate with spies in foreign countries simply by broadcasting strings of numbers over conventional radio,
from what are called numbers stations by radio enthusiasts (and also by
conspiracy theorists, of course). Of course, nowadays it’s perhaps more-feasible to send many kinds of messages by e-mail – and there are a number of one-time pad systems optimised for
fully-computerised use, although there exists a greater risk of being traced online than by simply tuning in a radio.
Now: go have a play!
Click the link – One-Time Pad Encryption/Decryption Engine in Javascript – to try out my
one-time pad engine and encrypt and decrypt a few messages of your own. It’s quite deliberately written in a way which does not communicate with my server at all, once the program has
downloaded (unplug your computer from your Internet connection if you like, and you’ll find that it still works), so I’m not able to see what you’re encrypting. You can use your own
codebook if you like, and the entire source code for the page should be reasonably easy to read, if you’re that way inclined. Have fun!
However, you certainly shouldn’t actually use it for passing secret messages around: read the caveats below if you can’t work out why for yourself!
Caveats
The first challenge with using one-time pads is finding a good secret key. People have used all kinds of things – patterns in music, entire text of books – that are all flawed and
imperfect. The only secret key good enough for use in a one time pad is a cryptographically-random set of number. The random numbers generated by a conventional computer are not good
enough: I suggest you get yourself five ten-sided dice and roll them all simultaneously, writing down the numbers which come up as they appear in front of you from left to right.
Repeatedly. Yes, this is a boring process. For convenience, my implementation will generate random numbers for you, if you like, but they’re not good enough for actual use. The United
States broke a German one-time pad in 1944 because the machine they used to generate the random numbers was not sufficiently random.
The second challenge is getting your secret key to the friend to whom you want to send secret messages. This must be done in person. If you transmit it by any other
medium, it could already have been compromised. Even if you encrypt it, the system can only be considered to be as good as that encryption, which defeats the point entirely.
During the cold war, KGB spies were issued with tiny keybooks like the one shown on the right. A book this small can be hidden in any number of places, as anybody who’s been geocaching knows! After receiving and decoding a message, the page used to provide the key could easily be burned,
eaten, or otherwise destroyed.
A third challenge comes from the fact that no key must ever be re-used. As soon as a key is re-used, the code is no longer unbreakable. A combined U.S effort broke a 1945 Soviet
one-time pad after the same key was used several times: once the U.S. knew something about the contents of some of the messages (they contained leaked British intelligence), they were
able to partially break the key.
There must be no way for an unauthorised party to observe the plaintext before it has been encrypted or after it has been decrypted. Your desktop PC won’t do, because your enemy can
read your screen through the wall, install
a keylogger, or just peep through your window!
And, of course, as with all cryptography, your system is only as secure as the people involved. If your friend can be bribed, blackmailed, tricked or tortured into giving up
information, the system fails. Obviously to maximise your ability to protect your system you should issue different keybooks to each of your trusted friends – this also helps to prevent
them from talking to one another and organising a coup against you!
This is how a one-time pad works. Suppose you and I agree a series of numbers, like this: 64191 25746 89891 93406 33604 89879. You keep a copy, and I keep a copy, and we never
tell anybody else those numbers, or the order in which they appear.
In practice, using a codebook is optional, but very-highly recommended. In the basic codebook I’ve provided with my implementation, the word “condition” goes down from being
“71547 23833 54” to just “99114 7”. A well-designed codebook will contain not only common words in your language, but anticipated words for the things that you expect to talk about in
your messages (like “MISSION”, “CAPTURED”, and – of course – “PANTIES”).
