Film Futures (Christmas Special): Elf

Computer Scientists and digital artists are behind the fabulous special effects and computer generated imagery we see in today’s movies, but for a bit of fun, in this series, we look at how movie plots could change if they involved Computer Scientists. Here we look at an alternative version of the Christmas film, Elf, starring Will Ferrell.

***Spoiler Alert***

Christmas Eve, and a baby crawls into Santa’s pack as he delivers presents at an orphenage. The baby is wearing only a nappy, but this being the 21st century the babys’s reusable Buddy nappy is an Intelligent nappy. It is part of the Internet of Things and is chipped, including sensors and a messaging system that allow it to report to the laundry system when the nappy needs changing (and when it doesn’t) as well as performing remote health monitoring of the baby. It is the height of optimised baby care. When the baby is reported missing the New York Police work with the nappy company, accessing their logs, and eventually work out which nappy the baby was wearing and track its movements…to the roof of the orphenage!

The baby by this point has been found by Santa in his sack at the North Pole, and named Buddy by the Elves after the label on his nappy. The Elves change Buddy’s nappy, and as their laundry uses the same high tech system for their own clothes, their laundry logs the presence of the nappy, allowing the Police to determine its location.

Santa intends to officially adopt Buddy, but things are moving rapidly now. The New York Police believe they have discovered the secret base of an international child smuggling ring. They have determined the location of the criminal hideout as somewhere near the North Pole and put together an armed task force. It is Boxing Day. As Santa gets in touch with the orphanage to explain the situation, and arrange an adoption, armed police already surround the North Pole and are moving in.

The New York Police Commissioner, wanting the good publicity she sees arising from capturing a child smuggling ring, orders the operation to be live streamed to the world. The precise location of the criminal hideout, so operation, is not revealed to the public, which is fortunate given what follows. As the police move in the cameras are switched on and people the world over, are glued to their screens watching the operation unfold. As the police break in to the workshops, toys go flying and Elves scatter, running for their lives, but as Santa appears and calmly allows himself to be handcuffed, it starts to dawn on the police where they are and who they have arrested. The live stream is cut abruptly, and as the full story emerges, and apologies made on all sides. Santa is proved to be real to a world that was becoming sceptical. A side effect is there is a massive boost in Christmas Spirit across the world that keeps Santa’s sleigh powered without the need for engines for many decades to come. Buddy is officially adopted and grows up believing he is an Elf until one fateful year when …

In reality

The idea of the Internet of Things is that objects, not just people, have a presence on the Internet and can communicate with other objects and systems. The idea provides the backbone of the idea of smart homes, where fridges can detect they are out of milk and order more, carpets detect dirt and summon a robot hoover, and the boiler detects when the occupants are nearing home and heats the house just in time.

Wearable computing, where clothes have embedded sensors and computers is also already a reality, though mainly in the form of watches, jewellery and the like. Clothes in shops do include electronic tags that help with stock control, and increasingly electronic-textiles based on metallic fibres and semi-conducting inks, are being used to create clothes with computers and electronics embedded in them.

Making e-textiles durable to be washed is still a challenge. Smart reusable nappies may be a while in coming.

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

Tony Stockman: Sonification

Two different coloured wave patterns superimposed on one anohter on a black background with random dots like a starscape. — Image by Gerd Altmann from Pixabay

Tony Stockman, who was blind from birth, was a Senior Lecturer at QMUL until his retirement. A leading academic in the field of sonification of data, turning data into sound, he eventually became the President of the “International Community for Auditory Display”: the community of researchers working in this area.

Traditionally, we put a lot of effort into finding the best ways to visualise data so that people can easily see the patterns in it. This is an idea that Florence Nightingale, of lady of the lamp fame, pioneered with Crimean War data about why soldiers were dying. Data visualisation is considered so important it is taught in primary schools where we all learn about pie charts and histograms and the like. You can make a career out of data visualisation, working in the media creating visualisations for news programmes and newspapers, for example, and finding a good visualisation is massively important working as a researcher to help people understand your results. In Big Data a good visualisation can help you gain new insights into what is really happening in your data. Those who can come up with good visualisations can become stars, because they can make such a difference (like Florence Nightingale, in fact)

Many people of course, Tony included cannot see, or are partially sighted, so visualisation is not much help! Tony therefore worked on sonifying data instead, exploring how you can map data onto sounds rather than imagery in a way that does the same thing.: makes the patterns obvious and understandable.

His work in this area started with his PhD where he was exploring how breathing affects changes in heart rate. He first needed a way to both check for noise in the recording and then also a way to present the results so that he could analyse and so understand them. So he invented a simple way to turn data into sound using for example frequencies in the data to be sound frequencies. By listening he could find places in his data where interesting things were happening and then investigate the actual numbers. He did this out of necessity just to make it possible to do research but decades later discovered there was by then a whole research community by then working on uses of and good ways to do sonification,

He went on to explore how sonification could be used to give overviews of data for both sighted and non-sighted people. We are very good at spotting patterns in sound – that is all music is after all – and abnormalities from a pattern in sound can stand out even more than when visualised.

Another area of his sonification research involved developing auditory interfaces, for example to allow people to hear diagrams. One of the most famous, successful data visualisations was the London Tube Map designed by Harry Beck who is now famous as a result because of the way that it made the tube map so easy to understand using abstract nodes and lines that ignored distances. Tony’s team explored ways to present similar node and line diagrams, what computer scientist’s call graphs. After all it is all well and good having screen readers to read text but its not a lot of good if all it tells you reading the ALT text that you have the Tube Map in front of you. And this kind of graph is used in all sorts of every day situations but are especially important if you want to get around on public transport.

There is still a lot more to be done before media that involves imagery as well as text is fully accessible, but Tony showed that it is definitely possible to do better, He also showed throughout his career that being blind did not have to hold him back from being an outstanding computer scientists as well as a leading researcher, even if he did have to innovate himself from the start to make it possible.

Related Magazine …

CS4FN Issue 19 – Touch it, feel it, hear it

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

The Machine Stops: a review

Old rusting cogs and a clock — Image by Amy from Pixabay

How reliant on machines should we let ourself become? E.M. Forster is most famous for period dramas but he also wrote a brilliant Science Fiction short story, ‘The Machine Stops’ about it. It is a story I first read in an English Literature lesson at school, a story that convinced me that English Literature could be really, really interesting!

Written in 1909 decades before the first computers were built never mind the internet, video calls, digital music and streaming, he wrote of a future with all of that, where humans live alone in identical underground rooms across the Earth, never leaving because there is no reason to leave, never meeting others because they can meet each other through the Machine. Everything is at hand at the touch of a button. Everything is provided by the Machine, whether food, water, light, entertainment, education, communication, and even air, …

The story covers themes of whether we should let ourself become disconnected from the physical world or not. Is part of what makes us human our embodiment in that world. He refers to this as “the sin against the body” a theme returned to in the film WALL-E. Disconnected from the world humans decline not only in body but also in spirit.

As the title suggests, the story also explores the problems of becoming over-reliant on technology and of what then happens if the technology is taken away. It is more than this though but the issue of repeatedly accepting “good enough” as a replacement for the fidelity of physical and natural reality. What seems wonderfully novel and cool, convenient or just cheaper may not actually be as good as the original. Human-human interaction that is face-to-face is far richer than we get through a video call, for example, and yet meetings have disappeared rapidly in favour of the latter in the 21st century.

Once we do become reliant on machines to service our every whim, what would happen if those ever more connected machines break? Written over a century ago, this is very topical now, of course, as, with our ever increasing reliance on inter-connected digital technology for energy, communication, transport, banking and more, we have started to see outages happen. These have arisen from the consequences of bugs and cyber attacks, from ‘human error’ and technology that it turns out is just not quite dependable enough, leading to country and world-wide outages of the things that constitutes modern living.

How we use technology is up to us all of course, and like magpies we love shiny new toys, but losing all the skills and understanding just because they can be now done by the machine may not be very wise in the long term. More generally, we need to make sure the technology we do make ourselves reliant on, is really, really dependable: far more dependable than our current standards are in actual practice. That needs money and time, not rushed introductions, but also more Computer Science research on how to do dependability better in practice. Above all we need to make sure we do continue to understand the systems we build well enough to maintain them in the long term.

Paul Curzon, Queen Mary University of London

Going Postal: A review

Semaphore tower showing all the flag positions — Image by Clker-Free-Vector-Images from Pixabay adapted by CS4FN

Any one claiming to be a hard-core Computer Scientist would be ashamed if they had to admit they hadn’t read Terry Pratchett. If you are and you haven’t, then ‘Going Postal’ is a good place to start.

‘Going Postal’, is a must for anyone interested in networks. Not because it has any bearing on reality. It doesn’t. It’s about Discworld, a flat world that is held up on the back of elephants, and where magic reigns. Technology is starting to get a foothold though. For example, cameras, computers and movies have all been invented…though they usually have an Elf inside. Take cameras: they work because the Elf has a paint box and an easel. Take too many sunsets and he’ll run out of pink! It is all incredibly silly…but it works and so does the technology.

Now telecommunications technology is gaining a foothold…Corrupt business is muscling in and the post office is struggling to survive. Who would want to send a letter when they can send a c-mail over the Clacks? The Clacks are a network of semaphore towers that allow messages to ‘travel at the speed of light’.

At each tower the operators

“pound keys, kick pedals and pull levers as fast as they can'”

to forward the message to the next tower in the network and so on to their destination. The clacks are so fashionable, people have even started carrying pocket semaphore flags everywhere they go, so they can send messages to people on the other side of the room.

“But can you write
S.W.A.L.K. on a clacks?
Can you seal it with
a loving kiss?
Can you cry tears
on to a clacks,
can you smell it,
can you enclose
a pressed flower?
A letter is more than
just a message.”

Moist von Lipwig, a brilliant con-artist who just did one con too many, is given the job of saving the Post-office…his choice was ‘Take the job or die’. Not, actually, such a good deal given the last few Postmasters all died on the job … in the space of a few weeks.

Will he save the post office, or is the march of technology unstoppable?…and just who are the ‘Smoking GNU’ that you hear whispers about on the Clacks?

Reading this book has got to be the most fun way imaginable of learning about telecom networks, not to mention entrepreneurship and the effect of computers on society. None of the actual technology is the same as in our world of course, but the principle is the same: transmission codes, data and control signals, simplex and duplex transmissions, image encoding, internet nodes, encryption, e-commerce, phreakers and more…they are all there, which just goes to show computer science is not just about our current computer technology. It all applies even when there is no silicon in sight.

Oh, and this is the 33rd Discworld novel, so if you do get hooked, don’t expect to get much more done for the next few weeks as you catch up.

Paul Curzon, Queen Mary University of London

More on…

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

The Alien Cookbook

An alien looking on distraught that two bowls of soup are different, one purple, one green. — Image by CS4FN from original soup bowls (thick and thin) by OpenClipart-Vectors and alien image by Clker-Free-Vector-Images from Pixabay

How to spot a bad chef when you’ve never tasted the food (OR How to spot a bad quantum simulator when you do not know what the quantum circuit it is simulating is supposed to do.)

Imagine you’re a judge on a wild cooking competition. The contestants are two of the best chefs in the world, Chef Qiskit and Chef Cirq. Today’s challenge is a strange one. You hand them both a mysterious, ancient cookbook found in a crashed spaceship. The recipe you’ve chosen is called “Glorp Soup”. The instructions are very precise and scientific: “… Heat pan to 451 degrees. Stir counter-clockwise for exactly 18.7 seconds. … Add exactly 3 grams of powdered meteorite (with the specified composition). …” The recipe is a perfectly clear algorithm, but since no human has ever made Glorp Soup, nobody knows what it’s supposed to taste, look, or smell like. Both chefs go to their identical kitchens with the exact same alien ingredients. After an hour, they present their dishes.

Chef Qiskit brings out a bowl of thick, bubbling, bright purple soup that smells like cinnamon.
Chef Cirq brings out a bowl of thin, clear, green soup that smells like lemons.

Now you have a fascinating situation. You have no idea which one is the “real” Glorp Soup. Maybe it’s supposed to be purple, or maybe it’s green. But you have just learned something incredibly important: at least one of your expert chefs made a mistake. They were given the exact same, precise recipe, but they produced two completely different results. You’ve found a flaw in one of their processes without ever knowing the correct answer.

This powerful idea is called Differential Testing.

Cooking with Quantum Rules

In our research, the “alien recipes” we use are called quantum circuits. These are the step-by-step instructions for a quantum computer. And the “chefs” are incredibly complex computer programs called quantum simulators, built by places like Google and IBM.

Scientists give these simulators a recipe (a circuit) to predict what a real quantum computer will cook up. These “dishes” could be the design for a new medicine or a new type of battery. If the simulator-chef gets the recipe wrong, the final result could be useless or even dangerous. But how do you check a chef’s work when the recipe is for a food you’ve never tasted? How do you test a quantum simulator when you do not know exactly what a quantum circuit should do.

FuzzQ: The Robot Quantum Food Critic

We can’t just try one recipe, one quantum circuit. We need to try thousands. So we built a robot “quantum food critic”, a program we call FuzzQ. FuzzQ’s job is to invent new “alien recipes” ie quantum circuits and see if the two “chefs” cook the same dish (i.e. different simulators do the same thing when simulating it). This process of trying out thousands of different, and sometimes very weird, recipes is called Fuzzing.

Here’s how our quantum circuit food critic works:

It writes a recipe: FuzzQ uses a rulebook for “alien cooking” to invent a new, unique, and often very strange quantum circuit.
It gives the recipe to both chefs: It sends the exact same quantum circuit to “Chef Qiskit” (the Qiskit simulator) and “Chef Cirq” (the Cirq simulator).
It tastes the soup: FuzzQ looks at the final result from both. If they’re identical, it assumes they’re correct. But if they do different things, so one did the equivalent of make a purple, bubbling soup and the other made the equivalent of a clear, green soup, FuzzQ sounds the alarm. It has found a bug!

We had FuzzQ invent and “taste-test”, so check the results of, over 800,000 different quantum recipes.

The Tale of the Two Ovens

Our robot critic found 8 major types of quantum “cooking” errors. One of the most interesting was for a simple instruction called a “SWAP”, which was discovered by looking at how the two chefs used their high-tech “ovens”.

Imagine both chefs have an identical oven with two compartments, a Top Oven and a Bottom Oven. They preheat them according to the recipe: the Top Oven to a very hot 250°C, and the Bottom Oven to a low 100°C. The recipe then has a smart-oven command:

“Logically SWAP the Top Oven and Bottom Oven.”

Both chefs press the button to do the “SWAP”.

Chef Cirq’s oven works as expected. It starts the long process of cooling the top oven and heating the bottom one.
Chef Qiskit’s oven, however, is a “smarter” model. It takes a shortcut. It doesn’t change the temperatures at all but just swaps the labels on its digital display so that the one at the top previously labelled the Top Oven is now labelled as the Bottom Oven, and vice versa. The screen now lies, showing Top Oven: 100°C and Bottom Oven: 250°C, even though the physical reality is the opposite: the one at the top is still the incredibly hot, 250°C and the one below it is still 100°C.

The final instruction is:

“Place the delicate soufflé into the physical TOP OVEN.”

Chef Cirq opens his top oven (ie the one positioned above the other and labelled Top Oven), which is now correctly at 100°C, having cooled down, and bakes a perfect soufflé.
Chef Qiskit, trusting his display, opens his top oven (ie the one positioned above the other but internally now labelled Bottom Oven) and puts his soufflé inside. But that physical oven that is at the top is still at 250°C. A few minutes later, he has a burnt, smoky crisp.

Our robot judge, FuzzQ, doesn’t need to know how to bake. It just looks at the two final soufflés. One is perfect, and the other is charcoal. The results are different, so FuzzQ sounds the alarm: “Disagreement found!”

This is how we found the bug. We didn’t need to know the “correct temperature”. We only needed to see that the two expert simulators, when given the same instructions, produced two wildly different outcomes. Knowing something now is amiss, further investigation of what each quantum simulator did with those identical instructions, can determine what actually went wrong and the problematic quantum simulator improved. By finding these disagreements, we’re helping to make sure the amazing tools of quantum science are trustworthy.

Vasileios Klimis, Queen Mary University of London

Getting Technical …

Read the OOPSLA academic paper

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

Jerry Elliot High Eagle: Saving Apollo 13

Apollo 13 Mission patch of three golden horses travelling from Earth to the moon — Image by NASA Public domain via Wikimedia Commons

Jerry Elliot High Eagle was possibly the first Native American to work in NASA mission control. He worked for NASA for over 40 years, from the Apollo moon landings up until the space shuttle missions. He was a trained physicist with both Cherokee and Osage heritage and played a crucial part in saving the Apollo 13 crew when an explosion meant they might not get back to Earth alive.

The story of Apollo 13 is told in the Tom Hanks film Apollo 13. The aim was to land on the moon for a third time following the previous two successful lunar missions of Apollo 11 and Apollo 12. That plan was aborted on the way there, however, after pilot James Swigert radioed his now famous if misquoted words “Okay, Houston … we’ve had a problem here”. It was a problem that very soon seemed to mean they would die in space: an oxygen tank had just exploded. Instead of being a moon landing the mission turned into the most famous rescue attempt in history – could the crew of James Lovell, Jack Swigert and Fred Haise get back to Earth before their small space craft turned into a frozen, airless and lifeless space coffin.

While the mission control team worked with the crew on how to keep the command and lunar modules habitable for as long as possible (they were rapidly running out of breathable air, water and heat and had lost electircal power), Elliot worked on actually getting the craft back to Earth. He was the “retrofire officer” for the mission which meant he was an expert in, and responsible for, the trajectory Apollo 13 took from the Earth to the moon and back. He had to compute a completely new trajectory from where they now were, which would get them back to Earth as fast and as safely as possible. It looked impossible given the limited time the crew could possibly stay alive. Elliot wasn’t a quitter though and motivated himself by telling himself:

“The Cherokee people had the tenacity to persevere on the Trail of Tears … I have their blood and I can do this.”

The Trail of Tears was the forced removal of Native Americans from their ancestral homelands by the US government in the 19th century to make way for the gold rush . Now we would call this ethnic cleansing and genocide. 60, 000 Native American people were moved with the Cherokee forcibly marched a 1000 miles to an area to the West of the Mississippi, thousands dying along the way.

The best solution for Apollo 13, was to keep going and slingshot round the dark side of the moon, using the forces arising from its gravity, together with strategic use of the boosters to push the space craft on back to Earth more quickly than on those boosters alone. The trajectory he computed had to be absolutely accurate or the crew would not get home and he has suggested the accuracy needed was like “threading a needle from 70 feet away!” Get it wrong and the space craft could miss the Earth completely, or arrive too fast to reenter earth’s orbit and return through the atmosphere.

Jerry Elliot High Eagle, of course, famously got it right: the crew survived, safely returning to Earth and Elliot was awarded the President’s Medal of Freedom, the highest American honour possible, for the role he played. The Native American people also gave him the name High Eagle for his contributions to space exploration.

Paul Curzon, Queen Mary University of London

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

Service Model: a review

A robot butler outline on a blood red background — Image by OpenClipart-Vectors from Pixabay

Artificial Intelligences are just tools, that do nothing but follow their programming. They are not self-aware and have no ability for self-determination. They are a what not a who. So what is it like to be a robot just following its (complex) program, making decisions based on data alone? What is it like to be an artificial intelligence? What is the real difference between being self-aware and not? What is the difference to being human? These are the themes explored by the dystopian (or is it utopian?) and funny science fiction novel “Service Model” by Adrian Tchaikovsky.

In a future where the tools of computer science and robotics have been used to make human lives as comfortable as conceivably possible, Charles(TM) is a valet robot looking after his Master’s every whim. His every action is controlled by a task list turned into sophisticated human facing interaction. Charles is designed to be totally logical but also totally loyal. What could go wrong? Everything it turns out when he apparently murders his master. Why did it happen? Did he actually do it? Is there a bug in his program? Has he been infected by a virus? Was he being controlled by others as part of an uprising? Has he become self-aware and able to made his own decision to turn on his evil master. And that should he do now? Will his task list continue to guide him once he is in a totally alien context he was never designed for, and where those around him are apparently being illogical?

The novel explores important topics we all need to grapple with, in a fun but serious way. It looks at what AI tools are for and the difference between a tool and a person even when doing the same jobs. Is it actually good to replace the work of humans with programs just because we can? Who actually benefits and who suffers? AI is being promoted as a silver bullet that will solve our economic problems. But, we have been replacing humans with computers for decades now based on that promise, but prices still go up and inequality seems to do nothing but rise with ever more children living in poverty. Who is actually benefiting? A small number of billionaires certainly are. Is everyone? We have many better “toys” that superficially make life easier and more comfortable – we can buy anything we want from the comfort of our sofas, self-driving cars will soon take us anywhere we want, we can get answers to any question we care to ask, ever more routine jobs are done by machines, many areas of work, boring or otherwise are becoming a thing of the past with a promise of utopia, but are we solving problems or making them with our drive to automate everything. Is it good for society as a whole or just good for vested interests? Are we losing track of what is most important about being human? Charles will perhaps help us find out.

Thinking about the consequences of technology is an important part of any computer science education and all CS professionals should think about ethics of what they are involved in. Reading great science fiction such as this is one good way to explore the consequences, though as Ursula Le Guin has said: the best science fiction doesn’t predict the future, it tells us about ourselves in the present. Following in the tradition of “The Machine Stops” and “I, Robot”, “Service Model” (and the short story “Human Resources” that comes with it) does that, if in a satyrical way. It is a must read for anyone involved in the design of AI tools especially those promoting the idea of utopian futures.

Paul Curzon, Queen Mary University of London

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on research agreement EP/W033615/1.

Hacking DNA

A jigsaw of DNA with peices missing — Image by Arek Socha from Pixabay

DNA is the molecule of life. Our DNA stores the information of how to create us. Now it can be hacked.

DNA consists of two strands coiling round each other in a double helix. It’s made of four building blocks, or ‘nucleotides’, labelled A, C, G, T. Different orders of letters gives the information of how to build each unique creature, you and me included. Sequences of DNA are analysed in labs by a machine called a gene sequencer. It works out the order of the letters and so tells us what’s in the DNA. When biologists talk of sequencing the human (or another animal or plant’s) genome they mean using a gene sequencer to work out the specific sequences in the DNA for that species. They are also used by forensic scientists to work out who might have been at the scene of a crime, and to predict whether a person has genetic disorders that might lead to disease.

DNA can be used to store information other than that of life: any information in fact. This may be the future of data storage. Computers use a code made of 0s and 1s. There is no reason why you can’t encode all the same information using A, C, G, T instead. For example, a string of 1s and 0s might be encoded by having each pair of bits represented by one of the four nucleotides: 00 = A, 01 = C, 10 = G and 11 = T. The idea has been demonstrated by Harvard scientists who stored a video clip in DNA.

It also leads to whole new cyber-security threats. A program is just data too, so can be stored in DNA sequences, for example. Researchers from the University of Washington have managed to hide a malicious program inside DNA that can attack the gene sequencer itself!

The gene sequencer not only works out the sequence of DNA symbols. As it is a computer, it converts it into a binary form that can then be processed as normal. As DNA sequences are long, the sequencer compresses them. The attack made use of a common bug found in programs that malware often uses: ‘buffer overflow’ errors. These arise when the person writing a program includes instructions to set aside a fixed amount of space to store data, but then doesn’t include code to make sure only that amount of data is stored. If more data is stored then it overflows into the memory area beyond that allocated to it. If executable code is stored there, then the effect can be to overwrite the program with new malicious instructions.

When the gene sequencer reaches that malware DNA, the converted program emerges and is converted back into 1s and 0s. If those bits are treated as instructions and executed, it launches its attack and takes control of the computer that runs the sequencer. In principle, an attack like this could be used to fake results for subsequent DNA tests, subverting court cases, disrupt hospital testing, steal sensitive genetic data, or corrupt DNA-based memory.

Fortunately, the risks of exactly this attack causing any problems in the real world are very low but the team wanted to highlight the potential for DNA based attacks, generally. They pointed out how lax the development processes and controls were for much of the software used in these labs. The bigger risk right now is probably from scientists falling for spear phishing scams (where fake emails pretending to be from someone you know take you to a malware website) or just forgetting to change the default password on the sequencer.

Paul Curzon, Queen Mary University of London

Password strength and information entropy

Comparison of the password strength of Tr0ub4dor&3 (easy to guess, difficult to remember) and correcthorsebatterystaple (hard to guess but easy to remember if you turn it into a picture) — CREDIT: Randall Munroe, xkcd.com https://xkcd.com/936 – reprinted under a CC Attribution-NonCommercial 2.5 License

How do you decide whether a password is strong? Computer scientists have a mathematical way to do it. Based on an idea called information entropy it’s part of “Information Theory”, invented by electrical engineer Claude Shannon back in 1948. This XKCD cartoon for computer scientists uses this idea to compare two different password. Unless you understand information theory the detail is a bit mind blowing to work out what is going on though… so let’s explain the computer science!

Entropy is based on the number of guesses someone would need to make trying all the possibilities for a password one at a time – doing what computer scientists call a brute force attack. Think about a PIN on a mobile phone or cash point. Suppose it was a single digit – there would be 10 possibilities to try. If 2-digit PINS were required then there are now 100 different possibilities. With the normal 4 digits you need 10,000 (10^4 = 10x10x10x10) guesses to be sure of getting it. Different symbol sets lead to more possibilities. If you had to use lower case letters instead of digits, there are 26 possibilities for length 1 so over 450,000 (26^4 = 26x26x26x26) guesses needed for the 4 letter password. If upper case letters are possible that goes up to more than 7 million (52 letters so 52^4 = 52x52x52x52) guesses. If you know they used a word though you don’t have to try all the possibilities, just the words. There are only about 5000 of those, so far fewer guesses needed. So password strength depends on the number of symbols that could be used, but also whether the PIN or password was chosen randomly (words aren’t a random sequence of letters!)

To make everything standard, Shannon used binary to do entropy calculations so assumed a symbol set of only 0 and 1 (so all the answers become powers of 2 because he used 2 symbols). He then measured them in ‘bits’ needed to count all the guesses. Any other groups of symbols are converted to binary first. If a cashpoint only had buttons A, B, C and D for PINs, then to do the calculation you count those 4 options in binary: 00 (A), 01 (B), 10 (C), 11 (D) and see you need 2 bits to do it (2^2 = 2×2 choices). Real cashpoints have 10 digits and need just over 3 bits to represent all of a 1 digit PIN (2^3 = 2x2x2 = 8 so not enough, 2^4 = 2x2x2x2 = 16 so more than you need so the answer is more than 3 but less than 4). It’s entropy would be just over 3. To count the possibilities for a 4-digit PIN you need just over 13 bits, so that is its entropy. The lower case alphabet needs just under 6 bits to store the number of possibilities, so entropy is about 6, and so on.

So entropy is not measured directly in terms of guesses (which would be very big numbers) but instead indirectly in terms of bits. If you determine the entropy to be 28 bits (as in the cartoon), that means the number of different possibilities to guess would fit in 28 bits if each guess was given its own unique binary code. 28 bits of binary can be used to represent over 268 million different things (2^28), so that is the number of guesses actually needed. It is a lot of guesses but not so many a computer couldn’t try them all fairly quickly as the cartoon points out!

Where do those 28 bits come from? Well they assume the hacker is just trying to crack passwords that follow a common pattern people use (so are not that random). The hacker assumes the person did the following: Take a word; maybe make the first letter a capital; swap digits in place of some similar looking letters; and finally add a symbol and letter at the end. It follows the general advice for passwords, and looks random … but is it?

How do we work out the entropy of a password invented that way? First, think about the base word the password is built around. They estimate it as 16 bits for an up to 9 letter word of lower-case letters, so are assuming there are 2^16 (i.e. 65,000) possible such base words. There are about 40,000 nine letter words in English, so that’s an over estimate if you are assuming you know the length. Perhaps not if you assume things like fictional names and shorter words are possible.

As the pattern followed is that the first letter could be uppercase, that adds 1 more bit for the two guesses now needed for each word tried: check if it’s upper-case, then check if it’s lower-case. Similarly, as any letter ‘o’ might have been swapped for 0, and any ‘a’ for 4 (as people commonly do) this adds 3 more bits (assuming there are at most 3 such opportunities per word). Finally, we need 3 bits for the 9 possible digits and another 4 bits for the common punctuation characters added on the end. Another bit is added for the two possible orders of punctuation and digit. Add up all those bits and we have the 28 bits suggested in the cartoon (where bits are represented by little squares).

Now do a similar calculation for the other way of creating passwords suggested in the cartoon. If there are only about 2000 really common words a person might choose from, we need 11 bits per word. If we string 4 such words together completely at random (not following a recognisable phrase with no link between the words) we get the much larger entropy of 44 bits overall. More bits means harder to crack, so this password will be much, much harder than the first. It takes over 17 trillion guesses rather than 268 million.

The serious joke of the cartoon is that the rules we are told to follow leads to people creating passwords that are not very random at all, precisely because they have been created following rules. That means they are easy to crack (but still hard to remember). If instead you used the 4 longish and unconnected word method which doesn’t obey any of the rules we are told to follow, you actually get a password that is much easier to remember (if you turn it into a surreal picture and remember the picture), but harder to crack because it actually has more randomness in it! That is the real lesson. How ever you create a password, it has to have lots of randomness for it to be strong. Entropy gives you a way to check how well you have done.

Paul Curzon, Queen Mary University of London

He attacked me with a dictionary!

Letters in an unreadable muddle — Image by JL G from Pixabay

You might be surprised at how many people have something short, simple (and stupid!) like ‘password’ as their password. Some people add a number to make it harder to guess (‘password1’) but unfortunately that doesn’t help. For decades the official advice has been to use a mixture of lower (abc) and upper case (ABC) characters as well as numbers (123) and special characters (such as & or ^). To meet these rules some people substitute letters for numbers (for example 0 for O or 4 for A and so on). Following these rules might lead you to create something like “P4ssW0^d1” which looks like it might be difficult to crack, but isn’t. The problem is that people tend to use the same substitutions so password-crackers can predict, and so break, them too.

Hackers know the really common passwords people use like ‘password’, ‘qwerty’ and ‘12345678’ (and more) so will just try them as a matter of course until they very quickly come across one of the many suckers who used one. Even apparently less obvious passwords can be easy to crack, though. The classic algorithm used is a ‘dictionary attack’.

The simple version of this is to run a program that just tries each word in an online dictionary one at a time as a password until it finds a word that works. It takes a program fractions of seconds to check every word like this. Using foreign words doesn’t help as hackers make dictionaries by combining those for every known language into one big universal dictionary. That might seem like a lot of words but it’s not for a computer.

You might think you can use imaginary words from fiction instead – names of characters in Lord of the Rings, perhaps, or the names of famous people. However, it is easy to compile lists of words like that too and add them to the password cracking dictionary. If it is a word somewhere on the web then it will be in a dictionary for hacking use.

Going a step further, a hacking program can take all these words and create versions with numbers added, 4 swapped for A, and so on. These new potential passwords become part of the attack dictionary too. More can be added by taking short words and combining them, including ones that appear in well known phrases like ‘starwars’ or ‘tobeornottobe’.

The list gets bigger and bigger, but computers are fast, and hackers are patient, so that’s no big deal…so make sure your password isn’t in their dictionary!

– Jo Brodie and Paul Curzon, Queen Mary University of London

from the archive

	Music AI Kriss Kross… on The day the music didn’t …
	Music AI Kriss Kross… on Separate your stems
	Musical Algorithms… on You’ll be Bach! – create…
	The art of animatron… on I’m (not) a little …
	The Decline and Fall… on Victorian volunteers needed…