Seagate Includes IEEE P1619.3 in an FDE Whitepaper

Seagate recently published a white paper depicting the IEEE 1619.3 key management protocol used in a system containing Seagate Full Disk Encryption (FDE) hard disks. It's an interesting read if you're into the hardware encryption scene.

The white paper mentions using existing key management systems, like IBM's EKM (Enterprise Key Management) system, with storage systems that include Seagate FDE hard disks

The FDE encrypts the hard disk data using an AES-128 encryption key (NIST's Advanced Encryption Standard), and stores the only copy of this encryption key on the hard disk in encrypted form. To decrypt the encryption key, you need an 'authentication key'. The FDE also stores a cryptographic hash of the authentication key, which is used to verify whether the user entered the correct authentication key.

The beauty of this setup is that it is possible to perform a fast secure-erase of the hard disk by simply erasing the encrypted encryption key. Also, if an attacker was able to open the hard disk or compromise the firmware, the only available information is the encrypted encryption key and the hash of the authentication key. Without the authentication key, it is impossible to get any data off the hard disk.

There are a few caveats here, however:

1. In the absence of a key management server, the authentication key is likely a password entered by the user, which makes the strength of the encryption only as strong as the weaker of the entropy of the password (which is typically very low) or the physical security of the hard disk (which is unknown). If someone is able to comprise the firmware of the FDE hard disk to reveal the hashed authentication key or encrypted encryption key, then it becomes possible to launch an off-line dictionary attack against likely passwords, making it possible to decrypt the data.
2. Neither the white paper nor any other source I've seen describes the AES encryption mode used for protecting the data and the encryption key in the FDE. Just using AES-128 is not sufficient to ensure a high-level of security -- you need to use AES in a secure mode of operation. For example, using AES in Electronic Code Book (ECB) mode is notorious for leaking a significant amount of data -- see an example of Tux (the Linux penguin) encrypted using ECB as compared to other modes. I'm not saying that Seagate is using a bad mode of operation -- it's just that we don't know.
3. The white paper mentions P1619.3 even though the standard is still in relatively early stages. On the one hand, I like seeing publicity for P1619.3, but on the other it's hard to say exactly how it will look in the end. It may not be what we expect.
   

Overall, I'm very happy to see encryption enter the hard disk market and to see increased interest in the 1619.3 work. The FDE hard disk is certainly sufficient for most user's security needs. However, for the agencies with high security needs (like the government), the lack of FIPS 140-2 certification and encryption mode disclosure makes it a difficult (if not impossible) purchase. Hopefully after P1619.3 helps create interchangeable key management solutions, we'll see the FDE volumes increase enough to justify improvements like FIPS certification.

Is 91 Prime?

Quick -- without looking it up, tell me: Is 91 prime?

Hard to say, isn't it? It looks fairly prime. It's odd; it's not divisible by 5 or 11 -- or 3 either...

In this article, I'd like to show to several ways to quickly factor numbers in your head, and even some hints for tricks to speed up number factoring for computer programs. Factoring numbers has many important applications, including RSA (which is used in SSL encryption on your web browser). For me, I like to use the process of factoring numbers as a way to memorize a number. By putting significance on a number (and by going through the process of putting significance on a number), it's easier to recall numbers.

But first, a little lead-in...

Cryptonomicon
In Neil Stephenson's Cryptonomicon, Lawrence Waterhouse shows his cryptographic prowess to some British World War II officers while discussing Special Detachment 2701:

"Do you have any questions?" the Main Guy asks.
"Did Alan Choose the number?" [asks Waterhouse]
"You mean Dr. Turing?"
"Yes. Did he choose the number 2701?"
This level of detail is clearly several ranks beneath the station of the men in the Broadway Buildings. They look startled and almost offended, as if Waterhouse has suddenly asked them to take dictations.
"Possibly," says the Main Guy. "Why do you ask?"
"Because," Waterhouse says, "the number 2701 is the product of two primes, and those numbers, 37 and 73, when expressed in decimal notation, are, as you can plainly see, the reverse of each other."
All heads swivel toward the don, who looks put out. "We'd best change that," he says, "it is the sort of thing that Dr. von Hacklheber would notice." He stands up, withdraws a Mont Blanc fountain pen from his pocket, and amends the organizational chart so that it reads 2702 instead of 2701. As he is doing this, Waterhouse looks at the other men in the room and thinks that they look satisfied. Clearly, this is just the sort of parlor trick they have hired Waterhouse to perform.

This change sets in action one of the main subplots. You'll have to read the book to find out more (which I highly recommend).

Factoring Tricks
Most (mathematically inclined) people can quickly pick off the first several primes, just from memory: 2, 3, 5, 7, 11, 13, 17, 19, ... It's when you start getting past about fifty where things get a little sketchy.

Here are some tricks for factoring numbers by dividing by small primes.

2:
The first "trick" is to check whether the number is odd or even. If it's even (and not 2), then it's not prime because it is divisible by two.

5:
The next check is to see if the last digit is a '0' or '5'. If so, it's divisible by 5.

These first two tricks work because our numbering system -- decimal -- does some of the work for us. Since 10 is divisible by both 2 and 5, base 10 already computes the result in the last digit of dividing by 2, 5, or 10. If we used something like hexadecimal (base 16), then this trick wouldn't work for 5 -- it would only work for 2 (or 4 or 8). If we used base 12 (like American clocks do), then looking at the last digit would tell us whether the number is divisible by 2 or 3 (or 4 or 6) -- but not 5.

3:
The next trick is to add all the digits of the number, and see whether the result is divisible by 3. If so, then the entire number is divisible by 3. In our example, we can test 91 by adding 9 + 1 = 10 -- which is not divisible by 3.

Let's test 123456:

1 + 2 + 3 + 4 + 5 + 6 = 21 (= 7 x 3).

This process can be repeated, so to test 21 we have 2 + 1 = 3, which is divisible by 3.

This trick works because we're representing numbers in a base such that "base - 1" is divisible by three (10 - 1 = 9, which is divisible by 3 and 9). The process of adding digits works because we are subtracting 10 times the digit, but then adding 1 times the digit, for a net change of subtracting 9 times each digit. Take this example:

345 = [(3 * 100)] + [(4 * 10)] + [5]
sum of digits = 345 - (3 * 100) + 3 - (4 * 10) + 4
sum of digits = 345 - (3 * 99) - (4 * 9)
sum of digits = 12

Adding or subtracting multiples of 9 (or 99, or 999, ...) does not change the remainder when dividing by 9 (or by 3). That's basically why it's possible to add the digits of a number to test divisibility by 9 (or 3).

11:
Testing divisibility by 11 is pretty easy for two digit numbers: if the two digits are the same, then the whole result is divisible by 11. It's when the number gets larger that things get a little trickier.

The method I'd like to describe here for testing divisibility by 11 is to group the original number into pairs of digits starting from the right, and then add these pairs and check whether the sum is divisible by 11. If the resulting sum is in 3 (or more) digits, repeat the process until 2 digits are remaining and see whether the digits are the same.

Here's an example:

Is 13574 divisible by 11?
1 + 35 + 74 = 110 (add pairs)
1 + 10 = 11 (add pairs again)
11 is divisible by 11 -- therefore 13574 is divisible by 11

The reason why this trick works is the same basic reasoning as for the trick with 3 and 9. The difference is that adding pairs of digits is equivalent to subtracting a multiple of 100 (or 10,000, etc) from the original number, and adding back that value one time, for a difference of 99 (or 9999, etc). Since 99 = 3 * 3 * 11, the result still equals the original number, modulo 11 (or 3).

The same basic principle applies to larger groupings of digits in any base (binary, decimal, hexadecimal...). I'll get into more details in a subsequent article about how this can speed up factoring large numbers.

7:
For 7, the trick is to successively subtract twice the last digit from the other digits to the left. If you get a number that is divisible by 7 during any stage of this process, then the original number is divisible by seven.

Here's an example:

Is 8638 divisible by 7?
863 - 2*8 = 847 (subtract twice the last digit)
84 - 2*7 = 70 (subtract twice the last digit)
70 = 7 * 10, which is divisible by 7 -- therefore 8638 is divisible by 7

How about our original number?

Is 91 divisible by 7?
9 - 2*1 = 7 -- therefore 91 is divisible by 7 (91 = 7 * 13)

There you have it -- 91 is not prime.

Conclusion
It's unclear whether factoring will get you a hot date or the next promotion, but it will help keep your mind sharp and give you some memory tools, or best of all, the illusion that you too can have the cryptographic genius of Stephenson's Waterhouse. In the next installment, I hope to entertain my programming geek readers with a discussion of how to speed up the process of finding large prime numbers using a binary generalization of the methods for finding divisibility by 3 or 11. For the rest of you, I hope to have given you an amusing diversion before your boss notices that you're reading random blogs instead of doing real work. If you're caught, just ask your boss if 91 is prime... :)