What is Standard Referencing of Cryptography Papers I am writing a paper. One of my references is

  1)Barreto, P. and Rijmen, V., “The Khazad Legacy-Level Block Cipher,” Submission
     to the NESSIE Project, vol. 97, 2004.

My professor criticize me that why I wrote submission to the NESSIE Project or why you did not write the journal of this paper or did not wrote the number of pages of this paper. What is its conference and where did it hold?

I searched in internet but most of all papers write this reference like $(1)$.

I am really confused and need help to write this kind of cryptography papers.

Really Thanks for any suggestions.

I failed to find what the "vol. 97, 2004" part of the question's citation refers to, or a formal journal or proceedings publication for that paper. It is much earlier (made public in November 2000).

The first author cites his paper (at line 38 in the conference paper section here) as:

  BARRETO, P. S. L. M.;  Rijmen, V.; 2000: The KHAZAD Legacy-Level Block Cipher. In: 1st Open NESSIE Workshop, 2000, Leuven (Belgium). Proceedings of the 1st Open NESSIE Workshop.

The second author cites his paper (at line 235 here) as:

  P. S. Barreto, and V. Rijmen, "The Khazad legacy-level block cipher," In Proceedings of the 1st NESSIE Workshop, 15 pages, 2000.

It also has been cited as

  P. Barreto and V. Rijmen. The Khazad Legacy-Level Block Cipher. In
  First Open NESSIE Workshop, KU-Leuven, 2000. Submission to NESSIE.

If I had to cite this paper on this website, it could be as:

  Paulo S.L.M. Barreto and Vincent Rijmen, The KHAZAD Legacy-Level Block Cipher, submission to First Open NESSIE Workshop, 13-14 November 2000, Leuven, Belgium; file khazad/B/Khazad.pdf in khazad.zip.

The closest I found to 2004 is that Paulo Barreto cites (in the Other publications section here) a different, shorter paper,

  V. Rijmen, BARRETO,  P. S. L. M., “The Khazad Block Cipher,”, The Perl Journal 7, p. 5, 2003.

It is online here and was apparently an insert in this.

Addition: if there was ever formal Proceedings of the 1st Open NESSIE Workshop, its current web presence is this. Here are the remains of a Nessie Book planned circa 2004.


Potential Service Life of ChaCha20? I have some very sensitive family files that I want to store in the cloud on multiple providers for maximal reliability and redundancy. It's essentially a large archive of all our family photos, documents, and confidential photos. I'll be needing them in about ~20 years, but I won't access them or update them during this interval. These files must not be accessed by anyone but myself.
I am skeptical about AES being able to last for that long, because there could be advances in cryptanalysis. Instead, I'm considering ChaCha20, because it's a modern cipher and was sought for by security engineers at Google.
Supposing that I encrypt all files offline, use a secure key (along with Argon2), and ensure integrity (Poly1305), will my data theoretically be able to last for that long (the best attacks on ChaCha20 only break 7 rounds)? If not, is there a possible cipher that could? There will only be one copy, preventing chosen-plaintext attacks.

There's simply no way to know. I find it very unlikely that AES will be vulnerable to a ciphertext-only attack in the next 20 years (remember, it has been around for over 20 years already and attacks haven't gotten very far). There's no reason to believe the same won't be true for ChaCha20. If you use a good cipher with 256-bit keys (to avoid potential speedups from quantum computers running Grover's algorithm which halves the effective key size of a symmetric cipher), you should be fine.
If you really, really want, you could use something like VeraCrypt which provides you with the option to use three ciphers in a row: AES, Serpent, and Twofish, all of which are extremely secure.
We can say with some level of confidence that it will remain secure for your purposes.


Why is the state of an LFSR not output? According to Wikipedia LFSRs are used as PRGs but due to their linearity they are easy to cryptanalyze. Also, using Berlekamp-Massey consecutive output bits allow reconstruction of the internal LFSR state (I think the rule was something like $2n$ bits for state size $n$).

Now my question is a much more profane one. Given the following diagram for how an LFSR works doesn't it simply output its state and, therefore become trivially predictable?

LFSRs are very useful as building blocks of ciphers, with some nonlinearity introduced. For example Trivium is a very strong and fast cipher, which includes a little amount of quadratic nonlinearity in 3 coupled LFSRs.

An example of bad use of LFSRs--and by no means the only one--is the A5 series of ciphers, of GSM fame, where majority clocking does not include enough nonlinearity/unpredictability.


What is the difference between forward secrecy and key freshness? Is all random private key that generating a unique session key is both forward secrecy and key freshness?

The term ‘perfect forward secrecy’ is bad.  Rather than talking about whether a protocol has perfect forward secrecy, you should talk about when in the protocol you erase keys.  Then, although ‘key freshness’ isn't a common technical term in cryptography, this suggests a clear answer:

Key freshness is presumably about when you generate new keys so that future interactions can't be broken even if the old keys are compromised.
Key erasure is when you erase old keys so that past interactions can't be broken even if your current memory is compromised.


Randomly initialised global counter used to encrypt the kth message with $\operatorname{IV} = \operatorname{IV} + k \hspace{5mm} mod \hspace{5mm} 2^n$ The use of an increasing IV is not secure for a block cipher. That is, using a random IV for the first message then $\operatorname{IV} + 1$ for the second , $\operatorname{IV}+ 2$ for the 3rd etc. How can I construct an attack to show that this mode is not secure?

A block cipher, per se, does not have a notion of initialization vector.  But a randomized or stateful message cipher may.  If you're building an application, you should forget the concept of ‘block cipher’ altogether: the fact that some cryptographic magic is built out of a pseudorandom permutation family whose name is spelled A-E-S is not important to you; the security contract of the result, including your obligations and the security you get in exchange, is what's important.

For a randomized cipher like AES-CBC, your obligation in the security contract is to choose an IV unpredictably.

If, given the first message's IV, the adversary can guess the second message's IV, the security contract is voided.  This mistake was exploited to recover plaintext in ssh sessions in 2009[1] (paywall-free).
For a stateful cipher like AES-CTR, your obligation in the security contract is typically to choose a nonce uniquely, which you can do by counting.  (The ‘nonce’, for number used once, is sometimes called an ‘IV’, but some authors—like this one—prefer to reserve the term ‘IV’ for unpredictable ones.)

It does not matter if the adversary can predict the nonce in advance, as long as the sender never repeats a nonce.  As a bonus, you can immediately detect buggy implementations by having the receiver require the nonces to be sequential.

One can always safely use state to choose the IV for a randomized cipher, by deriving it by a pseudorandom function of the number of messages so far; and one can choose a nonce randomly for a stateful cipher, but at risk of nonce collision, so it's not so safe.

All this said, you should really use an authenticated message cipher.  Even if an adversary can't read secrets in an encrypted message by eavesdropping, without authentication you might act on adversary-controlled input which causes secrets to leak.  Examples of authenticated ciphers include:

AES-GCM, with a message sequence number for the 96-bit nonce;
NaCl crypto_secretbox_xsalsa20poly1305, with a message sequence number or uniform random nonce, since the 192-bit nonce is large enough to be safely chosen uniformly at random; or,
if you must use AES-CBC, at least use it in encrypt-then-MAC composition with HMAC-SHA256 or similar, and the sender must choose the IV unpredictably for each message.


Is it better to maximize memory usage or number of passes with Argon2i 1.3? I wrote a small application that uses Argon2i for deriving symmetric  keys for encryption of local files and secret Curve25519 keys. Argon2i v1.3 is susceptible to TMTO attacks if the number of passes is below 10, according to the most recent paper  I could find: https://eprint.iacr.org/2016/759.pdf

Ideally, of course, I would increase both. However, I am trying to find parameters that maximize security on a variety of machines, some of which are limited by CPU much more so than by RAM, such as old laptops. Let's say  I am aiming for a computation time of around 10 seconds. I can use much more RAM if the number of passes is 3, which is the minimum recommended for Argon2i. However, this appears to allow a TMTO attack that reduces that RAM usage according to the paper above. If  I increase the number of passes to > 10, I must use much less RAM to achieve the same computation time, however, the TMTO attack above does not apply.

On fast CPUs, increasing the number of passes is not a big problem because I can still use a lot of RAM. On slow CPUs, it can be much more significant. As a practical example, I tried this on a T23 ThinkPad. The results are below.

Tcost=3 Mcost=128 MiB Parallelism=1
Computation time: 10 seconds

Tcost=11 Mcost=40 MiB Parallelism=1
Computation time: 10 seconds

Given the most recent TMTO attacks in the Alwen-Blocki paper above, does an attacker with a GPU gain more of an advantage attacking the first example or the second? What about an ASIC?

For reference, here's Argon2d with only 1 pass and a target of 10 seconds

Tcost=1 Mcost=448 MiB Parallelism=1
Computation time: 10 seconds

(I am strongly considering going to Argon2d)

As of October 2017, the resource I've found most useful for getting a quick, practical sense of how pick parameters for Argon2 is the (still draft) RFC, in particular section 9, which gives this guidance (in 9.2):

The best attacks on the 1-pass and 2-pass Argon2i is the low-storage attack described in [CBS16], which reduces the time-area product (using the peak memory value) by the factor of 5.  The best attack on 3-pass and more Argon2i is [AB16] with reduction factor being a function of memory size and the number of passes. For 1 gibibyte of memory: 3 for 3 passes, 2.5 for 4 passes, 2 for 6 passes. The reduction factor grows by about 0.5 with every doubling the memory size. To completely prevent time-space tradeoffs from [AB16], the number of passes must exceed binary logarithm of memory minus 26.

Since $\log_2(128\ \mathrm{MiB}) = 27$, this actually suggests that you should be able to use $t = 3$, $m = 128\ \mathrm{MiB}$ as your first alternative proposes.  (Yes, $27 - 26 = 1$, but you need at least three passes to defeat the [CBS16] attacks.)
It's also worth quoting section 9.3 in full:

9.3. Security for time-bounded defenders
A bottleneck in a system employing the password-hashing function is often the function latency rather than memory costs. A rational defender would then maximize the bruteforce costs for the attacker equipped with a list of hashes, salts, and timing information, for fixed computing time on the defender’s machine. The attack cost estimates from [AB16] imply that for Argon2i, 3 passes is almost optimal for the most of reasonable memory sizes, and that for Argon2d and Argon2id, 1 pass maximizes the attack costs for the constant defender time.

The draft RFC doesn't say which memory sizes they consider reasonable, but they do repeatedly use 1 GiB throughout the draft as a reference figure.  For example the reduction factors given in the first quote are based on 1 GiB, and the quote notes that these increase with more memory—but you're proposing to use less memory than that.

Or, as your question proposes and comments concur, you might consider not using Argon2i.  The draft RFC in fact recommends Argon2id over either 2i or 2d.  Then you just need one pass, because the advantage of tradeoff attacks on 2d and 2id doesn't depend on the number of passes (section 9.2):

The best tradeoff attack on $t$-pass Argon2d is the ranking tradeoff attack, which reduces the time-area product by the factor of 1.33.
The best attack on Argon2id can be obtained by complementing the best attack on the 1-pass Argon2i with the best attack on a multi-pass Argon2d. Thus The best tradeoff attack on 1-pass Argon2id is the combined low-storage attack (for the first half of the memory) and the ranking attack (for the second half), which bring together the factor of about 2.1. The best tradeoff attack on t-pass Argon2id is the ranking tradeoff attack, which reduces the time-area product by the factor of 1.33.

So for 1 GiB memory size, you need six passes of Argon2i to reduce attacker advantage to a similar level as one-pass Argon2id (2 vs. 2.1), and both are still behind Argon2d (1.33).  This speaks strongly in favor of Argon2id, and is presumably the reason the draft RFC recommends it.


AES with bigger keys more secure? Say you were to generate a 512 bit AES key, then encrypted a message by running it through AES CTR 256 twice, with the first and last parts of the key respectively.

Would it be as secure as modifying an AES implementation to increase the rounds to 28?

Cryptographic security is not a one-dimensional spectrum. Increasing the key size increases keyspace, which is the maximum number of possible keys that must be iterated through to complete a brute force attack. Increasing rounds, on the other hand, reduces the chances that novel cryptanalysis, which allows an attacker to break the cipher faster than brute force, will be successfully applied to the cipher.

Cascading encryption
Cascaded encryption, even with stream ciphers, is vulnerable to a meet-in-the-middle attack, which reduces the effective keyspace from 512 bits to 384 bits. It is further reduced because layered stream ciphers commute (the order of the stream ciphers doesn't matter, so two keys whose first and second halves are swapped are equivalent). However, it will not reduce security and the keyspace will be larger than 256 bits, even if it won't reach the theoretical 512-bit maximum that you want. Regardless, no one is going to brute force a 256-bit key and doubling it to practically improve security is a quixotic endeavor.
In order to avoid the meet-in-the-middle attack, you would need to redefine AES to use a 512-bit key. This would require a deeper knowledge of the Rijndael key schedule, but if you successfully do it, you would be able to take full advantage of the larger key, even if it's unnecessary. This is a lot more difficult than just increasing the number of rounds though, and without heavy analysis, something may break.
Increasing rounds
Increasing the rounds has a bigger effect, although it does not increase the keyspace at all. Increasing the rounds from 14 to 28 would drastically improve security. But that doesn't mean you should do it! It's not necessary, because 14 rounds is already considered sufficient. You'd be decreasing performance while increasing the security from "excessive" to "even more excessive". There's no reason to do it. If you did have to, you would need to make sure you adjust the round constants correctly through $\text{rcon}$. Rijndael is able to generate up to 255 extra round keys, in theory, without modifying the key schedule.
AES with 256-bit keys was defined with 14 rounds (12 and 10 rounds for AES defined with 192 and 128-bit keys, respectively). This number was selected based on extensive analysis from many experts all over the world. During the AES selection process by NIST, the best attack was found to only penetrate 6 rounds. The designers of the cipher (called Rijndael at the time) decided to add four extra rounds at a minimum as a "security margin" to hedge against future attacks. It has held up extremely well so far.


Implementation of a side channel attack? As homework I need to find the password of a crackme in ascii-coded binary. We were also given a specific part of the crackme (in the image below), which we will need to use a side channel attack against, most probably a timing attack.

I know that, based on the function given, you can find out the right password length, since the program would take longer to compute when the length is right.
I'm just not sure how I would implement the timing attack.

Could somebody please help?

I wish I had such homeworks when I studied, mine implied pen and papers only, sadly.

You have to get your hands dirty there. This means that you have to code something which will, as said by Ruggero in his comment:

determine the length by trying random password of different lengths and timing the time your program will take to return
determine the actual password thanks to the fact that the time needed by the program to return is a direct function of the edit distance between the actual password and the string you used as input.

The difficult part for 2. is that there is some noise added to the computation because of that random_time variable. This means that the nearer to the actual password you'll get, the more noise you'll obtain.

In order to counter this, however, you may rely on statistical analysis since you may run that program many time with the same input. So you'll have a mean deviation of only 4.5, which means that when you run a few times the same input, you'll get a Gaussian repartition with a mean value equal to roughly 4.5 plus the actual value of the difference between the inputed characters and the actual characters.

This would be the theoretical approach, I guess...

In your case because the usleep will take 0.01 seconds times the differences plus the random_wait... On average, when provided with the valid password, it'll take around 0.045 seconds.

So you may want to try to do so:
 - determine the length
 - benchmark the mean time with a all-zero string of that length (running it a few times, like 20-30 times should be good enough given the resolution of the wait time)
 - benchmark the mean difference to the previous computed mean time when changing only one characters of the input string at a time, do so for each position in the input string
 - compute the actual password thanks to all of that information, by trying to minimize the edit distance between your input and the actual password. (Eventually this may just allow you to narrow down the range of possible password to an amount which is easily bruteforced... but I think you can manage the noise added by random_time easily thanks to only a few trials with the same input and should get the right result.)

Here are a few other thing you may also try to, if you dislike having to wait so long at each execution of your binary:

if you have a crackme and you can run it on your device, and can do whatever you want, you may try to tamper with the usleep to get it to simply print its current value (maybe using a custom usleep implementation through a LD_PRELOAD trick ?) and then use the above method.
if you cannot tamper with its execution, you may try to count the number of instruction it's running and kill it when it passes a threshold and try with another input, this may be the quickest way to recover the password, instead of using the time it takes, you can use the number of instructions executed. This is possible using for example pintools, they even provide an example of such a counter.
more generally, reverse engineering and/or patching the crackme may help you.

PS: In the end, I'm not sure this question is really about cryptography or side-channels... But I don't really know where it may belong to.


Can a public key be same as private key? As I understand, we choose the public and private keys to be mutual inverses. However, it is possible that, in a group, there can be numbers which are their own inverses.
E.g. Consider p = 7, q = 3. n = 21, phi(n) = 12.
For the group G = {s | gcd(s,21) = 1} there are four numbers 1, 8, 13 and 20 which are their own inverses.

In such a case, it is possible to choose these numbers as both private and public keys. Isn't it?

Let me know if I have understood this correctly.

That's correct. In some cases, you could, if you really wanted, make a public key equal the private key. It would completely negate the benefit of using a public key cryptosystem, though, because access to the public key would imply access to the private key. It would turn it into a crappy symmetric scheme.

As noted in comments, most common RSA implementations set the public exponent to a fixed value, usually a Fermat prime like 3 or 65537. In that case, for an appropriately-sized modulus, there is no chance for the private exponent to equal the public exponent. The private exponent is always larger.


Is there a standard for OpenSSL-interoperable AES encryption? Many AES-encrypted things (files, strings, database entries, etc.) start with "Salted__" ("U2FsdGVkX1" in base64).
I hear it's some sort of OpenSSL interoperability thing: a b c.

Is there some standard reference somewhere (perhaps an RFC?) that explains how such OpenSSL-inter-operable AES-encrypted things are produced and later decrypted?

Ideally, an answer would link to a standard reference for the entire process, or perhaps a brief summary list of steps with a link to a standard reference for each step, something like:

To decrypt such a thing beginning with "U2FsdGVkX1" and with a known password,

first do base64 decoding -- see Wikipedia: base64. The result will start with "Salted__". Be careful not to use C strings, because the result may include several 0x00 bytes.
...
(I guess something about salting and the IV goes here?)
(I guess something about CBC or CTR goes here?) -- see Wikipedia: block cipher modes of operation.
(Perhaps something about message authentication goes here?)
...
AES-decrypt each block with decrypt_one_AES_block( key, block_of_128_bits ) -- see Wikipedia: AES article and A Stick Figure Guide to the Advanced Encryption Standard (AES).
save the result of each decrypt_one_AES_block(), concatenate them all together, and that's your plaintext. If the original was human-readable text or an HTML file, it may be OK to store the result in a C string; but other kinds of things may include several 0x00 bytes incompatible with C strings.

It may sound like I'm planning to write an implementation myself.
I reassure you that I plan to use one of several available libraries -- it's just that when reviewing the libraries, I'd like to know what they should be doing.
What should OpenSSL libraries be doing?

Is there a standard for OpenSSL-interoperable AES encryption?

Since this is still open and the issue keeps coming up:

TLDR: There are lots of things in OpenSSL that implement standards including AES, but the key derivation part of enc is partly nonstandard (at least by default)

First, OpenSSL has several commandline operations it calls commands (although they usually aren't separate programs, as typical commands are on Unix), and a whole range of library calls, that do encryption and decryption with numerous symmetric algorithms of which AES is only one as well as several asymmetric algorithms. Major ones are PKCS#7/CMS and semantically equivalent S/MIME; PKCS#8/rfc5208 and PKCS#12/rfc7292; and the SSL/TLS protocols for which it is named.

The file format with Salted__ is used by one specific OpenSSL command enc. Although if the commandline executable is given a cipher name instead of a command it silently translates to enc -- for example openssl aes-128-cbc ... becomes openssl enc -aes-128-cbc ... -- so people often perceive and describe this as 'OpenSSL AES-128-CBC encryption' as if it were the only AES-128-CBC encryption OpenSSL does.

enc can encrypt and decrypt files (including anything the OS can provide as standard input and output, such as a pipe) with a wide range of options in (mostly) two dimensions:

the symmetric cipher algorithm and mode, and padding. OpenSSL library provides and enc can use several algorithms, which may vary depending on build but currently default to Blowfish CAST DES DES-EDE(3) (usually called TripleDES TDES or TDEA) IDEA RC2 RC4 Camellia SEED and AES; I haven't bothered linking all the standards. Some algorithms, especially AES, have options for key size. All except RC4 are block ciphers and must be used with a mode such as CBC ECB or CTR; although algorithms and modes are actually defined by separate standards, enc (and the EVP API) combines them in a single name like aes-128-cbc above. (added) A list of the algorithm-and-modes is available through version 1.0.2 from openssl list-cipher-commands or just openssl enc -?, or version 1.1.0 from openssl enc -ciphers. Do not use openssl ciphers which shows something quite different: the ciphersuites available for SSL/TLS protocol communication.

Some block modes (CBC and ECB) require data be a multiple of the cipher's block size; since in general real data doesn't do this, it is necessary to add padding when encrypting and remove it when decrypting. By default OpenSSL uses the padding scheme defined by PKCS#7 which extends a scheme defined in PKCS#5, and therefore is usually still called PKCS#5 or just PKCS5 padding. If you specify -nopad this is not done, and (for these modes) encrypting (or decrypting) wrong-size data gives an error.
all symmetric ciphers require a key, and some modes require an Initialization Vector (IV). enc can use a 'raw' key and if applicable IV specified on the commandline, with -K (uppercase!) and -iv and in hexadecimal. However its default and usual mode is to do Password Based Key Derivation (combined with encryption to give Password-Based Encryption, PBE), and this in turn has several options.

The password can be entered several ways, using legacy option -k (lowercase) or -kfile or newer option -pass or prompted for and typed with no terminal echo (if possible).

The newer, preferred and default option is salted key derivation, which strengthens the derivation (but see below) by using 8-byte random salt. It is also possible to specify a specific salt with -S in hex, or disable salting with -nosalt. If salt is used, random or not, a very simple header is added to the ciphertext consisting of the ASCII characters Salted__ and the 8 bytes of salt. (Standardized PBEs like PKCS#12 also convey the salt, but use much more extensive and flexible formats.)

The key derivation process is based on PBKDF1 from PKCS#5/rfc2898 but modified, and is implemented by the API function EVP_BytesToKey whose man page should be available in any Unix system with OpenSSL installed and on the website. A bit confusingly, and inconsistent with more recent best practice, this 'key derivation' actually derives both the key and IV if applicable. To lay out the relationship exactly:

PBKDF1 uses a choice of hash from MD2 MD5 SHA1, and an iteration count, and (required) salt. It initially forms password || salt and hashes it, then hashes the first hash, then hashes the second hash, iterating to a total of count times. PKCS5 PBES1 uses PBKDF1 to produce both key and IV -- but only for RC2 and (single) DES, neither of which is acceptable today.
EVP_BytesToKey uses any hash supported by EVP, which may depend on build options but currently defaults to MD4 MD5 MDC2 RIPEMD RIPEMD160 SHA1 and the original SHA2 family (but not the later '512 slash' additions), plus iteration count and optional salt. It does one block like PBKDF1 as H^count (password||salt) with the salt omitted if not used, but if the required 'key material' is more than one block, it then does additional blocks as H^count (prevblock||password||salt) ditto. Whether the EVP_BytesToKey result is used for IV depends on the caller.
enc uses EVP_BytesToKey with salt by default (but see options above); (edit) hash MD5 by default through 1.0.2 or SHA256 by default in 1.1.0 released 2016-08 but you can specify otherwise with the option -md which was only documented from 1.0.0 but actually available before; and iteration count ONE. Thus the key and IV if applicable used by enc before 1.1.0 defaults to

key[||IV] = b0=md5(t=pw[||salt]) || b1=md5(b0||t) || b2=md5(b1||t) ...

This is a poor PBKDF. Because all the available hashes (including default MD5 or SHA256) are fast and this PBKDF 'iterates' only once, an attacker can quickly try large numbers of possible passwords to find yours, unless your password contains enough entropy without any significant 'strengthening' -- and most people don't choose, and even if given can't remember, such strong passwords.
But we are stuck with it for backward compatibility.

Thus for examples:

openssl rc4-128 [-e|-d] -k sekrit -nosalt
# uses RC4 with 128-bit key (RC4 is a stream cipher and uses no IV)
# derived using no salt, MD5 (unless 1.1.0), and count 1 from 'sekrit'

openssl aes-256-cbc [-e|-d] -k sekrit -md sha1
# uses AES in CBC mode with 256-bit key and 128-bit IV
# (both) derived using random salt, SHA1 and count 1 from 'sekrit'
# and adds the Salted__ header with the salt to the ciphertext

And finally, if you specify -base64 or the abbreviation -a, the ciphertext (including header if any) is encoded to base64 on encryption, and decoded from base64 on decryption; this is fairly commonly needed because some applications, systems, or protocols cannot handle the arbitrary (quasi-random) binary bytes needed for ciphertext. (edit) Similarly if you specify -z plaintext is compressed before encryption or decompressed after decryption, but only if OpenSSL was built with compression (zlib), and after the CRIME and BREACH attacks some builders or packagers disable compression entirely. These options are independent of the cipher and key/PBKDF, and in fact you can use them alone to only base64 encode/decode or zlib compress/decompress without doing encryption or decryption at all.

Base64 is used with slight variations in many standards but OpenSSL mostly follows the original PEM in 4.3.2.4 (no internal hyperlink because 1993 was before WWW became popular). Two caveats: base64 decoding silently ignores part and sometimes all of a line with a non-base64 character; this is useful when OpenSSL uses it internally to read PEM-format files, but may not be so in other applications. And before 1.1.0, it silently ignores lines longer than the 76-character limit specified in MIME unless you add -A (uppercase). zlib compression is related to, but not quite the same as, gzip.

Inter-version compatibility: (added) using password-based encryption and decryption depends critically on using the same parameters and especially the same hash in the PBKDF for both operations. As noted above, the default hash used by the enc command changed in 1.1.0 to SHA256 versus MD5 in lower versions. Thus data encrypted using the default hash in lower versions won't decrypt with the default in 1.1.0 or vice versa.

if data was encrypted with the default (MD5) on an older version, decrypt in 1.1.0 (and presumably higher when released) with -md md5
if data was encrypted with the default (SHA256) on 1.1.0 (or presumably higher), decrypt in an older version (at least back to 0.9.8, possibly before) with -md sha256
to proactively prevent a problem, specify -md consistently for both encryption and decryption even when it's redundant

UPDATE: OpenSSL 1.1.1 (2018-09) adds an option for -pbkdf2 -- with default iteration count 10000 -- and an option -iter to change that count -- and gives a warning when you don't use these i.e. when you default to the old scheme, described above. This is the standard PBKDF2 from PKCS5v2/RFC2898, although 10k is rather low (but much better than 1!); even my aging laptop with a Celeron can do 100-200k without noticeable delay. Compare
Can I dynamically calculate an appropriate number of iterations for PBKDF2 based on the system time, rather than using a fixed value?
https://security.stackexchange.com/questions/110084/parameters-for-pbkdf2-for-password-hashing/
https://security.stackexchange.com/questions/3959/recommended-of-iterations-when-using-pkbdf2-sha256 .
But the iteration count isn't recorded in the file, so you must either remember it (which makes varying it inconvenient) or store it elsewhere such as the filename or other metadata like an NTFS alternate stream.
Also, it still uses the traditional enc behavior of deriving both the key and IV (if needed), not choosing the IV by a separate random process, as the encryption scheme PBES2 in PKCS5v2 does.


Cryptographic Symmetric Stream Cipher Let me know a cryptographic symmetric stream cipher system with only two functions say S() and P() and it should satisfy the following conditions:

There will be two independent computers say M1 and M2 (no connection exists between them) and only one function should be stored in a machine.

For example: Function S() will be executed on machine "M1" and the function P() on machine "M2".
User selects a random string of bits (say X) of desired length (L) as input.
User selects a machine randomly (either M1 or M2) and executes the function with the selected random string X as input to it. For example: if machine *"M1"*is selected then the function S() will be executed to produce a output Y = S(X).
Then the user executes the other function P() with Y as input to produce the original random string X.

For example: X = P(Y).
And again user repeats the process in reverse order using the same random string X as input. For example: the function P() in machine "M2" will be executed to produces a output Z = P(X).
And again the user executes the other function S() with Z as input to produce the original random string X. For example: X = S(Z).
Length of outputs Y and Z should be equal to the length of input X.
Outputs Y and Z should be non-linear with respect to the input X, and
Output of S(X) and P(X) should be different. For example: Y != Z.
Keeping it simple, it should demonstrate S(P(X)) = P(S(X)) = X.

For example: function S and P are inverses of each other.

My questions:

How secure such a cipher?
I feel such functions output may be difficult for any known cryptanalysis, if not, why?
Is it easy/hard to design such a system?

Whenever you have two functions such that, for any X and any Y,
  X == S(P(X))
and also
  Y == P(S(Y)),
then
X and Y are bijective functions.

With modern secure communication systems, exactly the same plaintext message can be encrypted to many different ciphertext messages -- in particular, they are designed such that the message "attack" is unlikely to encrypt to the same ciphertext twice -- so therefore their "encryption" and "decryption" functions are not bijective.

Nevertheless, many classic ciphers are bijective, and often several of the parts inside a modern secure communication system are also bijective.

(The complete ciphertext message for a modern secure communication system typically begins with a random initialization vector or other nonce, has a "body" generated by some bijective function applied to the plaintext -- the particular bijective function is selected by a combination of the initialization vector and the encryption key -- and ends with a message authentication code.).

reciprocal ciphers

A cipher where P() and S() are not only bijective, but are the same function -- i.e., for any X, P(X) == S(X), and X == P(P(X)) -- is common, and known as a reciprocal cipher.

Some of the more famous reciprocal ciphers are:

The Enigma machine was a reciprocal cipher machine
ROT13
Beaufort cipher
Kama-sutra ciphers
XOR-based stream ciphers
One Time Pads (both XOR and Beaufort cipher versions)

Most mechanical cipher machines use a reciprocal cipher, so it wouldn't need a separate "encode mode" and "decode mode".

non-reciprocal bijective ciphers

Many classic ciphers are bijective, but not reciprocal: S(X) != P(X).

For example, the following ciphers are bijective but (usually) not reciprocal:

monoalphabetic substitution ciphers (except for Kama-sutra ciphers), and in particular the Caesar cipher (except for ROT13).
The standard Vigenère cipher, and the "variant Beaufort" cipher.
One Time Pads (the Vigenère cipher version)
transposition cipher (except for a few "paired-up" reciprocal transpositions)
permutation cipher

Practically all modern ciphers are based on either stream ciphers (RC4, A5/2, Solitaire cipher, etc.) or single-block ciphers (AES, DES, etc.), which are bijective but (almost always) not reciprocal.

Many modern single-block ciphers are built with a Feistel network structure that, in each round, cascades a reciprocal permutation E ("swap the left and right half of the block") and a keyed reciprocal substitution cipher U, to build a non-reciprocal bijective encryption function S(x) == E(U(X)) != P(X) = U(E(X).
It is widely believed that practically any non-linear function can give adequate security if it is iterated over enough rounds.

(Is it a coincidence that you used the names S() and P() that have the first letter of two common operations in cryptography, substitution and permutation, aka confusion and diffusion ?)

security

These bijective ciphers (both reciprocal and non-reciprocal) have a wide range of security, covering both ends of the spectrum:

Monoalphabetic substitution ciphers (aka cryptograms) published in newspapers as puzzles that are daily cracked by amateurs.
One-time pads which (in both reciprocal versions, and also the non-reciprocal version) are uncrackable.


Paillier's Cryptosystem - Secure Key Size Given Paillier's Cryptosystem. What size in bits would be considered secure  for now and the near future? I know it differs for every cryptosystem.

For reference, the most important part of my implementation of the key generation is given below. I would wish like to increase the performance of my app but remain secure for the near future. What would be the recommended bit size, and why? Thank you for your time.

final int PRIME_CERTAINTY = 100;
final int BITLENGTH = ???;
BigInteger p, q;
do {
  p = BigInteger.probablePrime(BITLENGTH / 2, new SecureRandom());
} while (!p.isProbablePrime(PRIME_CERTAINTY));

do {
  q = BigInteger.probablePrime(BITLENGTH / 2, new SecureRandom());
} while (!q.isProbablePrime(PRIME_CERTAINTY) || q.equals(p));

n = p.multiply(q);

You should be using a 2048-bit modulus, as with RSA. Personally I feel comfortable with 1536, but 2048 is considered the minimum standard.


DIY over-encryption with a related key I know next to nothing about cryptography, which is bad because I'm a programmer. I was exploring some code the other day and the encryption part of it seemed a little strange to me. I'd like the name/terminology/links to this algorithm/concept so I can learn more about it, and I'd also like to know if it's secure or a waste of processing. Also please bear with me, I don't know any of your terminology u.u

The code included some stuff that sounds pretty good: it uses CBC with AES/Rijndael (using 256 bit block size) with null byte padding (the data is supposed to end with a certain character so null bytes works). The IV is randomly generated with each encryption and is then prepended to the encrypted data (second question: does this practice have a name?). But then as a wrapper around that it has another layer of "encryption"? - I'll try to explain it the best I can:

First, the key that was used in the AES/Rijndael is passed through a hash function. I'll call this the key hash? This same value is used in both encrypting and decrypting. Then the encrypted data (from the AES CBC, and with the IV in front) is broken into chunks the same length of the key hash (blocks?). Each byte of the key hash is added to the encrypted byte, and then modulus-ed(?) (if > 255 then subtract 255). Currently the hash function used is MD5, but I'd also like to know about this in a more general sense too.

Is this whole method secure? What is it called? Is it a waste of processing? Can it be done more efficiently/better? Why did the developer choose to do it like this? Etc... So many questions!

Not important but: The developer then proceeds to store/send the encrpyted data over the network as... doubly base64 encoded data, and then inside xml. e.g. xml(base64(base64(encrypted data)))... Gross!!! And the original data is so verbose and redundant too.

The key that was used in the AES/Rijndael for encryption is passed through a hash function

(strikethrough/strikeout mine)

That's OK if the hash function is secure and not vulnerable to timing attacks. Obviously MD5 is not a great option as it has been proven to be insecure. For this specific function however - similar to key derivation - it's OK. You should not be able to retrieve the key value as a hash is a one way function.

  I'll call this the key hash? This same value is used in both encrypting and decrypting. Then the encrypted data (from the AES CBC, and with the IV in front) is broken into chunks the same length of the key hash (blocks?). Each byte of the key hash is added to the encrypted byte, and then modulus-ed(?) (if > 255 then subtract 255).

This is basically a one-time pad where the key is repeated. Now normally it would be relatively easy to find the "hash" key with a known plaintext attack. With the ciphertext being properly randomized that is not possible. If however some part of the original AES/CBC ciphertext is ever leaked then the hashed key becomes known and the cipher can be reversed.

Basically this scheme doesn't add much security. It also shows a very limited understanding of cryptographic techniques and encoding methods. Because of this it should be seen as a risk, even if the scheme cannot be attacked directly. If MD5 is ever reversed you're in trouble. For now it is indeed a waste of bandwidth and processing time.

Furthermore, if you'd ever want to use hardware based encryption then the encryption key value will not be directly available (as the encryption operation is performed in the hardware itself). So it's probably not possible to perform MD5 over the key, making this scheme incompatible with hardware based security.

Finally, there seems a lot to be going on, but this scheme in all its needless complexity seems to miss an authentication tag. This means that an attacker may send you corrupted data that's still successfully decrypted. The attacker won't be able to simply inject any data, but it is possible to at least let the receiving party process garbage. In that sense the hash function could have been put to better use in a HMAC construction. In that case a SHA-2 hash such as SHA-256 should be preferred of course.


Do well-known hash functions have any "impossible" output values? What I'm wondering is whether the codomain and image of common hash functions are strictly equal… or whether there are any known values which have no possible preimage.

For example, SHA-1 outputs a 160-bit digest. Can it be proved that every possible sequence of 160 bits is a possible output of SHA-1 (even though corresponding preimages cannot be easily computed, by design), or are there certain outputs which can be demonstrated to be impossible based on the construction of the hash function?

This question about uniformity of hash function output seems related, though what I'm interested in has less to do with overall uniformity, and more with provable existence/non-existence of any preimage for specific outputs.

No, it is not known that any cryptographic hash in common use has impossible output values (that is a bitstring of the appropriate size to be an output, but that is not reached by any input message). That's at least for MD5, the SHA(-1/-2) family of FIPS 180-4, SHA-3 of FIPS 202, RIPEMD-xxx, Blake/2, Tiger/2, Whirlpool.

In fact, it would be surprising that such impossible output value exists, and even more that it could be exhibited:

For a hash modeled as a random function, the probability that there is such value is lower than $1/2$ for a $n$-bit hash when there are more than $n\,2^n$ inputs; and that probability lowers with larger message input sets. See this for details.
For a Merkle-Damgård hash with Davies-Meier round function, the message block at most twice as large as the output, and the length padding at most about a quarter of the block size (like MD5 and direct larger successors are), under the assumption that the underlying block cipher is a Pseudo Random Permutation, and by an adaptation of the above reasoning, it is very probable that all outputs are reached with a single message block; and even more probable that they all are reached with two message blocks. Anything else seems to require a severe defect of the underlying block cipher, and any known such defect seems considerably lesser.
For the sponge construction of SHA-3, a similar argument can be made that a severe defect of the sponge function would be required to have some output values unreachable.


Zero Knowledge Proof using hash chains - Is there a flaw in the algorithm? I came across this blog post http://blog.stratumn.com/zkp-hash-chains/ which provides a Protocol to prove in zero-knowledge that an integer (such as age or balance) is greater than a known threshold.

It is based on this paper: Verifiable Auctions for Online Ad Exchanges

The protocol is as follows:

A trusted central document authority that provides proof services. P has requested a secret S from this authority, for use in proving her age. The authority assigns a secret (256 bit) S to P. Let’s say P's (S) is:

0000000000000000000000000000000027ae41e4649b934ca495991b7852b855

The Authority then calculates a hash-chain one link greater than P's age:

EncryptedAge=HASH^{ActualAge+1} (S)

P also computes

Proof=HASH ^ {1+ActualAge−AgeToProve} (S)

P then sends to the other party:

The Authority’s signed Proving Kit (which contains her EncryptedAge )
The Proof she calculated

The party that needs to verify P's age does:

Extracts P's EncryptedAge from the Authority’s message
Computes:

VerifiedAge=HASH ^ {AgeToProve} (Proof)

Compares VerifiedAge == EncryptedAge. If equal then age is higher than age to verify.

Here is the code in JavaScript to test above protocol: https://repl.it/repls/SmartOccasionalQueries

I think there is a flaw in the protocol, it occurs in this step:

Proof=HASH ^ {1+ActualAge−AgeToProve} (S)

When 1+ActualAge is equal to AgeToProve, then hash is not applied on S.

It ends up sending the secret as Proof. S should have been maintained as secret.
It ends up computing that verified Age == encrypted age, where as it is not, example: https://repl.it/repls/OrderlyPalegreenScriptinglanguages

The below is example from the blog, with Age = 19, and AgeToProof = 20:

In fact, it gets even worse if 1+ActualAge is less than AgeToProve, since in that case P would have to find a preimage for the hash in step 3!

But (even without actually following any of your links) I would guess that there's an implicit  assumption that a legitimate P will not even attempt to run the protocol unless ActualAge ≥ AgeToProve, since proving that they're not quite old enough doesn't gain them anything anyway.

Of course, a malicious P could do whatever they want, including accidentally (or deliberately!) revealing the secret.  But in general, we don't really care if a malicious party will do something that only hurts themselves.

OK, let me extend my answer after reading the linked blog post and article.

First of all, note that the blog post and the article actually describe different protocols with different participants and goals.  Specifically, the protocol described in the blog post has three participants:

a prover P who wants to prove to the querier Q that their age $a$ (a non-negative integer number of years) meets or exceeds some minimum limit $q \ge 0$, without revealing how much older than the minimum limit they are;
a querier Q who wants to know whether P is at least $q$ years old; and
a government authority A that knows how old P is, is trusted by both P and Q, and can sign messages in such a way that Q can verify that they come from A, even if relayed by P.

In the protocol describe in the article, however, the authority A does not exist!  Instead, in that protocol, P simply picks an arbitrary (non-negative integer) number $x$ and sends to Q a commitment to that number, such that they can later both:

prove to Q that the number $x$ they picked is greater than or equal to some threshold $q \ge 0$, without revealing how much greater it is; and
optionally, to release the exact value of $x$ and prove that this is indeed the number that they earlier committed to.

The reason this distinction matters is because the protocol outlined in the blog post actually contains some vestigial features (specifically, the way the initial seed for the hash chain is selected) that aren't required for the scenario described in it, and which could be left out to simplify the protocol!  Those features are only needed if we want P to be able to also optionally prove their exact age to Q.

To illustrate how the protocol is supposed to work, let me first start by describing a simpler protocol for the three-party case.  Specifically, instead of all this messing around with hash chains, the authority A could simply issue the prover P with a bunch of separate signed "tickets", each stating that:

  Authority A hereby certifies that P is at least $x$ years old.

where $x$ ranges from zero to P's actual age $a$.  Then, to prove that they're at least $q$ years old, P simply needs to select the ticket with $x = q$ and reveal it.

The problem with this scheme is that it requires A to sign a separate ticker for every year of P's life, and for P to store all of them.  (Honestly, that might not be much of a problem in practice, since in real life $a$ rarely exceeds 100.  But it could be a problem if we, say, decided to count P's age in days or even seconds instead of years.)  It would be kind of nice if we could have a scheme where:

the authority A could send P a single ticket stating their actual age;
there was a way for P (or anybody else!) to decrement the age on the ticket, i.e. to take a valid ticket that says the P is at least $x$ years old, and obtain a valid ticket stating that P is at least $x-1$ years old;
there was no way for P or anybody else to reverse this operation, i.e. to increment the age on the ticket and have it still accepted as valid; and
the authority A could simply sign a single ticket stating that "P is at least 0 years old", knowing that anybody who applies the decrement operation to any other valid ticket (and only to a valid ticket!) for P's age enough times will eventually obtain the signed ticket and be able to verify the signature.

One way to achieve that is to include an arbitrary string of, say, 256 bits on each ticket, and have the decrement operation include hashing that string with SHA-256 and replacing it with the hash output.  That is, A could send P a ticket stating:

  Authority A hereby certifies that P is at least $a$ years old.  Hash: $s$.

and a signature for the ($a$ times decremented) ticket:

  Authority A hereby certifies that P is at least 0 years old.  Hash: $H^a(s)$.

where $s$ is a random 256-bit string and $H^a$ denotes SHA-256 iterated $a$ times.

When P wants to prove to Q that they are at least $q \le a$ years old, they can then apply the decrement operation $a-q$ times to the original ticket sent by A to generate a ticket stating:

  Authority A hereby certifies that P is at least $q$ years old.  Hash: $H^{a-q}(s)$.

and send it to Q along with the signature for the "at least 0 years old" ticket that they received from A.  And Q, in turn, can apply the same decrement operation $q$ more times to re-derive the "at least 0 years old" ticket, and then verify that it matched A's signature.

The reason this works is because SHA-256 is (believed to be) preimage resistant.  This means that, given a random string $s$, it's easy for anybody to calculate SHA-256($s$), but effectively impossible to find any string $r$ such that SHA-256($r$) = $s$.  Thus, given the original ticket stating that they are (at least) $a$ years old (with the random hash $s$), P can easily obtain a valid ticket for any age $q \le a$, but not for any age greater than $a$.

OK, but then why does the protocol described in the blog post (and in the VEX paper) have the authority A first choose a random "seed" string $r$, and then use $s$ = SHA-256($r$) as the hash on the first ticket sent to P?

Well, one reason why one might do that is to make sure that the hash on the first ticket really looks like a normal SHA-256 output.  Sure, a random 256 bit string should be indistinguishable from a random SHA-256 output anyway, but we all know that in reality, random number generators can have subtle bugs that are often hard to test for.  Hashing the initial random value gives a little extra assurance that nobody can find any way to distinguish the original ticket stating P's true age from any decremented derivatives of it.

But that doesn't mean that A would have to ever reveal their original random value $r$ to P.  And indeed, the protocol as described above works perfectly well without it.  So why, then, does the VEX paper (and the blog post based on it) seem to suggest revealing this $r$ to P?  And doesn't doing so let P lie about their age by one year?

I'll answer the second question first.  Knowing $r$ will not let P lie about their age, provided that:

the seed $r$ is deliberately chosen not to be a possible SHA-256 output, and
the querier Q always verifies that the hash on the ticket is a possible SHA-256 output before accepting it as a proof of age.

OK, but what good does revealing $r$ to P do?  Well, it allows P to also choose to reveal (and prove!) their exact age to Q by disclosing $r$.  Since, as noted above, $r$ must not look like a valid SHA-256 output, this means that Q can be sure that it's indeed the first value in the hash chain leading down to the "at least 0 year old" hash signed by A, and that therefore $s$ = SHA-256($r$) must be the hash corresponding to P's true age (at the time A generated the signature, anyway).

Basically, without this extra feature, P could always decide to lie about being younger than they actually are, and there would be no way for Q to detect that, at least not without extra infromation from A.

For the age checking protocol described in the blog post, this isn't really a particularly important feature.  After all, if P needed to be able to prove their exact age, they could just get A to sign a separate message stating it.

However, for the verifiable auction protocol described in the original VEX paper it is essential, because in that protocol there is no central authority A, and the provers instead get to freely choose the value they want to commit to.  Without a way to reveal and verify the actual committed value at some point, the provers could just pick some huge value (say, one billion) at the start of the auction, and only later decide which "at least" queries they actually want to answer affirmatively.

Anyway, it turns out that, while the protocol as designed (and reasonably interpreted) is sound as far as I can tell, the JS implementations linked from the blog post and from your question are both buggy.

In fact, both of them have two bugs: one of that allows the prover to generate a bogus proof for a minimum age one year greater than their true age (revealing their secret seed in the process), and another bug that allows the verifier to accept it.

The first bug is simply that the prover should never attempt to generate a proof for a minimum age that they don't actually meet.  A minimal fix to the code linked from the blog post would be to add the following like to the beginning of the challenge() function:

function challenge(age, age_to_prove) {
  if (age < age_to_prove) return null;  // <- ADD THIS LINE!
  Q = hashchain(S, Number(age)+1-Number(age_to_prove))
  document.getElementById("display_Q").innerHTML = Q
  return Q
}

A similar bug is also present in the prove() function in your code, and can be fixed the same way.

The second bug is that, even if the prover (deliberately or by mistake) tries to use their initial hash chain seed as a proof of age, the prover must not accept it.  The blog post does correctly note this in the "Soundness" section:

  The exception to this is for $AgeToProve=ActualAge+1$, in which case Paula could just send $S$. However, as the format of $S$ is publicly known, a watchful verifier would detect the fraud [...]

but the linked JS code doesn't actually include such a check.  As a result, the verifier in the demo will happily accept the seed $S$ as bogus proof of age (and, due to the first bug, the prover will in fact respond with the seed if asked for a proof of a minimum age greater than their true age).

The blog post also uses a rather unfortunate choice for the format of the initial secret seed: 128 zero bits followed by 128 random bits, for a total of 256 bits.  The reason this choice is bad is that it precisely matches the output bit length of SHA-256, making it theoretically possible (even if extremely unlikely) for a genuine SHA-256 output to match the format of the secret seeds.  Literally any other choice of seed length (including just leaving out the 128 zero bits) would've avoided this issue.

Anyway, sticking with the poorly chosen seed format, a basic fix for the verify() function would be to add something like the following check at the top of it:

if (Q.length != 64 || Q.substr(0,32) == '00000000000000000000000000000000') {
  // this does not look like an SHA-256 output; verification failed!
  return null;
}

Of course, if the format of the secret seed was changed so that it wasn't exactly 256 bits (= 64 hex digits) long, then the .substr() check could be removed.  And also, of course, if the protocol was simplified (at the cost of removing the option for exact age verification) so that the prover never learned the secret seed to begin with, then this check would not even be necessary.


Authentication protocol Alice and Bob share a secret key K. Suppose that someone suggests the following methods to allow Alice to securely authenticate to Bob.

Bob generates a random message r, enciphers it using K under a secure block cipher scheme and sends the encrypted message to Alice. Alice decrypts it, adds 1 to it and sends the result encrypted with K under the same block cipher to Bob. Bob decrypts the message and compares it with r. If the difference is 1, then he is sure he is communicating with Alice; or else, as no one else knows the secret K, he is talking to an impersonator. Is this protocol secure?

Is this secure based on the difference of 1 or is that still prone to attack?

TL;DR: It's not secure, due to MITM attacks

Just because Bob receives r + 1, it doesn't mean that he is really talking to Alice. What if Mallory intercepted the key exchange of k and intercepts messages like so:

Mallory intercepts Bob's key exchange to Alice.
Bob and Mallory do the key exchange, Bob thinks that Mallory is Alice.
Mallory and Alice do the key exchange, Alice thinks that Mallory is Bob.
Bob sends r to Alice, but it's intercepted by Mallory.
Mallory forwards the message to Alice and Alice computes r + 1, sends this to Bob (inadvertently via Mallory)
Any data send from Bob to Alice will go via Mallory, without either party knowing.

This way it appears that Alice did r + 1, but Mallory can still read all messages between them. This is solved with authenticated encryption.

For the key exchange, use authenticated (EC)DHE, and for encryption either sign-then-encrypt or encrypt-then-mac for data integrity (though this is more important for stream ciphers, as editing the ciphertext will edit the plaintext correspondingly).

So for example, using ECDSA you could do SymmetricEncrypt(message + ECDSA(message)) for sending data, and for the key exchange, you could use ephemeral key pairs for the (EC)DHE, and use static key pairs to sign the ephemeral ones.

Either party then verifies the signatures of the data received in order to check that they are talking with the person that they think they are.

Here's a worked example, using ECC:

Assume Bob owns sPK1, and sSK1
Assume Alice owns sPK2, and sSK2

Where s means static, PK and SK standing for public key and private key respectively.

Bob creates ePK1, and eSK1
Alice creates ePK2, and eSK2

Where e stands for ephemeral.

Bob sends Alice ePK1, sSK1(ePK1). Bob sends Alice his ephemeral public key and a signature of it, proving Bob is the sender of the key.
Alice sends Bob ePK2, sSK2(ePK2).
Both parties receive and verify the others ephemeral public key. Both parties then combine their own ephemeral private key with the others ephemeral public key, yielding the same result either side. (In this example, this is done with EC Point Multiplication - ECDHE)
Alice and Bob then run the result through SHA(3)_256 for a 256 bit symmetric key.
All messages can be send like: AES-256-GCM(message, sSKn(message)), producing a ciphertext and MAC tag.

Side note: For symmetric encryption, AES-GCM is recommended, as it uses CTR as the underlying AES mode, which is fast as its paralellizable, and produces a MAC tag without the need for a second key to be derived / generated.

EDIT
In order to make sure the static keys (for signing) belong to who they should do, a CA would issue certificates to Alice and Bob, so the static keys are definitely correct, and not forged.


Space complexity and cryptography It appears that in cryptography a lot of definitions are based on the time complexity of various algorithms. For example, a "good" encryption scheme should be resilient against a polynomial adversary. Or, inverting the image of a one-way function should take more than polynomial time.

But what about space complexity?

Why is there hardly any discussion (at least in introductory textbooks) of space complexity?
Maybe there is an encryption scheme out there that can be 'broken' in polynomial time, but only with super-polynomial space. Should that scheme also be considered 'safe'?
Are there any known non-trivial results about the space complexity of some cryptographic primitive? By non-trivial I mean something that isn't an immediate result of $\mathrm{NP}\subseteq \mathrm{PSPACE}$ or something similar...

Maybe there is an encryption scheme out there that can be 'broken' in polynomial time, but only with super-polynomial space.

That possibility can be excluded; if an algorithm uses $F(x)$ time (for any $F$), then that algorithm can be implemented using $O(F(x))$ space.  The reason is fairly obvious; in $F(x)$ steps, the algorithm can access at most $\ell F(x)$ memory locations (assuming a 'step' accesses at most $\ell$ memory locations, where $\ell$ is some constant).  So, by tracking which memory locations the algorithm actually touches, and just tracking those (which another constant multiplier in terms of overhead), and so this modified algorithm uses (at most) a constant factor more memory than the total number of steps.


Certificate Path Verification of X509 Certificate I have the trusted root certificate which I am validating using the self signed key. I also have the intermediate certificate, which i am validating using the root certificate.
Now when i am validating the certificate do i need to trace back the whole chain to validate the certificate?
Or can i say i have done TPC, if i just validate it using the intermediate only(since i have already validated my intermediate with its root before)?

Now when i am validating the certificate do i need to trace back the whole chain to validate the certificate?

Not each time, no. You can do some caching, if you like (since root CAs tend to be valid for many years). But I don't think performance gains will be worth the added complexity of the caching idea.

Also: if you plan to honor the expiration dates in the root CA itself, then you have to check these using some other mechanism.

Also: you may have to account for the (unlikely) case of the intermediate CA being revoked.

So, unless you have a good reason not to check each time, then I recommend checking the complete chain from end-entity-certificate (inclusive) up to trust-anchor (inclusive). It's easier to understand.


Why has the McEliece cryptosystem not gained much acceptance, but now is a candidate for post-quantum cryptography? I understand that the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece, almost around the same time RSA came about.

Why has the McEliece cryptosystem never gained much acceptance in the cryptographic community, but now is a candidate for post-quantum cryptography?

The simple answer is that there are two reasons:

The lack of a standard implementation. RSA has an acknowledged standard while McEliece doesn't.
The size of the key. It's huge! In the multi-megabit range. In terms of today's communication networks, that is bad, but - in my opinion - not too bad. It means it takes time to exchange, but once you have built up your local DB of keys for actors that you communicate with, well, so what. But storing the keys is another matter. You can't just pop them in to a varchar field: you need to really think about your local key storage issues.

That said, I think that there is a definite use case for McEliece coming. Especially if you have secrets that have to be secure for a long period of time.

Current PKE used for thanks like SSL and bank transactions is fine: the time to live for the transaction is relatively small. But think of the security around a property transaction using smart contracts: lots of property is held for > 20 years. If the title deeds are proven via a secure document then you need the security on that document to live at least that long - probably many times that length.

Just for fun, I downloaded a version of McEliece called CodeCrypt, compiled that and generated a key. It took 9 minutes of CPU time!

Now, if I have done this all correctly, the public key is only 4K, and the private secret 20K, which is either way too short, or (more probably) I have made a mistake somewhere.


Why does second pre-image resistance imply pre-image resistance I am studying hash functions. I can understand why collision resistance implies second preimage resistance, but I don't get why second preimage resistance should imply first preimage resistance.
Could anybody be help me with this argument from Introduction to Modern Cryptography by Katz & Lindell, please?

Collision resistance: This is the strongest notion and the one we have considered so far.

Second pre-image resistance: Informally speaking, a hash function is second pre-image resistant if given $s$ and $x$ it is infeasible for a probabilistic polynomial-time adversary to find $x' \ne x$ such that $H^s(x') = H^s(s)$.

Pre-image resistance: Informally, a hash function is pre-image resistant if given $s$ and $y = H^s(x)$ (but not $x$ itself) for a randomly chosen $x$, it is infeasible for a probabilistic polynomial-time adversary to find a value $x'$ such that $H^s(x') = y$. (Looking ahead to later chapters in the book, this essentially means that $H^s$ is one-way.)

[...] Likewise, any hash function that is second pre-image resistant is also pre-image resistant. This is due to the fact that if it is possible to invert
$y$ and find an $x^\prime$ such that $H^s (x^\prime ) = y$ then it is possible to take $x$, compute
$y = H^s (x)$ and invert it again obtaining $x^\prime$. Since the domain of $H$ is infinite,
it follows that with good probability $x \neq x^\prime$. We conclude that the above
three security requirements form a hierarchy with each definition implying
the one below it.

Let me try to elaborate on their proof. Suppose you had a hash function $H$ that was second-preimage resistant but not first-preimage resistant. By showing that this leads to a contradiction, we will be showing that with second-preimage resistance, you must have first-preimage resistance. Namely, we will show that the lack of first-preimage resistance is enough to break second-preimage resistance.

When breaking second-preimage resistance, we are given a random $x$ and the goal is to find another $x' \ne x$ such that $H(x') = H(x)$. Suppose we are given a random $x$. Then we can compute $H(x)$ and then use our preimage-finding algorithm (since this hash function isn't first-preimage resistant, remember?) to find an input $x'$ such that $H(x') = H(x)$.

The question becomes whether or not $x' = x$. For a hash function with an infinite domain, there are infinitely many inputs that $H$ maps to the same output. That is, there exist infinitely many second-preimages for any particular $x$; the question is whether or not we can find one.

Intuitively, the preimage-finding algorithm "should" give back an $x' \ne x$. After all, there are infinitely many inputs that map to the same output as $x$, so the probability that we find the exact $x$ we were given "should be" low, right?

So we should have an $x' \ne x$ such that $H(x') = H(x)$. But this is a second preimage! Thus, assuming that $x'$ indeed does not equal $x$, we cannot have a hash function that has second-preimage resistance but not first-preimage resistance. Thus, second-preimage resistance must imply first-preimage resistance. This is not a formal proof: just an intuitive argument.

The crucial assumption in this "proof" is that the domain is infinite. If it were not infinite, then all bets are off. In that case, the output size of the hash function needs to be sufficiently small relative to the input size for this argument to hold. I've written about that idea in great detail on my answer on the question "Pre-image resistant but not 2nd pre-image resistant?", so I refer you to that for more technical details.


Security of RSA public key depending on how it's computed I understand that the public key in RSA encryption may be computed using Euler's totient function or Carmichael's totient function.

I'm now trying to figure out how the choice of totient function affects the security of the public key, if any. Are there any ways in which a chosen totient function may make it easier or harder to compute the private key from the public key?

Edit for clarification: Are there any direct ways in which the choice of totient functions may affect the 'backtracking' process of figuring out the private key (d) from the public key (e)?

I'm now trying to figure out how the choice of totient function affects the security of the public key, if any.

Not at all.  The totient function used has absolutely no affect on the public key.  When you generate the public/private key pair, you usually select $p, q$ and $e$ (in some order), and then compute $d$ (using the totient); because the public key is a function of $p$, $q$ and $e$ (which were all selected before you used the totient), the totient has no impact on the public key.

The only effect it has would be on the $d$ parameter that is contained within the private key - we don't place that into the public key, and so the public key isn't affected.  And, even the holder of the private key (would can look at $d$) might not care - if he uses the CRT optimization, he would use the $p, q, dp, dq$ and $qInv$ parameters (which are also not affected by the totient) and typically ignore $d$.


When a client connects to a SSL/TLS encrypted server it hashes the certificate, right? This is a very basic question about hashing: When a client connects to a SSL/TLS encrypted server it hashes the certificate, right?

So, an attacker could steal the public certificate in the transfer and tell the victim that he is the server. Wouldn’t that be possible because the hash would be the same? (I know that this is impossible, but I don´t know why.)

The certificate isn't a secret. If all that's needed to impersonate a server was the certificate, everybody who ever connected to that server (which doesn't reject connections!) would be able to impersonate him.

What instead happens is the following:
The server sends a piece of data (the certificate) which binds a public key to a domain and potentially a company. This binding is done by a trusted CA and enforced with a signature which the client can verify.

In the next step one of two things happen:

The client encrypts the so-called pre-master secret with the public key from the certificate (which he knows belongs to the legitimate owner of the domain) OR
The server signs another (fresh) (DH) public key  which the client can verify was known to the legitimate owner of the domain. Now the client responds with his (fresh) (DH) public key.

Now there's a piece of information that only the legitimate owner of the private key associated to the certificate can know: Either the pre-master secret OR the private (DH) key. No matter which information is shared, now a "master-secret" is generated which cannot be pre-calculated because it includes randomness from both the server and the client. To finally verify both parties share the same master-secret (which is only possible if the server actually knew the private key from the certificate) they both exchange "secret-key-signatures" over all previous handshake messages and thus assure each other that they know the secret key. The identity of the server is thus confirmed (and not earlier than this).


What's wrong with this digital signature scheme? With regards to user authentication...

The server sends Alice a randomly chosen number.
Alice signs the number and sends the signature back to the server.
The server checks the signature using Alice's public key. If it's valid, the server accepts her connection request.

Suppose that Alice uses the same private key to log in to the server and sign her emails. The authentication mechanism signs the bare challenge without hashing, while Alice signs the hash of the email message.

Apparently, the server can forge emails from Alice under this scheme? If so, how could this be prevented?

Regardless of the possible answers here, which probably focus on some technical difference between the signature scheme for authentication vs the signature scheme for non-repudiation, the practical way to prevent this is to have at least two key pairs for the different use cases.

Alice would have a private key and matching certificate to perform the authentication. Preferably she would even have multiple ones for each use case, with access conditions matching the use case. Although this scheme uses signatures, it uses them just to authenticate Alice at a particular time and the signatures do not need to last.

Alice would have another private key and matching certificate to perform the signatures for non-repudiation. Non-repudiation is used for documents to show that a specific person has signed it; that person nor others cannot repute the signature: it must have been set by somebody who has access to the private key. These signatures are stored with the document so that they can be accessed later.

The private keys for non-repudiation generally need higher security than those for authentication. Signatures are stored, so the key size needs to be future proof. This difference is reflected in the certificate, which may for instance have to adhere to an established Certificate Practice Statement to be accepted - a self signed certificate created on your computer cannot be used to buy a house.

Old style Government ID cards commonly have three private keys and matching certificates on them: one key for authentication (to the OS, TLS or applications), one key for non-repudiation (a digital signature to replace the written signature you are used to) and one for decryption (to keep messages send to you confidential).


Hypothetical encryption technique, is it secure? This to me, sounds like a great idea, but with all rosy-tinted ideas it needs some grounding in reality. Here are the steps of the hypothetical system (with the hypothetical part highlighted):

User runs program to encrypt a file.

Prompts for user password.

Hypothetical part (is it secure?):

Program has a list of encryption techniques stored (assume the techniques are publicly known: they can be any level of complexity but how they encrypt is known) and their decryption counterparts.
Each symbol in the password selects a different technique (assume what symbol picks which technique are known: it can be changed but the changes are publicly known).
The program progresses through each symbol in the password encrypting the file with a different algorithm at each stage.
Each encryption technique can take one or all values from the password: the sum of symbols up to the current position (in the password), the sum of the entire password, and the position. These are used to modify the internal encryption process (the sum up to current position used as part of a modulus, for example). Which means if the letter is in the wrong place, it won't decrypt correctly.

Am I correct in assuming that:

A longer password adds more layers of encryption in this hypothetical scenario and thus adds more security and thus encourages longer passwords (a double positive trait)?
Even with the encryption algorithms known, because the password determines what order it's encrypted in, and how many layers, an attacker cannot guess how it was encrypted besides obtaining the password?
That no file (assuming each password is different) will be encrypted the same way twice?
The password is the only major vulnerability?

In short, is it secure?

Are there any flaws people could see with this idea?

First, I would like to point you to this answer. Copying the TL;DR from there:

  Multiple encryption addresses a problem that mostly doesn't exist.

You are better off using a single well chosen algorithm.

That said, here are answers to some of your questions:

  A longer password adds more layers of encryption in this hypothetical scenario and thus adds more security and thus encourages longer passwords (a double positive trait)?

It is not generally true that more layers equals better encryption (cf.  Cascade Ciphers: The Importance of Being First). In particular, in those cases where it can be proved that it is as strong as even one of the layers it is assumed that the keys are independent. Your keys are clearly not independent.

  That no file (assuming each password is different) will be encrypted the same way twice?

If by "same way" you mean into the same ciphertext, then that is already the case with any secure encryption algorithm (with high probability). If you mean with the same cascade, then probably so, if you have as many techniques as different symbols. I.e. a-zA-Z etc. all give a different algorithm. Otherwise some passwords that differ will still lead to the same cascade.

  The password is the only major vulnerability?

No, the algorithms can also leak information about the password through e.g. implementation mistakes or even weaknesses in the algorithm. And the more algorithms you implement, the higher the chances one of them is buggy. As an example of such a mistake:

  The program progresses through each symbol in the password encrypting the file with a different algorithm at each stage.

This is probably almost impossible to implement without timing attacks, so in any situation where the attacker would be able to observe how long it takes to encrypt/decrypt something, they could learn things about the password, narrowing down a brute force or dictionary attack even if they are unable to recover the whole password.

If you nonetheless wish to use more than one algorithm to guard against breaks, I recommend:

Use just two, always. That is simple enough to limit issues and the chance that both are broken should be small with modern well vetted algorithms.
Use stream ciphers (or block ciphers in CTR mode). Their cascade is provably as strong as the stronger if the keys are independent.
Use independent keys that you derive from the password using a strong password hash.
Add authentication.

For example, you could use AES-GCM(ChaCha20(m)), with keys derived using scrypt.


What is the purpose of an Authentication Tag in AEAD encryption schemes? AEAD encryption schemes produce something referred to as an "authentication tag." What does this tag consist of, what is its purpose, and is the tag itself human-readable data such as a plaintext string or is it cipher text?

What does this tag consist of ... is the tag itself human-readable data

It will most likely be a string of random looking bits. It is not intended or required for humans to participate in the verification process.

  what is its purpose

The algorithm uses it to verify whether or not the ciphertext and/or associated data have been modified.

If either the ciphertext or associated data has been modified, then the procedure that re-computes the validation tag on the receiving end will end up generating a different tag. The algorithm will check the re-computed tag against the tag that was bundled with the ciphertext and associated data (which collectively can be referred to as a "cryptogram").

If the tags don't match, that means some part of the ciphertext and/or associated data have been modified.

If the tags do match, that means that no part of the ciphertext and/or associated data have been modified*

* at least, there is a a high probability assuming that the keys have not been compromised and the authentication scheme is secure


What is arithmetic circuits indeed? I know that Boolean circuits and Arithmetic circuits are two different ways of representing a computation. But I want to know how to instantiate arithmetic circuits and it's computation in practice. For example, when we multiply two l bits numbers, we say that arithmetic circuits are efficient because it represent those two nums as two field elements, and only need 1 multiplication gate. But I don't understand: don't we have to represent those two nums in bits in machine code? And do we have to represent that multiplication gate in basic blocks such as and-gate/xor-gate...or is there a real circuit structure is multiplication gate?
Sorry for such a dummy question, but this confuse me for quite a long time and I can't find the answer by myself. So could anyone give me some guide or some paper to this question?
Great thanks.

The whole point is that in the Aritmetic Circuit (AC) model we take a field and use field operations (+,*) as building blocks.
Each field operation is represented as a single output multiple input gate.
The total number of gates and the depth of the AC are typical measures of complexity. Size and bit structure of inputs does not explicitly come into it, each operation is considered of some fixed complexity.
The goal is to find the minimum complexity circuit realizing a certain formula.


Hash email address with a non-random salt for moderate security? Crypto noob here. I have an application that has only moderate security requirements (internal use, limited audience). I want to send a unique url with a token in it to each user. If anyone has the url, they can submit information on the user's behalf.

Can I just hash their email with a secret salt to produce the same token every time? I realize these won't expire, and knowing the token lets anyone spoof the user, but these are acceptable for my application. When they submit information, I'm thinking I can just re-hash their email with the secret, and make sure it matches the submitted token.

Is this a bad idea? Which hashing algorithm should I use? Should I change my approach?

There's absolutely zero need to have the token tied to the user's email address.

Just add a column in the database for the token, generate the token randomly, and send it out to the user. If you want to go one step further, send the user the token, but only store $H(token)$ in the database, where $H$ is a sound cryptographic hash function of your choosing.


What is the PGP Web of Trust Strongset? I understand that it is a system that "establishes the authenticity of the binding between public keys and their owners", but how does one join this web of trust? Do you have to physically meet one of the existing members, and they can get you in?

The web of trust is no longer active. It was removed in GPG version 2.2.17.

The way it worked was that people would meet in person and sign each other's keys, then upload those keys and signatures to a network of "keyservers". Or maybe they'd just verify that email could be delivered to the other person. Or sign whatever they were asked to with no verification. In theory you could likely find some path of signatures back to a signature by someone you trust, thereby letting you establish a chain of authentication to believe that a key belonged to a given person, as long as everyone in the chain always actually did verification of all the keys they signed. In practice that was rarely done, people just trusted keys identity on first use.

Then in June 2016 the keyserver network was attacked in a way that fundamentally broke the whole thing. Anyone can add a signature attesting that a key in the keyserver is valid for the name it claims to be for. Anyone can add 150,000 such signatures. GPG breaks horribly whenever a key with more than about 150,000 signatures is used, or is anywhere in the chain of trust needed to verify another key. Someone signed a couple of popularly-used keys 150,000 times each, thus breaking GPG for everyone who was actually trying to use the Web of Trust.

So the Web of Trust was removed, the keyserver network is useless, and nobody really cares because no one really relied on it anyway.

And this is all without mentioning all the other massive vulnerabilities in the design and implementation of PGP/GPG, like its default to 1024-bit DSA keys with SHA-1 hashes (both broken), its common doomed attempts to encrypt email, lack of forward secrecy, use of RSA for encrypting, extremely complicated interface, long-lived identity keys, ease of creating colliding key fingerprints, etc, etc. It's a long, long list and not entirely on-topic to this answer.


functional encryption over homomorphic encryption I recently read about "functional encryption" which seems interesting, although I didn't understand yet how it works ... but is it possible to combine it or adapt it with homomorphic encryption in the context of neural networks particularly.
Suppose you have a neural network that you run over some data encrypted homomorphically (say paillier for example) ..
linear computations will be performed without any problem ..
but the only issue will be with activation functions which are non linear, and thus require to decrypt the intermediate results (weighted sums) in order to apply the activation functions ...
in case we don't want to disclose the private key, can we use something like functional encryption in order to allow the application of activation functions only, something like a special private key that allows only a specific activation function to be performed, and do not allow to decrypt any other information ?!

The main difference between FE and HE is that:
In HE, for the decryption you need to interact with the owner of the secret-key, but in FE everybody who has access to the ciphertext and functional key can decrypt the massage.
While HE can efficiently support different kinds of computation over encrypted data, FE supports limited class of functionality (in theory it still can support general functionality).
This limited class includes: inner-product (which might be what you called weighted sum) and quadratic functionality.
Recently there has been a European Project called FENTEC, they are trying to implement the existing FE schemes.


Definition and meaning of "semantic security" I'm taking a Coursera cryptography course. The definition of semantic security is hard to understand. I tried to restate it with some slight changes (the word "efficient" was in the original definition). Have I gotten it right?

  The adversary chooses two messages: $m_0, m_1$.
  We encrypt one of these messages: $c \leftarrow E(k, m_b)$.
  The adversary has to guess which message was ciphered.

  There are two events: $M_b = \{ \ \text{adversary $A$ decides that $m_b$ is ciphered} \ \}$.

  $E$ is semantically secure if for all "efficient" adversaries $A$
  advantage $\operatorname{Adv}[A, E] = \big| \ \Pr(M_0) \ - \ \Pr(M_1) \ \big|$ is negligible.

This means the adversary can't tell which of the two messages is ciphered.

What if it could? What does this definition mean in practice?

Update: in the original definition (which is given on a diagram and wasn't stated clearly) there is a concept of two experiments, $exp(b)=1$ when the adversary decides $m_b$ is ciphered. And events are: $M_b = \{ \ \text{$exp(b) = 1$} \ \}$. I don't get this part of definition.

What if it could? What does this definition mean in practice?

Consider $M_0=$ attack and $M_1=$ don't attack. If the adversary can distinguish which message you are sending to your troops, they can optimize their strategy to defeat you.

Another example. Say you are casting a yes ($1$) no ($0$) vote for a proposed piece of legislation. If the adversary can distinguish between yes and no votes, they might be able to throw the election (by discarding votes that don't go their way) or persecute you according to your vote.


Can Reed Solomon parity blocks be used as an all-or-nothing transform? Consider the following scheme:

Perform an (N,N) Reed-Solomon encoding (i.e. N data blocks, N parity blocks)
Drop the N data blocks and keep only the N parity blocks.

Are these N parity blocks an all-or-nothing transform? (meaning missing even one parity block does not permit decoding the original data blocks)

Reed-Solomon codes are Maximum-Distance-Separable codes and thus have the property that in a $[n,k]$ RS code ---- meaning than there are a total of $n$ blocks of which $k$ are data blocks and $n-k$ are parity block ($n=2N$ and $k=N$ in the OP's notation) ---- any $k$ blocks are sufficient to reconstruct the entire codeword, that is, all the blocks can be found if we know $k$ of them. Note that it does not matter whether the $k$ blocks available are a mixture of data and parity blocks or parity blocks only, just as long as $k$ blocks are available.

So, in the scheme envisioned by the OP, if one has a $[2N,N]$ Reed-Solomon code ($N$ data blocks, $N$ parity blocks, for a total of $2N$ blocks) and keeps only the $N$ parity blocks, the $N$ data blocks can be reconstructed. If fewer than $N$ of the parity blocks, then the data blocks cannot be reconstructed in the sense that the decoder can come up with a list of $M$ possible candidates for the $N$ data blocks but cannot say which of the candidates is the correct one.  Here, each of the $M$ candidates on the list is a vector $[D_1, D_2, \ldots, D_N]$
of $N$ data block (each $D_i$ is a data block) and the decoder cannot determine which is the correct vector of $N$ data blocks. What is $M$?  Well, $M$ is the number of possible distinct values that each data block might have and thus is either the number of elements in the finite field over which the Reed-Solomon code is defined, or some power $L$ thereof if each data block is a vector of length $L$ over the finite field (and we are using an interleaved Reed-Solomon code). Either way, $M$ is pretty large.


If you hashed a hash an infinite number of times would you end up with a unique hash? If you took a hashing algorithm for example MD5 and repeatedly passed the output hash back into the algorithm an arbitrarily large number of times would you eventually end up with one unique hash?

My idea is that the maximum number of hashes initially is $2^{128}$ however if you feed the hash back into the algorithm there would be collisions so two or more input hashes will map to one single output hash thus reducing the entropy, if this process is repeated indefinitely would it result in one single hash? or is it possible that there would be a point after which no collisions will ever happen?

This is a thought experiment and is probably not possible but I would like to know.

If you repeatedly apply a generic function on its result, in a finite domain, you tend to obtain a "rho" structure: at some point, you enter a cycle whose length is (roughly) $\sqrt{N}$, where $N$ is the size of the output space for your function. In the case of MD5, $N = 2^{128}$ (MD5 outputs 128-bit values), so the cycle will have length about $2^{64}$ values. You can hash "infinitely", you will never end up on a unique value. See this answer for some details and a picture.

Well, strictly speaking, you might end on a unique value, which would be called a fixed point, but we don't know if such fixed points actually exist with MD5. For a randomly selected function, there is a probability of about $63\%$ that a fixed point exists at all. But existence of a fixed point does not mean that you will reach it. In fact it is expected that for most cases you will end in the "big inner cycle"; if there is a fixed point at all, you will ultimately hit it only with probability $1/\sqrt{N}$ or so, i.e. pretty rarely.

In all generality, when starting from some input and hashing repeatedly, you always end up walking a cycle, and that never ends. A fixed point is a special case of a cycle with only one element. For a given function, one expects that
there is a "big" cycle that you ultimately reach for most inputs, and a collection of much smaller cycles that you almost never reach.


What is a 'known answer test' (KAT)? Came across this concept on while reading up on the key-encapsulation protocol SIKE but haven't been able to find a good explanation of what a known answer test is formally.

What is a known answer test, and why is it useful?

What is a known answer test

It appears to be a publicly available set of parameters and values that allow you to check the correctness of an implementation.

If so, then they're more commonly referred to as "test vectors".

  why is it useful?

Since the output of cryptographic algorithms are almost invariably supposed to "look random", it is very hard to know whether or not things are functioning correctly by just looking at the output.

With outputs that are known to be correct, you can supply the corresponding parameters to the software and test your outputs against the known correct answers.

If the two do not match, then something is wrong with the implementation that you're testing.

If the two do match, then it is probable that the implementation is (at least partially) correct.

It is possible to pass one test and fail another due to some kind of programming error, so a passing unit test does not mean that the implementation is guaranteed correct with 100% certainty (but it is probably correct with high probability if it passes all of the tests).


How to get the original list back given a shuffled list and seed? Say I have a shuffled list that was shuffled in Python using random.shuffle(). The shuffling was performed using a seeded random number generator. Is there a way I can get the original list back, i.e. un-shuffle the list?
eg list1=[1,4,2,5] after seeding random and shuffling list2=[5,2,1,4] is there a way to get back list1 if we only have knowledge of list2 and seed value

Yes. Throughout this, I will make the assumption (which appears to be the case) that random.shuffle() permutes the list in a way that only depends on:

The seed used
The length of the list being shuffled

This is to say that, for a fixed seed and fixed length of a list (say $n$), random.shuffle() chooses some permutation $\sigma\in S_n$, and then sends the list:

$$[a_1,a_2,\dots, a_n] \mapsto [a_{\sigma(1)}, a_{\sigma(2)},\dots, a_{\sigma(n)}]$$

For example, if $n = 4$, and $\sigma$ sends $1 \to 2$, $2\to 4$, $3\to 3$, and $4\to 1$, then for any initial list $[a_1, a_2, a_3, a_4]$, random.shuffle() will permute it to $[a_{\sigma(1)}, a_{\sigma(2)},\dots, a_{\sigma(n)}] = [a_2, a_4, a_3, a_1]$.

Let $ls = [a_1,\dots, a_n]$ be the (initial) list you care about, and let $\sigma(ls) = [a_{\sigma(1)},\dots, a_{\sigma(n)}]$ be the shuffled version of it.
We can "unshuffled" it by using our prior assumption about random.shuffle() to "find" the permutation $\sigma$ that was used before.
In particular, if we set the seed the same, and use a list $\mathsf{perm} = [b_1,\dots, b_n]$ of the same length, we'll have that:

$$\sigma(\mathsf{perm}) = [b_{\sigma(1)}, b_{\sigma(2)},\dots, b_{\sigma(n)}]$$
Then, if we have some way of restoring $\sigma(\mathsf{perm})\mapsto \mathsf{perm}$, we can simply "do these same steps" to $\sigma(ls)$ to recover $ls$.

Because of this, a particularly easy choice of $\mathsf{perm}$ to work with is $\mathsf{perm}= [1,2,\dots,n]$ (we can return to it via sorting).
Note in that $b_i = i$, so $\sigma(\mathsf{perm}) = [\sigma(1),\dots, \sigma(n)]$.

One particularly easy way to "sort $\sigma(\mathsf{perm})$, but apply the same sequence of transpositions to $\sigma(ls)$" is by creating the "zipped list":

$$\mathsf{zipped\_list} = [(\sigma(ls)[0], \sigma(\mathsf{perm})[0]), (\sigma(ls)[1], \sigma(\mathsf{perm})[1]), \dots, (\sigma(ls)[n], \sigma(\mathsf{perm})[n])]$$

Note that each part of each tuple has been permuted precisely the same way! So we can view this as:
$$\sigma([(a_1, 1), (a_2, 2), \dots, (a_n, n)])$$
I.e. our initial list, along with the list $[1,2,\dots,n]$, with the same permutation applied to both of them.
We can then remove this permutation by sorting this larger list based on the second component of each tuple.
This will return the list $\sigma([1,2,\dots,n])$ to $[1,2,\dots,n]$, and will therefore return $\sigma([a_1,\dots,a_n])$ to $[a_1,\dots, a_n]$ as well (as the same sequence of moves, which "cancel out" $\sigma$, are being applied to each list).

In case this theoretical description of what's happening is still not clear, the following python3 code should demonstrate that this works.
I've additionally uploaded it to an online interpreter here.

import random

def shuffle_under_seed(ls, seed):
  # Shuffle the list ls using the seed `seed`
  random.seed(seed)
  random.shuffle(ls)
  return ls

def unshuffle_list(shuffled_ls, seed):
  n = len(shuffled_ls)
  # Perm is [1, 2, ..., n]
  perm = [i for i in range(1, n + 1)]
  # Apply sigma to perm
  shuffled_perm = shuffle_under_seed(perm, seed)
  # Zip and unshuffle
  zipped_ls = list(zip(shuffled_ls, shuffled_perm))
  ls.sort(key=lambda x: x[1])
  return [a for (a, b) in ls]

These should satisfy, for any list ls, and any choice of seed, that unshuffle_ls(shuffled_under_seed(ls, seed), seed) == ls, which you can experimentally validate.