Cryptography

Quantum Cryptography (a background)

In this article I hope to illustrate some of the ideas behind the strange topic of Quantum Cryptography, though I won't be discussing cryptography itself, that comes later - just the necessary physics. First we must consider the nature of light (this can be generalised to any particle once we get all quantum mechanical, but let's stick with light for now).

Classically, light can be thought of as a wave. It's a transverse wave meaning that the 'oscillations' of the thing doing the waving are at right angles to the direction that the wave is travelling in. Another example of transverse waves are waves on the surface of water.

Picture showing waves horizontally and vertically polarised

These oscillations defined a 'plane' in which the waves are oscillating, and this plane can be oriented at any angle. Waves on the surface of water are vertically polarised. Though the plane of polarisation can be any angle, it is convenient to pick two planes which are at 90 degrees to each other. We can express any polarisation by talking about how much of each is present. Hence, we can talk of 'vertical' and 'horizontal' polarization. Here is an applet which demonstrates this.

You can see polaroid filters in action if you have a pair of polaroid glasses (often sold as 'anti-glare'). Find a light shining on a surface such as a desk. You don't want to be 'square on' to the surface, the light should be bouncing at an angle, 45 degrees is a good start. For the most obvious effect, don't use a mirror.

Look at the surface through your polaroid glasses, then rotate them 90 degrees, and keep looking. You should see the glare change in brightness. You will find that polaroid glasses are best at reducing glare from horizontal reflections when held normally. (See: Brewsters' Angle)

If you use your glasses for driving, you may find that you have trouble with the LCD screens on petrol pumps, this is because the LCD screen relies on polarising light!

If you take a polarised filter, this will ensure that all the light which passes through has the same polarisation. Classically, if a particular wave comes in with an amplitude of A, and a plane of polarisation at angle θ to the plane of polarisation, the amount of light which emerges has amplitude Acosθ.

Picture showing the effect of multiple polarising filters

Suppose that we have two polaroid filters. Unpolarised light hits the first and emerges polarised. It emerges with amplitude, A (on average). This light hits the second filter. The two filters have an angle θ between their planes of polarisation - the amount of light which emerges is Acosθ. So, if the filters are aligned, the second filter has no effect. If it is turned 90 degrees, no light emerges (note, if it is turned 180 degrees, it has no effect - the sign of the amplitude doesn't matter, it's not 'negative light'!)

(Note that for real filters, there is a little scattering, so 90 degrees doesn't give total black, and zero degrees does give some reduction in intensity)

Imagine we have two filters, aligned at 90 degrees. No light emerges. This is because the cosine of 90 degrees is zero.

Now, insert a filter at 45 degrees between the two. What happens? More 'stuff' can only make the amount of light getting through smaller, right? The cunning reader will have assumed that I wouldn't ask the question if the answer were obvious. Some light emerges. In this circumstance, two filters allows through less light than three.

This counterintuitive result is easily explained. Imagine the second filter is at an angle of θ compared to the first.  The third is at 90 degrees. In other words, the angle from the second is (90-θ). From the first filter, we have light with amplitude Acosθ. This is then reduced by the third filter by cos(90-θ). The overall light intensity is now Acosθ.cos(90-θ) or Asinθcosθ, this reduces to A(sin2θ)/2. In other words, we get most light out when sin2θ=1, or when 2θ=90°, or when θ=45° 

The newly inserted second filter is changing the polarisation of the light.

Take your time on polarisation, it's important that you understand the above if you're to comprehend subsequent articles. We'll put this aside for a while, though - the next step is to talk about photons.

Mythbusters Gagged

Adam Savage, of the excellent 'Mythbusters' programme(*) reports that they were going to do a segment on RFID chips only to have the lawyers descend from Visa, American Express etc.

Texas Instruments comes on along with chief legal counsel for American Express, Visa, Discover, and everybody else... They were way, way outgunned and they absolutely made it really clear to Discovery that they were not going to air this episode talking about how hackable this stuff was, and Discovery backed way down being a large corporation that depends upon the revenue of the advertisers. Now it's on Discovery's radar and they won't let us go near it.

A great quote from the video:

You do have about 3000 people in the room who aren't under such legal arrangements.

The full video is here, and starts with a great talk from Savage about his obsessions.

The point is that keeping the information 'secret' does not stop the bad guys getting it - it stops the rest of us knowing that our information is insecure. If you're reliant on security by obscurity you have no security at all. Given that RFID is a widely distributed technology, the RFID chips should be able to withstand full scrutiny if they're to be trusted for the purpose.

They can't withstand that scrutiny, as evidenced by the reaction of the lawyers, and by this video.

With a bigger antenna on this I can go into Starbucks and get the [details] of everyone there.

It's a shame discovery didn't feel able to nod at the lawyers, and then make the programme anyway - including the conversation with the legal people. Still, when you're depending upon ad revenues, it's not as easy as all that - at least in the short term. A good argument for the BBC TV Licence!

(*) Although the announcer in the UK does often mix concepts of mass, pressure, force etc. Not sure about the guy in the US - the people in the show sometimes do this too, but that comes across to me as more of a 'shorthand' - as they obviously know the difference!

Bank unilaterally changes password

Just seen a funny, but worrying, story on the BBC, a man who had the password 'Lloyds is pants' on his bank account had it changed by the bank to 'no it's not'. It was changed as it was 'inappropriate'. He tried to change it to 'Lloyds is Rubbish' - or 'Barclays is better' but this was not allowed. He tried 'censorship', but was told his password had to be six letters or less!

  1. "No it's not" is more than six letters.
  2. A bank suggesting a password that's seven letters long is too long is sadly mistaken
  3. Why was an employee at the bank even able to see the whole password?

When the password is set, it should be done by having the customer enter it secretly in the branch, at the time the account was opened. If done by post, then it should be by an anonymised form which bears a reference number allowing the computer to tie the password to the account, but not for the person entering that password to know the account.

Anyone employee needing to verify a customer should be told by the computer to ask for the 'second, tenth and eleventh' characters of the password, they should enter them - but not be able to see the characters before a correct verification (so if just one letter is wrong, the employee can't know what two were).

At no time should an employee be able to link a full password to an account. The only time an employee should even see a full password is if they're in the section of the head office which handles the anonymised forms.

Unless I've overlooked something, this seems indicative of a security flaw... and as someone with shares in the bank concerned, it worries me. I've written to the bank to try and find out what's happening here.

The bank said: "It is very disappointing that he felt the need to express his upset with our service in this way. Customers can have any password they choose and it is not our policy to allow staff to change the password without the customer's permission. "

GeoHashing

Via xkcd I learned of a new idea called 'Geohashing' geohashing

Essentially the idea is that based on some seed data, some complicated sums are done to give a location.

People get to that location for a meetup.

A map tool is available which does the sums for you. You set the date, click your area and it gives you a location.

Due to problems with the seed data (US stock market) and time zones a new rule has been introduced today for people east of 30 degrees west. This is taken care of automatically by the map tool. There are several pieces of code for implementing this - though most have yet to be updated to reflect the 30W rule.

The idea is that the seed data is processed using an algorithm called md5. This algorithm produces a 'hash' of the data. it is difficult to find alternate data which produces the same hash. A small change in the data produces a big change in the hash.

The idea of a hash is a way of producing a 'fingerprint' of a file. I.e. I could send you a file, but how would you know it hadn't been tampered with? Well, I could phone you, you could recognise me and I could read you the hash of that file (which you can then generate and check).

A hash can also be used as a zero knowledge proof. I.e. I wanted to prove to you that I had discovered some fact. I might not want you to know the fact (yet). For example, I might know the first line of the 'Times' editorial for next saturday. I could generate a hash of that line and give it to you - when the paper is published that information can be checked.

In this case, the md5 algorithm is used to give a reasonable pseudo-randomisation of one number into another. It's just a bit of fun.

I've not gone to a geohash event myself - but I like the concept.

The Cold War is Back?

Following the Alex Litivenko murder, it appears that we never left the Cold War, with allegations of MI6 and KGB involvement in a murder, claim and counter-claim, with intrigue and mystery. All the stuff of a good Le Carré novel.

I'd be surprised if someone wasn't already working on a screenplay or novelization. A thought that's depressing as it follows an actual murder.

(Update: Now there's talk of missiles. Lovely - Murk)

Stupid Security

Privacy International has opened up nominations for the 'Stupid Security Awards 2006'.

The Stupid Security Awards is an open competition run by Privacy International to discover the world's most pointless, intrusive, annoying and self-serving security measures. The awards aim to highlight the absurdities of the security industry. The awards were first staged in 2003 and attracted over 5,000 nominations from members of the public from around the world.

The competition is judged by an international panel of well-known security experts, public policy specialists, privacy advocates and journalists. Together they decide on the following award categories:

  • Most Egregiously Stupid Award
  • Most Inexplicably Stupid Award
  • Most Annoyingly Stupid Award
  • Most Flagrantly Intrusive Award
  • Most Stupidly Counter Productive Award

Unworkable security practices and illusory security measures do nothing to help issues of real public concern. They only hinder the public, intrude unnecessary into our private lives and often reduce us to the status of cattle.

It's hard to know just where to start, but the recent scares about airports have lots of possibilities, for example the reduction in hand luggage size - as if someone could smuggle something nasty in slightly larger luggage, but not slightly smaller. In addition there's the fact that liquids can't be taken through security - but can be bought on the far side of security but not if travelling to the USA, bottles of water bought at the airport are much more dangerous when flying to the US. Obviously.

There's also the whole idea that ID cards will axiomatically make us secure (potential terrorists would have valid ID too).

The full announcement is here, and says:

The airline industry is the most prominent offender, but it is not alone. Consider the UK rail company that banned train-spotters on the grounds of security (e.g. see this article(external). Or the security desk of a US office building that complained because paramedics rushing to attend a heart-attack victim had failed to sign-in. Or the metro company that installed a $20,000 biological weapons/gas detector and placed it openly next to a power plug so terrorists could conveniently unplug the device.

In 2003, the final list was published with this leading paragraph:

"The extraordinary number of nominations indicates that the situation has become ridiculous" said Mr Davies. "Security has become the smokescreen for incompetent and robotic managers the world over".

Solution to Puzzle 18

Last week I posted this problem:

- X . . . . X . . X   . . . X X . . . X .   . . . X - - - X . . 
- X . - . . X - . .   X X - . . . X . X X   . - X X . - - . X . 
- . X . X - X - X -   . - - X X . X . - X   . . . X - . - - X X 
. - - . X . . X . X   - . - . X . X X - -   - X . . - . X X - X 
. X - . . - X - X .   - . - . - X X . . X   - X . . . X X . X - 
. X - . - . X - - -   X - . . X . X - . .   X X . . - X . . . X 
. . X - . X - - . X   X - - X - - - X . -   . X . . . X . X X - 
. - . X - - - X - .   . X . X . - . - . -   X X - . . X - - - X 
- X . . . X X . - X   - . X - . . X X - .   . X . - X . . . X . 
. . . X . X . . . X   X . . . . X . - X .   . . - X . X X - X . 
. . . X . X . . X .   - . X X . . - X . .   . X . . - X . - X . 
- . . X X - - X . X   . - X - . X . . X -   . X - - . X . - . - 
. - X X . - X - . X   X - . . - X X . . X   . . . X X . - X X . 
. . X . - - . X . -   X - . - . X . X X -   . . . X . X - X . - 
- X . X . X - . X X   - . - . X . . . . X   . - X . - . X . - X 
- . - . X - X . X .   - . X . . . X 

As usual, if you'd rather try to work the problem out for yourself, then please do so before reading on!

The key lay in pure recognition, this is morse. The dots and dashes have their usual meaning. The X is a pause between characters, XX is a pause between words.

The decoded text is below:

This should be a pretty easy piece of text. It's encoded using Morse code. Dots and dashes have their usual meaning. An X is a space between characters.

Solution to Puzzle 17

Last week I published this puzzle:

R D L T Y D H Q R H W S J A A R L E A O O C L Y U
U Y N J T G R I O X B L D M M V D E O U P L R A Q
E D E O X B I S P B L F T F K P L Y Y V W C Z W A
D R H M N G T N V U U Y D R H M N Z N S E C U W T
C W M J C Z L B L P C O Y D P X P B L Y U U Y N V
D E C R Z C B N D Q Q R D I Y O D E M N H C V Y O
M R I S L Y Y U G R I

If you haven't yet attempted it, you may wish to do so before moving on.

To solve this you would have first tried to establish the key length, and then looked at the frequencies of letters encoded with identical key letters. This would have allowed you to make good guesses for each key letter, and then form the plaintext.

This text was prepared using the Cipherclerk applet, the input text was a quote from the Lenny Henry show, 'Chef!'

L E T M E E X P L A I N T H E O R D E R O F T H I N G S T O
Y O U T H E R E S T H E A R I S T O C R A C Y T H E U P P E
R C L A S S T H E M I D D L E C L A S S W O R K I N G C L A
S S D U M B A N I M A L S W A I T E R S C R E E P I N G T H
I N G S H E A D L I C E P E O P L E W H O E A T P A C K E T
S O U P T H E N Y O U

Reformatting the text we get this:
Let me explain the order of things to you. There's the aristocracy, the upper class, the middle class, working class, dumb animals, waiters, creeping things, head lice, people who eat packet soup, then you

Source: Gareth Blackstock (Lenny Henry), Chef!

Enciphered using 'Beaufort cipher'.
Using the alphabetic key 'chef'.
The length of the plain text is 161 letters.

Plain text alphabet is 26 Letters: A-Z.
Operation Mode:Repetitive Key

Within beaufort, the enciphering and deciphering operations are identical, and so it does not matter which is chosen for decryption.

Puzzle 18

This should prove to be relatively easy, the solution will be posted next week.

- X . . . . X . . X   . . . X X . . . X .   . . . X - - - X . . 
- X . - . . X - . .   X X - . . . X . X X   . - X X . - - . X . 
- . X . X - X - X -   . - - X X . X . - X   . . . X - . - - X X 
. - - . X . . X . X   - . - . X . X X - -   - X . . - . X X - X 
. X - . . - X - X .   - . - . - X X . . X   - X . . . X X . X - 
. X - . - . X - - -   X - . . X . X - . .   X X . . - X . . . X 
. . X - . X - - . X   X - - X - - - X . -   . X . . . X . X X - 
. - . X - - - X - .   . X . X . - . - . -   X X - . . X - - - X 
- X . . . X X . - X   - . X - . . X X - .   . X . - X . . . X . 
. . . X . X . . . X   X . . . . X . - X .   . . - X . X X - X . 
. . . X . X . . X .   - . X X . . - X . .   . X . . - X . - X . 
- . . X X - - X . X   . - X - . X . . X -   . X - - . X . - . - 
. - X X . - X - . X   X - . . - X X . . X   . . . X X . - X X . 
. . X . - - . X . -   X - . - . X . X X -   . . . X . X - X . - 
- X . X . X - . X X   - . - . X . . . . X   . - X . - . X . - X 
- . - . X - X . X .   - . X . . . X 

As usual, please feel free to discuss, but be wary of spoilers in the comments.

Solution to Puzzle 16

Last week I posted this puzzle:

MOE FRXSTGNJ-THPED NEGSBNHMSZE HTD XEGYNHMRXJ XELRXP FSNN SB ST LHAM H ZEXJ DHTGEXRYB QSEAE RL NEGSBNHMSRT. SM GXHTMB HTJ PSTSBMEX MOE HFSNSMJ MR HPETD, XEQNHAE, RX XEQEHN EUSBMSTG NEGSBNHMSRT. MOE LXSGOMETSTG MOSTG SB MOSB: MOEJ IRYND FE HFNE MR PHCE PHKRX AOHTGEB MR MOE NHI ISMORYM QHXNSHPETM FESTG HFNE MR EUHPSTE SM QXRQEXNJ, MHCSTG HIHJ MOE HFSNSMJ RL QHXNSHPETM MR PEHTSTGLYNNJ XEQXEBETM MOE ASMSVETB RL MOSB ARYTMXJ.

If you haven't yet attempted it, you may wish to do so before moving on.

The boringly-named Legislative and Regulatory Reform Bill is in fact a very dangerous piece of legislation. It grants any minister the ability to amend, replace, or repeal existing legislation. The frightening thing is this: they would be able to make major changes to the law without Parliament being able to examine it properly, taking away the ability of Parliament to meaningfully represent the citizens of this country.

This is the preamble on the Save Parliament website.

You probably would have solved this by looking at the most frequent letters in the ciphertext, and knowing that ETAIN are the most common letters in english, with TH and HE the most common pairings of letters, you could have assigned best guess values to each letter in the ciphertext. Words would have begun to suggest themselves, after a few false starts you should have got a near complete text.

Puzzle 17

Another puzzle for you today, this is an example of the Beaufort Cipher. I will post a solution in a week.

R D L T Y D H Q R H W S J A A R L E A O O C L Y U
U Y N J T G R I O X B L D M M V D E O U P L R A Q
E D E O X B I S P B L F T F K P L Y Y V W C Z W A
D R H M N G T N V U U Y D R H M N Z N S E C U W T
C W M J C Z L B L P C O Y D P X P B L Y U U Y N V
D E C R Z C B N D Q Q R D I Y O D E M N H C V Y O
M R I S L Y Y U G R I

Please do not post the solution in the comments, but do feel free to hint if asked. The solution will appear on one week.

Puzzle 16

It's been a while since I posted a cryptographic problem, so here is a new one. This one should be fairly simple as it's a monoalphabet

MOE FRXSTGNJ-THPED NEGSBNHMSZE HTD XEGYNHMRXJ XELRXP FSNN SB ST LHAM H ZEXJ DHTGEXRYB QSEAE RL NEGSBNHMSRT. SM GXHTMB HTJ PSTSBMEX MOE HFSNSMJ MR HPETD, XEQNHAE, RX XEQEHN EUSBMSTG NEGSBNHMSRT. MOE LXSGOMETSTG MOSTG SB MOSB: MOEJ IRYND FE HFNE MR PHCE PHKRX AOHTGEB MR MOE NHI ISMORYM QHXNSHPETM FESTG HFNE MR EUHPSTE SM QXRQEXNJ, MHCSTG HIHJ MOE HFSNSMJ RL QHXNSHPETM MR PEHTSTGLYNNJ XEQXEBETM MOE ASMSVETB RL MOSB ARYTMXJ.

Please do not post the solution in the comments, but do feel free to hint if asked. The solution will appear on one week.

Solution to Puzzle 15

Last week's puzzle was:

HZ ZHZCECCZ LCXCZEF EUI, A WDAWR WITTAZMI GZHE UAL LCZE EI A THSHEADF JDHLIZ NID A WDHTC EPCF MHMZ'E WITTHE.

EPCLC TCZ JDITJESF CLWAJCM NDIT A TAVHTGT LCWGDHEF LEIWRAMC EI EPC SIL AZOCSCL GZMCDODIGZM.

EIMAF, LEHSS UAZECM YF EPC OIXCDZTCZE, EPCF LGDXHXC AL LISMHCDL IN NIDEGZC.

HN FIG PAXC A JDIYSCT. HN ZI-IZC CSLC WAZ PCSJ. AZM HN FIG WAZ NHZM EPCT.

TAFYC FIG WAZ PHDC: EPC A ECAT.

Here is the solution:

The solution was from the introduction to 'The A Team'

In nineteen seventy two, a crack commando unit was sent to a military prison for a crime they didn't commit.

These men promptly escaped from a maximum security stockade to the Los Angeles Underground.

Today, still wanted by the government, they survive as soldiers of fortune.

If you have a problem. If no-one else can help. And if you can find them.

Maybe you can hire: The A Team.

The cipher alphabet was formed by lining up ABCDEFG etc with the key order on my keyboard, that is AZERTYUIOP... I am using a french layout. If you can't see this, try changing the way you write out the alphabets (i.e. sort the other alphabet into alphabetical order).

Puzzle 15

Okay, it has been a while, but here is a new cryptographic puzzle:

HZ ZHZCECCZ LCXCZEF EUI, A WDAWR WITTAZMI GZHE UAL LCZE EI A THSHEADF JDHLIZ NID A WDHTC EPCF MHMZ'E WITTHE.

EPCLC TCZ JDITJESF CLWAJCM NDIT A TAVHTGT LCWGDHEF LEIWRAMC EI EPC SIL AZOCSCL GZMCDODIGZM.

EIMAF, LEHSS UAZECM YF EPC OIXCDZTCZE, EPCF LGDXHXC AL LISMHCDL IN NIDEGZC.

HN FIG PAXC A JDIYSCT. HN ZI-IZC CSLC WAZ PCSJ. AZM HN FIG WAZ NHZM EPCT.

TAFYC FIG WAZ PHDC: EPC A ECAT.

It is a fairly easy one, especially if you begin to recognise the quote. Enjoy!

The solution will appear in one week.

An additional puzzle: How was the ciphering alphabet formed?