Date: Thu, 03 Mar 2005 01:30:15 +0100 From: "Poul-Henning Kamp" <phk@phk.freebsd.dk> To: Roland Dowdeswell <elric@imrryr.org> Cc: hackers@freebsd.org Subject: Re: FUD about CGD and GBDE Message-ID: <2759.1109809815@critter.freebsd.dk> In-Reply-To: Your message of "Wed, 02 Mar 2005 11:29:28 EST." <20050302162928.0916237012@arioch.imrryr.org>
next in thread | previous in thread | raw e-mail | index | archive | help
In message <20050302162928.0916237012@arioch.imrryr.org>, Roland Dowdeswell wri tes: >Let's discuss a simple example and see how it works. Let's walk >through a user login, with /etc/passwd on GBDE and the filesystem >mounted with mtime. These days, on the majority of low cost disks used in enduser configurations you risk looking an entire track if the disk were writing when you pulled power. (People complain about this, but doesn't seem to be willing to pay to avoid it.) So the cummulative increase of risk from using GBDE doesn't really register on the radar for people. And therein lies a very important lesson for you: It may not be a 100% theoretical ironclad guarantee, because few people are prepared to pay for that in the first place. >Contemporary filesystems generally do not lose data when a file is >read. ... unless they operate on contemporary products for data storage. >A dictionary attack refers specifically to the process of guessing >passphrases. As I said in so many words: GBDE does not in any way shape or form address this problem. GBDE provides a simple model for authentication on which many different key handing schemes, can be built. "There is no problems left in crypto research except key-handling", and I (or anybody else) would be very wrong if we claimed to have the EndlÖsung for that problem. The important feature in this situation is to be able to work with whatever keyhandling scheme the user (or administrator) wants to implement, not to ram our preference down their throat. >It is all well and good for both of us to talk about 2^256 and >2^2176 and 2^128 * 2^30, etc. But, a dictionary attack is likely >to be a lot closer to 2^35 or 2^40. This is, I think, in the >general use case the real threat. It is the low hanging fruit. Yes, absolutely. The difference between CGD and GBDE in this area is that for CGD it is not convincibly shown that it is the only feasible attack (because you use the same key for all sectors thus exposing the ciphers possible weaknesses big time), for GBDE everybody so far agrees that the key is the only feasible attack. >With GBDE, the dictionary attack can be performed half offline >because the SHA2/512 is not salted. Sure, but if the dictionary includes guessing the 1KB of random bits on my USB gadget, you are more than welcome to do so. If you as a user are worried about dictionary attacks, then you obviously will employ a key handling method which mitigates it. My preference is a storage gadget with a large slap of bits which are one part of the passphrase, other people have other preferences. GBDE supports them all. But there are also users who are rightly not worried about dictionary attacks: People transmitting data via CDroms in envelopes. They ship the bulk of thier data that way (and I mean BULK! in the case I'm thinking about. BofA could learn something here BTW!), but the GBDE key is generated from a PRNG and emailed using PGP. The entire process is automated. >With GBDE the keys used to encrypt each of the key-key sectors >remain static. So, like CGD there is no effective way to revoke >access to the disk from wily and intelligent insiders who at some >point had access to the disk, except by re-encrypting the whole >thing. With both systems, the `master key' remains static and >hence if you can calculate it once you have it. That is a non-problem which GBDE doesn't claim to address: The vily insider is very likely to already have taken a copy of the data he wanted. >While we are at it, I do not believe that having a key that is >larger than 1024 bits necessarily guarantees that the effort required >to crack it is commensurate with its size. That obviously depends on the attack method and direction. >E.g. given the bit-blender >approach of GBDE [from 7.4 of your paper], if you know the salt >then you can use a divide-and-conquer strategy to tease the master >key out in a ``reasonably short'' time. Less than 2^128 steps >certainly, if I look at things correctly. I don't think you do. 2^128 will give you only one data sector. Then you need 2^128 to bruteforce the key encryption. Then you need 2^128 inverse MD5 operations, however much effort we assign that it is not zero, it will take you at least one clock cycle for each to store the result. By the time you've done that, you know 16 byte values which appear in the master key, but you do not know their indices in the master key There are between (256!/(256-16)!) and 256^16 (= 2^127...2^128) different possibilities for those sixteen indices and you won't know which it is until you know how many, if any, of those 16 values are identical. You may have a detection mechanism for the data sector which allows you to stop as soon as you have a hit, but there is no detection mechanism to let you know when you have a hit for the key encryption (or the MD5 unless "MD5^-1" is truly found), so you will be forced to operate with all 2^128 possibilities for the key-key, and spend some effort on the inverse MD5 for all of those before you continue. (MD5 may or may not add any real strengt at this point, it's there only as a bit blender. If MD5 adds strength, it is multiplicative not additive, because it applies to all of the 2^128 possibilities.) At this point you will need to find storage space for the 2^128 * 16 bytes if you want to avoid recomputations. I belive this means that you'll need to store 2^32 bits on every hydrogen atom in the universe (and then some.) Once you break the second data sector open, you can start to weed some of the 2^128 possibilities out, but it will be a long time before you get that down to a manageable number because only impossible output codes from MD5 will prune it for you. Of the 2^128 possibilities from the first sector and the 2^128 possibilities for the second data sector you broke, some, but not all, will have shared values for some of the 16 bytes from the masterkey. Being identical is no guarantee that they have the same index in the masterkey, but you can nontheless at this point start to attack the toplevel MD5 based on that theory. Getting more like 10-20 sectors would improve your chances a lot but then you need more storage space. Attacking from the top side means breaking the 512 bytes which protect one of the master keys. Given that there are four of them, I will conceeede to 508 bits of work. If we cut that in half just on general principles of being very very conservative, we get down to where the 256 bit version of CGD is if we ignore the CGD's little issue with key reuse. >So, if I were attacking GBDE, what I would do would be to look for >the superblock which is ~trivial to recognise and then walk down >the directory chain until I found the files/directories that I >want. I'll give you the headstart that you know where the superblock is. So you brute force the superblock. (2^128). >From that you can find the relative sector position of the inode table (we totally ignore the uncertainty of the for keysectors interleaving here). Then you bruteforce the first inode block (2^128) Then you bruteforce the first sector of the root directory (2^128) and you are lucky and find the file right there. You're even more lucky that the file has an inode in the same inode sector you already handled. And now you can start to bruteforce the data sector of the file (of which there is only one) (2^128). Now, you can't possibly be more lucky than this so that was 2^132 in the ultimate best case, downhill etc etc. But let us be a bit realistic: In case you get a false hit on the superblock, when do you find out ? The superblock is highly structured, but it is not free of entropy, so this is a very real risk. The answer is that you will not be sure to find out until you have broken the inode sector as well. Well, what if that gives you false hit too ? You get the picture. With CGD if I suspect a hit I can just run fsck or mount it. Fsck may be slow when you are in a hurry, but it is a lot faster than bruteforcing a 128 bit AES. By the way: you keep comparing your AES256 version of CGD to my AES128 version of GBDE, but at the same time you want me to conceede that your 256 bit key is almost 1024 bits when seen in the right light. Lets us be fair and use a level ground: Let us compare two 128 bit version or two 256 bit versions. Now, which algorithm is stronger ? >If a breakthrough makes AES128 very easy to crack, then you can >just crack the sectors individually, ignoring the rest of the >system. Yes, but is would be Nsect easier with CGD as the entire thing unravels at the first sector I break. With GBDE I have to attack them one by one. And since it is almost a given that any attack on AES will be statistical in nature, GBDE is much more resistant because there is no two-way leverage on any of the algoritms. So, I will still claim that you get points for your key handling and flunk on the disk encryption side. -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 phk@FreeBSD.ORG | TCP/IP since RFC 956 FreeBSD committer | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?2759.1109809815>