Why Google Should Customize your Gmail Login Page to Prevent Phishing.

Disclaimer: The following post is uses Gmail and Google Accounts as a punching bag, but these problems discussed are both widely known, universal to identity providers on the web and not Google’s fault. Gmail has just been chosen to play the victim only due to it’s popularity and general bestness.

Password phishing attacks have been going on for over 25 years and the situation has only gotten worse. This post argues that by using a browser plugin to customize login pages on the client, attacks will have significantly greater difficulty forging believable login pages.

Two Phishing Attacks

I will argue this point by first showing two phishing attacks which would probably fool a fairly sophisticated computer user. These attacks are almost definitely not novel and are probably used in the wild. Compare these attacks to typical advice on preventing phishing. Consider the following two attacks:

Fake OAuth page: Websites will often allow users to authenticate with their google account using OAuth. If they are not logged into their Google account already it will ask them to login1. The workflow looks like this:

  1. Alice goes to a site that appears to have content that Alice wants.
  2. To access the content Website requires that Alice authenticates with her Google account before making a purchase.
  3. Alice clicks ‘authenticate with Google’ and is taken to a Google accounts login screen.
  4. Alice enters her username and password and is then allowed into the site.

Eve wants to steal Alice’s password so she setups up a website as above but in step 3 Alice is sent to a fake, but realistic looking gmail login page. Alice just gave her username and password away. Eve can interactively check if Alice’s provided a real username/password by supplying it to Gmail to see if it works. If Alice had Two-Factor authentication setup Eve can merely request a verification code from Alice as part of the login request. In fact if Eve wants to change the password and lock Alice out of her own account she can claim that the first verification code that Alice supplied (as part of her second factor) was incorrect and ask for a second one (loading the page for 60 seconds to wait for the first verification token to expire).

Tabnapping: Gmail has a habit of signing users out of their gmail accounts, which has trained users to sign back in at random points during the day. This can be exploited by crafting a page which when it detects that the user is inactive or idle it transforms into a fake gmail page saying that user has been logged out and that they should login again. This general approach is called tabnapping.

  1. Eve sents Alice a link to a fake Google Doc.
  2. Alice opens link and goes to bed, while she is sleeping the fake Google Doc rewrites itself so that it looks like a “you’ve been logged out, please login here” Google page.
  3. Alice wakes up, checks her laptop, logs into the fake Google login page. Game over.

Objections

Alice should be able to notice that she is signed into Google in other tabs: As [Google says]:(http://www.google.com/about/company/rewardprogram.html)

“At this time, the ability of malicious web sites to log users out of unrelated web applications is essentially unavoidable; it is a consequence of how the web is designed, and cannot be reliably prevented by any single website.” This means that Eve can log Alice out of her Google Account. In fact Eve can keep logging Alice out until Alice logs into Eve’s fake Google Account.

Alice can tell the difference between the fake login page and the real login page by inspecting the URL: Unfortunately there are really effective ways of making fake but undetectable urls (see also URL redirecting).

Alice uses HTTPS so she is safe: Phishing sites legally acquire valid HTTPS certificates. HTTPS offers zero protection in this scenario, other than the minimal cost to request a cert for a domain they control.

A Solution

The crux of the problem is that users have no way2 of telling a real Google accounts or Gmail login page from a fake one since the styling of a login page can be easily copied.

Customize/Skin the Login Page: Users will often skin or customize the look of the internal gmail web application by choosing a theme. Google should force new users to choose a unique skin for their ‘trusted’ home computer and persist this skin even when they are not signed into their Gmail account so that the skin will be applied to the login screen for their Gmail account. This skin would persist on the client 3, so an attacker would not be able to learn it by querying Google. Since the attacker can’t learn the skin that user is using, the attacker can’t replicate what the user expects to see. Thus the attacker will have difficulty fooling the user4. An example skin is shown below.

qr-codes: For added security the page could display a qr-code which the user could scan with their mobile phone to log themselves in without typing in a password. Isaac Potoczny-Jones has a neat blog post on using qr-codes as authentication5.

Problems

There are several problems with training users to use the look of a website to determine its trustworthiness.

  • The unique skin is now acting as a authentication to the user, but browsers and security models are not designed to protect how gmail looks to a user. Screen sharing skype sessions, xss attacks and photos could expose the look of the skin which then an attacker could copy. Since the user now trusts login pages that have their unique skin they will be easier to fool if the skin is compromised.

This is a real risk, but users already use the look of a webpage to judge it’s trustworthiness. Most phishing attacks are not targeted and this would stop these sorts of attacks and seriously complicate more advanced attack.

  • The unique skin can not persist across clients. The first time a user uses a computer they have to login to a plain page or a page which has the skin of another user.

This solution probably wouldn’t be that useful for people that use many difficult computers.

  • Chrome already has this functionality in that you can sign into chrome.. Since you are signing into the browser rather than into webpage phishing is impossible.

Unfortunately, signing into Google Chrome does not automatically sign you into all your Google Accounts. Passwords can be saved in Google Chrome, but there are numerous ways to trick someone into entering their password into a realistic looking login screen.

  1. For an example how legitimate sites do this go to goodreads.com in safe/incognito mode and click on the “sign in using Google” button. ↩

  2. Yes, yes, they can check the certificate of the page and maybe catch a poorly generated cert, but how many times do you check the certificate of the page when you login to Gmail? ↩

  3. This is really the tricky part as an attacker can wipe browser cookies at will. One surefire way would be to use a browser plugin or use the Google Chrome Sync functionality. ↩

  4. All users can be fooled given enough time and effort. ↩

  5. I don’t see any reason why Google is not doing this already. They support Two-Factor authentication. While qr-auth is as vulnerable as username/password schemes, a successful attack only steals a one-use token rather than a username and password. This would be perfect for situations in which someone is concerned about a keylogger. In fact if you combine qr-auth with a browser plugin it becomes more secure than username/password schemes since the plugin can verify if the page is gmail or not. ↩

BrainCookies, Johnny Mnemonic, and Other Uses for ‘Neuroscience Meets Cryptography’.

neuro things

In ‘Neuroscience Meets Cryptography: Designing Crypto Primitives Secure Against Rubber Hose Attacks’ Bojinov, Sanchez, Reber, Boneh, and Lincoln introduce a system for using implicit learning to store passwords in people’s subconscious. Because the person does not consciously know the password they will be unable to reveal it even if under legal coercion, interrogation or torture. This post will informally introduce the system and then look at some off-label uses for this and related techniques.

Neuroscience Meets Cryptography

To learn a password: The user plays a game very similar to Guitar Hero for 30 minutes, the game implicitly teaches the user to perform certain actions in certain situations (think something like muscle memory). The game records that they were taught certain subconscious behaviors.

Authentication: The game tests the users ability to play the game for 15 minutes. The responses of the player are dependent on some of the behaviors they subconsciously learned. Thereby the game can learn what password the player was taught.

The player does not consciously know the password. The learning phase and the authentication system are done in a controlled environment so that no one can watch the player play. The player does not have the ability to reveal the password, so the player can not be made to reveal the password, nor can an attacker learn the password using a game without first knowing the password1.

Alternative Uses

A big cookie

Brain Cookies: One alternative use of this technology would be to use it to covertly record uniquely identifying information in people’s subconscious. The immediate use of this that jumps out is a replacement for browser cookies. Website forces users to solve captchas to download content. The captchas can be implicit learning devices similar to the system above or they can be trivia questions such as “Who is the 23rd president?” or which of these shapes fit together that rely on explicit learning. Once a user has learned a fact or game, the speed and accuracy at which they answer that question or play that game can be used as identifying information. A big enough set of questions/abilities should be able to uniquely identify a person covertly. So the website does exactly that an tracks users using their own subconscious.

Anti-Cheating: A serious problem facing games such as Poker or World Of Warcraft is how to prevent cheating by collusion or by automation. For example: consider a game in which you want to tell if any of the player avatars are being controlled the same player. Get each avatar to perform game tasks to implicitly trains each player with a different password and then test each avatar to determine if any of the players have multiple passwords.

Or better yet use such a system to determine if a human or bot is playing the game (implicit learning as Turing test). Games such as World of Warcraft attempt to prevent players from using bots. Since a bot is not going to display implicit learning (or usually any learning for that matter), a game can covertly test if any of the players are computers or not by building an implicit learning task into the game mechanics. It is possible to build implicit learning into a computer program, but it is unlikely that a bot maker would consider such an attack in their threat model. Of course this means that the success of such a detection system depends on it’s complete secrecy from the bot makers, but it should not be difficult to build such a detection system such that it would look like a normal part of the game with the actual detection logic existing outside the client2.

Johnny Mnemonic

Johnny Mnemonic/Subconscious Stenography: Use the method in the paper, but instead of storing a password in someones subconscious, store a piece of secret information. The person with this information could act as a data courier similar to the protagonist of the short story Johnny Mnemonic. In fact the courier or mule might not even know they have this data stored inside of them they just played a game. The courier could pass through national borders with nothing incriminating to be found3.

brains

  1. Or so the paper argues:

    ”[..] the attacker intercepts trained users and subjects each one to queries, [..] ( [to succeed] this amounts to about one year of nonstop testing per user which will either interfere with the user’s learned password rendering the user useless to the attacker, or alert security administrators due to the user’s absence prompting a revocation of the credentials). Hence, even after capturing u = 100 users, the attacker’s success probability is only $2^{-16}$ Further complicating the attacker’s life is the fact that subjecting a person to many random SISL games may obliterate the learned sequence or cause the person to learn an incorrect sequence thereby making extraction impossible. ” - ‘Neuroscience Meets Cryptography: Designing Crypto Primitives Secure Against Rubber Hose Attacks’

    ↩

  2. Who knows maybe Blizzard is already doing this. ↩

  3. Bot net nodes could use this as a very sneaky covert channel. A botnet uploads a hacked copies of video games to piratebay. Players play the games, implicitly learning messages and passing the messages to the other games. ↩

A Review of William Liscum Borden’s ‘There Will Be No Time: The Revolution in Strategy’.

There Will Be No Time Book Cover

On my way home from work I came across of number of military books put out for garbage collection. Among the discarded books was a book published in 1946 on the strategy of nuclear war called “There Will Be No Time: The Revolution in Strategy” by William Borden1. This book anticipates paranoia and spirit of the cold war (“We must think unthinkable thoughts and do unthinkable deeds and our enemies are preparing to do worse to us.”). Now 50 some odd years later what did Borden get right, what did he get wrong.

Nuclear War as Tactical rather than Strategic.

His main claim is that nuclear wars are purely tactical rather than strategic. What he means by this is that an attacker in a nuclear war must choose between destroying strategic targets like cities or tactical targets like nuclear missile launchers and nations will choose tactical targets rather than strategic targets. This distinction later came to be referred to as countervalue (enemy cities) vs counterforce (enemy missile bases). His argument rests of the following claims:

  • Nuclear war is so fast that destroying a city does not provide any military benefits to the attacker nor any military costs to a defender.
  • Each bomb spent on an enemy city could be spent on an enemy missile base, each bomb spent on a missile base destroys many enemy bombs.
  • Therefore from a cost/benefit state point, nations will attack each others military and not civilian populations (nuclear wars will be wars in which both sides aim to disarm the other side by bombing each others weapons).
  • The winner will be the side that still has nuclear weapons left.

Furthermore he argues that since a nuclear war is not about destroying cities but about destroying weapons, a nation that hopes to win must have as many weapons as possible (the side that runs out of weapons loses). Thus, a nuclear deterrence strategy around having enough nuclear weapons to destroy all the enemies cities will not work because the targets will be missile bases not cities (if you fire all your missiles at cities, the enemy wins since you are disarmed and they have a full stockpile of nuclear weapons). This is directly opposed to the argument made by Bernard Brodie in ‘The Absolute Weapon’ that no one can win a nuclear war, rather they can be averted by establishing a credible deterrent (aimed at an enemies cities).

“Thus far the chief purpose of our military establishment has been to win wars. From now on its chief purpose must be to avert them. It can have almost no other useful purpose.” Bernard Brodie

Borden takes an extremely rationalist game playing approach to strategy that completely ignores human psychology. Brodie understands that emotions are extremely important in war and the strategy of war2. We do not know absolutely if Brodie is right or if in fact Borden is right, but it seems that a counter-value deterrence was a far more successful strategy than Borden anticipated. Also modern simulations and predictions about Nuclear War look much more like Brodie argued.3

Additionally Borden believed that all future wars that involved nuclear powers would be nuclear wars and therefore conventional military units would be worst than useless since they would divert money from nuclear weapons research and production. This turns out not to be the case.

What Borden Got Right.

I haven’t read much Nuclear Strategy from this time period, so I can not say if this book is merely reporting on what military planners knew at the time4 or if Borden is truly blazing a path. Regardless, ‘There Will Be No Time’ makes some incredible predictions:

  • The future development of Nuclear tipped Intercontinental Ballistic Missiles (which he refers to as long range “V-2“s) as a replacement for Strategic Bombers (missiles better than bombs).
  • The strategic value of submarines and naval vessels as nuclear missile platforms5.
  • The Inability to develop an effective shield against Nuclear missiles.
  • The development of unmanned aircraft (drones) for reconnaissance.
  • The use of nuclear weapons placed in orbital platforms (developed as Fractional Orbital Bombardment by CCCP in the 1960’s ) and it’s value for creating unpredictable missile paths to avoid early warning systems.
  • The inability to manufacture new nuclear weapons once a conflict has begun (nuclear wars are fought with the stockpiles built prior to the war). Thankfully this one hasn’t been tested, but it is now standard doctrine.
  • The value of quality over quantity in weapons and thereby the value of weapons research.
  • The use of suitcase nukes and nuclear attacks of unknown origin.
  • The creation of more powerful atomic weapons.

Paranoia.

“The time to attack is not after the aggressor’s diplomats have walked out of the United Nations but after speeches in which they have praised it and declared that nations cooperate or perish.” Borden - ‘There Will Be No Time’.

The first half of the book is fairly rational in terms of it’s analysis of how nuclear weapons would likely be used. The second half of the book is dedicated to an extreme form of cold-war paranoia. He argues that since the US can not know the motivations of foreign governments and the suprise is key to a nuclear attack, we can not tell if gestures of peace are made in good faith or merely to get the US to let it’s guard down, thus nations that preach peace are likely planning the nuclear annihilation of the US. I suspect that this paranoia comes from his immediate experiences with the Axis power’s willingness to attack allies while still under the banner of peace (The term “Atomic Pearl Harbor” is used countless times).

One World Government

One World or None Nuclear War Prevention: “One World or None” circa 1950 National Committee on Atomic Information

“It is reasonable to suppose that peace will replace anarchy among nations only when an inclusive world state monopolizes all power and is therefore able to discipline each individual man or any combination of men. Such a global state could tolerate no armed force loyal to any other authority other than itself, and it might even supervise and control local policemen. Only thus can present-day nation-states assure peace within their respective borders.” Borden - ‘There Will Be No Time’.

The most interesting thing reading this book was his advocacy for a one world state. I had assumed that such ideas were as unpopular in 1946 as they are now (ZOMG UN black helicopters), but I have subsequently read several other position papers from that time period and it appears that calls for a global authority with an absolute monopoly on nuclear weapons was quite common6. As far as nuclear strategy is concerned Borden doesn’t think a world government is likely before another world war and so dismisses it as a possible achievable means for peace.

Conclusions

‘There Will Be No Time’ is an interesting artifact from the past. It succeeds in it technical predictions but it’s prescriptive strategy is misses the mark because it assumes that nations will obey the rules of high-reason rather common human psychology. A mistake that would be made many times by later thinkers such as Herman Kahn.
It’s simple in its language and not badly written, but some of the themes repeat themselves. It also has uncomfortable reference to various races (usually used to represent nationalities), yellow peril, and cold war everyone-is-a-spy paranoia that is to be expected from a book of this time period written by a member of the US government (consider that the US government just carried out the Japanese American Internment). Overall an worthwhile read if you are interested in the history of the development of US nuclear strategy.

Appendix on William Liscum Borden

While researching this book I couldn’t find much collected information on William Liscum Borden so I have collected various facts and recollections here:

‘The man who provided the argument and the occasion was William Liscum Borden, a single-minded young zealot who thought he knew why Oppenheimer resisted Air Force demands for hydrogen bombs—”more probably than not,” Borden wrote the head of the FBI in November 1953, “J. Robert Oppenheimer is an agent of the Soviet Union.”’ An American Tragedy - The Atlantic

For the more conspiracy minded:

“Oppenheimer was targeted by the coal and big oil companies who were scared to death that he’d undermine their profits with cheap nuclear energy. So they used the testimony of Kenneth Pitzer and William Liscum Borden to ruin his credibility with the help of Joseph McCarthy’s Red Scare. They branded Oppy a communist. That saved their asses, but they saw a new opportunity to use our irrational fear of atomic bombs to get us all to shell out the bucks,” Death Bed Confession Sheds New Light on Atomic White Wash.

Another alarmed and influential participant that winter and spring of 1949 was a twenty-eight-year-old Yale College and Yale Law graduate and former bomber pilot named William Liscum Borden — a small man with a square jaw, blond, with blue eyes. Bright, ardent and Utopian, Borden had been an isolationist who had converted to interventionism shortly before Pearl Harbor. He had enlisted in the US Army immediately after graduation in 1942, volunteering to fly bombers, and saw three years’ service flying out of England with the Eighth Air Force. He had lost a college roommate and a relative to the war. Of the “men who died,” he wrote angrily in the months after victory, “many of them would be alive today had a little more honest realism been displayed before Pearl Harbor.” The honest realism Borden had in mind was “to think realistically about the worst that could befall as well as the best.” He had seen a V-2 rocket “streaming red sparks and whizzing past us” on its way to London one night in 1944 when he was returning in his B-24 from a mission to Holland. Hiroshima had a further “galvanic effect,” he said later, and he had “decided instantly that this was the most important thing in the world.” Between his military discharge and his entry into law school, Borden began writing a book that would “think straight about the strategic implications of the new weapons.” He called it, urgently, There Will Be No Time.

[..]

Borden published There Will Be No Time to modest sales in 1946. After graduating from law school the following year, he returned to Washington, where his family lived, to work for the Justice Department. From there, it seems, pursuing his Utopian visions, he and two law school classmates wrote Brien McMahon an alarming letter. They named it “the Inflammatory Document,” as if they were christening a new bomber; it proposed that the United States should take advantage of its atomic monopoly while that monopoly still existed and simply give Stalin a nuclear ultimatum: “Let Stalin decide — atomic peace or atomic war.” McMahon was Borden’s parents’ neighbor; the putative author of the Atomic Energy Act took Borden to lunch, rejected the young lawyer’s Churchillian brinkmanship but tendered him a job as legislative assistant. Borden joined McMahon’s Senate staff in August 1948. Congress went Democratic in the November elections that year and McMahon replaced Bourke Hickenlooper as chairman of the Joint Committee on Atomic Energy. Jn January 1949, the former bomber pilot who believed that only massive atomic strength could delay war with the Soviet Union became executive director of the Congressional committee that oversaw the development and production of the United States’s atomic arsenal. Dark Sun: The Making of the Hydrogen Bomb

  1. There were a few reviews after he published and a review by crisisofenclosure in 2010. ↩

  2. Clausewitz agrees with Brodie, which makes sense since Brodie was well read in Clausewitz. In fact it might make more sense to say Brodie agreed with Clausewitz. Certainly the connection has been made between them more than once.

    ”[..] it would be an obvious fallacy to imagine war between civilized people as resulting merely from a rational act on the part of the governments and to conceive of war as gradually ridding itself of passion, so that in the end one would never really need to use the physical impact of the fighting forces - comparative figures of their strength would be enough. That would be a kind of war by algebra. Theorists were already beginning to think along such lines when the recent wars taught them a lession. If war is an act of force, the emotions can not fail to be involved.” Clausewitz On War’

    ↩

  3. For a game which illustrates the countervalue/counterforce dilemma check out ‘Defcon: Everybody Dies’ by introversion software. It has several point scoring systems that model either Borden ideas (counterforce) or Brodies ideas (countervalue). See the manual for the score modes. ↩

  4. The book is more than just Borden’s ideas as much of the book is based on congressional testimony on Nuclear War given after the atomic bombing of Hiroshima and Nagasaki. ↩

  5. The Germans were attempting to launch V-2’s for their submarines, so it was not an unheard of idea but Ballistic missile submarines were not a reality until 1959 with the Soviet R-13. ↩

  6. See Robert C. Tucker’s ‘No First Use of Nuclear Weapons: A Proposal’(1963) or ‘One World or None: A Report to the Public on the Full Meaning of the Atomic Bomb’ (1946). The World Government has been in the public consciousness since before the 1930’s with H.G. Wells ‘The Shape of Things to Come‘(1933) and Olaf Stapledon’s fantastic book ‘Last and First Men’ (1930). ↩

Imagining a Secure Backdoor Cipher.

Lets say that you have an unbreakable cipher (or it’s closest approximation) and that you, Eve, have the ability to break all other known ciphers. There is a risk that if you use or deploy your unbreakable cipher it may be captured by your enemy Alice and thus prevent you from eavesdropping on Alice’s communication. What should you do?

Use an Insecure Cipher: One option is that Eve could use a cipher that she can break. Thus if the cipher is captured and used by Alice, Eve can still eavesdrop. A problem is that Alice may also discover this weakness and use it to listen to Eve’s communications1. One possible solution is to be design a secure cipher with a small enough key space that Eve could brute force the keys, but Alice with less resources would be unable to. This is a less than ideal solution because Alice may, in time, be able to build more powerful computers to allow her to break the cipher.

Weak Keys: It is not unimaginable that a cipher could exist which is secure only under some of its keys2. For example consider a cipher that is secure when the first bit of the key is $0$ but totally insecure when the first bit of the key is $1$. Lets construct a trivial example of such a cipher:

Encrypt(key, plaintext)
    if key[0] == 1
      return plaintext
    else 
      return SecureEncrypt(key, plaintext)

While the trivial example seems rather silly, I see no reason why a secure cipher and an insecure cipher might not be mixed together such that the cipher is only insecure under certain keys without being as obvious as our example. Under such a system Eve could choose to only use the strong keys and Alice would on the average use a weak key half the time.

Distinguishing Weak Keys: For Eve to use this system securely there must be a way of telling apart strong keys and weak keys. Assume Eve has a key generator that will only output strong keys. If Alice captures this key generator then Alice will be secure as she can now generate secret keys. Therefore spooknet can never put the key generator into the field. Instead Eve can pre-generate lists strong keys for use. If Alice captures some of these strong keys and uses them, Eve can still decrypt the messages since Eve has a copy of all the strong keys she has generated so far she can just try all the keys she has issued.

Laugh-Out-Loud Cats #736

Assumptions: This whole fantasy is based on the existence of certain functions for which there is no evidence that they exist. We need a function, $F$, that generates our backdoored cipher $C_k$, the strong key generator $G_k$, and the weak key attack function $A_k$, all under some key, $k$.

$$C_k, G_k, A_k \leftarrow F(K_k)$$

$C_k$ is the backdoored cipher we have been discussing all along. Under half its keys it is secure, under the other half of its keys it is unsecure. Given $C_K$ it is impossible distinguish the secure keys from the unsecure keys unless you have $k$.

$G_k$ is the strong key generator. Given a random seed $G_k$ produces a strong key. It has the property that even given many many secure keys and weak keys, one can not learn any information about $G_k$ or $k$.

$A_k$ is the attack function. Given some number of ciphertexts encrypted under an insecure key, it will determine the plaintext values.

$$\text{ciphertext} \leftarrow C_{k}\text{.encrypt}( \text{weak_key}, \text{plaintext} ) $$ $$ \text{plaintext} \leftarrow A_{k}( \text{ciphertext} )$$

Conclusion: If someone can find functions for which the above properties hold, they can generate a cipher which can be used securely by anyone that knows $k$ and not securely by everyone else. The biggest problem with the scheme is that SpookNet must store all the secure keys it has generated and transmit these keys to its users. Given the danger of these key being compromised prior to use one would have to develop hardened key stores for physically distributing the keys.

  1. One version of a built in weakness might be that given a particular plaintext the cipher outputs the key or some data which can be used to discover the key. ↩

  2. A variant of blowfish appears to be slightly less secure with certain keys than others. ↩

A Look at Security Through Obesity

A Very Heavy Strong Box

Jeremy Spilman has an excellent post (in two parts: part 1 and part 2) on ways to increase the security of the storing password hashes. Please read his full post for details as this post will be about the general idea and it’s further implications. I will be examining his scheme and developing related schemes that use ‘Security Through Obesity’ in this post. This entry is a rough sketch of some of the ideas that the Spillman scheme inspired.

Security Through Obesity1

‘Security Through Obesity’ Is the notion that you artificially increase the size of information you wish to protect to make it hard for an attacker to steal and hard for an attacker to store. Such a strategy has an analogue in the physical world. It is very common for safes or other protected objects to be made really heavy and awkward so someone can’t just walk away with it.

tl;dr Digital objects are very easy to secretly replicate and distribute unless they are very very large.

Protecting Password Hashes

The secure storage of password hashes is extremely important but sadly the technologies used and best practices have not evolved substantially since before 1978. Sure everyone uses salts (or atleast regrets not using salts), but salts project against only a very narrow risk and one which is generally not relevant due to the ascendancy of GPU brute force attacks2.

All of the password hash best practices are focused on making the hashes hard for an attacker to break but they ignore the equally important aims of preventing an attacker from accessing the hashes in the first place and detecting that an attacker has gained access. Detection is important because if users can change their passwords fast enough after a compromise the stolen hashes are of little value.

Security Through Obesity Password Hash Scheme

In Spilmans post he suggests creating two tables: a user table (consisting of the username and the salt) and a hash table (consisting of password hashes)3 with no direct connection between the two tables.

  1. User enters username and password.
  2. Salt is looked up in the user table for that username.
  3. Hash is computed from salt + password.
  4. We look up the hash we just computed in the hash table if we find that it exists in the hash table we authorize the user.

Since the only relationship between the user table and the hash table is the password (which is unknown) an attacker has no way of telling if a particular hash matches to a particular user without guessing a password. In fact an attacker has no way of telling if a hash is used by any user at all except through process of elimination. Therefore if we generate a large numbers of fake hashes and storing them in the hash table, the attacker at compromise time is unable to tell the real hashes from the fakes therefore must download all the hashes. Since the hash table which the attacker must download to break the hashes can be made arbitrary big, downloading these hashes presents a serious bandwidth and storage problem to an attacker.

This has the following benefits (for the sake of example lets assume that the hash table has been expanded to 1 TB by adding fake hashes):

Slow Down the Attack: Downloading 1 TB of data from a server at 50 Mbit/s ( using a T3 ) takes roughly 44 hours and likely much much longer.

Make the Attack Louder: This bandwidth spike will likely be noticed and shut down before an attacker has completed the download. Thereby denying the attacker all the password hashes and also detecting the compromise so that users can be alerted to change their passwords. Additionally an alert could be placed on the bandwidth the database uses so that if it spikes a warning is triggered (even if it isn’t an attacker downloading all the hashes, it probably a good idea to be alerted when a db starts using 100x it’s normal bandwidth).

Force a Direct Connection: An attacker can’t get download speeds approaching 50 Mbit/s using Tor or proxy networks. Therefore an attacker must either use a compromised host with lots of bandwidth or connect directly. Both of these options are sub-optimal for an attacker since they open up the possibility that the attacker will lose control a very valuable compromised host or that the attackers ip address will be exposed.

Increase Resource Costs: An attacker must have a location to store all of this data. Moving this data or publishing it online for others to crack becomes extremely expensive (you can’t post 1 TB files to paste bin).

Traffic Pattern Analysis: A 50MBit/s download for 44 hours creates a easy to detect pattern over network links. If an attack is detected early enough the download can be traced to it’s destination by traffic analysis even across multiple proxies or hops in a botnet.

Setting A Trap

Having a hash table (as in the ‘Security Through Obesity’ scheme) filled with fake hashes suggests an additional security measure, setting a trap. We have values in the hash table that we know only an attacker would request, thus we have a means to distinguish the behavior of a success attack from benign actions4.

Web Application Traps: Add code to your templates such that they always check for certain hash values when being rendered. If these values are found send an alert and refuse to render the page.

Network Traps: Setup your firewall to look for a few of the fake hash values (enough to catch a download early), send an alert if these values are being sent over your network.

Google Traps: Create google alerts and other automated systems to alert you if certain hash values ever show up on google or paste bin.

Account Traps Why stop at fake hash values. Create realistic looking usernames and hash values (with easily guessed passwords), so that if an attacker logs in with one of these trap accounts you will know that the hash table has been compromised5.

Protecting Encrypted Files with Security Through Obesity

So far this entry has focused on secure password hash storage using ‘Security Through Obesity’ but by no means is that the only area that can be improved by this technique. In this section we will show how to use ‘Security Through Obesity’ to protect encrypted files by building systems of increasing sophistication. My aim here is not to develop a ready made solution but to explore the ways in which download bandwidth and harddrive limitations can be a contraint on attackers.

The Trivial System: Consider the most trivial way to do this. Take a plaintext file, mix in 1 TB of random data by alternating between bits of the plaintext with the ciphertext ( plaintext bit between every n bits of random noise), and then encrypt using CBC this mix.

$$ \text{mix}( P, R ) \rightarrow P_0 | R_{0..n} | P_{1} | R_{(n+1)..2n} | … $$

$$ \text{EncryptCBC}( k, \text{mix}( \text{file},\text{1TB random data} ) ) $$

Lets look at two situations: the attacker has access to the encrypted file but not the key and the attacker has access to the key and the encrypted file. In the first case this scheme will slow down the attackers ability to download the file and provide a defender the other benefits of Security Through Obesity (high chance of detection, etc…). Unfortunately in the second case the attacker can just decrypt the file and exfiltrate the much smaller file. This isn’t extremely useful since the real threat is the attacker learning the plaintext, but this only slows down an attacker if she doesn’t have the key. Furthermore since we are using CBC mode an attacker could download two contiguous blocks of the ciphertext and later if they learn the key they could encrypt the bit in the last block. This is a very bad quality since it allows the attacker to avoid some of large size protections here and learn something about the plaintext.

A Slightly Better System: Use secret sharing to expand the data into $n$ shares that total to 1TB then random permute the order and bits of these shares and add a table of contents such that the table of contents, $tc$ can reconstruct the original shares. Encrypt the whole mess with CBC.

$$ \text{shares} = text{secret_share_expander}( \text{plaintext} )$$ $$ \text{tc}, \text{shuffled_shares} = \text{permute}( \text{shares} )$$

The object here it to prevent an attacker from learning anything about the plaintext without downloading and decrypting a significant subset of the encrypted file. Of course as before if the attacker has access to key and the encrypted file on the server, she can extract the small plaintext and download that.

Adding a Workfactor: The problem we arrive at is that if an attacker has access to both the encrypted file and the key then ‘Security Through Obesity’ adds no security benefit. One solution is to add a workfactor so that decrypting the file becomes a serious bottleneck to an attacker. Consider an decryption algorithm that takes 100 hours to run on the hardware that the data resides on. Note that this solves one of the typical problems with Time-Release Cryptography in that the attacker is either forced to copy the file to a more powerful machine or an attacker is forced to perform the decryption on a machine of our choosing, in either case we can lower bound the time before the attacker can decrypt the message( $\text{min}( \text{time_to_download}, \text{time_to_decrypt} )$ ).

Use Cases: While in most situations this is hardly ideal since fast decryption is a requirement, I can think of many situations in which a file is of such secrecy that a 100 hour wait would be acceptable.

Consider someone is physically transporting a small collection of very secret data (missile codes, ssh keys, zero-days). The best course of action would be to first encrypt this secret data and send the key by a secure channel (public key crypto over the internet springs to mind). The problem this ‘Security Through Obesity’ solves in this circumstance is that if someone covertly steals the data from you they will not have time to make a copy before you notice that it is gone. If they manage to capture both the key and the encrypted data they will not be able to quickly decrypt the data giving you time to react and take preventative measures (change the codes). Furthermore these measures prevent attackers from quickly transmitting this data allowing the defender time to either recapture it or at least slowing down the attackers ability to use it for their advantage.

Conclusions

‘Security Through Obesity’ does not provide the type of hard and sometimes brittle security that typifies most security measures. What it provides is the ability of defenders to apply a frictional cost on an attacker. While this sort of thinking is standard in physical security (big heavy things harder to steal) it is often over looked in information security which is a shame since it allows much needed and different quality of security.

  1. Alex_w on reddit came up with the term Security Through Obesity in a reddit thread in response to the Spilman post and I think it encapsulates this sort of idea perfectly (Spilman seems to agree since he edited his post to add the phrase). ↩

  2. Reddit user Solardiz was kind enough to point out that salts protect against a variety of time-memory and precomputation of which rainbow tables is a subset and that while salts do make GPU attacks more difficult (but they are not a sufficient security measure to defend against GPU attacks, one must still use a high workfactor). ↩

  3. Spilman’s scheme is a little more complicated than I have written here since he wishes to avoid the possibility that an attacker with access to another users salt and the ability to insert arbitrary values into the hash table could craft another hash which matched the users salt ( salt|password1, salt|password2). These details are not relevant to our discussion, but his solution is neat and you should read it. ↩

  4. There is almost no chance of false positives because the probability of random data colliding with hash values (assuming you are using 512 bit values) is much lower than the probability of an asteroid destroying your data center. ↩

  5. In fact it is an excellent idea to create a few fake user accounts with real email addresses and no guessable password. Attackers will sometimes sell email addresses to spammers. If these accounts start getting emails you learn that an attacker has compromised this information. Same idea works by putting hardcoded ssh keys in your code. If anyone uses these keys they attempt to connect to a server an email alert is sent out. ↩

Castle meet Cannon: What to do after you lose?

Most strategies are based around winning but what happens if you can’t win?

In my last post I talked about flipIt. One of the things that fascinates me about flipIt is it forces you to think about what you do when defense is impossible. In this post I’ll explore the evolution of fortress and castle building from the 12 Century to WW1 and it’s implications for network security.

Early Fortifications

Fortifications in 12th Century and before (pretty much all the way into the classical era) were designed to keep enemy soldiers outside the perimeter of the fort (such a fort is picture above). Doors were recognized as weak points which could be set on fire or smashed in and so the fortifications were designed to protect these vulnerable areas by reducing their surface area and allowing defenders to concentrate projectile and other violence against attackers approaching the doors. The more robust fortifications had two static lines of defense. If the first wall was breached the defenders could fall back to a second inner wall. Often to the fortification’s credit attackers choose to starve the defenders out rather than attempt to breach the walls. Winning was successfully holding a static perimeter.

Device Fort

A device fort

With the introduction of gun powder and use of cannons in Europe, fortifications came under greater threat. The general response was to mitigate the effect of cannons through rounder thicker walls, lower towers, and to place cannons on the wall themselves to provide a deadly response to the besieging cannons. In 1539 Henry VIII carried out such a program of fort modernization in Southern Europe and these fortifications became known as device forts. A device fort is pictured above, notice the thick circular squat walls designed for deflecting gunpowder weapons.

Star Forts

Unfortunately for defenders cannons kept getting stronger and building thicker castle walls hit a point of diminishing returns in terms of defensive utility and increasing cost. While cannons can easily destroy castle walls, (re)building castle walls is a extremely expensive. Furthermore stone and brick walls are static lines of defense that, by design, can not be easily moved to react to changes. A fort which was once strategically important is now left defending nothing of value.

The last of this approach of increasingly expensive threat mitigation was the beautiful star fort (shown above). Star forts had very short thick angled walls to defect projectiles and overlapping fields of fire to create a stand off distance.

Game Over: Again the power of cannons and artillery increased making even star forts highly vulnerable. Relying on the idea that walls could create an effective perimeter to keep attackers out now guaranteed failure. Defenders could no longer maintain an unbreakable perimeter. They had lost, and what happened next as interesting and successful as it’s results were terrible.

Trench Warfare

The solution was trench warfare. Trenches are cheap to build and repair. A defender can afford to build many lines of trenches if the first series of trenches are taken. Additionally if a particular trench position is destroyed or overwhelmed, new trench formations can be built quickly to respond to the changing dynamic. Combined with machine guns and barbed wire, trench warfare tilted the balance of war strongly in favor of defenders1.

Resiliency over Robustness: Perimeters were still impossible to defend, defenders still always lost, but it did not matter since new perimeters could be built before an attacker could take advantage of their success2.

This was the triumph of resiliency of humans + shovels over the robustness of stone walls. If losing is cheap enough you can still always lose and end up winning.

Stonewalls and Firewalls

This arms race of perimeter defense with increased cost and decreasing effectiveness has been mirrored in network security.

  • First we tried securing of our networks by requiring credentials to gain access and reducing surface area (protecting doors).

  • After that failed we added chroot jails, firewalls, automatic updates and IDS(second lines of defense, making the walls thicker). We added VPNs, sandboxing, and trusted computing chips creating star forts with multiple static fallback positions.

While all of these protections raise the security of our networks they are fundamentally based on holding a series of static perimeters. They are designed to raise the cost of an attack, but they also raise the complexity and cost of defending.

All the money that google spends on defending their network perimeter was completely defeated by an IE zero day.

Some Ideas

We need to accept the fact that there is no such thing as a secure perimeter3, that all of our most trusted systems will be repeatedly compromised, that defenders can never win. What do we do after we have lost? Reduce the cost of losing to the point that losing becomes affordable.

This list is written in goal -> method format.

  • Increase the speed and the decrease the cost of recovering from a compromise -> we have a factory reset button on mobile phones why not on servers.
  • Decrease the cost of data loss -> protect data rather than perimeters4.
  • Don’t be dependent any on part of your network -> release the chaos monkey!
  • Stay alert -> use tools to process, analyze and view log files even when nothing is going wrong. Add log files to your feedback loop, they are your eyes.
  • Hedge system integrity checks with things you don’t control -> use google analytics to check your work, send checksums of files by email to a gmail account who’s password no one knows and is stored in a company safe.
  • Stay nimble -> value software/hardware that can be easily and quickly altered/changed ( see the unix philosophy ), create the same system twice with two teams randomly fall over between the two systems, build layers of abstract to allow rapid transitions.
  • Increase organisational agility -> try multiple approaches to the same problem in parallel rather than in series. allow people to take risks, provide a space for people to change their minds without looking bad, make decisions locally and quickly and then iterate on the feedback,

tl;dr Central claim is that: (1). After a certain point in an arms race security strategies based on increasing the cost that an attacker must pay to succeed hit diminishing returns. (2). After this point the best strategy is to reduce the cost that a defender must pay when an attack succeeds.

  1. The reader should be careful to note that trench warfare was not the final development in defensive tactics and it was been quickly eclipsed by new offensive strategies including maneuver warfare (which predates trench warfare), infiltration tactics (which was developed in response to trench warfare) and aerial warfare (which renders trench warfare suicide without sufficient air defense). That being said, trench warfare with the addition of other tactics remains widely used in modern conflicts almost unchanged from its initial conception. ↩

  2. This strategy can also be seen in the development of armored knights. In response to gunpowder weapons, personal armor was strengthened (using new alloys) and thickened. This hit diminishing returns at which point armies switched to large numbers of unarmored conscripts. ↩

  3. Can anyone point me to a working link for Herzog’s talk “The Mobius Defense” slides. I read them a few years ago but all the links to it seem dead. ↩

  4. The idea that perimeters are easily broken so instead make everything a perimeter has been tried as a national ground warfare strategy in Albania. ↩

FlipIt: An Interesting Game

Shall we play a game?

This post is the first of several posts inspired by the game of flipIt. FlipIt is a strategic game created by Marten van Dijk, Ari Juels, Alina Oprea, and Ronald L. Rivest and introduced in the paper FLIPIT: The Game of “Stealthy Takeover”.

Play FlipIt: After seeing a talk about flipIt and unable to find any playable version online, I decide to write my own (which to the best of knowledge is the only playable version of flipIt online). To play flipIt click here. The source code and documentation plus additional modes can be found on github here. It is written using javascript and HTML5 so it will likely only work on chrome, firefox or possibly the latest version of IE.

Spy vs Spy: Aldrich Ames was a CIA Counter-Intelligence officer. He was also a spy feeding valuable intelligence to the Soviets and compromising US intelligence operations in the Soviet Union. He operated for ~9 years before the CIA recognized that they had a spy and began an investigation and determined that he was the leak. This strategic situation is the same one faced by computer networks, drug cartels, intelligence agencies and guerrilla networks.

All such organisations have a reasonable expectation that trusted personal/systems will eventually be recruited/captured by enemy organisations. Therefore such organisations must consume valuable resources to discover such betrayals and thereby regain secrecy. The question is then given the possible threats how often and at what cost should they spend resources on investigations/spy hunts/virus scans. This is where flipIt comes in.

FLIPIT: The Game of “Stealthy Takeover:” FlipIt was created to model these sorts of strategic situations and to study the best courses of action. Specifically flipIt was motivated by the recent interest in and success of Advanced Persistent Threats, or APTs1.

The basic idea is that given the current experience that perfect protection of trusted resources is unattainable, lets think about how we can optimally manage compromises of the our most trusted systems.

A game of flip it?

Rules

  1. Two players, player X (blue) and player Y (red) attempt to maintain control over a shared resource.
  2. At anytime in the game each player is allowed to play ‘flip’.
  3. The only way a player can learn the state of the game (who is in control) is when they play ‘flip’.
  4. If a player is in control of the resource and they play ‘flip’ they remain in control of the resource.
  5. If a player is not in control of the resource and they play ‘flip’ they gain control of the resource.
  6. Players gain points for the length of time they control the resource.
  7. Players lose points every time they play flip.

This reflects the situation that the CIA is placed in with regard to moles/enemy spies. They don’t know if they have been compromised. They can perform an investigation and determine if they have been compromised, also catching the spy in the act, but this action is very expensive. That is, the CIA has to trade off between remaining “mole free” (a good) and investigations (an expense).

Winning: How do you win2 a fair game of flipIt against intelligent adaptive human adversaries? I’m not sure.

In the real world what is the best move given that the other “players” can secretly capture/corrupt your most trusted personal/systems? Rivest suggests in his talk that you:

  • “Be prepared to deal with repeated total failure (loss of control).
  • Play fast! Aim to make opponent drop out!3
  • Arrange game so that your moves cost much less than your opponent’s!”

I will discuss this theme of success through affordable defeat (you win if you can afford to lose many times) in my next blog entry.

  1. There is some debate on what constitutes an Advanced Persistent Threats. For me the question is not what is the most semantically correct use of the word, but rather which is the most useful use. For absolute utility the definition given by Bruce Schneier definition hits the mark. He argues that an APT is distinguished not by solely by being highly capable but by being highly motivated to gain access to specific system or piece of information.

    “A conventional hacker or criminal isn’t interested in any particular target. He wants a thousand credit card numbers for fraud, or to break into an account and turn it into a zombie, or whatever. Security against this sort of attacker is relative; as long as you’re more secure than almost everyone else, the attackers will go after other people, not you. An APT is different; it’s an attacker who — for whatever reason — wants to attack you. Against this sort of attacker, the absolute level of your security is what’s important. It doesn’t matter how secure you are compared to your peers; all that matters is whether you’re secure enough to keep him out.” - Bruce Schneier: APT is a Useful Buzzword.

    ↩

  2. The paper provides very interesting mathematically rigorous winning strategies against certain types of constrained attackers. What happens when two humans play? ↩

  3. This is very similar to strategies advocated by John Boyd of getting inside your adversaries OODA loop by having a faster loop. In flipIt it is about moving cheaper rather than faster. ↩

An Interview, Bio-Ciphers, and the Kwisatz Haderach

e. coli

I was recently interviewed by Kerry Grens from the-scientist.com on the subject of infobiology research carried out at Tufts University. The authors present their work in the paper ‘InfoBiology by printed arrays of microorganism colonies for timed and on-demand release of messages,’ pdf available here. The research got quite a bit of press. I really enjoyed this paper and I want to talk about the ideas presented and some ideas I had for improving its security.

How does it work: The basic idea is this (explained using the typical Alice/Bob scenario):

  1. Encoding Alice encodes a message on a sheet of velvet by marking the sheet with strains of e. coli that each glow different colors when they reproduce (strain 1 glows green, strain 2 glows red, etc…).
  2. Transmission Alice mails the velvet to Bob.
  3. Decoding Bob presses the transmitted velvet into a plate of growth media and waits for the e. coli to start reproducing and glowing. Once the e. coli are glowing he reads off the message (something like Red means 0, Green means 1).

The e. coli strains are modified so that they grow only in certain growth mediums allowing the growth medium to act as a secret-key for the message (i.e. if you don’t know the growth medium you can’t grow the e. coli and thus can’t develop the message).

For the sake of discussion, lets name the strains 0, 1, 2, 3 and refer to the growth mediums as A, B, C, D.1 The marks on velvet will be represented by a series of parentheses proceeded by a $\text{V}$. For example velvet with the first mark being strain 1, the second mark being strain 3, the third mark being strain 2 would be represented as: $\text{V}[(1),(3),(2)]$. Marks can contain more than one strain which is represented as: $\text{V}[(1,4),(2,3),(2,4)]$.

Because marks can contain more than one strain, it is possible to encode more than one message on the velvet. For example if medium A grows only strain 1 and 2 and medium B grows only strain 3 and 4, then the velvet “ciphertext” $\text{V}[(1,4),(2,3),(2,4)]$ would decode to either $1,2,2$ or $4,3,4$ depending on the growth medium used.

Using these rules, this biological system acts as though it is a simple cipher. A bio-cipher.

The Security Properties: The security properties of the bio-cipher are:

  1. The ciphertext message can only be read by someone processing the secret key (the growth medium 2).
  2. An attacker is limited in how many keys they may try before the message is destroyed because the e. coli will die/change over time and there is only so many cells that one can reliably extract from the velvet.
  3. It is difficult to detect that a message exists (The e. coli on the velvet act as a invisible ink, see steganography).
  4. There is a time delay for the message to “develop” in the growth medium (the e. coli only expresses the glow trait when growing). The assumption being that the e. coli must be grown to discover the color of the e. coli and thus the message.
  5. The message is self deleting, as the bacteria grow they mutate and there is a selection bias against glowing so that within a short amount of time the developed message disappears and is replaced with noise.

The system can be attacked in a number of ways if the assumptions that justify the security properties can be violated. For instance the point that I made in the interview was that SNP-chips or another mechanism3 could be used to detect which strains were located in which marks on the velvet without developing the message violating security principals 1, 2, 4, and 5. That is, the security of the system rests on the assumption that the only way to learn the message is to develop it4.

Brute Forcing the Key: The attack I want to talk about is brute forcing the keyspace of all the possible growth media. The bio-cipher is developed by pressing the velvet into a single plate containing a single growth medium. The key space of growth medium is very limited and could be guessed by an attacker. Furthermore [Kerckhoffs’s principle] (http://en.wikipedia.org/wiki/Kerckhoffs’s_principle#Explanation_of_the_principle) states that:

“[A cipher system] must not be required to be secret, and it must be able to fall into the hands of the enemy without inconvenience;” - Auguste Kerckhoffs

It is best to assume that only the secret-key is secret. We must assume that an attacker, Eve, which has intercepted the velvet will know all the growth mediums. The only thing which she just will not know is which growth medium to use.[^2] If this space is small she might guess correctly and learn the message.

At this point one might raise the objection, why not encrypt the message with AES or some other modern cipher before encrypting it with the bio-cipher, but that in turn asks the question why use a bio-cipher at all. Just encrypt the message with AES, write it on a piece of paper and send it. The advantage of the bio-cipher is that it is very hard to detect5. The method of encoding acts as a form of invisible ink. The purpose of the key is not to make the message unreadable is it to convince the attacker that there is no message.

As an attacker has a reasonable chance of guessing the key, the bio-cipher offers only minimal protection.

Exponentially Expanding the Key Space I propose a method for fixing this weakness by transforming the bio-cipher into a bio one-time-pad. Assume we have engineered the following 4 strains and two growth mediums such that:

  • strain $1$ grows in A but dies in B and glows Green.
  • strain $2$ grows in A but dies in B and glows Red.
  • strain $3$ grows in B but dies in A and glows Green.
  • strain $4$ grows in B but dies in A and glows Red.

Each “mark” on the velvet either contains a mixture of strain 1 and strain 4 or a mixture of strain 2 and strain 3. Instead of stamping the velvet onto a single plate using a single growth medium, stamp the velvet onto a matrix of plates each containing either the growth medium A or B. The choice of which growth medium to use at each plate in matrix is the key.

The growth medium at each mark (or bit in our example) chooses which strain and color to express, but since both A and B can cause growth of a Red or Green expressing strain, the growth medium (key) reveals nothing about the message. The message without the growth medium can be any possible message, so without the key the message is meaningless and random.

Consider the velvet marked with pairs of strains like so $\text{V}[(1,4),(2,3),(2,3),(1,4)]$. If the velvet is developed on plates with the growth medium configuration $G[A, A, A, B]$ the result is a message which reads Green, Red, Red, Red. $$\text{V}[(1,4),(2,3),(2,3),(1,4)] + G[A, A, A, B] = 1,2,2,4 = \text{Green, Red, Red, Red}$$

Notice that if we flip a single bit of the key and it flips a single bit of the message.

$$\text{V}[(1,4),(2,3),(2,3),(1,4)] + G[A, A, B, B] = 1,3,2,4 = \text{Green, Red, Green, Red}$$

The bio-cipher has perfect security and we need only use two growth mediums.

Increasing the Time-Delay Using the bio one-time-pad method outlined in the previous paragraphs we can easily extend the message time delay to any length of time that we wish at the cost of longer messages. Take two velvet messages, the first message encodes the growth medium (key) for the second message (Green = A, Red = B). The second message can’t be developed until the first message is developed. If the development time is $8$ hours (as stated in the paper), then using four messages we can extend the development time to $4 \times 8 = 32$ hours.

For example Alive wants to make sure it takes at least 24 for Bob to read her message so Alice sends Bob three velvet sheets and the growth medium $G[B, B, A]$ to develop the first sheet $text{V}[(2,3),(1,4),(2,3)]$.

$$\text{V}[(2,3),(1,4),(2,3)] + \text{G}[B, B, A] = 3,4,2 = \text{Red, Green, Red} \rightarrow \text{G}[B,A,B]$$

Bob develops the first sheet to and gets $3,4,2$ which he uses to determine the growth medium for the second sheet.

$$\text{V}[(1,4),(2,3),(1,4)] + \text{G}[B, A, B] = 4,2,3= \text{Red, Red, Red} \rightarrow \text{G}[B,B,B]$$

Bob develops the second sheet and learns the growth medium for the third and final sheet.

$$\text{V}[(2,3),(2,3),(2,3)] + \text{G}[B, B, B] = 3,3,3= \text{Green, Green, Green}$$

Developing the final sheet Bob learns about Alice’s message. The process takes $24$ hours due to the intermediate velvet sheets.

Using 1000 messages we could extend the delay to 8,000 hours.6

The Kwisatz Haderach Cipher): One of the last sentences in the paper caught my eye. In the future work paragraph they have the following sentience:

“Sexual reproduction could be used to add another layer of complexity to the information system.” - InfoBiology by Printed Arrays of Mircoorganism Colonies for Timed and On-Demand Release of Messages.

It inspired me to develop a cipher which employs as it’s mechanism dominant and recessive sex linked traits. The full explanation of the cipher is a subject for a future blog entry but in short:

  • The ciphertext consists of several animals of the same species,
  • The secret-key is the precise order and number of generations in which you breed the animals,
  • The plaintext is the phenotype of the resultant descendants of the original animals after several generations of breeding.

I’ll leave the rest up to your imagination.

  1. The authors of the paper actually had base-seven code in the paper. I changed this for the sake of the example. ↩

  2. The strains each have selection markers added which confer antibiotic resistance. Therefore they can mix several strains onto the same “mark” on velvet. Given different growth mediums containing different antibiotics, different messages will appear. ↩

  3. There are a number of ways to harden an organism against analysis/reverse engineering. For example a large number of repeats to complicate assembly or using combinations of plasmids such that different combinations have different results but each colony of strains will always in aggregate have the same plasmids (plasmids that turn other plasmids off and so on) or encoding one way functions (hash functions) in kinase networks. It seems completely plausible to me that one could engineer strains of e. coli which would frustrate all modern analysis techniques. If anyone with a stronger background in bioinformatics and lab techniques is interested in collaborating on a paper about bacterial sequence drop me a line. ↩

  4. This is purely hypothetical, as I have limited wet lab experience. I was talking to a friend who works in a wet lab about this and he argued that it might be more difficult than it first appeared to me to learn about samples from velvet without culturing them. ↩

  5. Another advantage is it can be decrypted without access to a computer. ↩

  6. If you want to be more efficient you can use messages that are shorter than the final message and hash all the shorter messages together to generate the final key/growth medium. ↩

Proving the Differential Resistance of MD6

Lorenz cipher

A Gap is found: In 2009 a bug was found in the computer generated portion of the proof of the differential resistance of MD6. As I am a big fan of MD61 and it has a significant number of users in a security centric environment. I felt a strong desire to restore the proof of security.

The bug had already been fixed, but the fixed program wasn’t able to quickly prove that MD6 was secure against differential attacks. When I say quickly I mean that the prover was run for long periods of time without providing a satisfactory result. If the prover could be made faster it might be possible to restore the proof of security. I was given access to the original source code and spent a good chunk of my “project time” in 2010 attempting various strategies to both speed up the prover2 and to improve the proof method.

The Problem: Differential cryptanalysis of a hash function requires finding a differential path through the hash function that has a greater than average chance of generating a collision. The proof for the differential resistance of MD6 is approximately3:

  1. We use a computer program to upper bound the probability of any differential path surviving to the $n$-th round, $prob(n)$.
  2. The probability of a round surviving $m$ rounds where $m = 2 \times n$ is at least4 $2 \times prob(n)$
  3. We want to show that the probability of any differential path surviving to the final round of the hash function is at least $\frac{ 1 }{ 2^{k/2} }$ where $k$ is the key length5. It we can show this, we can show that MD6 is secure against the standard form of differential attack.

Part 1 was checked by a computer. Given a number of rounds, the program would compute the upper bound on the probability of a path surviving that number of rounds. For a larger number of rounds the program took increasing amounts of time. The program was not efficient enough to check the number of rounds we wanted to check and therefore the proof was in doubt.

Solve The Easy Stuff First: In early 2011 I met with success. My method was to break the problem into two cases: An easy case and a hard case. Then use the existing prover to find the upper bound for the differential paths which were very computationally trivial to lower bound (the easy case). To solve the hard case I developed a targeted time/exactness trade-off which efficiently upper bounded the non-trivial differential paths.

Not only did this method restore the proof of the differential resistance of MD6, but it also nearly doubled the security margin of MD6 against such attacks. The full paper is available here. The source code to replicate all the results can be found here on my github account.

Thanks: I like to thank Juniper routers for funding my trip to the Eurocrypt ECRYPT II hash function workshop to present these results and Ron Rivest and Lisa Yin for providing me with guidance and source control access.

  1. MD6 is a beautiful design. It is built out of Non-Linear Feedback Shift Registers employing 64-words and merkle-trees to take advantage of parallelism. It is a hash-function designed for a future filled with 64-bit massively parallel processors (exactly the sort of word Intel and ARM are building). ↩

  2. I managed to completely parallelize the algorithm. Given $n$ computers the program was speed up by a factor of $n$. I ran it on a cluster of 100 computers for several weeks with moderate success. I choose to abandon this method of attack not just because I needed a larger cluster but also because I wanted a proof that could be replicated by anyone with a desktop computer. The value of a proof of security is that it can be repeated and checked. ↩

  3. The complete details of the original proof can be found in the MD6 report Chapter 6.9. ↩

  4. The method is very much one of always assuming the worst case analysis to avoid computing all the possibilities. For example the program only deals in the hamming weights of registers in MD6 rather than their actual values. ↩

  5. A differential path with a probability so low provides no benefit over brute force aka the birthday attack. ↩

Spectral Hash Broken


While taking Ron Rivest’s class 6.857: Computer and Network Security (an incredible class that I can’t recommend enough to anyone interested in computer security) we were assigned to review the hash functions submitted to the NIST SHA-3 cryptographic hash function contest. Each homework group received a list of four hash functions to review. I choose to review Spectral Hash as I found the name entertaining.

The page for the student reviews can be found here. A careful reader might notice that my team choose not to make our reviews public. This was because I thought I had discovered an attack against Spectral Hash and wanted time to double check my results. I was concerned that a programming error may have been responsible for the collisions I was finding. While it turned out that I had made a programming error it was also the case that my attack was correct. After further analysis I contacted the authors of Spectral Hash and released the pre-print Attacks Against Permute-Transform-Xor Compression Functions and Spectral Hash.

The Attack:
The Spectral Hash compression function (each $C$ in Figure 1 is a call to the compression function) takes three parameters: a message $m$, an array of numbers $p$, and the output of the previous call to the compression function $h$. This is how the compression function1 works:

Permute: Take a block of the message $m$ and use it to permute/shuffle the array of numbers $p$. Transform: Use $p$ to generate a function $f$ to transform $m$ Xor: Take $f(m)$ and the previous output $h$ xor them together and return this value as output. The problem in Spectral Hash arises because each time you permute $p$ using $m$ therefore if you use the same $m$ you permute $p$ in exactly the same way. For an illustrative example consider a small deck of 5 cards. Ace=A, Jack=J, Queen=Q, K=King, and Joker=S.

playing cards
Before we shuffle the cards they are in the following order [A, J, Q, K, S]. Lets say decide to perform the following shuffle (permute): we swap the first two cards, move the third card to the forth position, move the forth card to the fifth position and move the fifth card to the third position. The order of the deck will evolve like this:
[A, J, Q, K, S] <— (starting order of the deck) [J, A, S, Q, K] [A, J, K, S, Q] [J, A, Q, K, S] [A, J, S, Q, K] [J, A, K, S, Q] [A, J, Q, K, S] <— We’ve returned to the starting position after 6 shuffles.

It is a known rule of group theory and card shuffling that applying the same permutation or shuffle over and over again will evidently return the deck it’s starting position (that is, unshuffle the previous shuffles). The number of iterations required to return to the starting position is called the order or period of the permutation. In our example our shuffle had an order of 5. Given a deck of $n$ cards the maximum possible order is given by the Landau function. As can be seen here, for a decent sized $n$ the order can be quite large. In fact there is card deck shuffling simulation software for stage magicians to model various shuffles [^1] used used in magic tricks.

The attack is simply this: find values of the message block $m$ that result in a permutation with a small order. Repeat these message blocks until $p$ returns to its starting state and continue providing the same value for $m$ until $h$ returns to initial value. Since two different values of $m$ will result in the same $h$, that is $h=IV$ you can generate arbitrary collisions2.

  1. The compression function defined in the Spectral Hash specification is not presented in this form. One of the results that I show in my paper is that Spectral Hash can be reformulated/reduced into this simple form. ↩

  2. The exact details are slightly more complicated than causing a collision in $h$ because Spectral Hash has a finalization function that protects against length-extension attacks, but defeating the finalization function is only trivially harder. ↩