| Message ID | 1492727320-26194-2-git-send-email-mkayaalp@linux.vnet.ibm.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Thu, 20 Apr 2017, Mehmet Kayaalp wrote: > Include a random filled binary in vmlinux at the space reserved with > CONFIG_SYSTEM_EXTRA_CERTIFICATE. This results in an uncompressed reserved Random data is not always going to be completely incompressible. And just how much it could be compressed also depends on the compression engine. Failures here would be quite annoying, even if they would be rare (not just due to the randomness factor, but also depending on just how overprovisioned the space reserved for the extra certificate was when compared with the real certificate size). Maybe it would be safer if you test it for incompressability once you generated the random data (using the same compression engine that the image will use)? If it fails, add some overprovisioning and retry... Alternatively, you could ship a static file with random data that has been tested to be uncompressible "enough" for every currently supported compression engine, maybe with a bit of a safety margin just in case a future compression engine does somewhat better...
> On Apr 20, 2017, at 7:13 PM, Henrique de Moraes Holschuh <hmh@hmh.eng.br> wrote: > > On Thu, 20 Apr 2017, Mehmet Kayaalp wrote: >> Include a random filled binary in vmlinux at the space reserved with >> CONFIG_SYSTEM_EXTRA_CERTIFICATE. This results in an uncompressed reserved > > Random data is not always going to be completely incompressible. And > just how much it could be compressed also depends on the compression > engine. It's almost impossible to compress random data. The compression algorithm is looking for a pattern, and there is none. Plus, the format of the compression adds an overhead. for n in `seq 8 24`; do \ perl -e 'srand(0); printf("%c", int(rand(256))) for (1..(1<<$ARGV[0]))' \ $n | bzip2 -9 -c -v > /dev/null; \ done (stdin): 0.615:1, 13.000 bits/byte, -62.50% saved, 256 in, 416 out. (stdin): 0.760:1, 10.531 bits/byte, -31.64% saved, 512 in, 674 out. (stdin): 0.780:1, 10.250 bits/byte, -28.12% saved, 1024 in, 1312 out. (stdin): 0.831:1, 9.629 bits/byte, -20.36% saved, 2048 in, 2465 out. (stdin): 0.895:1, 8.939 bits/byte, -11.74% saved, 4096 in, 4577 out. (stdin): 0.947:1, 8.449 bits/byte, -5.62% saved, 8192 in, 8652 out. (stdin): 0.972:1, 8.232 bits/byte, -2.90% saved, 16384 in, 16859 out. (stdin): 0.985:1, 8.122 bits/byte, -1.52% saved, 32768 in, 33266 out. (stdin): 0.990:1, 8.079 bits/byte, -0.99% saved, 65536 in, 66187 out. (stdin): 0.993:1, 8.060 bits/byte, -0.75% saved, 131072 in, 132055 out. (stdin): 0.994:1, 8.048 bits/byte, -0.60% saved, 262144 in, 263720 out. (stdin): 0.995:1, 8.042 bits/byte, -0.53% saved, 524288 in, 527067 out. (stdin): 0.996:1, 8.036 bits/byte, -0.45% saved, 1048576 in, 1053269 out. (stdin): 0.996:1, 8.036 bits/byte, -0.45% saved, 2097152 in, 2106558 out. (stdin): 0.996:1, 8.035 bits/byte, -0.44% saved, 4194304 in, 4212741 out. (stdin): 0.996:1, 8.035 bits/byte, -0.44% saved, 8388608 in, 8425198 out. (stdin): 0.996:1, 8.035 bits/byte, -0.44% saved, 16777216 in, 16850429 out. > Failures here would be quite annoying, even if they would be rare (not > just due to the randomness factor, but also depending on just how > overprovisioned the space reserved for the extra certificate was when > compared with the real certificate size). I wanted to avoid the randomness with the seed. For a given size, you will get the same random payload. There will be over-provisioning, but primarily because we don't know the size of the certificate to be inserted, and how much it will compress. > Maybe it would be safer if you test it for incompressability once you > generated the random data (using the same compression engine that the > image will use)? If it fails, add some overprovisioning and retry... The actual amount of over-provisioning will depend on the size and the compressibility of the certificate to be inserted. If you have a longer CN, it will compress more. > Alternatively, you could ship a static file with random data that has > been tested to be uncompressible "enough" for every currently supported > compression engine, maybe with a bit of a safety margin just in case a > future compression engine does somewhat better... The seed makes it static for a given size, and I tested it to be incompressible. But I don't know about the safety margin. Even without the compression, the reserved size is not accurate. If you reserve 4096 bytes, the DER encoded certificate inserted is not going to be exactly 4096 either (for reference, the built-in certificate is 1346 bytes). Compression makes it a little more inaccurate, but is over-provisioning several hundreds of bytes a concern when the bzImage is several megabytes? Unless you have a compression method that detects how the pseudo-random bytes are generated and encodes the recipe to generate it again, you can't achieve positive compression rates. I'm sure there is a proof for true random generation involving the Shannon entropy. > Henrique Holschuh Mehmet -- To unsubscribe from this list: send the line "unsubscribe linux-security-module" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, 20 Apr 2017, Mehmet Kayaalp wrote: > > On Apr 20, 2017, at 7:13 PM, Henrique de Moraes Holschuh <hmh@hmh.eng.br> wrote: > > On Thu, 20 Apr 2017, Mehmet Kayaalp wrote: > >> Include a random filled binary in vmlinux at the space reserved with > >> CONFIG_SYSTEM_EXTRA_CERTIFICATE. This results in an uncompressed reserved ... > > Alternatively, you could ship a static file with random data that has > > been tested to be uncompressible "enough" for every currently supported > > compression engine, maybe with a bit of a safety margin just in case a > > future compression engine does somewhat better... > > The seed makes it static for a given size, and I tested it to be > incompressible. But I don't know about the safety margin. Even without the If you tested the result to be incompressible enough, it is fine with me. > compression, the reserved size is not accurate. If you reserve 4096 bytes, > the DER encoded certificate inserted is not going to be exactly 4096 either > (for reference, the built-in certificate is 1346 bytes). Compression makes it > a little more inaccurate, but is over-provisioning several hundreds of bytes > a concern when the bzImage is several megabytes? Maybe for embedded, but in that case any overprovisioning would already be too much, and one has to fix the issue in some other way.
diff --git a/certs/.gitignore b/certs/.gitignore index f51aea4..4ecc8dd 100644 --- a/certs/.gitignore +++ b/certs/.gitignore @@ -2,3 +2,4 @@ # Generated files # x509_certificate_list +extra_cert_placeholder diff --git a/certs/Makefile b/certs/Makefile index 4119bb3..ad04feb 100644 --- a/certs/Makefile +++ b/certs/Makefile @@ -15,7 +15,12 @@ ifeq ($(CONFIG_SYSTEM_TRUSTED_KEYRING),y) $(eval $(call config_filename,SYSTEM_TRUSTED_KEYS)) # GCC doesn't include .incbin files in -MD generated dependencies (PR#66871) -$(obj)/system_certificates.o: $(obj)/x509_certificate_list +ifeq ($(CONFIG_SYSTEM_EXTRA_CERTIFICATE),y) +system_certs_incbin = $(obj)/x509_certificate_list $(obj)/extra_cert_placeholder +else +system_certs_incbin = $(obj)/x509_certificate_list +endif +$(obj)/system_certificates.o: $(system_certs_incbin) # Cope with signing_key.x509 existing in $(srctree) not $(objtree) AFLAGS_system_certificates.o := -I$(srctree) @@ -23,12 +28,22 @@ AFLAGS_system_certificates.o := -I$(srctree) quiet_cmd_extract_certs = EXTRACT_CERTS $(patsubst "%",%,$(2)) cmd_extract_certs = scripts/extract-cert $(2) $@ || ( rm $@; exit 1) -targets += x509_certificate_list +targets += $(system_certs_incbin) $(obj)/x509_certificate_list: scripts/extract-cert $(SYSTEM_TRUSTED_KEYS_SRCPREFIX)$(SYSTEM_TRUSTED_KEYS_FILENAME) FORCE $(call if_changed,extract_certs,$(SYSTEM_TRUSTED_KEYS_SRCPREFIX)$(CONFIG_SYSTEM_TRUSTED_KEYS)) + +ifeq ($(CONFIG_SYSTEM_EXTRA_CERTIFICATE),y) +# Generate incompressible bytes. Use seed to make it reproducible +quiet_cmd_placeholder = EXTRA_CERT_PLACEHOLDER + cmd_placeholder = perl -e 'srand(0); printf("%c", int(rand(256))) for (1..$(2))' > $@ + +$(obj)/extra_cert_placeholder: FORCE + $(call if_changed,placeholder,$(CONFIG_SYSTEM_EXTRA_CERTIFICATE_SIZE)) +endif + endif -clean-files := x509_certificate_list .x509.list +clean-files := $(system_certs_incbin) .x509.list ifeq ($(CONFIG_MODULE_SIG),y) ############################################################################### diff --git a/certs/system_certificates.S b/certs/system_certificates.S index c9ceb71..02b9222 100644 --- a/certs/system_certificates.S +++ b/certs/system_certificates.S @@ -17,7 +17,7 @@ __cert_list_end: .globl VMLINUX_SYMBOL(system_extra_cert) .size system_extra_cert, CONFIG_SYSTEM_EXTRA_CERTIFICATE_SIZE VMLINUX_SYMBOL(system_extra_cert): - .fill CONFIG_SYSTEM_EXTRA_CERTIFICATE_SIZE, 1, 0 + .incbin "certs/extra_cert_placeholder" .align 4 .globl VMLINUX_SYMBOL(system_extra_cert_used)
Include a random filled binary in vmlinux at the space reserved with CONFIG_SYSTEM_EXTRA_CERTIFICATE. This results in an uncompressed reserved area inside the bzImage as well, so that it can be replaced with an actual certificate later (after the bzImage is distributed). The bzImage contains a stripped ELF file with one section containing the compressed vmlinux. If the reserved space is initially filled with zeros, certificate insertion will cause a size increase in the compressed vmlinux. In that case, reconstructing the bzImage would require relocation. To avoid this situation, the reserved space is initially filled with random bytes. Since a certificate contains some compressible bytes, after insertion the vmlinux will hopefully be compressed to a smaller size. Signed-off-by: Mehmet Kayaalp <mkayaalp@linux.vnet.ibm.com> --- certs/.gitignore | 1 + certs/Makefile | 21 ++++++++++++++++++--- certs/system_certificates.S | 2 +- 3 files changed, 20 insertions(+), 4 deletions(-)