Efficient bit permutation using delta swaps

A common operation in cryptographic block cipher algorithms is to shuffle the input bits in some specified way. While such bit permutations are easy to do in hardware, they tend to be difficult to implement efficiently in software. The Initial Permutation (IP) in the DES block cipher is a good case in point. It is defined as the following rearrangement of the 64 input bits:

DES Initial Permutation

A naive implementation would loop through each of the 64 input bits one by one and place them at the correct position in the output. Needless to say, this would be rather slow. A pre-computed lookup table for a 64-bit permutation would be too huge to even consider, while multiple piece-wise lookup tables would most likely not offer any performance benefit over a naive loop. However, there is a clever solution using only 30 bitwise operations (15 XORs, 10 shifts, 5 ANDs). The key idea is to repeatedly swap non-overlapping groups of bits with an operation called a delta swap:

In a nutshell, the delta swap operation can simultaneously swap multiple bit pairs where the two bits in each pair are separated by the same distance from each other. Let’s examine how this works. (Notation: \oplus means XOR, \ll means bitwise shift left, \gg means bitwise shift right)

We start with the input block represented as a sequence of 64 bits:

a=a_{1}a_{2}...a_{64}

Suppose we want to swap the bit at position i with the bit at position j, where j > i. The distance between the two bits is

\delta=j-i

Now notice that if we construct a temporary value b=b_{1}b_{2}...b_{64} such that

b_{n} = \left\{ \begin{array}{lr}a_{i} \oplus a_{j} & : n \in \{i,j\} \\ 0 & : n \notin \{i,j\} \end{array} \right.

then a \oplus b swaps the bits a_{i} and a_{j} as required, because of the following properties of XOR:

a_{i} \oplus (a_{i} \oplus a_{j})=a_{j} \\ a_{j} \oplus (a_{i} \oplus a_{j})=a_{i}

a_{i} \oplus 0=a_{i}

bitbox1

This is exactly how a delta swap works. The temporary value b is constructed by shifting the input a to the right \delta bits, then XORing with the unshifted version of a. This places a_{i} \oplus a_{j} in b_{j}. The other bits of b are then zeroed out by ANDing with a mask that only has the bit at position j turned on. Finally, the bit swap in a is accomplished by XORing a with an unshifted b and then with b shifted left \delta bits. This is illustrated diagrammatically below.

bitbox12

In order to swap multiple bit pairs simultaneously, we need only turn on the appropriate bits in the AND mask. Specifically, for each 1 bit in the mask, the corresponding bit in the input will be swapped with the input bit that is \delta positions to its left.

Now that we’re armed with the delta swap technique, let’s return to the original problem of implementing the DES Initial Permutation efficiently. Notice that if we arrange the 64-bit input block in the DES algorithm as an 8 x 8 bit matrix, then the Initial Permutation can be visualized as a flip of the matrix about its diagonal (the one that extends from bit 57 to bit 08), followed by the shuffling of its rows. We can accomplish this with a sequence of five delta swaps. The first three flip the matrix about its diagonal, and the last two shuffle the rows.

DeltaSwap1

DeltaSwap2

DeltaSwap3

DeltaSwap4

DeltaSwap5

The DES Final Permutation (FP), being the inverse of the Initial Permutation, can be implemented by performing the same delta swaps in reverse order. The reason why the delta swap technique is so useful is that it works for any permutation of bits. In fact, it can be shown that for 64-bit permutations the required number of delta swaps will never exceed 11.

Lockheed Martin Cyber Attack Linked To RSA Data Breach

Update (Jun 7): RSA chairman Art Coviello has now admitted that the attack was linked to the March 2011 SecurID breach, and offers to implement risk-based authentication or replace all tokens as a gesture to customers. Still no official confirmation of what was stolen, however.

U.S. aerospace giant Lockheed Martin reported on Saturday that it detected and thwarted a “significant and tenacious attack” on its network a week ago.

An unnamed source with direct knowledge of the attacks claimed that hackers broke in by creating duplicates of the SecurID tokens used by Lockheed Martin’s users. The company responded by shutting down remote access to its networks and replacing almost 100,000 of the SecurID tokens.

Although the link to the RSA data breach has not yet been confirmed, it is another possible clue to what many in the information security community have long suspected: The RSA breach involved the theft of the token seed records which, with some additional information, could be used to duplicate the functionality of the RSA tokens.

Interestingly, it appears that RSA has secretly briefed some of its customers on the details of the March 2011 data theft. Two people familiar with the briefings reported that the company required them to sign non-disclosure agreements promising not to discuss the advice that was provided.

New SecurID Breach Details

RSA employee Uri Rivner shares new details on the SecurID breach in an April 1st blog post. What was initially described as an “extremely sophisticated attack” of the “Advanced Persistent Threat” variety turns out to have been a simple spear-phishing campaign with a malicious Excel attachment containing a 0-day Adobe Flash exploit (perhaps this is what RSA means by “extremely sophisticated”). Once the attacker established a foothold inside the network, it was apparently a simple matter to find a way to the crown jewels. The attack was reportedly detected in progress, although this did not prevent the stolen data from making its way to an unknown destination on the Internet via FTP. RSA is not doing itself any favors by continuing to withhold the details of what was stolen, and putting a ridiculous corporate spin on what was essentially a simple, run-of-the-mill phishing attack.

Encrypted Notes Could Hold Key To Unsolved Murder

The FBI is asking amateur code breakers to help with an unsolved murder case. In 1999, the body of 41-year-old Ricky McCormick was found in a field near St. Louis, Missouri. The only possible clues to his death are two hand-written notes that were found stuffed in his pocket. The notes appear to be encrypted with a deceptively simple-looking cipher, but have so far resisted all attempts at cryptanalysis. The FBI’s code-breaking unit is hoping more eyes on the problem will help crack this puzzle.

A word of warning to would-be decipherers: Several famous codes and ciphers have tantalized cryptanalysts for decades or even centuries, and have never been solved (a comprehensive list is maintained by Elonka Dunin).

Automated Solution of Simple Substitution Ciphers

About a year ago, I was working on the solutions to the cryptograms in the first chapter of the Mathematical Cryptography book, and the idea struck me that it would be nice to have a computer program that could automatically solve such puzzles. It turns out that this is easier said than done, especially if the spaces between words are not preserved in the ciphertext and the puzzle author took pains to manipulate the character frequencies of the underlying message.

Exercise 1.4 (c) from the book is a good example. I urge you to try to solve it by hand in order to get an appreciation for the nature of the problem. It is not easy! Then think about how you would teach a computer to perform this feat automatically.

GSZES GNUBE SZGUG SNKGX CSUUE QNZOQ EOVJN VXKNG XGAHS

AWSZZ BOVUE SIXCQ NQESX NGEUG AHZQA QHNSP CIPQA OIDLV

JXGAK CGJCG SASUB FVQAV CIAWN VWOVP SNSXV JGPCV NODIX

GJQAE VOOXC SXXCG OGOVA XGNVU BAVKX QZVQD LVJXQ EXCQO

VKCQG AMVAX VWXCG OOBOX VZCSO SPPSN VAXUB DVVAX QJQAJ

VSUXC SXXCV OVJCS NSJXV NOJQA MVBSZ VOOSH VSAWX QHGMV

GWVSX CSXXC VBSNV ZVNVN SAWQZ ORVXJ CVOQE JCGUW NVA

Over the past 25 years, many papers have been published on the subject in various journals, and many interesting approaches have been proposed. It may be a surprise for some to learn that even state-of-the-art algorithms are not capable of reliably solving very short cryptograms (under 200 characters in length), especially when word divisions are eliminated.

My own attempt, building on work done by Prof. Richard Spillman (who first proposed attacking the problem via genetic algorithms) and Sam Hasinoff (who first suggested using character n-gram models), is an open source program called Alkindus. It works quite well, and is easily capable of solving puzzles similar to the ones from Mathematical Cryptography in a fully automated manner.

The work-in-progress paper describing the theory and empirical results is in need of a large collection of cryptograms completely independent of the Project Gutenberg corpus of English-language text that I used to train the underlying n-gram model. To use cryptograms derived from the training data itself would be cheating! So, I am especially interested in obtaining large amounts of English text (varying from say, 50 to 2500 characters in length), which could be used to put the program through a proper, rigorous test. If you have any suggestions, please let me know.

RSA SecurID data compromised

UPDATE 5 (March 25): A surprisingly well-informed and technically accurate article from a mainstream site? Go figure.

UPDATE 4 (March 23): I’ve posted some suggested detection and prevention activities in light of the breach here.

UPDATE 3 (March 23): Some observers are putting two and two together regarding the nature of the breach and what was stolen.

UPDATE 2 (March 21): Reports of a new official email to customers regarding the breach are beginning to appear. RSA is still not willing to confirm the theft of the token seed record database. However, reading carefully between the lines leaves one with the unmistakable impression that the strength of the SecurID solution has been reduced to the single factor of “something you know”.

Incident Overview

1. What happened?
Recently, our security systems identified an extremely sophisticated cyber attack in progress, targeting our RSA business unit. We took a variety of aggressive measures against the threat to protect our customers and our business including further hardening our IT infrastructure and working closely with appropriate authorities.

2. What information was lost?
Our investigation to date has revealed that the attack resulted in certain information being extracted from RSA’s systems. Some of that information is related to RSA SecurID authentication products.

3. Why can’t you provide more details about the information that was extracted related to RSA SecurID technology?
Our customers’ security is our number one priority. We continue to provide our customers with all the information they need to assess their risk and ensure they are protected. Providing additional specific information about the nature of the attack on RSA or about certain elements of RSA SecurID design could enable others to try to compromise our customers’ RSA SecurID implementations.

4. Does this event weaken my RSA SecurID solution against attacks?
RSA SecurID technology continues to be an effective authentication solution. To the best of our knowledge, whoever attacked RSA has certain information related to the RSA SecurID solution, but not enough to complete a successful attack without obtaining additional information that is only held by our customers. We have provided best practices so customers can strengthen the protection of the RSA SecurID information they hold. RSA SecurID technology is as effective as it was before against other attacks.

5. What constitutes a direct attack on an RSA SecurID customer?
To compromise any RSA SecurID deployment, an attacker needs to possess multiple pieces of information about the token, the customer, the individual users and their PINs. Some of this information is never held by RSA and is controlled only by the customer. In order to mount a successful direct attack, someone would need to have possession of all this information.

6. What constitutes a broader attack on an RSA SecurID customer?
To compromise any RSA SecurID deployment, the attacker needs to possess multiple pieces of information about the token, the customer, the individual users and their PINs. Some of this information is never held by RSA and is controlled only by the customer. In order to mount a successful direct attack, someone would need to have possession of all this information.

The broader attack we referenced most likely would be an indirect attack on a customer that uses a combination of technical and social engineering techniques to attempt to compromise all pieces of information about the token, the customer, the individual users and their PINs. Social engineering attacks typically target customers’ end users and help desks. Technical attacks typically target customers’ back end servers, networks and end user machines. Our prioritized remediation steps in the RSA SecurID Best Practices Guides are focused on strengthening your security against these potential broader attacks.

7. Have my SecurID token records been taken?
For the security of our customers, we are not releasing any additional information about what was taken. It is more important to understand all the critical components of the RSA SecurID solution.

To compromise any RSA SecurID deployment, the attacker needs to possess multiple pieces of information about the token, the customer, the individual users and their PINs. Some of this information is never held by RSA and is controlled only by the customer. In order to mount a successful attack, someone would need to have possession of all this information.

8. Has RSA stopped manufacturing and/or distributing RSA SecurID tokens or other products?
As part of our standard operating procedures, while we further harden our environment some operations are interrupted. We expect to resume distribution soon and will share information on this when available.

UPDATE 1 (March 20): Apparently, RSA executives have been telling customers to ensure that they don’t give out the serial numbers on their tokens. This is yet another clue that the breach may have involved the theft of the database mapping token seed records to token serial numbers.

In an open letter to its customers, RSA chief Art Coviello disclosed yesterday that an internal data breach had been discovered affecting the security of RSA’s SecurID product line. He states:

While at this time we are confident that the information extracted does not enable a successful direct attack on any of our RSA SecurID customers, this information could potentially be used to reduce the effectiveness of a current two-factor authentication implementation as part of a broader attack. We are very actively communicating this situation to RSA customers and providing immediate steps for them to take to strengthen their SecurID implementations.

We are left to wonder and speculate on the exact meaning of this statement. Perhaps the worst-case scenario would be the theft of the token seed record database.  A little background information will clarify why this would be of significant concern.

Each RSA token uses 3 input numbers which are mangled using the AES-128 block cipher to generate a new 6-digit token code every 30 or 60 seconds:

  • A token-specific 128-bit random seed (used as the AES encryption key)
  • The current date/time in YY/M/D/H/M/S format (64-bit)
  • The token’s serial number (32-bit) + 32 bits of padding

The security of the token depends on the fact that the 6-digit code is unpredictable.  If hackers stole RSA’s database containing a mapping of token serial numbers to corresponding random seeds, it would allow the hackers, in effect, to predict what 6-digit number is displayed on any token at any time.

In order to exploit this information, they would also need to know:

  • the serial number of the token attached to the account they are targeting, and
  • the PIN (password) of the owner of the account

This information would need to be gathered using the same methods used to attack standard password information, i.e. through phishing, social engineering, repeated guessing, etc. In effect, it would reduce the security of the RSA token from two-factor to single-factor: Once you have the victim’s PIN and token serial number (which is stamped on the back of the token itself), you have all the information necessary to authenticate as the victim.

Without further details from RSA about the extent of the data breach, it is impossible to say whether this is in fact what happened.  However, one thing is clear: RSA’s customers need more reassurance than they are currently getting.

Mathematical Cryptography

I am currently working my way through An Introduction to Mathematical Cryptography. This excellent textbook provides the theoretical background necessary to understand a number of public-key algorithms, including Diffie-Hellman, ElGamal, RSA, and Elliptic Curve Cryptography. As I complete the exercises at the end of each chapter, I will post my solutions here.

Follow

Get every new post delivered to your Inbox.