... taken from Wikipedia: https://commons.wikimedia.org/wiki/File:Tux_ecb.jpg .... might be five implementations of AES:
Linux Kernel Cryptographic API for fun and profit Gilad Ben-Yossef
Gilad Ben-Yossef © 2017 Arm Limited
[email protected] Twitter: @giladby
About me My name is Gilad Ben-Yossef. I work on upstream Linux kernel cryptography and security in general and arm® TrustZone® CryptoCell® support in particular.
I’m working in various forms with and on the Linux kernel and other Open Source projects for close to twenty years – i.e. I’m an old bugger… ☺ I co-authored “Building Embedded Linux Systems” 2nd edition from O’Reilly.
I’m a co-founder of HaMakor, an Israeli NPO for free and open source software and of August Penguin, the longest running Israeli FOSS conference.
2
© 2017 Arm Limited
Dedication
May these teaching serve to free men and women from tyranny, oppression and suffering. “How long do you want these messages to remain secret? … I want them to remain secret for as long as men are capable of evil.” ― Neal Stephenson, Cryptonomicon
3
© 2017 Arm Limited
4
© 2017 Arm Limited
Act I Alice, meet Bob – A (very) short introduction to Cryptography
5
© 2017 Arm Limited
P: Plain text C: Cipher text K: Key E: Encryption D: Decryption
Symmetric Encryption K
P
E C = E(k, P)
K
C
C
D
P
P = D(k, C)
E is a function that takes a key and a block of plain text* and outputs a block of random looking cipher text *.
D is the inverse function to D which takes the random looking cipher text* and the same key as input and outputs the original plain text*. 6
© 2017 Arm Limited
* Which doesn’t have to be and often isn’t text but rather binary data.
P: Plain text C: Cipher text K: Key E: Encryption D: Decryption
Block Ciphers Break down message to blocks, encrypt each block using the key
P = P1 P2 Ek
…
Pi
Ek
C = C1 C2
…
…
Pn
Ek
Ci
…
Ek
Cn
Examples: DES, 3DES, AES 7
© 2017 Arm Limited
Deprecated: do not use algorithms mark like these for anything new.
The problem with block ciphers
Identical plain text block yield identical cipher text blocks 8
© 2017 Arm Limited
Tux the Penguin, the Linux mascot. Created in 1996 by Larry Ewing with The GIMP. "Permission to use and/or modify this image is granted provided you acknowledge me
[email protected] and The GIMP if someone asks.” ECB Tux taken from Wikipedia: https://commons.wikimedia.org/wiki/File:Tux_ecb.jpg No Penguins were harmed during the making of this slide.
Modes of Operation Symmetric cryptographic functions E and D can be treated as black boxes. We can define different ways to use these black boxes to encrypt/decrypt our messages. These are referred to as the Modes of Operation of the symmetric cipher – how we choose to use it. We previously saw the most basic mode of operation called Electronic Code Book mode, or ECB mode for short.
Other modes of operations are defined that can, among other things, turn a block cipher into a stream cipher, thus making it more secure.
9
© 2017 Arm Limited
Cipher Chaining This is the Cipher Block Chaining mode, or CBC mode for short:
P1
P2
P2
P: Plain text C: Cipher text K: Key E: Encryption D: Decryption IV: Initial Vector
C0 = IV Ci = Ek(Pi Ci-1) Pi = Dk(Ci) Ci-1
IV
K
E C1
K
E C2
K
E C2
Each cipher block is dependent on the key and the previous blocks. Other operation modes include Output FeedBack, Cipher FeedBack and CounTeR modes. 10
© 2017 Arm Limited
Cryptographic Hashes (Digests) The ideal cryptographic hash function is: •
Deterministic
•
Quick to compute
•
Infeasible to generate a message from its hash value except by brute force
•
A small change to a message changes the hash value so extensively that the new hash value appears uncorrelated with the old hash value
•
Infeasible to find two different messages with the same hash value
“Regular” hash function requirements
Examples: MD5, SHA1, SHA2, SHA3, SM3 11
© 2017 Arm Limited
Source: Wikipedia
Message Authentication Codes Message Authentication Code, or MAC for short, is a method for generating a value that is computed from a message and a secret (key) that can tells the recipient: •
That the message has not be changed from the way it was originally sent
•
That the sender knows the secret (key)
For example, this can be a (bad!) MAC built on top of a cryptographic hash function:
MACk(M) = H(K || M) Example MACs: CBC-MAC, HMAC, GMAC
12
© 2017 Arm Limited
Hash Based Message Authentication Codes Where
13
HMAC(K, m) = H((K’ opad) || H(K’ ipad) || m))
•
H is a cryptographic hash function,
•
K is the secret key,
•
m is the message to be authenticated,
•
K' is another secret key, derived from the original key K (by padding K to the right with extra zeroes to the input block size of the hash function, or by hashing K if it is longer than that block size),
•
|| denotes concatenation,
•
⊕ denotes exclusive or (XOR),
•
opad is the outer padding (0x5c5c5c…5c5c)
•
ipad is the inner padding (0x363636…3636). © 2017 Arm Limited
Source: Wikipedia
Authenticated Encryption Authenticated Encryption with Associated Data (AEAD) is a form of encryption which simultaneously provides confidentiality, integrity, and authenticity assurances on the data; decryption is combined in single step with integrity verification. These attributes are provided under a single, easy to use programming interface. An example of an AEAD in common use is Galois/Counter Mode, or GCM for short, shown in the picture above. • 14
GCM is considered a very efficient AEAD since it can produce both the cipher text and the MAC in a single pass on the data. © 2017 Arm Limited
Public Key Encryption Public key cryptography, or asymmetrical cryptography, uses a pair of keys: Public keys which may be disseminated widely and Private keys which are known only to the owner.
A public keys can encrypt a message only the private key can decrypt. The public key can authenticate a signature of a message generated by the private key.
15
© 2017 Arm Limited
Act II Here be Dragons The Linux kernel Crypto API
16
© 2017 Arm Limited
Transformations A transformation is an algorithm that transforms data. •
A transformation can be a cipher (i.e. encryption and decryption), whether symmetric or asymmetric, a hash, compression of data, IV generation and random number generation
•
TIP: this is the reason the handle to crypto API object is typically named “tfm”.
A transformation implementation is a code module that registers with the kernel that can provide a transformation. •
It can be just code running on the CPU, code that uses a special instruction as part of the CPU or a driver to some piece of hardware off of the CPU.
Multiple transformation implementation can exist that provide that same transformation. •
17
e.g. for an Arm CPU there might be five implementations of AES: the on-core implementations AES-CE, NEON, assembly and plain C and an off-core CryptoCell implementation.
© 2017 Arm Limited
Templates A transformation can be self contained (.e.g AES or SHA-2) but it can also be a template that works on another transformation: •
cts(aes) is AES working in Counter operation mode.
•
hmac(sha256) is SHA 256 being used as an HMAC.
Templates can be cascaded •
e.g. rfc4106(gcm(aes))) is AES in GCM operation mode as used in IPsec.
Templates can also express generic implementation augmentation. •
For example cryptd(aes) refers to code that runs an AES implementation in parallel inside kernel threads on all the system CPUs in parallel.
The same template works on multiple underlying transformations. •
18
e.g. cts(aes) and cts(3des) © 2017 Arm Limited
Priorities and true names There can be multiple transformation implementation, including template implementation, which provided the exact same transformation •
E.g. aes-ni, aes-asm and aes-generic are three different AES implementation on x86_64
When you use a generic name (e.g. aes) to refer to a transformation, the Crypto API will provide you the implementation with the highest priority that matches your request, based on priority value provided by the implementation when they register with the Crypto API. •
As we will see ahead you can limit the Crypto API to ignore certain type of providers based on their properties as we will see ahead.
If you want to refer to a specific implementation, use its driver name to refer to it. •
19
E.g. “aes-ni” forces the selection of the implementation that uses the AES-NI instruction.
© 2017 Arm Limited
/proc/crypto gby@gby:~$ cat /proc/crypto name : crc32 driver : crc32-pclmul module : crc32_pclmul priority : 200 refcnt : 1 selftest : passed type : shash blocksize : 1 digestsize : 4
20
© 2017 Arm Limited
Generic name
Driver’s name Priority
name driver module priority refcnt selftest type async blocksize min keysize max keysize ivsize geniv
: : : : : : : : : : : : :
xts(aes) xts-aes-aesni aesni_intel 400 1 passed ablkcipher yes 16 32 64 16
/proc/crypto continued gby@gby:~$ cat /proc/crypto | grep name
name
: aes
name
: crc32
name
: aes
name
: xts(aes)
name
: crct10dif
name
: lrw(aes)
name
: crct10dif
name
: __xts-aes-aesni
name
: crc32c
name
: __lrw-aes-aesni
name
: stdrng
name
: pcbc(aes)
name
: lzo
name
: rfc4106(gcm(aes))
name
: aes
name
: __gcm-aes-aesni
name
: sha1
name
: ctr(aes)
name
: md5
name
: __ctr-aes-aesni
name
: cbc(aes)
name
: __ecb-aes-aesni
name
: ecb(aes)
name
: __cbc-aes-aesni
name
: __ecb-aes-aesni
name
: __aes-aesni
21
© 2017 Arm Limited
We have 3 different implementations of AES We can use AES in 7 different operation modes
Synchronous versus Asynchronous A transformation’s implementation may be either synchronous or asynchronous. Synchronous implementations: •
Run wholly on the CPU itself in a synchronous fashion (take CPU cycles during all the run)
•
Access virtual memory using the CPU MMU mechanism
Asynchronous implementations: •
MAY be implemented using off-CPU resources (i.e. typically dedicated hardware), or not
•
MAY access memory via DMA and not have access to MMU, or not.
•
In fact, synchronous implementation are a sub group of asynchronous ones! –
e.g. cryptd(aes-ni) turns the synchronous aes-ni implementation into an asynchronous implementation by running it on several cores in parallel.
You can limit yourself to working only with synchronous implementations by passing the CRYPTO_ALG_ASYNC flag to allocation calls. 22
© 2017 Arm Limited
Backlog Transformation implementations have a certain capacity for in flight requests •
i.e. descriptor ring space, hardware FIFO etc.
If you pass the CRYPTO_TFM_REQ_MAY_BACKLOG flag to callback setting API call, you will allow the implementation provider to queue up back log word to a software queue if it doesn’t have enough capacity. •
If this happens, your callback function will be called twice: –
Once with err set to –EINPROGRESS to indicate it got queued off of the backlog.
–
A second time when it is actually processed
The kernel now has a generic implementation of this mechanism for transformation providers can use to implement this. •
23
However, the author believes it is currently buggy and is working to fix it… ☺ © 2017 Arm Limited
API Typical Life Cycle 1.
Allocate a transformation object (tfm)
2.
Get properties of the transformation chosen by the kernel (e.g. digest size)
3.
Set global transformation properties (e.g. encryption key)
4.
Allocate a request object
5.
Set request specific parameters, such as GFP flags and callback function to call when operation finish
6.
Initialize the request
7.
Feed data (e.g. buffers to encrypt or hash)
8.
Finalize (e.g. read final HMAC value)
9.
Free request object
10. Free transformation object 24
© 2017 Arm Limited
Symmetric cryptography code example I struct tcrypt_result { struct completion completion; int err; };
/* Perform cipher operation */ static unsigned int test_skcipher_encdec(struct skcipher_def *sk, int enc) { int rc = 0;
/* tie all data structures together */ struct skcipher_def { struct scatterlist sg; struct crypto_skcipher *tfm; struct skcipher_request *req; struct tcrypt_result result; };
if (enc) rc = crypto_skcipher_encrypt(sk->req); else rc = crypto_skcipher_decrypt(sk->req); switch (rc) { case 0: break; case -EINPROGRESS: case -EBUSY: rc = wait_for_completion_interruptible( &sk->result.completion); if (!rc && !sk->result.err) { reinit_completion(&sk->result.completion); break; } default: pr_info("skcipher encrypt returned with %d result %d\n", rc, sk->result.err); break; } init_completion(&sk->result.completion);
/* Callback function */ static void test_skcipher_cb(struct crypto_async_request *req, int error) { struct tcrypt_result *result = req->data;
if (error == -EINPROGRESS) return; result->err = error; complete(&result->completion); pr_info("Encryption finished successfully\n"); }
return rc; } 25
© 2017 Arm Limited
Symmetric cryptography code example II /* Initialize and trigger cipher operation */ static int test_skcipher(void) { struct skcipher_def sk; struct crypto_skcipher *skcipher = NULL; struct skcipher_request *req = NULL; char *scratchpad = NULL; char *ivdata = NULL; unsigned char key[32]; int ret = -EFAULT; skcipher = crypto_alloc_skcipher("cbc-aes-aesni", 0, 0); if (IS_ERR(skcipher)) { pr_info("could not allocate skcipher handle\n"); return PTR_ERR(skcipher); } req = skcipher_request_alloc(skcipher, GFP_KERNEL); if (!req) { pr_info("could not allocate skcipher request\n"); ret = -ENOMEM; goto out; } skcipher_request_set_callback(req, CRYPTO_TFM_REQ_MAY_BACKLOG, test_skcipher_cb, &sk.result);
26
© 2017 Arm Limited
/* AES 256 with random key */ get_random_bytes(&key, 32); if (crypto_skcipher_setkey(skcipher, key, 32)) { pr_info("key could not be set\n"); ret = -EAGAIN; goto out; } /* IV will be random */ ivdata = kmalloc(16, GFP_KERNEL); if (!ivdata) { pr_info("could not allocate ivdata\n"); goto out; } get_random_bytes(ivdata, 16); /* Input data will be random */ scratchpad = kmalloc(16, GFP_KERNEL); if (!scratchpad) { pr_info("could not allocate scratchpad\n"); goto out; } get_random_bytes(scratchpad, 16); sk.tfm = skcipher; sk.req = req;
Symmetric cryptography code example III /* We encrypt one block */ sg_init_one(&sk.sg, scratchpad, 16); skcipher_request_set_crypt(req, &sk.sg, &sk.sg, 16, ivdata); init_completion(&sk.result.completion); /* encrypt data */ ret = test_skcipher_encdec(&sk, 1); if (ret) goto out;
pr_info("Encryption triggered successfully\n"); out: if (skcipher) crypto_free_skcipher(skcipher); if (req) skcipher_request_free(req); if (ivdata) kfree(ivdata); if (scratchpad) kfree(scratchpad); return ret; }
27
© 2017 Arm Limited
API documentation and code examples Documentation/crypto or http://www.chronox.de/crypto-API/crypto/index.html
28
© 2017 Arm Limited
Pitfalls to look out for • This call requests only synchronous implementations tfm = crypto_alloc_ahash("md5", 0, CRYPTO_ALG_ASYNC); •
Yes, it’s totally backwards – the mask flag masks out the async. Implementations!
• If you see code that passes NULL as a callback like the following, it’s probably used the mask flag (see above) to request only synchronous implementations: • ahash_request_set_callback(req, 0, NULL, NULL); • Remember that operation may complete synchronously or asynchronously based on the transformation provider discretion only and you need to handle both cases! • Don’t ignore the err parameter of the callback. • Remember that if you passed the CRYPTO_TFM_REQ_MAY_BACKLOG flag when setting the callback, your callback may be called twice. • Even the request init function might sometime complete asynchronously. 29
© 2017 Arm Limited
Thank You! Danke! Merci! 谢谢! ありがとう! Gracias! Kiitos! 30
© 2017 Arm Limited
Auxiliary Slides
© 2017 Arm Limited
32
DM-Crypt and DM-Verity Protecting your file systems from the scum of the universe
© 2017 Arm Limited
DM-Crypt dm-crypt is a transparent disk encryption subsystem in Linux It is part of the device mapper infrastructure, and uses cryptographic routines from the kernel's Crypto API. dm-crypt was designed to support advanced modes of operation, such as XTS, LRW and ESSIV, in order to avoid watermarking attacks. dm-crypt is implemented as a device mapper target and may be stacked on top of other device mapper transformations. •
It can thus encrypt whole disks (including removable media), partitions, software RAID volumes, logical volumes, as well as files.
•
It appears as a block device, which can be used to back file systems, swap or as an LVM physical volume.
It is used by Android devices to implement Full Disk Encryption. 33
© 2017 Arm Limited
Simple dm-crypt setup example # cryptsetup luksFormat fs3.img # cryptsetup open --type luks fs3.img croot # mke2fs /dev/mapper/croot
# mount -t ext2 /dev/mapper/croot /media # umount /media/ # cryptsetup close croot
This examples uses AES in XTS operating mode to protect a loopback mounted partition file. Make sure to remember your chosen key or your data is lost! 34
© 2017 Arm Limited
DM-Verity Device-Mapper's "verity" target provides transparent integrity checking of block devices using a cryptographic digest provided by the kernel crypto API. T •
This target is read-only.
dm-verity helps prevent persistent rootkits that can hold onto root privileges and compromise devices. The dm-verity feature lets you look at a block device, the underlying storage layer of the file system, and determine if it matches its expected configuration.
It does this using a cryptographic hash tree. For every block (typically 4k), there is a SHA256 hash. Dm-verity can optionally FEC to protect against hash data corruptions.
DM-Verity is used by Android devices. 35
© 2017 Arm Limited
How does DM-Verity work? Dm-verity uses a Merkle tree of storage blocks to protect the integrity of the read only data on the storage device, in a way that the integrity can be evaluated in a lazy fashion during runtime instead of pre-mount time. It needs a singular trusted root hash to achieve security
36
© 2017 Arm Limited
Simple dm-verity setup example # veritysetup format filesystem.img signature.img # veritysetup create vroot filesystem.img signature.img \ ffa0a985fd78462d95c9b1ae7c9e49…5e3f13c10e4700058b8ed28
# mount -t ext2 /dev/mapper/vroot /media/ # umount /media # veritysetup remove vroot
This examples uses SHA 256 to protect the integrity of the loopback file system provided the root hash is secure. 37
© 2017 Arm Limited
The Arm trademarks featured in this presentation are registered trademarks or trademarks of Arm Limited (or its subsidiaries) in the US and/or elsewhere. All rights reserved. All other marks featured may be trademarks of their respective owners. www.arm.com/company/policies/trademarks
38
© 2017 Arm Limited
