Category Archives: cryptography

Foam Kernow crypto ‘tea party’

Last night we ran an experimental cryptoparty at Foam Kernow. We’d not tried something like this before, or have any particular expertise with cryptography – so this was run as a research gathering for interested people to find out more about it.

One of the misconceptions about cryptography I wanted to start with is that it’s just about hiding things. We looked at Applied Cryptography by Bruce Schneier where he starts with explaining the 3 things that cryptography provide beyond confidentiality:

Authentication. It should be possible for the receiver of a message to ascertain it’s origin; an intruder should not be able to masquerade as someone else.
Integrity. It should be possible for the receiver of a message to verify that it has not been modified in transit; an intruder should not be able to substitute a false message for a legitimate one.
Nonrepudiation. A sender should not be able to falsely deny later that they sent the message.

It’s interesting how confidentiality is tied up with these concepts – you can’t compromise one without damaging the others. Also how these are a requirement for human communication, but we’ve become so used to living without them.

One of the most interesting things was to hear the motivations for people to come along and find out more about this subject. There were general feeling of loss of control over online identity and data. Some of the more specific aspects:

  • Ambient data collection, our identity increasingly becoming a commodity – being modeled for purposes we do not have control over.
  • Centralisation of communication being a problem – e.g. gmail.
  • Never knowing when your privacy might become important eg. you find yourself in an abusive relationship, suddenly it matters.
  • Knowing that privacy is something we should be thinking about but not wanting to. Similar to knowing we shouldn’t be using the car but doing it anyway.
  • Awareness that our actions don’t just affect us, but our families, friends and colleagues privacy – needing to think about them too.
  • Worrying when googling about health, financial or legal subjects.
  • Being aware that email is monitored in the workplace.

We talked about the encryption we already use – gpg for email with thunderbird and Tor for browsing anonymously. One of the tricky areas we talked about was setting this kind of thing up for mobile – do you need specific apps, an entire OS or specific hardware? This is something we need to spend a bit more time looking into.

Personally speaking, on my phone I use a free firewall so I can at least control which apps on my phone can be online – and I only became aware of this from developing for android and seeing the amount of ‘calling home’ that completely arbitrary applications do regularly.

We also discussed asymmetric key pair crytography – how the mathematics meshes so neatly with social conventions, so you can sign a message to prove you wrote it, or sign someone else’s public key to build up a ‘web of trust’.

We didn’t get very practical, this was more about discussing the issues and feelings on the topic. That might be something to think about for future cryptoparties.

A cryptoweaving experiment

Archaeologists can read a woven artifact created thousands of years ago, and from its structure determine the actions performed in the right order by the weaver who created it. They can then recreate the weaving, following in their ancestor’s ‘footsteps’ exactly.

This is possible because a woven artifact encodes time digitally, weft by weft. In most other forms of human endeavor, reverse engineering is still possible (e.g. in a car or a cake) but instructions are not encoded in the object’s fundamental structure – they need to be inferred by experiment or indirect means. Similarly, a text does not quite represent its writing process in a time encoded manner, but the end result. Interestingly, one possible self describing artifact could be a musical performance.

Looked at this way, any woven pattern can be seen as a digital record of movement performed by the weaver. We can create the pattern with a notation that describes this series of actions (a handweaver following a lift plan), or move in the other direction like the archaeologist, recording a given notation from an existing weave.

example
A weaving and its executable code equivalent.

One of the potentials of weaving I’m most interested in is being able to demonstrate fundamentals of software in threads – partly to make the physical nature of computation self evident, but also as a way of designing new ways of learning and understanding what computers are.

If we take the code required to make the pattern in the weaving above:

(twist 3 4 5 14 15 16)
(weave-forward 3)
(twist 4 15)
(weave-forward 1)
(twist 4 8 11 15)

(repeat 2
 (weave-back 4)
 (twist 8 11)
 (weave-forward 2)
 (twist 9 10)
 (weave-forward 2)
 (twist 9 10)
 (weave-back 2)
 (twist 9 10)
 (weave-back 2)
 (twist 8 11)
 (weave-forward 4))

We can “compile” it into a binary form which describes each instruction – the exact process for this is irrelevant, but here it is anyway – an 8 bit encoding, packing instructions and data together:

8bit instruction encoding:

Action  Direction  Count/Tablet ID (5 bit number)
0 1         2              3 4 5 6 7 

Action types
weave:    01 (1)
rotate:   10 (2)
twist:    11 (3)

Direction
forward: 0
backward: 1

If we compile the code notation above with this binary system, we can then read the binary as a series of tablet weaving card flip rotations (I’m using 20 tablets, so we can fit in two instructions per weft):

0 1 6 7 10 11 15
0 1 5 7 10 11 14 15 16
0 1 4 5 6 7 10 11 13
1 6 7 10 11 15
0 1 5 7 11 17
0 1 5 10 11 14
0 1 4 6 7 10 11 14 15 16 17
0 1 2 3 4 5 6 7 11 12 15
0 1 4 10 11 14 16
1 6 10 11 14 17
0 1 4 6 11 16
0 1 4 7 10 11 14 16
1 2 6 10 11 14 17
0 1 4 6 11 12 16
0 1 4 7 10 11 14 16
1 5

If we actually try weaving this (by advancing two turns forward/backward at a time) we get this mess:

close

The point is that (assuming we’ve made no mistakes) this weave represents *exactly* the same information as the pattern does – you could extract the program from the messy encoded weave, follow it and recreate the original pattern exactly.

The messy pattern represents both an executable, as well as a compressed form of the weave – taking up less space than the original pattern, but looking a lot worse. Possibly this is a clue too, as it contains a higher density of information – higher entropy, and therefore closer to randomness than the pattern.

Quipu: further experiments in Düsseldorf

A report on further experimentation with Julian Rohrhuber and his students at the Institute for Music and Media in Düsseldorf during our coding with weaves and knots remote seminar this week.

skype

As we have so little idea what the Inca are telling us in their Quipu, it seems appropriate to add a cryptanalysis approach to our toolkit of inquiry. One of the first things that a cryptanalyst will do when inspecting an unknown system is to visualise it’s entropy in order to get a handle on any structures or patterns in the underlying information. This concept comes from Claude Shannon’s work on information theory in the 40’s, where he proved that information obeys fundamental laws of physics. The concept that information and “cyberspace” may not be as intangible and otherworldly as we might believe (in fact is grounded in physical reality along with everything else) is one of the recurring themes of the weavingcodes project.

Shannon’s innovation was to separate the concepts of data quantity from information value, and he claims that information is equivalent to surprise – the more surprising a piece of data is, the more information it contains. Conversely a piece of information which we expect to hear by definition doesn’t really tell us very much. The potential for some data to be surprising (or more specifically it’s potential to reduce our uncertainty) can be measured statistically, with a quantity he called entropy, as it is analogous to states in thermodynamic systems.

slide

Shannon defined a generalised communication system, which is handy to give us a way of reasoning about our situation in relation to the Inca. Our main unknown is the source of the messages they are sending us, are they accounting information, calendars or stories? We know a bit more about the transmitters of the messages, the khipukamayuq – the knot makers and quipu keepers. At the time Shannon was working on information theory, he was part of the start of the movement away from analogue, continuous signals and towards digital signals – with advantages that they are highly resistant to noise and can be carried further and combined together to increase bandwidth. Quipu are also mainly comprised of digital information – the type of a knot, the number of turns it’s comprised of or the twist direction of a thread are all discreet (either one thing or another) and therefore highly robust to material decay or decomposition. We can still ‘read’ them confidently after 500 years or more without the digital signal they represent being degraded too badly, if only we could understand it. At the same time, none of us working on this have access to a real quipu, so our receivers are the archaeologists and historians who study them, and compile archives such as the Harvard Quipu Archive we are using.

Although entropy is a very simplistic approach mathematically, it’s main use is to give us a tool for measuring the comparative information carrying potential of data which we have no idea about. Here are all the quipu in the Harvard database in order of average entropy bits they contain (only listing every other quipu ID):

entropy-per-quipu

This graph is calculated by making lists of all the discreet data of the same type, e.g. knot value, type, tying direction, pendant colours and ply direction (ignoring lengths and knot positions as these are continuous) – then calculating Shannon entropy on histograms for each one and adding them together.

We can also compare different types of information against one another, for example the main data we currently understand has some specific meaning are the knot values, partly derived from the knot type (long, single or figure of eight), which represent a decimal notation. If we compare the entropy of these we can expect them to have roughly similar average amounts of information:

entropy-values-types

The meanings of colours, ply and structure are largely unknown. Here are the knot values compared with the colours:

entropy-values-colours

And this is pendant ply direction compared with knot values for each quipu:

entropy-values-ply

At this point the most useful aspect of this work is to give us some outliers to inspect visually and sonically – more on that soon.

Coding with knots: Inca Quipu

This week I’m teaching at IMM Düsseldorf with Julian Rohrhuber which has given me a chance to follow up a bit on Inca Quipu coding with knots, a dangling thread from the weavecoding project. Quipu are how the Incas organised their society, as they had no written texts or money – things like exchanges (for example from their extensive store houses) were recorded via knots. Researchers have been able to decode the basic numeric system they used, but 20% of the quipu seem to follow a different set of rules, along with extra information encoded via thread material, twist direction, colour and other knot differences. I’ve written a python program for converting the Khipu Database Project excel charts into graphviz files for visualising:

quipu5

The knots are described in ascii art, with S and Z relating to the ply and knot ‘handedness’ direction they are tied in:

O : a single knot 
O/O : two single knots tied in S direction (it's rotated 90 degrees :)
(\\\\) : a long knot of value '4' tied in the Z direction
/8 : end (figure of 8) knot tied S direction

The pendant nodes also have labels describing their ply direction and the side the attach on, so “S R” is S ply & recto attached.

The hardest part of this has been a bit of more recent media archeology to figure out the colour values, I’ve had to cross reference the original Ascher-Ascher Quipu Databooks published in 1978 which contain their own colour system which more or less maps to the NBS-ISCC Munsell colour chart originally proposed in 1898. Luckily that site provides hex colour values – hopefully they are vaguely accurate, the current lookup table is here:

colour_lookup = {
    "W": "#777777",
    "SR":  "#BF2233",
    "MB" : "#673923",
    "GG" : "#575E4E",
    "KB" : "#35170C",
    "AB" : "#A86540",
    "HB" : "#5A3D30",
    "RL" : "#AA6651",
    "BG" : "#4A545C",
    "PG" : "#8D917A",
    "B" : "#7D512D",
    "0B" : "#64400F",
    "RM" : "#AB343A",
    "PR" : "#490005",
    "FR" : "#7F180D",
    "DB" : "#4D220E",
    "YB" : "#BB8B54",
    "MG" : "#817066",
    "GA" : "#503D33"
}

How to back up your encryption keys

Without really noticing it I’ve gradually acquired more and more encryption keys without understanding how to back them up properly. Until fairly recently I lazily assumed that remembering the passphrases would be enough in case of my laptop catching on fire, but this is not the case.

I use GPG keys both for authenticity over email, and encryption when sending people passwords for stuff I’m setting up for them. The Ubuntu launchpad also uses GPG for signing packages for which I use a different key. I also run a bunch of servers, for which I use ssh keys to prove my identity, then there is the Android play store, that requires binaries to be signed, using yet another key, which is also shared for OUYA packages too.

The main algorithm in use for authentication in all these cases is called RSA. RSA and similar algorithms generate a pair of keys, one public and one private. The private key data is encrypted using yet another algorithm (usually AES) which is what your passphrase is used for. When it’s needed, you type your passphrase in, it decrypts the RSA private key and uses that to identify you. So it’s vitally important that this key data is backed up as it can’t be recreated from your passphrase. There doesn’t seem very much information online on the practicalities of all this, so I’m documenting the process with links to where I got info here, partly in order to get feedback if it’s wrong!

With ssh it’s just a matter of copying the contents of your .ssh directory – which contain the public and encrypted private key. The android keys are in a file called .keystore, in your home directory.

When it comes to GPG the best way seems to be to list and export them individually with:

gpg --list-secret-keys
gpg --export-secret-keys your-id-number > secret-key.asc

The id number is the part after the slash for each keypair. At the same time, it’s important to back up a revocation key for each key – this allows you to tell the GPG trust network if your identity becomes compromised by someone finding out your key (or losing/forgetting your passphrase, which is perhaps more likely). You can do this with:

gpg --gen-revoke your-id-number

And paste the result into a text file.

So you can take all these files and store them somewhere safe on a usb stick for example. It all needs to be encrypted so it doesn’t matter if it’s found and accessed. I almost made a fundamental mistake and encrypted it with GPG, which would have been like locking my house keys inside the house. Instead you can encrypt the file using AES independently using this command:

openssl aes-256-cbc -in your-key-file.tar.gz -out your-key-file.tar.gz.enc

I’m assuming once this is done, the best practice is to put it in various places to reduce the chances of it getting lost, as it doesn’t matter if it’s accessible. Make sure to use a long passphrase you won’t forget! The advice given here is to use a long randomly generated string and write it on a piece of paper, which is stored in a safety deposit box – this is the approach to take if you are in charge of really important stuff, I’m not sure that I’m at that point yet :)

Some post-Snowden thoughts

One of the most interesting outcomes of the the Snowden revelations for me are that they have exposed to the light of day an awful lot about how different groups of people relate to technology and authority. There are the side that worries about the internet becoming the “worst tool of human oppression in all of human history” and then we have the “I’ve got nothing to hide so I don’t care” vast majority. I think a lot of us have to be in the second group most of the time, just to operate normally – even if we have sympathies with the first.

map

One problem is the idea that the internet has gradually become intertwined with our societies to the point where it is inconceivable that we could have a functioning civilisation again without it. This does, I think provide a sense of unease to most people – but at the same time it’s easy to brush away. The fact we take the internet entirely for granted is perhaps the most surprising thing of all but I think primarily down to the unease, the easiest option is to trivialise it’s role.

In some attempt to keep up with the news in a realm I know next to nothing about, I’ve been reading a book called Applied Cryptography by Bruce Schneier – this book was first published in 1996 but feels very current, fascinating and probably quite unique in that it comprises half cultural/political discussion and half source code. On page two he explains three vital requirements for social interaction and computers that that cryptography provides (beyond secrecy):

– Authentication. It should be possible for the receiver and sender of a message to ascertain it’s origin; an intruder should not be able to masquerade as someone else.

– Integrity. It should be possible for the receiver of a message to verify that it has not been modified in transit; an intruder should not be able to substitute a false message for a legitimate one.

– Nonrepudiation. A sender should not be able to falsely deny later that he sent the message.

Jaron Lanier wrote in “You are not a gadget” that we become “less human” as we use online services like Twitter and Facebook, as we submit ourselves to their abstractions rather than demand more from them. I think Lanier’s underlying message has some truth to it, but his blame is mostly in the wrong place.

For all sorts of technical, political and accidental reasons, we are all being trained to communicate without cryptography, whilst having evolved as humans to understand social interaction in ways that absolutely require it. The evidence from psychology and history is that a society that reduces communication to this level does not have a bright future. One solution to this I like a lot is the approach of the cryptoparty movement – a great way to widely spread understanding of these issues and the solutions involved.

Oh, and this is my public key.