Implement Maximum-Quality Random Number Generation Using AES-XTS XEX-based Tweaked CodeBook with OpenSSL and AES-NI Support

Knogle commented 3 weeks ago

Ahoy, this pull request introduces the implementation of AES-256-XTS, kind of a improvement of AES-CTR (XEX-based Tweaked CodeBook mode with ciphertext Stealing) for secure encryption or in this case, wiping of block devices, combined with Blake2 for hashing. This solution is designed to enhance data security (for your wiped data) , and performance by writing 2x256-bit at once. The use of AES-XTS mode, in conjunction with the Blake2 hashing algorithm, provides a reliable and secure disk wipe. Also providing a massive speed increase by 49% compared to plain AES-CTR.

Key Features

AES-XTS Mode with Ciphertext Stealing (CTS): AES-XTS is suitable for wiping storage devices in our case. The use of ciphertext stealing allows AES-XTS to handle data blocks that are not a multiple of the block size, which is a common scenario in a lot of block devices. This makes AES-XTS more secure and versatile compared to AES-CTR, as it ensures all data is wiped without security concerns or leftovers. Instead of 256b we write 512b, 2x 256b keys.
Blake2 Hashing Integration: Blake2 is used for hashing the entropy and ensuring reverse-proof data streams.
Hardware Acceleration with AES-NI: The use of AES-NI (Advanced Encryption Standard New Instructions) Allows maximum performance.

Advantages of AES-256-XTS with Ciphertext Stealing over AES-CTR

Handling of Non-Multiple Block Sizes: Ciphertext stealing allows AES-XTS to wipe data blocks of varying sizes without needing padding, unlike AES-CTR, which typically requires the data to be a multiple of the block size. This capability ensures complete encryption of all blocks, including the last partial block, enhancing security and efficiency.
Improved Security Against Predictable Patterns: The combination of AES and the XTS mode ensures that each block is uniquely encrypted, even if the same data is present in multiple locations. This prevents patterns that could be exploited in attacks, which is a potential vulnerability in modes like AES-CTR.

Implementation Details

Initialization: The AES-256-XTS mode is initialized using a 256-bit key. A unique tweak value, derived from the data block’s address and processed via the Blake2 hash, ensures each block is encrypted differently.
Blake2 Hashing: Blake2 is used to hash the metadata and tweak values, providing a fast and secure hashing mechanism. This step ensures data integrity and checks for tampering before wiping.
**TODO: I will add an ECDH algorithm there soon.
Ciphertext Stealing: AES-XTS mode employs ciphertext stealing to handle blocks that are not a multiple of the encryption block size. This technique ensures all data is wiped securely without adding padding, thereby maintaining data consistency and reducing processing overhead.
Integration with OpenSSL: Utilizing OpenSSL for cryptographic operations guarantees reliability and leverages established libraries. Less overhead in nwipe. The integration with OpenSSL also facilitates the use of hardware acceleration through AES-NI.

Testing and Validation

Randomness Tests: Extensive randomness testing has been conducted using the NIST test suite, confirming the high quality of random number generation, essential for secure disk wipe.
Performance Benchmarks: Benchmark tests demonstrate that AES-256-XTS, optimized with AES-NI, outperforms software-only wiping methods, making it suitable for deployment in high-demand environments.

Conclusion

This implementation of AES-256-XTS with Blake2 hashing offers a comprehensive solution for secure block device wiping, addressing limitations found in other wiping modes like AES-CTR. By incorporating ciphertext stealing and leveraging hardware acceleration, this implementation provides a balance of security, integrity, and performance, making it ideal for modern data storage and protection needs.

I look forward to feedback and collaboration to further improve this implementation.

NIST Suite Test

A total of 188 tests (some of the 15 tests actually consist of multiple sub-tests)
were conducted to evaluate the randomness of 32 bitstreams of 1048576 bits from:

    /dev/loop0

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

The numerous empirical results of these tests were then interpreted with
an examination of the proportion of sequences that pass a statistical test
(proportion analysis) and the distribution of p-values to check for uniformity
(uniformity analysis). The results were the following:

    188/188 tests passed successfully both the analyses.
    0/188 tests did not pass successfully both the analyses.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Here are the results of the single tests:

 - The "Frequency" test passed both the analyses.

 - The "Block Frequency" test passed both the analyses.

 - The "Cumulative Sums" (forward) test passed both the analyses.
   The "Cumulative Sums" (backward) test passed both the analyses.

 - The "Runs" test passed both the analyses.

 - The "Longest Run of Ones" test passed both the analyses.

 - The "Binary Matrix Rank" test passed both the analyses.

 - The "Discrete Fourier Transform" test passed both the analyses.

 - 148/148 of the "Non-overlapping Template Matching" tests passed both the analyses.

 - The "Overlapping Template Matching" test passed both the analyses.

 - The "Maurer's Universal Statistical" test passed both the analyses.

 - The "Approximate Entropy" test passed both the analyses.

 - 8/8 of the "Random Excursions" tests passed both the analyses.

 - 18/18 of the "Random Excursions Variant" tests passed both the analyses.

 - The "Serial" (first) test passed both the analyses.
   The "Serial" (second) test passed both the analyses.

 - The "Linear Complexity" test passed both the analyses.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

The missing tests (if any) were whether disabled manually by the user or disabled
at run time due to input size requirements not satisfied by this run.

Screenshot from 2024-08-23 21-58-26

PartialVolume commented 3 weeks ago

Nice, I'll review as soon as I can with view to merging along with aes-ctr.

Just out of interest what's the binary size of nwipe with each of these two branches?

Knogle commented 3 weeks ago

Alright :)

In case of aes-ctr

964K src/nwipe

And aes-xtr

980K ../nwipe-aes-xtr/src/nwipe

And the current master branch.

956K src/nwipe

Offtopic, but i am currently having an issue on my Fedora machine. /dev/urandom giving trash entropy on all algorithms, on other machines fine. Also when dd'ing directly from /dev/urandom the entropy fails all tests. Due to this issue, independent of those algorithms, i'd like to implement a proper procedure to ensure proper entropy and give some error in case of failure. Even though it's not a cryptography focused program nwipe, but i think leverage OpenSSL algorithms to ensure proper entropy and verify it for any PRNG in use.

PartialVolume commented 3 weeks ago

Alright :)

In case of aes-ctr

964K src/nwipe

And aes-xtr

980K ../nwipe-aes-xtr/src/nwipe

Offtopic, but i am currently having an issue on my Fedora machine. /dev/urandom giving trash entropy on all algorithms, on other machines fine. Also when dd'ing directly from /dev/urandom the entropy fails all tests. Due to this issue, independent of those algorithms, i'd like to implement a proper procedure to ensure proper entropy and give some error in case of failure. Even though it's not a cryptography focused program nwipe, but i think leverage OpenSSL algorithms to ensure proper entropy and verify it for any PRNG in use.

Re sizes, that's good.

Re entropy of urandom, yes go ahead and implement that. Maybe also notify the Fedora guys if it looks like it's Fedora specific. What over distros are you using that it works fine on or have you only tested the entropy of urandom on Fedora?

Knogle commented 3 weeks ago

Yeah i will continue with the implementation. Imo it may be something critical, also for data wiping, but also for Fedora. So i will go for bugzilla and report this issue. Here, the same nwipe on Ubuntu 1st. and then on my Fedora machine.

chairman@compile-ubuntu:/tmp/sts$ cat result.txt 
A total of 188 tests (some of the 15 tests actually consist of multiple sub-tests)
were conducted to evaluate the randomness of 32 bitstreams of 1048576 bits from:

    /dev/loop0

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

The numerous empirical results of these tests were then interpreted with
an examination of the proportion of sequences that pass a statistical test
(proportion analysis) and the distribution of p-values to check for uniformity
(uniformity analysis). The results were the following:

    188/188 tests passed successfully both the analyses.
    0/188 tests did not pass successfully both the analyses.

chairman  /  tmp  cat sts/result.txt 
A total of 188 tests (some of the 15 tests actually consist of multiple sub-tests)
were conducted to evaluate the randomness of 32 bitstreams of 1048576 bits from:

    /dev/loop0

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

The numerous empirical results of these tests were then interpreted with
an examination of the proportion of sequences that pass a statistical test
(proportion analysis) and the distribution of p-values to check for uniformity
(uniformity analysis). The results were the following:

    0/188 tests passed successfully both the analyses.
    188/188 tests did not pass successfully both the analyses.

martijnvanbrummelen / nwipe