On July 11, 2008, Thales UK (a subsidiary of the French defense company Thales) submitted a proposal to acquire all the assets of nCipher for roughly US$100 million. nCipher produces cryptographic hardware, and recently acquired most of the assets of NeoScale Systems for just under US$2 million.
The deal is still pending a vote by the nCipher board, but the offer carries a 2x premium on previous stock prices, so it doesn't seem likely that this vote will fail.
The technical editor for the IEEE P1619.3 was employed by NeoScale and is currently employed by nCipher, soon to be acquired by Thales. nCipher is a strong supporter of the P1619.3 key management effort and I'm hoping that Thales will continue in this strong support.
It's a little unclear to me how to pronounce "Thales". The namesake is an ancient greek philosopher, and as such the name should be pronounced "Thay' - leaz". However, the French owners prefer to pronounce it more like "Tal-less".
Links:
Showing posts with label Cryptography. Show all posts
Showing posts with label Cryptography. Show all posts
2008-07-06
TrueCrypt Releases version 6.0
On July 4th, 2008, the TrueCrypt Foundation released TrueCrypt version 6.0. TrueCrypt is a very popular open-source disk encryption tool that is currently based on the XTS-AES encryption mode that the IEEE P1619 Task Group developed and standardized in December 2007. As the chair of the IEEE Security in Storage Working Group (SISWG) -- the group that oversaw the development of XTS -- I'm very pleased to see the continued adoption of XTS in the industry.
On a related note, NIST is currently considering XTS as an Approved Mode of Operation for protecting U.S. government confidential data under FIPS 140-2. If NIST accepts XTS, this will be a huge boon to TrueCrypt and similar tools that use XTS. If you use TrueCrypt or other tools that use XTS, please send NIST a comment (before Sept 2008).
For a limited time, you can pick up a free copy of XTS from IEEE. After September, you'll have to buy it from the IEEE store. See the P1619 homepage for instructions and other information.
On a related note, NIST is currently considering XTS as an Approved Mode of Operation for protecting U.S. government confidential data under FIPS 140-2. If NIST accepts XTS, this will be a huge boon to TrueCrypt and similar tools that use XTS. If you use TrueCrypt or other tools that use XTS, please send NIST a comment (before Sept 2008).
For a limited time, you can pick up a free copy of XTS from IEEE. After September, you'll have to buy it from the IEEE store. See the P1619 homepage for instructions and other information.
2008-06-19
BITs "Whitepaper" on key management
Here's an interesting paper on cryptographic key management:
BITS: Enterprise Key Management
Apparently, the ANSI X9 group is considering starting a standards effort based on the BITS whitepaper. I think that key management is starting to get a little crowded for standards, but until one standard emerges as the most adopted in the industry, the hunting season is still open.
The IEEE Key Management Summit on September 23-24 (Baltimore, MD) has a 30-minute slot for ANSI X9, so we might be able to get more details then...
BITS: Enterprise Key Management
Apparently, the ANSI X9 group is considering starting a standards effort based on the BITS whitepaper. I think that key management is starting to get a little crowded for standards, but until one standard emerges as the most adopted in the industry, the hunting season is still open.
The IEEE Key Management Summit on September 23-24 (Baltimore, MD) has a 30-minute slot for ANSI X9, so we might be able to get more details then...
2008-05-23
How to Prevent the Random Number Bug in Debian OpenSSL in Other Implementations
As probably the entire hacker community has heard by now, there was a bug recently discovered in Debian's OpenSSL implementation that crippled the random number generator. For background, see Schneier's Coverage, Slashdot's Coverage, Debian's Announcement, Ubuntu's Announcement, and a Cartoon.
On the surface, this just looks like a stupid mistake by one Debian maintainer. But if you look at the details, it's not that obvious. Here one of the two lines in question, within md_rand.c
Truthfully, if I were in the same position as a maintainer, there's a good chance I might have commented out these lines too. Code analysis tools are very useful in helping to maintain high code quality, and crippling these tools also has consequences. The right action is not always obvious, and when you go through hundreds of lines of code it's easy to forget the significance of a single line like this.
The fundamental issue with random number generators (RNGs) is that they are infamously difficult to test. A standard software regression test takes a known input to a program and checks for a known output. RNGs aren't like that -- at least when used with good seeds. A good seed never repeats and cannot be tested against known answers. Instead, you have to perform statistical tests on several samples from the seed source (examples: DIEHARD, NIST's RNG suite).
This problem is much more widespread than people think. This is also a very common problem in embedded systems. Many instantiations of SSL don't properly seed their RNG. This won't cause the system to fail, testers won't ever catch it, and customers won't complaint. So from the vendor perspective, there's really no incentive to make it work. Most of the engineers adding OpenSSL don't know much about cryptography, and often won't know to or even bother to hook up a seed. Some systems don't have a good way to generate this seed.
Even NIST' Computer Security Division (the owner of FIPS 140-2, a major cryptographic standard for government agencies) has mostly washed their hands of this problem. FIPS 140-2 used to include statistical tests on the entropy (i.e, 'randomness') source used to create the seed, but now the only requirement is that the vendor justify a certain entropy level.
To solve this problem, I think that OpenSSL (and other SSL implementations) needs to add some kind of sanity check to the seed to make sure this mistake doesn't happen again. Here's a rough outline of this test:
Caveat: Make sure that the files that store these seeds are properly protect from access and modification. If the entropy source is poor, it's possible to leak information about the rest of the system, or even give hints as to what the subsequent seed will be as used by the real random number generator.
When it comes to security, you really can't rely on people to catch these kinds of mistakes through code reviews. You need to have good tools to automatically catch this. Unfortunately, making the tools is difficult, which is why we still mostly rely on code reviews.
Although code reviews are better than nothing, and in this case, it sounds like even a code review would have helped...
On the surface, this just looks like a stupid mistake by one Debian maintainer. But if you look at the details, it's not that obvious. Here one of the two lines in question, within md_rand.c
MD_Update(&m,buf,j); /* purify complains */This function seeds the cryptographically secure pseudo-random number generator, which then generates important things like cryptographic keys. The security of a cryptographic key is solely in the difficulty of an attacker to guess the value (like a house key's tumbler positions), and if it is predictable, there is no security. The maintainer removed this line because the Purify and Valgrind tools complained about uninitialized data.
Truthfully, if I were in the same position as a maintainer, there's a good chance I might have commented out these lines too. Code analysis tools are very useful in helping to maintain high code quality, and crippling these tools also has consequences. The right action is not always obvious, and when you go through hundreds of lines of code it's easy to forget the significance of a single line like this.
The fundamental issue with random number generators (RNGs) is that they are infamously difficult to test. A standard software regression test takes a known input to a program and checks for a known output. RNGs aren't like that -- at least when used with good seeds. A good seed never repeats and cannot be tested against known answers. Instead, you have to perform statistical tests on several samples from the seed source (examples: DIEHARD, NIST's RNG suite).
This problem is much more widespread than people think. This is also a very common problem in embedded systems. Many instantiations of SSL don't properly seed their RNG. This won't cause the system to fail, testers won't ever catch it, and customers won't complaint. So from the vendor perspective, there's really no incentive to make it work. Most of the engineers adding OpenSSL don't know much about cryptography, and often won't know to or even bother to hook up a seed. Some systems don't have a good way to generate this seed.
Even NIST' Computer Security Division (the owner of FIPS 140-2, a major cryptographic standard for government agencies) has mostly washed their hands of this problem. FIPS 140-2 used to include statistical tests on the entropy (i.e, 'randomness') source used to create the seed, but now the only requirement is that the vendor justify a certain entropy level.
To solve this problem, I think that OpenSSL (and other SSL implementations) needs to add some kind of sanity check to the seed to make sure this mistake doesn't happen again. Here's a rough outline of this test:
- During OpenSSL's initialization, immediately collect several samples from the seed source. The number depends on the constraints of the system, but NIST's old FIPS 140-2 statistical test collected 20,000 bytes, which is a reasonable number.
- Run simple statistical tests on these samples (see FIPS 140-2 for an example) and make sure the entropy source is reasonable.
- Store the first 100 bytes or so of this sample set in non-volatile memory, (e.g, hard disk, flash), and keep a history of several thousand of these initial samples. Discard the other samples (don't use them as part of the real seed)
- Run another statistical test on the series of first samples. If there is a correlation between these samples (i.e,. the values tend to be the sample after initialization), then fail with a big obnoxious error that you'd hope no distribution maintainer or embedded software engineer would miss.
Caveat: Make sure that the files that store these seeds are properly protect from access and modification. If the entropy source is poor, it's possible to leak information about the rest of the system, or even give hints as to what the subsequent seed will be as used by the real random number generator.
When it comes to security, you really can't rely on people to catch these kinds of mistakes through code reviews. You need to have good tools to automatically catch this. Unfortunately, making the tools is difficult, which is why we still mostly rely on code reviews.
Although code reviews are better than nothing, and in this case, it sounds like even a code review would have helped...
2008-05-15
Ada beats Colossus in Cipher Challenge
I caught this article on Slashdot about an Ada program beating Colossus in a challenge to quickly decrypt messages from the Lorenz SZ42 cipher. The Ada program took 46 seconds versus what Colossus (the World War II machine in Bletchley Park that cracked German messages) solved in about three and a half hours.
Ada has me very fascinated because I'm interested in programming languages that lend themselves to computational correctness and high execution speed. I haven't used Ada, but I tend to hear good things about it, and would like to try using it next time I start a project. I'm particularly interested in how it would help programs that use cryptography and that are going through a Common Criteria evaluation.
According to the TIOBE Index, as of May 2008, Ada is sitting at #17 with 0.431% popularity and a rating of 'B'. From that point of view it doesn't look like the hottest thing out there, but it has Objective-C (Mac's darling) way out-ranked. Objective-C is #47 with 0.083% popularity, which makes me wonder if it's worth learning for writing Mac OS X Widgets. Fortunately, Mac's Xcode provides some good hooks for Python (#7, 4.6% popularity) and Ruby (#10, 2.85%)...
Ada has me very fascinated because I'm interested in programming languages that lend themselves to computational correctness and high execution speed. I haven't used Ada, but I tend to hear good things about it, and would like to try using it next time I start a project. I'm particularly interested in how it would help programs that use cryptography and that are going through a Common Criteria evaluation.
According to the TIOBE Index, as of May 2008, Ada is sitting at #17 with 0.431% popularity and a rating of 'B'. From that point of view it doesn't look like the hottest thing out there, but it has Objective-C (Mac's darling) way out-ranked. Objective-C is #47 with 0.083% popularity, which makes me wonder if it's worth learning for writing Mac OS X Widgets. Fortunately, Mac's Xcode provides some good hooks for Python (#7, 4.6% popularity) and Ruby (#10, 2.85%)...
2008-04-29
Follow-up to Hitachi's Announcement of AES-256 Encryption Within a Hard Disk
As many readers noticed, last week Slashdot covered a announcement that Fujitsu is the first to offer 256-bit AES encryption in their MHZ2 CJ Series 320 GB 2.5" hard drives. As chair of the IEEE P1619 Security in Storage Working Group, I felt an obligation to get more details on exactly what 'AES-256' encryption means. So I clicked on the handy box to submit questions, and got the following responses from Fujitsu:
1. What is the mode of operation for the AES block cipher (e.g., ECB, CBC, CTR, etc)?I had similar questions about Seagate's Full Disk Encryption (FDE) hard drive, and couldn't get any answers there, either. According to AES Certificate #587, Seagate is using Electronic Code Book (ECB) for their FDE. Unfortunately, ECB is a very insecure mode-of-operation, one that I hope NIST eventually withdraws. To visually see what I mean, take a look at the ECB encryption of Tux the penguin. The latest rumors I've heard is that Seagate is moving to cipher-block-chaining (CBC) encryption (a much more secure mode-of-operation) for subsequent encrypting hard disks. Fujitsu will likely take a similar course, although there is expected to be some flexibility in the algorithms.
===> We don't disclose this.
2. How are the 256-bit AES keys managed?
===> We don't disclose this.
3. Is Fujitsu considering NIST FIPS 140-2 certification for this disk drive (like Seagate is doing)?
===> under consideration.
In contrast, tape drive vendors have been much more open about the details of their tape encryption. According to the LTO-Technology page, LTO uses the AES-GCM mode as specified in IEEE P1619.1 (soon to be published as IEEE Std 1619-2007). Sun's T10000 uses AES-CCM, both as specified in P1619.1 and in NIST SP 800-38C. IBM's TS1120 also uses AES-GCM.
So why aren't hard disk vendors disclosing the technical details about their encryption implementation?
Here are my thoughts:
- Hard disk vendors don't think that the mode of encryption is too important because it is difficult to get direct access to the encrypted data (this would require bypassing the firmware or putting the hard disk on a spin stand)
- Hard disk vendors are afraid that weaknesses will be found in their encryption mode, whether real or perceived
- There are no good standards to use for hard disk encryption
While it is true that most users don't understand enough about encryption to even know what a mode-of-operation is, I believe that these details will become increasingly important as buyers become better educated and demand open details about the encryption. Otherwise there is no way to know whether you've been sold snake oil that doesn't actually provide measurable benefits (for example, weak ECB encryption of the entire hard disk using the otherwise strong AES block cipher).
Concerning standards, this is an example of how the late arrival of IEEE 1619 has caused confusion in the storage encryption industry. When IEEE 1619 start about 6 years ago, the goal was to create a strong encryption standard suitable for data storage devices. First came the wide-block EME mode. This mode fell when Antoine Joux found a vulnerability that sent Shai Halevi and Phil Rogaway back to the drawing board. Next was the LRW mode. This fell when Niels Ferguson of Microsoft noted in Crypto 2006 that you can leak the tweak key if encrypted with itself (Microsoft has no control over where the keys are). About this same time, the Trusted Computing Group wanted to endorse LRW (this was dropped). About two years ago during the LRW unrest, Mart Somermaa pointed the group to the XEX mode as proposed by Phil Rogaway. The P1619 group added ciphertext-stealing to this mode and called it XTS-AES.
The XTS-AES algorithm was approved last December by IEEE as part of IEEE 1619-2007, and is nearly published. After it is published, IEEE will submit XTS to NIST for consideration as an Approved Mode of Operation for FIPS 140-2. If NIST accepts XTS, then this will become an excellent mode for hard disk vendors to consider.
2008-04-08
RSA 2008: Cryptographer's Panel
As one of the great highlights of the RSA Conference is the cryptographer's panel with the great experts of modern public key cryptography: Whitfield Diffie, Martin Hellman of Diffie-Hellman fame (discrete log crypto) and Ron Rivest and Adi Shamir of RSA fame (crypto based on the integer factorization problem -- used in SSL).
This is a rough draft post that will be cleaned up later, but contains the last part of the discussion:
Question from Burt: Where would you put your research effort?
Diffie: I'd put research into genetics - We'll see the first child made from two women, showing that men are an expensive and unnecessary thing to have around.
Hellman: We need to become more rational in our approach to security
Closing remarks:
Diffie: I'm optimistic about this subject. People are going to get along just fine -- cyber security is very important. The most important thing in the 20th century is client server computing. By putting important information onto a single computer, it's possible to control access. -- Something's going to happen that we don't expect, from younger people
Hellman: Don't be afraid to tackle problems
Rivest: (countering Diffie): There is a lot of cryto still to be discovered. We're still at the early stages of tying worst-case complexity to best-case complexity -- how to run crypto protocols in parallel so that they don't interfere -- we need the secure platform -- next problem is user interfaces
Shamir: It's about subtlety behind the schenes --- multiple lines of defense -- most of the basic elements are there. But we haven't reached nirvana -- we need to develop tools and techniques -- a GPS for data, need the ability to located where your data is. Use 160-bit sha-1 summary to help locate this data. This could help the information management problem
Burt: 1024-bit RSA -- how much longer before the publicly announced factorization
Shamir - next year
Hellman - I was at Certicom -- Elliptic curves have been rock-solid since inception
Rivest - Use Moores law - There are low-probability algorithms that are hard to predict
Burt -2010 is the transition to 2048 bit keys
These guests will be in the crypto commons for more discussion.
This is a rough draft post that will be cleaned up later, but contains the last part of the discussion:
Question from Burt: Where would you put your research effort?
Diffie: I'd put research into genetics - We'll see the first child made from two women, showing that men are an expensive and unnecessary thing to have around.
Hellman: We need to become more rational in our approach to security
Closing remarks:
Diffie: I'm optimistic about this subject. People are going to get along just fine -- cyber security is very important. The most important thing in the 20th century is client server computing. By putting important information onto a single computer, it's possible to control access. -- Something's going to happen that we don't expect, from younger people
Hellman: Don't be afraid to tackle problems
Rivest: (countering Diffie): There is a lot of cryto still to be discovered. We're still at the early stages of tying worst-case complexity to best-case complexity -- how to run crypto protocols in parallel so that they don't interfere -- we need the secure platform -- next problem is user interfaces
Shamir: It's about subtlety behind the schenes --- multiple lines of defense -- most of the basic elements are there. But we haven't reached nirvana -- we need to develop tools and techniques -- a GPS for data, need the ability to located where your data is. Use 160-bit sha-1 summary to help locate this data. This could help the information management problem
Burt: 1024-bit RSA -- how much longer before the publicly announced factorization
Shamir - next year
Hellman - I was at Certicom -- Elliptic curves have been rock-solid since inception
Rivest - Use Moores law - There are low-probability algorithms that are hard to predict
Burt -2010 is the transition to 2048 bit keys
These guests will be in the crypto commons for more discussion.
My RSA Conference 2008 Schedule
I will be at the RSA Conference from Monday April 7 to Friday. For those who would like to meet up during this week, here is my anticipated schedule:
(I'll update this entry periodically as things change...)
Tuesday:
10:25 - 11:20: Cryptographer's Panel (with Diffie, Hellman, Rivest, and Shamir (no Adleman))
11:20 - 1:30: Lunch -- Meet at the nCipher exhibit
1:30 - 2:40: RED 309 - Real World Key Management: News from the trenches
3:00 - 3:50: RED 309 - Cryptographic Security for Ruby on Rails Web Services
4:10 - 5:20: RED 309 - Security Usability: The New Challenge (with Phillip Hallam-Baker)
5:40 - 6:30: RED 309 - Beyond the Coding Errors: The Complete View of Software Security
6:30 - 9:00: Dinner (TBD)
Wednesday:
8:00 - 8:50: RED 300 - Improved AES Implementations
9:10 - 10:20 RED 300 - Public Key Encryption with Special Properties
10:40 - 11:50 RED 300 - Side Channel Cryptanalysis
2:00 - 6:00 Key Notes
6:30-7:30 "Dinner for 6"
Thursday:
8:00 - 8:50: RED 310 - High-Speed Risks in 802.11n Networks
9:10 - 10:20 RED 308 - Extended Validation: Raising the Bar for Internet Trust
10:40 - 11:50 RED 308 - PCI DSS Security Standards Foundation and future
2:00 - 5:00 Keynotes
Friday:
9:00 - 9:50: RED 308 - Standardizing Key Management for Trusted Storage
10:05 - 10:55: RED 308 - The New FIPS 140-3 Standard
11:10 - 12:00 RED 308 - What's New with XACML, the Access Control Standard?
Catch bus for flight: around 1:00 pm
If anyone is interested in meeting up, please shoot me an e-mail or give me a call on my cell phone: 303-717-2717
2008-03-09
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:
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:
- 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.
- 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.
- 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.
2008-03-08
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:
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:
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:
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:
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:
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... :)
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.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).
"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.
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]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).
sum of digits = 345 - (3 * 100) + 3 - (4 * 10) + 4
sum of digits = 345 - (3 * 99) - (4 * 9)
sum of digits = 12
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?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).
1 + 35 + 74 = 110 (add pairs)
1 + 10 = 11 (add pairs again)
11 is divisible by 11 -- therefore 13574 is divisible by 11
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?How about our original number?
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
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... :)
2008-02-26
Who uses IEEE 1619 and 1619.1?
Last December, IEEE approved the standards two encryption standards (See Press Release):
Currently the IEEE Security in Storage Working Group (SISWG) is investigating the possibility of submitting the IEEE 1619 XTS mode to NIST for consideration as an Approved Mode of Operation for FIPS 140-2 certification. One of the questions asked on the SISWG e-mail reflector was whether there is widespread industry support for these newly approved modes.
From doing some web searching, I've come up with the following list of companies who are claiming compliance to these newly approved standards.
IEEE 1619 (XTS-AES) Support
If you know of implementations that expect IEEE 1619 or 1619.1 compliance, please post a comment with the vendor and product name, with a link to the appropriate webpage.
- IEEE 1619 (specifying the XTS encryption mode, commonly used for disk encryption); and
- IEEE 1619.1 (specifying GCM, CCM, CBC-HMAC, and XTS-HMAC encryption modes, typically for tape) .
Currently the IEEE Security in Storage Working Group (SISWG) is investigating the possibility of submitting the IEEE 1619 XTS mode to NIST for consideration as an Approved Mode of Operation for FIPS 140-2 certification. One of the questions asked on the SISWG e-mail reflector was whether there is widespread industry support for these newly approved modes.
From doing some web searching, I've come up with the following list of companies who are claiming compliance to these newly approved standards.
IEEE 1619 (XTS-AES) Support
- True Crypt - Version 5.0 now supports XTS for software disk encryption
- (Update from 2016: TrueCrypt is no longer maintained and has been accumulating security issues so this is no longer recommended. Please see this list of alternatives instead).
- FreeOTFE - Free On-The-Fly-Encryption
- dmcrypt - Encryption for the Linux 2.6 kernel
- Hifn: "Hifn’s full line of Applied Services Processors as well as its board-level security acceleration products currently support, and are compliant with, the encryption algorithms specified in the IEEE 1619 standards"
- Helion Technology: AES-XTS cores
- Elliptic Semiconductor:
- IP Cores: XTS-AES IEEE P1619 Core Families XTS2 and XTS3
- Hightech Global Design & Distribution: Combined AES-GCM-XTS/XEX-CCM IP Core
- JetStream Media Technologies: High Speed XTS/XEX-AES Core
- SafeNet, Inc.: SafeXcel IP AES/GCM/XTS Accelerators
- IBM, HP, Quantum, Tandberg's LTO-4 Tape Drive uses IEEE 1619.1 GCM-AES
- IBM's TS1120 Enterprise Tape Drive uses GCM
- Sun's T10000 Enterprise Tape Drive uses 1619.1 CCM
- Many core vendors (basically same list as for 1619)
If you know of implementations that expect IEEE 1619 or 1619.1 compliance, please post a comment with the vendor and product name, with a link to the appropriate webpage.
Subscribe to:
Posts (Atom)
