mbox series

[v2,0/2] crypto: LEA block cipher implementation

Message ID 20230525121301.722682-1-letrhee@nsr.re.kr
Headers show
Series crypto: LEA block cipher implementation | expand

Message

Dongsoo Lee May 25, 2023, 12:12 p.m. UTC
This submission contains a generic C implementation of the LEA cipher algorithm and test vectors for it.

The LEA algorithm is a lightweight block cipher that processes data blocks of 128-bits and has three different key lengths, each with a different number of rounds:

- LEA-128: 128-bit key, 24 rounds,
- LEA-192: 192-bit key, 28 rounds, and
- LEA-256: 256-bit key, 32 rounds.

The round function of LEA consists of 32-bit ARX(modular Addition, bitwise Rotation, and bitwise XOR) operations. See [2, 5, 7] for details.

LEA is a Korean national standard block cipher, described in "KS X 3246"[1] and is also included in the international standard, "ISO/IEC 29192-2:2019 standard"[2].

It is one of the approved block ciphers for the current Korean Cryptographic Module Validation Program (KCMVP).

We expect that the first application of the patch would be disk encryption on the Gooroom platform ('Gooroom' is a Korean word, meaning 'cloud') [3]. Currently, the Gooroom platform uses AES-XTS for disk encryption. The main reason for submitting this patch is to make disk encryption with LEA (e.g. LEA-XTS) available on there.

The Gooroom platform is a government-driven Debian-based Linux distribution in South Korea. In Korea, there are many crypto companies that want to bundle Linux into their products and sell them. They create their own Gooroom platforms by modifying the original Gooroom platform for their services. (Of course, the Gooroom platform is not mandatory, and companies wishing to use Linux are free to choose an appropriate distribution.) BTW, in Korea, many crypto companies want to use LEA, because LEA is one of the block ciphers of the KCMVP, a validation program for commercial crypto S/W to be delivered to the Korean government.

The Linux Crypto API already has another Korean block cipher, ARIA, also one of the block ciphers of the KCVMP. However, LEA is more widely used than ARIA in industry nowadays, because LEA is one of the lightweight cryptography standard of ISO/IEC [2] and performs well on low-end devices that support 32-bit operations. So we think they are complementary to each other.

In general, it's obvious that the hardware-accelerated AES is the best performer. However, there exist not only environments where the hardware-accelerated AES is not supported, but also situations where AES is not preferred for various reasons. In these cases, if someone wants to encrypt using a block cipher, LEA could be an alternative.

There are also SIMD implementations for efficiently using LEA, which is not included in this patch. We have SSE2 and AVX2 assembly implementations, some of which were included in the previous version of the patch. The SIMD implementations are being re-implemented to support a wider range of environments.

Apart from this, we also have implemented LEA in lightweight environments such as 8-bit AVR, 16-bit MSP and 32-bit ARM [4]. If LEA were to be included in the Linux kernel, it would be possible to modify and supplement the submission with lightweight implementations to provide efficient encryption on embedded linux devices.

Although the designers of LEA did not provide test vectors in their paper [5], the ISO/IEC standard [2] and the KS standard [1] do. Furthermore, the Block Cipher LEA Specification("블록암호 LEA 규격서", written in Korean) document on the LEA introduction page [6] and the Wikipedia article on LEA [7] show the same test vectors as in the standards.

The test vectors for ECB, CBC, CTR, and GCM modes included in the testmgr module are taken from the KCMVP Cryptographic Algorithm Verification Criteria V3.0("KCMVP 검증대상 암호알고리즘 검증기준 V3.0", written in Korean) [8]. Test vectors for the XTS mode were generated by ourselves, and we crosschecked them using Crypto++ [9] and testmgr on Linux.

The implementation has been tested with kernel module tcrypt.ko and has passed the selftest using above-mentioned test vectors. It also has been tested with CONFIG_CRYPTO_MANAGER_EXTRA_TESTS and KASAN enabled considering the previous review.

[1] KS X 3246, 128-bit block cipher LEA.
[2] ISO/IEC 29192-2:2019, Information security — Lightweight cryptography — Part 2: Block ciphers.
[3] https://github.com/gooroom https://www.gooroom.kr/
[4] https://github.com/cryptolu/FELICS/tree/master/block_ciphers/source/ciphers/LEA_128_128_v01/source
[5] Hong, Deukjo, et al. "LEA: A 128-bit block cipher for fast encryption on common processors.", WISA 2013.
[6] https://seed.kisa.or.kr/kisa/algorithm/EgovLeaInfo.do
[7] https://en.wikipedia.org/wiki/LEA_(cipher)
[8] https://seed.kisa.or.kr/kisa/kcmvp/EgovVerification.do
[9] https://www.cryptopp.com/

Changelog:
v2:
- Reimplemented the Generic C implementation as a Loop version.
  - The decryption code was adapted from an optimized implementation by Eric Biggers.
    https://git.kernel.org/pub/scm/linux/kernel/git/ebiggers/linux.git/commit/?h=old/wip-lea&id=1d1cbba14380f8a1abc76baf939b9e51de047fb6
- Removed AVX2 SIMD implementation.
- Added comments for functions.
- Improved the description in Kconfig.
- Added test vectors from the standard documentation.

Comments

Herbert Xu June 1, 2023, 10:38 a.m. UTC | #1
Dongsoo Lee <letrhee@nsr.re.kr> wrote:
>
> We expect that the first application of the patch would be disk encryption on the Gooroom platform ('Gooroom' is a Korean word, meaning 'cloud') [3]. Currently, the Gooroom platform uses AES-XTS for disk encryption. The main reason for submitting this patch is to make disk encryption with LEA (e.g. LEA-XTS) available on there.

We don't add kernel algorithms without an in-kernel user.  Is
there an existing in-kernel user that can use this as is or are
you going to add one?

Thanks,
Eric Biggers June 2, 2023, 9:39 p.m. UTC | #2
On Fri, Jun 02, 2023 at 03:05:16PM +0900, Dongsoo Lee wrote:
> Additionally, we are exploring the possibility of using `blk-crypto` for
> encryption. Currently, the ciphers available for `blk-crypto` are
> AES-256-XTS, AES-128-CBC-ESSIV, Adiantum, and SM4-XTS. We would like to add
> LEA-256-XTS to these.
> 
> ( https://github.com/torvalds/linux/blob/master/block/blk-crypto.c#L21 )
> 
> Instead of disk encryption, it is also possible to use `fscrypt` to encrypt
> the file system for data-at-rest environments. `fscrypt` currently supports
> AES-256-XTS, AES-256-CTS-CBC, AES-128-CBC-ESSIV, AES-128-CTS-CBC, SM4-XTS,
> SM4-CTS-CBC, Adiantum, and AES-256-HCTR2.
> 
> ( https://github.com/torvalds/linux/blob/master/fs/crypto/keysetup.c#L16 )
> 

Currently the only user of blk-crypto is fscrypt.  So the above two paragraphs
are really talking about the same thing.

I haven't seen any patch that proposes adding LEA support to fscrypt.  Also, I'm
not sure that the information you've provided so far is sufficient motivation
for adding it to fscrypt.  I did recently allow another national pride cipher,
SM4, to be added to fscrypt, but that was only because a user said they were
being *required* to use SM4.  It's not clear that's the case for LEA.

- Eric
Dongsoo Lee June 9, 2023, 11:57 a.m. UTC | #3
On Fri, 2 Jun 2023 14:39:46 -0700, Eric Biggers wrote:
> I haven't seen any patch that proposes adding LEA support to fscrypt.
> Also, I'm
> not sure that the information you've provided so far is sufficient
> motivation
> for adding it to fscrypt.  I did recently allow another national pride
> cipher,
> SM4, to be added to fscrypt, but that was only because a user said they
> were
> being *required* to use SM4.  It's not clear that's the case for LEA.

Hello,

We thought that having the dm-crypt module as an in-kernel user of this
patch is enough to apply it. Of course, it would have been better to include
fscrypt in the patch, as file system encryption is very important for
data-at-rest encryption along with disk encryption.

Unfortunately, currently, vendors trying to supply Linux-based data-at-rest
encryption products by utilizing the dm-crypt or the fscrypt modules to
government agencies or public institutions in Korea are experiencing great
difficulties.

According to Korean regulations, the data transmitted and stored by
government agencies and public institutions must be protected using KCMVP
validated cryptographic modules. (KCMVP, the Korean Cryptographic Module
Validation Program, is a Korean security accreditation program for
cryptographic modules, like the CMVP in the United States.) According to the
KCMVP, cryptographic modules that are to be adopted in government agencies
and public institutions are required to use the approved cryptographic
algorithms to encrypt data. As mentioned earlier, LEA, SEED, and ARIA are
the only KCMVP-approved block ciphers.

As you know, the best approach to performing data-at-rest encryption on
Linux is using kernel modules like dm-crypt or fscrypt. Therefore, applying
the proposed patch would be very beneficial for the vendors wanting to
supply Linux products to government agencies or public institutions in
Korea, since they must use the KCMVP-approved cryptographic algorithms such
as LEA.

We kindly request a positive response to enable the utilization of
data-at-rest encryption in such special circumstances, thereby improving
Korea's Linux environment.

Thank you.
Eric Biggers June 10, 2023, 2:14 a.m. UTC | #4
On Fri, Jun 09, 2023 at 08:57:36PM +0900, Dongsoo Lee wrote:
> Unfortunately, currently, vendors trying to supply Linux-based data-at-rest
> encryption products by utilizing the dm-crypt or the fscrypt modules to
> government agencies or public institutions in Korea are experiencing great
> difficulties.

Why are they having "great difficulties" when the kernel already supports two
other "KCMVP-approved block ciphers", ARIA and SEED?  Why aren't they using
dm-crypt with ARIA or SEED?

> According to Korean regulations, the data transmitted and stored by
> government agencies and public institutions must be protected using KCMVP
> validated cryptographic modules.

And does LEA (or SEED or ARIA) support in Linux actually solve that problem?
Just adding support for these algorithms to Linux does not mean that Linux
automatically becomes a "KCMVP validated cryptographic module", right?  Do you
have a complete plan that would actually solve the claimed problem?

- Eric
Dongsoo Lee June 16, 2023, 8:08 a.m. UTC | #5
Hello.

On Fri, 9 Jun 2023 19:14:50 -0700, Eric Biggers wrote:
>Why are they having "great difficulties" when the kernel already supports
two other "KCMVP-approved block ciphers", ARIA and SEED?  Why aren't they
using dm-crypt with ARIA or SEED?

As you mentioned, the two KCMVP-approved block ciphers, ARIA and SEED, are
supported by the kernel. Therefore, we can use dm-crypt with ARIA or SEED.
However, LEA, being a relatively new algorithm, has distinct advantages over
ARIA and SEED. LEA shows better performance, provides a clearer structure,
and offers simpler implementation on SIMD, compared to ARIA and SEED.
(Furthermore, SEED only provides up to 128-bit security.) Consequently,
there are many products in Korea that use LEA as the default cipher.

Considering these advantages, vendors may add LEA to the kernel of the Linux
distribution by themselves to develop Linux products that supports LEA.
(Some vendors are known to have already attempted this. However, definitely
not all vendors have the capability to do so.) Furthermore, supporting the
most recent and efficient KCMVP-approved block cipher, LEA, may be very
helpful for the vendors to promote their products.

It would cause problems if each vendor implements LEA in the kernel on its
own. It may lead to fragmentation in kernel implementations, potentially
causing compatibility issues among vendors and posing challenges for system
maintenance when faced with major kernel changes.

In addition, the data-at-rest encryption market is just beginning to grow in
South Korea. Therefore, vendors may prefer to use LEA as the default cipher
for data-at-rest encryption, since it is the most recent and efficient one
of the KCMVP approved block ciphers (as mentioned earlier) and they do not
need to worry about the compatibility issues.

Lastly, although LEA-XTS may not outperform AES-XTS or Adiantum, it is still
worthwhile to add LEA to the kernel, as it can be implemented on various
platforms that support SIMD instructions, and it is also an ISO/IEC standard
lightweight cipher.

On Fri, 9 Jun 2023 19:14:50 -0700, Eric Biggers wrote:
>And does LEA (or SEED or ARIA) support in Linux actually solve that
problem?
>Just adding support for these algorithms to Linux does not mean that Linux
automatically becomes a "KCMVP validated cryptographic module", right? Do
you have a complete plan that would actually solve the claimed problem?

As you said, simply adding support for LEA in the kernel doesn't
automatically solve the problem. Of course, additional efforts are needed to
solve it.

As you may know, KCMVP validates cryptographic modules, which means that
when KCMVP validates a Linux-based cryptographic module, it validates the
entire module, not just the Linux kernel inside the module. To obtain
validation for a product, vendors need to develop various tools that can be
used for required testings and write down required documentations.

If LEA becomes available in the Linux kernel, we plan to implement
data-at-rest encryption using LEA on the previously mentioned Gooroom
platform. Vendors can then use it as a reference. We will also develop
backporting codes for several LTS kernels, enabling vendors to utilize LEA
in the Linux distribution that their product runs on. Additionally, we will
implement and provide the necessary tools for KCMVP validation. This series
of efforts, starting with adding LEA to the kernel, will assist vendors in
developing their own KCMVP-validated products, which means the problem can
be solved.

Thank you.