Re: Early boot, activation, upgrades
On Jul 14, 2007, at 9:07 AM, C. Scott Ananian wrote: > This seems to imply a much beefier initramfs than is currently the > case, and one that is invoked on every boot. It can be done without beefing up the initramfs much, but you have a good point about it requiring one for every boot. Let me think a bit about how best to do this without one. -- Ivan Krstić <[EMAIL PROTECTED]> | http://radian.org ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On 7/14/07, Ivan Krstić <[EMAIL PROTECTED]> wrote: > On Jul 10, 2007, at 5:54 PM, C. Scott Ananian wrote: > > Unless we're actually going to do a full cryptographic authentication > > of the entire FS image at every boot, the kernel checking is just > > security theater. > I missed this message when originally following the thread. This is > incorrect. Verifying the integrity of the kernel and the initramfs is > necessary and sufficient for guaranteeing that the anti-theft daemon > gets started in a container that cannot be killed. Making theft non- > trivial is the entire point behind the crypto dance; if that is met, > we don't care whether the rest of the FS is modified. This seems to imply a much beefier initramfs than is currently the case, and one that is invoked on every boot. --scott -- ( http://cscott.net/ ) ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On Jul 10, 2007, at 5:54 PM, C. Scott Ananian wrote: > Unless we're actually going to do a full cryptographic authentication > of the entire FS image at every boot, the kernel checking is just > security theater. I missed this message when originally following the thread. This is incorrect. Verifying the integrity of the kernel and the initramfs is necessary and sufficient for guaranteeing that the anti-theft daemon gets started in a container that cannot be killed. Making theft non- trivial is the entire point behind the crypto dance; if that is met, we don't care whether the rest of the FS is modified. -- Ivan Krstić <[EMAIL PROTECTED]> | http://radian.org ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On Jul 11, 2007, at 3:50 PM, Mitch Bradley wrote: > It wasn't obvious how to coerce the code to do 256-bit truncated > Whirlpool, so I don't have a number for that. Whirlpool doesn't matter for the general boot case anyway. Looks like if we go with SHA-256 and ECC-256 we can do the verification in about 0.6 seconds, which is fine by me. -- Ivan Krstić <[EMAIL PROTECTED]> | http://radian.org ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
More benchmarks for bios_crypto on LX: Whirlpool: 1.16 sec / MiB SHA512: 0.42 sec / MiB SHA256: 0.28 sec / MiB <<--- New result (SHA256 is 1.5x the speed of SHA512) RSA verification: 0.025 sec / hash ECC521 verification: 1.13 sec / hash ECC256 verification: 0.31 sec / hash <<--- New result (ECC256 is 3.5x the speed of ECC521) It wasn't obvious how to coerce the code to do 256-bit truncated Whirlpool, so I don't have a number for that. ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On Jul 11, 2007, at 1:25 AM, Jonathan Herzog wrote: > Now that I've looked through the code for LTC SHA-512, I'm pretty > sure that I can examine LTC SHA-256 in a day or two. Is there an > imminent deadline I should know about? I don't want to change the crypto going in the Trial-2 firmware at this point so there isn't an imminent 2-day deadline, but if we're changing the primitives, I'd like to get it done very soon. To provide context: the bios-crypto was originally going to be solely used to ascertain integrity of BIOS updates, but we're now planning to use it for kernel integrity verification as well (which happens on every boot), and it's too slow for that. To accommodate both use cases without adding primitives to the library, I proposed going from the current state (Whirlpool, SHA-512, ECC-521, RSA-2048) to 256-bit truncated Whirlpool, SHA-256, ECC-256, and RSA-2048 (no change there). I'm perfectly comfortable with this not meaningfully reducing the overall security of the BIOS update verification, while letting us use just SHA-256 and ECC-256 to do kernel integrity verification, which should prove substantially faster (benchmark is pending). > As for the 256-bit curve: yes, it will trigger unaudited code > paths, but that's because I haven't yet audited every function used > by the ECC package. ECC uses a lot of math, for example, and I > haven't yet looked at each mathematical function yet. However, I > can say that the 256-bit curve defined in LTC matches the NIST > recommendation, and that the unaudited code paths triggered by that > curve will be in the underlying math functions, not LTC itself. Right. The math functions are in your queue to be audited, correct? Cheers, -- Ivan Krstić <[EMAIL PROTECTED]> | http://radian.org ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
Timings for OFW access to JFFS2 files in NAND FLASH: First access (scanning NAND to create memory index of nodes): 7 seconds Subsequent accesses: 0.5 seconds fixed + 0.5 sec / MiB (approximately) ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
Now that I've looked through the code for LTC SHA-512, I'm pretty sure that I can examine LTC SHA-256 in a day or two. Is there an imminent deadline I should know about? As for the 256-bit curve: yes, it will trigger unaudited code paths, but that's because I haven't yet audited every function used by the ECC package. ECC uses a lot of math, for example, and I haven't yet looked at each mathematical function yet. However, I can say that the 256-bit curve defined in LTC matches the NIST recommendation, and that the unaudited code paths triggered by that curve will be in the underlying math functions, not LTC itself. -- Jonathan Herzog Cryptographic consulting [EMAIL PROTECTED] www.jonathanherzog.com On Jul 10, 2007, at 1:14 PM, Ivan Krstić wrote: Jon, do you think you would be able to audit the LTC SHA-256 code reasonably quickly, and do you have qualms about the NIST 256-bit ECC curve triggering unaudited code paths? I'm not familiar with that code. -- Ivan Krstić <[EMAIL PROTECTED]> | http://radian.org ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
Clearly we have to hash & check an unknown kernel given to us on a USB drive (say), but is checking the authenticity of the kernel on our flash actually buying us any security? It's much easier to 0wn the system by altering the root fs then by backdooring the kernel. Protecting the root fs by extension protects the kernel images. Unless we're actually going to do a full cryptographic authentication of the entire FS image at every boot, the kernel checking is just security theater. On the other hand, if we are to boot from an external USB device, we *definitely* need to require an initramfs. We should authenticate the kernel and the initramfs, and then the initramfs must authenticate the rest of the filesystem before allowing boot. I may be missing an essential threat here. Discussion wanted. --scott -- ( http://cscott.net/ ) ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
Complete timings for bios_crypto on LX: Whirlpool: 1.16 sec / MiB SHA512: 0.42 sec / MiB RSA verification: 0.025 sec / hash ECC verification: 1.13 sec / hash Combined time for verifying 1MiB firmware image is 1.16 + 0.42 + 2*0.025 + 2*1.13 ~= 3.9 sec. That is 2.3 sec fixed + 1.6 sec / MiB Assuming a 1.5 MiB kernel + 2 MiB initrd, the 4-check time would be about 8 seconds. If we used SHA512+RSA only, the kernel+initrd time would be about 1.5 seconds. For a 1.5 MiB kernel with no ramdisk, the SHA512+RSA time would be about 0.7 seconds. ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On 7/10/07, C. Scott Ananian <[EMAIL PROTECTED]> wrote: > The AES encryption on the Geode is spec'ed at 40MiB/sec. Using a > fixed key converts AES into a hash function which is over 50x faster > than what we've got. I take this back, partially: the Geode AES is geared towards bulk encryption with a fixed key. Although my copy of Applied Crypto is at home, hash-using-block cipher algorithms rekey often (see http://en.wikipedia.org/wiki/Hash_functions_based_on_block_ciphers and its footnote 1). I couldn't immediately find cycle breakdowns for rekeying on the Geode, but it's reasonable to assume that we can't quite hash at 40MiB/s. However, the 50x factor gives us plenty of room to play with, and the Geode AES interface lets us pipeline the two halves of an MDC-2 implementation ( http://eprint.iacr.org/2006/294.pdf ). It may be of academic interest to implement and benchmark AES-128/MDC-2 now that I've got an XO, but from what I'm hearing our hash algorithms are already pretty much set in stone. --scott -- ( http://cscott.net/ ) ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On 7/10/07, C. Scott Ananian <[EMAIL PROTECTED]> wrote: > The AES encryption on the Geode is spec'ed at 40MiB/sec. Using a > fixed key converts AES into a hash function which is over 50x faster > than what we've got. For reference, that would be p512 of http://www.amd.com/files/connectivitysolutions/geode/geode_lx/33234E_LX_databook.pdf and chapter 18 of Applied Cryptography, "ONE-WAY HASH FUNCTIONS USING SYMMETRIC BLOCK ALGORITHMS". As a stopgap, using only SHA-512 (and leaving off the whirlpool hash) will more than double our authentication speed. --scott -- ( http://cscott.net/ ) ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On Jul 10, 2007, at 4:09 PM, Mitch Bradley wrote: > Such code is welcome in principle, but in practice, I don't really > have time to reintegrate different code for the near term deliveries. Yeah, it's not a near-term solution at all. If we do anything, a changeover to faster primitives that doesn't break the OFW integration in any way is the only thing I consider viable. -- Ivan Krstić <[EMAIL PROTECTED]> | http://radian.org ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On Jul 10, 2007, at 3:52 PM, Mitch Bradley wrote: > Whirlpool takes 1.16 sec/MiB. SHA512 takes 0.42 sec/MiB (on a preB3, > i.e. an LX CPU). Maybe we have to change the primitives we're using. These timings are entirely acceptable for BIOS updates, but not quite enjoyable for every boot (which we didn't have in mind when we were rolling the crypto). We could come down to shorter RSA and ECC, and SHA-256 and 256-bit truncated Whirlpool. Unfortunately, our crypto audit has been performed on the current set of primitives. Jon, do you think you would be able to audit the LTC SHA-256 code reasonably quickly, and do you have qualms about the NIST 256-bit ECC curve triggering unaudited code paths? I'm not familiar with that code. -- Ivan Krstić <[EMAIL PROTECTED]> | http://radian.org ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
It's probably too late now, but.. The AES encryption on the Geode is spec'ed at 40MiB/sec. Using a fixed key converts AES into a hash function which is over 50x faster than what we've got. --scott -- ( http://cscott.net/ ) ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
Ivan Krstić wrote: > On Jul 10, 2007, at 4:00 PM, NoiseEHC wrote: > >> There is an MMX WHIRLPOOL version in cripto++. Are you using that? >> > > We had to optimize for code size, and the only suitably licensed > library we could find that would let us squeeze all four primitives > into a ~60K package was LTC. The git tree is here: > > git://dev.laptop.org/bios-crypto > > Code from other libraries that has an equal or smaller compiled > footprint and is faster is certainly welcome. > Such code is welcome in principle, but in practice, I don't really have time to reintegrate different code for the near term deliveries. > -- > Ivan Krstić <[EMAIL PROTECTED]> | http://radian.org > > ___ > Devel mailing list > Devel@lists.laptop.org > http://lists.laptop.org/listinfo/devel > ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On Jul 10, 2007, at 4:00 PM, NoiseEHC wrote: > There is an MMX WHIRLPOOL version in cripto++. Are you using that? We had to optimize for code size, and the only suitably licensed library we could find that would let us squeeze all four primitives into a ~60K package was LTC. The git tree is here: git://dev.laptop.org/bios-crypto Code from other libraries that has an equal or smaller compiled footprint and is faster is certainly welcome. -- Ivan Krstić <[EMAIL PROTECTED]> | http://radian.org ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
There is an MMX WHIRLPOOL version in cripto++. Are you using that? Mitch Bradley wrote: > Whirlpool takes 1.16 sec/MiB. SHA512 takes 0.42 sec/MiB (on a preB3, > i.e. an LX CPU). > > ___ > Devel mailing list > Devel@lists.laptop.org > http://lists.laptop.org/listinfo/devel > > > ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
Whirlpool takes 1.16 sec/MiB. SHA512 takes 0.42 sec/MiB (on a preB3, i.e. an LX CPU). ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
C. Scott Ananian wrote: > On 7/10/07, Mitch Bradley <[EMAIL PROTECTED]> wrote: >> In particular, the current code does: >> Hashes file data with whirlpool >> Hashes file data with SHA-512 >> Verifies RSA signature against whirlpool hash >> Verifies RSA signature against SHA-512 hash >> Verifies ECC signature against whirlpool hash >> Verifies ECC signature against SHA-512 hash > > Well, the four signature validation checks are independent of the size > of the file data. I think the original concern was whether the > activation initramfs was going to bloat the kernel enough to > significantly slow down the hashing steps. If that is the case, then > dropping either whirlpool or SHA-512 would help -- or we could debloat > the initramfs, split the initramfs signature from the kernel signature > and only check the initramfs if it is used, speed up the whirlpool > implementation, or speed up the SHA-512 implementation. I don't yet > have an XO to benchmark on -- does anyone know the rough throughput > (MB/s) of the current whirlpool and SHA-512 implementations? > --scott > I'll have to do some more work to get a breakdown, but I do have a rough number to use as a starting point. Using junk data as the input and a good key file (that doesn't match the junk data), the combined test goes at 1.5 seconds per megabyte. That is basically the two hashes plus the first verification step (RSA+whirlpool), since the first step will fail and it won't do the other three. Regression indicates that the first verify step takes about 35 ms - the bulk of the time is in the hash. I think the ECC verification steps must be slower, because the total time for all steps on good data of length 100K is 2.5 seconds. ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On 7/10/07, Mitch Bradley <[EMAIL PROTECTED]> wrote: > In particular, the current code does: > Hashes file data with whirlpool > Hashes file data with SHA-512 > Verifies RSA signature against whirlpool hash > Verifies RSA signature against SHA-512 hash > Verifies ECC signature against whirlpool hash > Verifies ECC signature against SHA-512 hash Well, the four signature validation checks are independent of the size of the file data. I think the original concern was whether the activation initramfs was going to bloat the kernel enough to significantly slow down the hashing steps. If that is the case, then dropping either whirlpool or SHA-512 would help -- or we could debloat the initramfs, split the initramfs signature from the kernel signature and only check the initramfs if it is used, speed up the whirlpool implementation, or speed up the SHA-512 implementation. I don't yet have an XO to benchmark on -- does anyone know the rough throughput (MB/s) of the current whirlpool and SHA-512 implementations? --scott -- ( http://cscott.net/ ) ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
Ivan Krstić wrote: > On Jul 10, 2007, at 8:46 AM, C. Scott Ananian wrote: >> Can't we just SHA1 the kernel+initrd bundle and sign the hash? SHA1 >> should be fast enough... > > The hashes we have available in OFW through the LTC code are Whirlpool > and SHA-512. It's non-trivial to amend the list at this time. The > current crypto code uses a slow(ish) and paranoid combination of the > two hashes with two signature systems because it was designed to > verify BIOS updates, where maximal paranoia is justified. We will want > to adjust the system to drop down to a single hash algorithm and > signature system for the normal boot integrity verification, which > should make it quite a bit faster. In particular, the current code does: Hashes file data with whirlpool Hashes file data with SHA-512 Verifies RSA signature against whirlpool hash Verifies RSA signature against SHA-512 hash Verifies ECC signature against whirlpool hash Verifies ECC signature against SHA-512 hash If we want to use an abbreviated test for the kernel, I will need to change the packaging of the crypto code so the firmware has finer-grained access to the piece-parts. ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On 7/10/07, Ivan Krstić <[EMAIL PROTECTED]> wrote: > On Jul 9, 2007, at 7:08 PM, C. Scott Ananian wrote: > > In theory, we then do some basic XO networking setup (unwritten due to > > a lack of XO which will be soon remedied) and then invoke activation > > if necessary (Ivan will write this part?). > > I'll post code for this shortly. Please do, even in an unfinished state. I was re-reading the BitFrost spec, and noticed the 'activation from USB key' option -- so early boot need to have USB/IDE modules, etc. This should be easy to get working, but I'd like to finish 'activation' before I start 'upgrade'. --scott -- ( http://cscott.net/ ) ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On Jul 9, 2007, at 7:08 PM, C. Scott Ananian wrote: > In theory, we then do some basic XO networking setup (unwritten due to > a lack of XO which will be soon remedied) and then invoke activation > if necessary (Ivan will write this part?). I'll post code for this shortly. -- Ivan Krstić <[EMAIL PROTECTED]> | http://radian.org ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On Jul 10, 2007, at 8:46 AM, C. Scott Ananian wrote: > Can't we just SHA1 the kernel+initrd bundle and sign the hash? SHA1 > should be fast enough... The hashes we have available in OFW through the LTC code are Whirlpool and SHA-512. It's non-trivial to amend the list at this time. The current crypto code uses a slow(ish) and paranoid combination of the two hashes with two signature systems because it was designed to verify BIOS updates, where maximal paranoia is justified. We will want to adjust the system to drop down to a single hash algorithm and signature system for the normal boot integrity verification, which should make it quite a bit faster. -- Ivan Krstić <[EMAIL PROTECTED]> | http://radian.org ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On 7/10/07, Mitch Bradley <[EMAIL PROTECTED]> wrote: > Decompression is fast, but the signature verification is not so fast, > especially since there are several different algorithms. Can't we just SHA1 the kernel+initrd bundle and sign the hash? SHA1 should be fast enough... --scott -- ( http://cscott.net/ ) ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
C. Scott Ananian wrote: > On 7/9/07, Mitch Bradley <[EMAIL PROTECTED]> wrote: >> At that 3M size, I'm beginning to have second thoughts about the "one >> initrd for both activation and normal booting" idea. A busybox >> (statically linked with uclibc) with enough trimmings to do darn near >> anything compresses to about 0.6 MB. The fact that the kernel can >> currently boot with no initrd at all makes it hard for me to swallow the >> proposition of tripling the load image size in the usual case. > > I'll look into how small I can make it tomorrow. If we've got to have > the initrd for activation, we might as well do normal boot with it, > since the time spent decompressing is still minimal for the sizes > we're talking about. I can try to quantify that claim once I get my > B4. ;-) > --scott > Decompression is fast, but the signature verification is not so fast, especially since there are several different algorithms. ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On 7/9/07, Mitch Bradley <[EMAIL PROTECTED]> wrote: > At that 3M size, I'm beginning to have second thoughts about the "one > initrd for both activation and normal booting" idea. A busybox > (statically linked with uclibc) with enough trimmings to do darn near > anything compresses to about 0.6 MB. The fact that the kernel can > currently boot with no initrd at all makes it hard for me to swallow the > proposition of tripling the load image size in the usual case. I'll look into how small I can make it tomorrow. If we've got to have the initrd for activation, we might as well do normal boot with it, since the time spent decompressing is still minimal for the sizes we're talking about. I can try to quantify that claim once I get my B4. ;-) --scott -- ( http://cscott.net/ ) ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
C. Scott Ananian wrote: > On 7/9/07, Mitch Bradley <[EMAIL PROTECTED]> wrote: > >> I looked at those git trees and didn't see the python runtime stuff in >> the initramfs tree. How does it get included, and how big is it? >> > > Packages in initramfs are specified by: > > http://dev.laptop.org/git?p=users/cscott/d-i;a=blob;f=build/pkg-lists/olpc/common;hb=HEAD > > python2.5-minimal is about 2MB of the 3MB compressed initramfs. The > python2.5 binary is 1.4M (compressed) of that; it's likely that I > could trim this down a bit more -- I notice that the python2.5 binary > is unstripped, and stripping yields 470k compressed -- but I'm > reluctant to minimize stuff until Ivan's written his activation code > and we know roughly what packages we'll be wanting. For instance, > there are a lot of different encodings represented in > /usr/lib/python2.5/encodings which I've left because I don't know at > this point if activation will require a localized UI. > > For comparison, the existing traditional 'mayflower' initrd created > used for emulation is 2.3MB. So at the instant we're paying about > 700k for the privilege of writing our activation code in python, but > this number is pretty bogus. > At that 3M size, I'm beginning to have second thoughts about the "one initrd for both activation and normal booting" idea. A busybox (statically linked with uclibc) with enough trimmings to do darn near anything compresses to about 0.6 MB. The fact that the kernel can currently boot with no initrd at all makes it hard for me to swallow the proposition of tripling the load image size in the usual case. ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
Re: Early boot, activation, upgrades
On 7/9/07, Mitch Bradley <[EMAIL PROTECTED]> wrote: > I looked at those git trees and didn't see the python runtime stuff in > the initramfs tree. How does it get included, and how big is it? Packages in initramfs are specified by: http://dev.laptop.org/git?p=users/cscott/d-i;a=blob;f=build/pkg-lists/olpc/common;hb=HEAD python2.5-minimal is about 2MB of the 3MB compressed initramfs. The python2.5 binary is 1.4M (compressed) of that; it's likely that I could trim this down a bit more -- I notice that the python2.5 binary is unstripped, and stripping yields 470k compressed -- but I'm reluctant to minimize stuff until Ivan's written his activation code and we know roughly what packages we'll be wanting. For instance, there are a lot of different encodings represented in /usr/lib/python2.5/encodings which I've left because I don't know at this point if activation will require a localized UI. For comparison, the existing traditional 'mayflower' initrd created used for emulation is 2.3MB. So at the instant we're paying about 700k for the privilege of writing our activation code in python, but this number is pretty bogus. --scott -- ( http://cscott.net/ ) ___ Devel mailing list Devel@lists.laptop.org http://lists.laptop.org/listinfo/devel
