post-quantum cryptography - PQC

Development
41
42
43

I’m seeing a lot of misconceptions about QC in here, so I want to clear things up below. If you want to see my replys to the programs listed in the comments, scroll down furhter.

I feel like if Whonix wants to use PQC, then it would mean that the user would have to make everyone they are communicating with to agree on using a specific PQC-resistant cipher/signature program. With most people using RSA and ECC, this would be hard but not impossible to achieve. This would mean that people would have to manually crunch the numbers regarding the validity of your signature unless Whonix has an in-built GUI for PQC applications.

As far as I’m aware from my knowledge in Theoretical Computer Science, the integer factorization problem (RSA) and finding the value “p” in an eliptic curve (discrete log) (ECC) are NP-intermediate and co-NP respectively. It is currently debated on whether discrete log is NP-hard or not.

For the laymen here, this means that a classic computer has to brute-force or can only find the answer in an exponential function, that is that the time it takes for a computer to find the answer increases exponentially with the amount of possible answers.

In contrast, a very smart man from MIT (Peter Shor) figured out that quantum computers can do this process is “poly-logarithmic time” which says that the time it takes for a quantum computer to factor a number is equal to the logarithm of the amount of possible answers.

While this is scary, the caveat is that a quantum computer needs no noise or decoherence to be as effective as it can. Literally and figuratively breathing on a qubit or even the room being too hot that completely disrupt the superposition.

I’d say that the amount of scientists who say that QC is a fad compared to those who are genuinely worried is a 50/50. We just don’t know when quantum computers can finally have their true power revealed as they have so many obstacles to go through.

Currently, the biggest number factored only with a quantum computer that ran more than mere milliseconds was 21, and the biggest factored with a hybrid quantum-classical system was 261, 980, 999, 226, 226, with the calculation being 15538213 x 16860433 was done with 10 qubits and was only RSA-40 bits.

We are far from the Whonix project having to consider this so early in development, but I think that these first baby steps are fine, but developing a GUI/CLI tool equivalent to GnuPG/libgcrypt or gpa is absurd.

@Patrick if you absolutely need help with cryptographically approved methods, then I recommend crystals-kyber as it is NIST approved. NTRUEncrypt also seems fairly nice. Both of these have no known efficient polynomial (easy to solve and answer) problems on both classical computers and QC.

The articles you listed on PQC are very interesting, and I somewhat agree with Linus when he says that QC’s may not exist. I personally think that while QC’s will exist, they will always have noise that will make breaking RSA and ECC hard as their bit sizes go up. I expect in 20-30 years we will probably have the key sizes of today be broken.

Even with me saying that I find making PQC solutions for Whonix absurd I’m considering working on making a GUI/CLI tool for this in Whonix as I want to volunteer for a project that I love, but I have no idea where to propose one once the code is written. Any ideas?

44

Please consider maintaining this as an independent upstream project.

Making it specific to Whonix would only limit peer review, security and this is essential for such an application.

Please ask more people.

That depends… A new algorithm or implementation of existing algorithm into an app usable by users?

Also does it need to be a new application or would it be worthwhile to contribute to lets say GnuPG, Sequoia-PGP, signify, OTR, fork codecrypt, or other existing protocols / messengers?

45

While ago I’ve read that kicksecure wanted to use codecrypt signatures for extra security [unable to find source for that] and recently I got inspired by rhash[1] for a slight proposal, let’s call it paranoid-sign for now.

paranoid-sign would be simple cli program that would utilize the following libraries to produce recursive digest files that are recursively signed with multiple algorithms, as provided by stated libraries.

So the result would be keys and signatures with higher disk / bandwidth cost, with the pro of defense in depth benefit.

Such approach is perfect for high security requirements, only project that I am aware of that stacks algorithms for maximum integrity is rhash[1] (and codecrypt partially).

Since all critical functions would be offloaded onto external libraries, it would be very low line count program making it easy to audit it. The only problem being - is another program needed?

How many people / projects would benefit from paranoid-sign? Is it better to urge projects like GnuPG (which should eventually get PQC support) to add something like --paranoid mode keys and signing or make program just for this purpose to get this functionality early?

I am aware that this may be slightly off-topic to Whonix, I am bringing this idea up because codecrypt signatures were meant to be used for kicksecure and Whonix.

Has anything ever come out of this?

[1] https://github.com/rhash/RHash

46

I wouldn’t call it paranoid as this implies a mental issue but PQC is very much accepted as potentially becoming an issue.

related: use codecrypt to sign Whonix releases

The assumption here is that if signed by multiple algorithms, that makes it quantum-resistant? While that is conceivable, I don’t know if that is true. Therefore this assumption could use (a few) reference(s).

If that was true, all that would be needed would be a wrapper script around openssl and maybe other existing hashsum creation tools? That would be nice but also somehow sounds too simple to be true. In that case, auditing would be trivial as the algorithms are implemented by already trusted, existing tools.

I don’t think campaigning them would speed up things. gpg could not even be convinced to use the most secure default security settings among other things. Maybe that is why there is now Sequoia-PGP (gpg replacement) - OpenPGP - Development - Kicksecure Forums which seems to have the intention to re-implement things in a better designed way.

Only contributing code the way they want it or forking/new source code would work.

Also consider checking PQC plans for sequoia and contributing to sequoia.

1 Like
47

I used the word paranoid because I was inspired by Qubes OS[1] which has --paranoid-mode argument for qvm-backup-restore.

In the case of Qubes OS it implies distrust of backup integrity, in the case of paranoid-sign it would imply distrust in using single algorithm, ex. sha+rsa.

I will use the word hardened from now on to reduce confusion and stay more consistent with Whonix / kicksecure themes.

It would be quantum resistant, because it would use quantum resistant algorithms. It would just use all which are provided by liboqs[2].

Multiple algorithms would be chosen for signing because if only one was selected, it could be weaker than thought[3][4] and undermine security. With multiple algorithms, weakness in only one is less relevant for an attacker who wants to forge signatures or similiar.

For hashes - multiple algorithms are also used, in this case its used to mitigate any possible collision attack, ex. attacker has reliable sha256 0 day where it is possible to inject malicious code / binary without the checksum changing.

This is also the strategy which Signal[5] uses, although for encryption and not signing - it is still same base idea.

We believe that the key encapsulation mechanism we have selected, CRYSTALS-Kyber, is built on solid foundations, but to be safe we do not want to simply replace our existing elliptic curve cryptography foundations with a post-quantum public key cryptosystem. Instead, we are augmenting our existing cryptosystems such that an attacker must break both systems in order to compute the keys protecting people’s communications.

Distros such as Gentoo[6] are using multiple hashes, in their case its for package integrity.

Hash types
The hashes currently supported by Portage include:
MD5
SHA1
SHA256 (SHA-2)
SHA512 (SHA-2)
SHA256 (SHA-3)
SHA512 (SHA-3)
RMD160 (RIPEMD) (strongly discouraged)
BLAKE2S
BLAKE2B
WHIRLPOOL (strongly discouraged)

Which is very similar list to openssl dgst -list output.

This is absolutely correct. Bash script as openssl wrapper is possible, not for liboqs as that is C library, so this could be split into 2 programs - hardened-sign and hardened-sum.

  • hardened-sign would be simple C program that would invoke hardened-sum and sign the output with all available liboqs signing algorithms.
    • Additionally generate keys and output them to public / private files, this function is already present in liboqs, with only file handling missing - which is very simple to implement anyways.
    • Include timestamp and other metadata maybe.
  • hardened-sum would be extremely simple bash script for wrapping openssl (as you described) to generate checksums, to be used by hardened-sign and for casual integrity checking unrelated to signatures.

I’ve made proof of concept hardened-sum to further compliment this idea.

Prototype for hardened-sum 
#!/bin/bash

# TODO: maybe shellcheck
# TODO: maybe gnu parallel

# parse output of `openssl dgst -list`
# and convert it into array of `openssl` arguments,
# which can be used for generating list of digests with different algorithms
function parse_supported()
{
	local list_header="Supported digests: "
	algorithm_list=$(openssl dgst -list	\
		| tr -s " "			\
		| tr -d "\\n"			\
		| cut -c ${#list_header}-)

	IFS=" " read -ra algorithm_array <<< $algorithm_list
}

function hardened_sum()
{
	for algorithm_name in ${algorithm_array[@]}
	do
		# cut first character of every algorithm name which is '-', due to openssl expecting
		# `openssl sha256 ...` - and not
		# `openssl -sha256 ...`
		local cut_name=$(echo $algorithm_name | cut -c 2-)

		# some algorithms such as md4 output an error, remove `2>/dev/null` for err output
		# https://github.com/openssl/openssl/issues/21247
		# forced to use `default` provider - see `openssl list -providers` output
		local check_sum=$(openssl $cut_name $1 2>/dev/null)
		if [[ -n $check_sum ]]; then
			echo $check_sum
		fi
	done
}

parse_supported
hardened_sum $1

With the example usage of
echo "match" > example-file
hardened-sum example-file > example-file.sum
hardened-sum example-file > example-file.sum2
diff -s example-file.sum example-file.sum2

Files example-file.sum and example-file.sum2 are identical

echo "no match" > example-file
hardened-sum example-file > example-file.sum2
diff -q example-file.sum example-file.sum2

Files example-file.sum and example-file.sum2 differ

Example hardened-sum output

BLAKE2B-512(example-file)= ebf8449995381306bb75e8148e8a50cd3d0355eb1c5f202467726750f5099979af06278397495849b166df7a9499a6be0fb8f03f9fb10dabd86192f904663cfd
BLAKE2S-256(example-file)= ecb405ea5aea66e29579854c8b0554458da8a965640054c70e9142bc8777015f
MD5(example-file)= 93e160c18b18022eb6f54aa9b38f464d
MD5-SHA1(example-file)= 93e160c18b18022eb6f54aa9b38f464daae00a793cba151c1d6d009855187402cd30731d
RIPEMD-160(example-file)= 6687fc01c08e80eefa46906e5ac145d6dd43e772
RIPEMD-160(example-file)= 6687fc01c08e80eefa46906e5ac145d6dd43e772
RIPEMD-160(example-file)= 6687fc01c08e80eefa46906e5ac145d6dd43e772
SHA1(example-file)= aae00a793cba151c1d6d009855187402cd30731d
SHA2-224(example-file)= 5a75fcad70f3a9db52cfe0b8b545c09f2c10cd6bca89a0ba7dc8f6bb
SHA2-256(example-file)= a3010e49f491e79357181823002f73df0158eff1921ac1e64726a5e9ecabcbb1
SHA3-224(example-file)= b6ce4230eb37f77759e0ea366aeff9a2043ba7bb9059c3d297162280
SHA3-256(example-file)= 00e3a0e68452a0ae0102c46f5160b9a2359c4f07850bd9e4c777ac6e91c58e26
SHA3-384(example-file)= 9d1e1898969be4815448b1da18ff93b8cd74d32e779e3c3afd69ffd5b7627b514456021f080ad4d6e491b8a62d9b8f9e
SHA3-512(example-file)= 8d9140e61ab7c2f9cc861c4711e1051439fe0dee0a0bb7317b0a0af459ec2412c811dbaf23d7c1ad3620ae96442e950b7ddba347ee1c9b61f230c805c898fd05
SHA2-384(example-file)= 3419af7e0290b459a4126371aced775aa345aa9e93c9061ea330c8812112f36655ab620806fe0590982901bf22cb3c17
SHA2-512(example-file)= 794f3ac5802068c6545c057a05afc52b5f5a0d196477dcc215cf05dac9ac314d598cfe36eed5250d4072c805e642e9dcb725d88bafbb957adcbf48760f69ff1d
SHA2-512/224(example-file)= 22c20611e910599711e024aeaaa8a9e4e64cd374053e40dc7570e56a
SHA2-512/256(example-file)= 0df0004b812f4778f27cc21922626288d1bd924ed0ecabe854706f404d5db4a3
SHAKE-128(example-file)= 5af0950fdb04049d4366c3207f034ff7
SHAKE-256(example-file)= d45ddf62a1a418cd1ef8754dda6ca5f5db1b2643f54c8dcbbe5b30f3550a366b
SM3(example-file)= 951f91d3c07a86509c4ed4416b8bea47cad2e7e350e25d8e45064b28480520c5
MD5(example-file)= 93e160c18b18022eb6f54aa9b38f464d
SHA1(example-file)= aae00a793cba151c1d6d009855187402cd30731d

These programs could be used on top of GnuPG for additional security, ex. users who want to make 100% sure they aren’t being targeted by any forgery.

(By that I mean signing GnuPG signature with hardened-sign.) - to not force everyone to use some random program (random is arguable as it would be using completely public libraries so anyone could manually check signature/sum output even without hardened-sign and hardened-sum being present.)

  • Ignore signature - no integrity.
  • Verify GnuPG - integrity against classic computing attacks (debatable), but no assured integrity against quantum computing attacks…
  • Verify hardened-sign - integrity against quantum computing attacks, but no assured integrity against classic computing attacks.
  • Verify both - integrity against both.

Integrity here means that verifiability that data came from expected person, attacks mean discoverability of private key for future impersonation / man in the middle… etc.

Benefits of hardened-sign approach over something like codecrypt are seamless introduction of security fixes & new algorithms.

So to me seems like I should implement hardened-sign and hardened-sum and upload the source publicly ex. on github, then propose their hardened functionality to be included in GnuPG, its forks and other projects for security benefit.

[1] https://dev.qubes-os.org/projects/core-admin-client/en/stable/manpages/qvm-backup-restore.html
[2] https://github.com/open-quantum-safe/liboqs
[3] https://blog.cr.yp.to/20231125-kyber.html
[4] https://blog.cr.yp.to/20240102-hybrid.html
[5] https://signal.org/blog/pqxdh/
[6] https://wiki.gentoo.org/wiki/Repository_format/package/Manifest

1 Like
48

Any non-C library? Rust? Python? Any other ways to avoid C?

I wouldn’t worry about GnuPG. It will always be possible to sign with multiple tools at once. Well, obviously just don’t use file extensions that are already taken by others such as .asc, .sig, .gpg.

I wouldn’t worry much about GnuPG compatibility. I’d suggest to think big and design this as a tool that can be used to replace GnuPG. Similar how signify was implemented. Legacy free.

But then the digest files might require version numbers because how else at a later time the program would now to insist on which algorithms to verify.

I don’t think this is how GnuPG development works. That has an almost zero percent chance of working. Check this out, dunno about it:

If you want to land patches in GnuPG or others you need to discuss this with them beforehand. Otherwise might hit a blocker.

Sequoia isn’t a a fork of gpg. It’s a rewrite from scratch in Rust. It implements the OpenPGP standard.

Both, GnuPG and Sequoia might be adamant about standardization.

1 Like
49

https://github.com/open-quantum-safe/liboqs-go
https://github.com/open-quantum-safe/liboqs-python
https://github.com/open-quantum-safe/liboqs-cpp
https://github.com/open-quantum-safe/liboqs-rust

Library backend code still remains in C, but the projects listed above allow you to call the functions from different languages.

Sure.

Maybe and same can be said about hardened-sign automatically adding signature algorithms, hardened-sum could have additional output such as:

7/10 checksums verified successfuly
1 CHECKSUM FAILED THIS IS BAD OBVIOUS COMPROMISE (can’t think of anything better on the fly)
1 unknown hashing algorithm - imaginary-algorithm512
1 algorithm not present in digests file - madeup-algorithm512

Similar output could exist for hardened-sign. There are still other issues (mainly key files for signing) with this idea and possibly error prone, so for the sake of stability there could be static list of algorithms that are today considered safe and just use those, hardened-sum could retain --dynamic argument for standalone digests - not intended for signing.

Post-quantum algorithms seem to be chosen already and I don’t know the last time new hashing algorithm was added to openssl so maybe dynamic idea may be obsolete.

Overall currently needs more thinking.

2 Likes
50

An attacker coild remove a signature from the digest file. How you’d notice that? I think you cannot. Therefore hardcode all algorithms being mandator and required matching.

2 Likes
51

Good catch, there are some solutions to noticing it, obviously simply hardcoded list is best.

Include list of used signing algorithms in digest files (similarly formatted as hashing algorithms) then program output could be altered to warn about missing signatures.

Alternatively some kind of self protecting signatures approach could be used ex.:
[ algorithm-2_sign(algorithm-1_signature) algorithm-1_sign(algorithm-2_signature) ]
or done in recursive way:
algorithm-2_sign(algorithm-1_sign(digests_file))

  • These aren’t better than hardcoded list, would still require knowledge of used algorithms but as suggested could be included in digests file. Just throwing ideas out there.

Additional notes:

liboqs is currently not present in aptitude:
apt search liboqs

Sorting… Done
Full Text Search… Done

This means currently the binary would need to have liboqs statically linked, meaning no automatic updates. Although oqs provides an openssl provider:
https://github.com/open-quantum-safe/oqs-provider/
https://www.openssl.org/docs/manmaster/man7/provider.html

About “dynamic” approach:
I believe this would be perfect solution for long term use, currently has some obstacles. It would remove the need to switch programs to get latest gen crypto software (in this case gpg → codecrypt → whatever comes next) in future, so I want to get the idea out there.

Let’s say openssl would export list of algorithms.
(I have not investigated openssl as lib, I don’t know if it provides what I’m describing. Needs investigation, take everything below as pure idea material.)

Pseudo C, everything here is made up:

struct signing_algorithm
{
    char* algorithm_name; // ex.: "p521_dilithium5"
    size_t crypto_gen; // ex.: 1 - classic, 2 - pqc, 3 - whatever would be beyond post quantum
    func_def function_pointer;  // reference to function export
    size_t extra_data; // anything missed/ specific to this algorithm only

    size_t private_size, public_size, signature_size; // expected function output sizes
};

// everything that this library provides, exported.
signing_algorithm signing_algorithms[] = {
   ...
};

// exported, to be used for iterating `signing_algorithms`.
size_t signing_algorithms_size = ARRAYSIZE(signing_algorithms);

Same would be present for hashing algorithms as alternative way to implement hardend-sum to avoid parsing openssl dgst -list in bash.

If this was in place in some library like openssl, there would be minimal user interaction to adding new algorithms. If openssl updated via package manager every new algorithm would be automatically built into hardened-sign, hardened-sum.

  • signing keys would have to be added, maybe --update-keys that parses specified private key and generates more keys for algorithms that were missing and outputs new public key blob.
    • This means old signatures could be updated without losing compatibility, old signatures could be verified with new algorithms present (with a warning about old signature), users could verify files signed with new private key even if they don’t have new public key blob (they would be warned about outdated key / missing algorithms).
  • ???

Sorry if this post is less coherent, instead of filling this thread up with semi unrelated information I will think about writing a spec for this, perhaps called something like “self maintaining signature software” - unless someone can point out flaw about this approach, then I may just stick to good old

52

Often it is not but in this case it’s easy to be opinionated.

I don’t think any application should interface with the package manager to find out what algorithm are supported. That would be highly unusual. It is however common to require a specific minimum dependency version, check that and refuse operation when it is missing.

Also supported Debian version: stable would be nice. That however means, if a signature is created on Debian testing which in theory has newer dependency versions, it shouldn’t generate signatures when running on Debian testing which are considered insecure on Debian stable.

If the dependency (openssl) supports the same algorithms on every common, sane Linux distributions and if these are usually append only (none are removed in later releases) then could dynamically parse them. But you probably still need version numbers in the signature. Or perhaps as part of the file extension (might be less ideal). Because this should be somewhat distribution portable.

I wouldn’t bother with classic or legacy. The fewer settings, the better. Just use secure defaults. And if a newer version is needed, use more secure defaults. The more different ways users can use to create different types of signatures, the more difficult it gets to parse them (in future versions).

Also you don’t want your tool to get a bad reputation. When hardened-sum generate a checksum, it’s best if users undoubtedly know its (reputation) for its great superior properties. Avoid coming up the discussion “but some people use it to create PQC insecure signatures”, “it depends”.

It might also make sense to discuss this on some related mailing list where cryptography knowledgeable people might be available. Bitcoin was posted on the metzdowd cryptography mailing list? So that might be suitable. Because this stuff is not something I would be comfortable developing. Kicksecure, Whonix is development on a very different level, a very different type of work.

1 Like