Protecting a short password I figured that a really secure password would be an AES 128 key. If this key were to be base 64 encoded, I could replace 4 random bytes in it in order to make it unusable unless you know which bytes were replaced and by what.

The process would be like this:

generate a key: [²ú·0ýóQS%ô6
base64 encode it to make it readable: iVuy+rcw/fNRU56AiiX0Ng==
replace 4 random bytes of it iVuy+icw/fNRG5oAiiJ0Ng==

I would remember what the 4 bytes are i.e. the password
the computer would remember which bytes got changed (in this case: 13, 6, 19, 15) and in what order

My question is: how difficult (how many attempts) would it be to guess the correct key if you got hold of the original.

Another way of asking this is: how long has the key to be in order to make it difficult (several decades of guessing with a super computer) with changing just 4 random bytes.

I guess there is a simple mathematical formula to calculate this. But I don't know it.

thank you for your support

The adversary has

a ciphertext encrypted under your key;
a copy of the key with $k$ bytes erased; and
knowledge of which $k$ bytes have been erased.

The adversary can try to decrypt the ciphertext and decide if the decryption makes sense in time $T$.

To find the key, the adversary need only do $2^{8k}$ trial decryptions, for a total time cost of $2^{8k} T$.

The key point is that there's usually no sensible way to make $T$ big.

Ergo, when $k$ is $4$, this is obviously easy.


Can i XOR an array of bytes with an equal length key securely If i have say 64 bytes, can i XOR those bytes with another 64 random bytes, and have two new arrays, where both are needed to reconstruct the first?

Intuetively i need some symmetric encryption like AES, but i cant figure out how the XOR above can be attacked. Does the content matter?

If i have say 64 bytes, can i XOR those bytes with another 64 random bytes, and have two new arrays, where both are needed to reconstruct the first?

This is known as XOR secret sharing or in the case of two splits also known as a the (binary) One-Time-Pad.

Indeed if for every execution of the split-up operation a new independent random string is used then always both (/all) shared parts are needed for reconstruction. Any less number of shares / parts leaks no information about the shared message except for the length and what was already known anyways.

Note though that this provides no protection against tampering, i.e. if somebody flips a bit in either share and the other(s) doesn't then the reconstructed message will have the bit flip without a strong cryptographic guarantee of this being noticed.

Also note that security breaks down horribly if the same randomness is used with two different messages. Of course if you re-use randomness for the same message then an adversary can notice that.


Does RC4 continue to be used anywhere? RC4 in TLS is now broken. But the breaking seems to have a lot to do with how web transactions work in general. Is there any application outside of the web where RC4 is still used? I know that WEP is long out of the window. Any other widely used applications?

RC4 seems to be an option in the SSH1 and SSH2 protocols, so yes, it is still in use as cipher. AES seems to be preferred in most configurations, but "arcfour" is still often used as fallback.

WPA and WPA2 may also use RC4 instead of AES, using TKIP. Again, this protocol was introduced to replace the broken WEP protocol while still relying on the faster RC4 protocol. So it's still often used as fallback in case WPA2 with AES is unavailable, e.g. on older hardware without hardware AES support.


Why do people worry about the exceptional procedure attack if it is not relevant to ECDSA? The exception procedure attack is described here:
https://www.iacr.org/archive/pkc2003/25670224/25670224.pdf

People are afraid of this attack, because it could leak information on the private key in exceptional cases. [pun intended]

The assumed scenario for this attack is illustrated below:

If the attack is "not relevant to ECDSA, because the base point of ECDSA is usually fixed as the system parameter" then why do people worry about this attack?
The authors also note that "When the order of the elliptic curve is divisible by
a small integer, the curve has several exceptional points. In other words, the
curves whose order are prime are secure against the proposed attack, namely
the recommended curves in several standards" The NIST curves have an order that is prime as well, then why do Tanja Lange and Daniel Bernstein mention this attack as a reason why the NIST curves are insecure, if the attack wouldn't work against these standardised curves?

Regarding your first question:

It is relevant for the Elliptic Curve Diffie-Hellman (ECDH) key exchange. In this scenario the user performs a scalar multiplication with the other user's public key, which is a variable point chosen by a possible attacker.

Note that another reason for the attack to not apply on ECDSA is because the scalar in ECDSA is a randomly selected integer different for each signature, which makes the attack ineffective as the attacker needs to test several base points with the same target scalar.

Regarding your second question:

It is not that simple. There might be condition where exceptions occurs even on prime order curves. For example if you don't restrict your scalar to be smaller than the curve's order or if you do a computation different from the classic double and add or if you don't use the standard formulas to achieve regularity (as the formula of Brier and Joye) or speed (as for example some Co-Z formula).

One of the point djb is making is that using the montgomery ladder on montgomery curves is extremely efficient and exception-free that you don't want to consider other solutions. And that works very well for ECDH.
While for signatures you might rely on Twisted Edwards where similar properties apply.

Overall the message is not that we can't do exception free constant time implementation on the good old prime order curves. It's just that it is not as simple and in particular not as efficient then do it on Montgomery or Twisted Edwards curves.


Pedersen commitments in bulletproofs In Bulletproofs range proof, Pedersen commitments look like $C=aG+bH$

If I need to proof several values' range proof and keep G as constant, do I need to change H everytime?

I have found it doesn't change in Grin and dalek-cryptography.

Pedersen commitments fulfil two basic properties:

Perfectly hiding.

Since $b$ is uniformly random, $C=aG+bH$ can become any element of the group, independent from the randomness of $a$.

Computationally binding.

If I don't know the discrete logarithm relation between $G$ and $H$, I cannot cheat by opening $C$ to a different $a,b$ pair.

Additionally, Bulletproofs relies on Pedersen commitments being additively homomorphic: for another commitment $C'=a'G+b'H$, we have that $C+C'$ is a commitment to $a+a',b+b'$. To see this: $C+C' = (a+a')G+(b+b')H$. For this to work, we need $H$ to be a fixed point.

So, to sum up: $H$ shouldn't change because we require additive homomorphism, and $H$ does not need to change because it already provides perfect hiding!


Does the time to evaluate a hash function depend on the function input size? Suppose we have a (variable-input size) hash function modeled as a random oracle. Can it be consistent to say that the time to evaluate this function depends on the input size ?

It all depends on how you define the machine that implements the random oracle. Consider this pseudo code random oracle that uses a hash table:

def rand_oracle(input, hash_table):
    input_hash_key = get_hash(input)
    if input_hash_key in hash_table:
        return hash_table[input_hash_key]
    else:
        return something truly random

You need to compute the input_hash_key by using the get_hash function. This function is usually implemented so that it's dependent on the length of the input.

Also, the line "if input_hash_key in hash_table" implies there is a test for hash collisions if any. This usually happens by comparing the input bits against the found entry. If they match (bit/byte by bit/byte), it's not a collision, else it's a collision.

So it all depends on how you view your machine that is implementing the random oracle. At some point, there are analysis that need to be performed for a length that is always dependent on the input length.

I think your confusion is from the fact that hash tables can perform lookups that are in the asymptotic worst run time complexity set O(1) if there is no hashing collisions -- yes this is the lookup/search time for the right entry, which different the time needed to generate the hash.


Is 512 bits a more secure hashing than 256 bits? I know that 512 bit hashing is more secure, but I don't really know why. I hope someone can help me to better understand it in more detail.

When there is no known weakness in the hash function we talk about their generic1 resistances

Pre-image resistant: given a hash value $h$ find a message $m$ such that $h=Hash(m)$. E.g., consider storing the hashes of passwords on the server. An attacker will try to find a valid password to your account.

Second Pre-image resistant: given a message $m_1$ is should be computationally infeasible to find another message $m_2$ such that $m_1 \neq m_2$ and $Hash(m_1)=Hash(m_2)$, e.g., producing a forgery of a given message.

Collision resistance : it is hard to find two distinct inputs, $a$ and $b$, that hash to the same output $a$ and $b$, i.e., $H(a)= H(b)$ and $a \neq b.$

A hash function with output size $n$ is expected to have $\mathcal{O}(2^n)$ pre-image resistance and secondary image resistance and $\mathcal{O}(\sqrt{2^n)} = \mathcal{O}(2^{n/2})$ collision resisance. The collision resistance is less due to the birthday paradox (attack).
If we plug 256 and 512 into those equations you will see that

256 has $\mathcal{O}(2^{256})$ pre and secondary and $\mathcal{O}(2^{128})$ collision resistance, whereas
512 has $\mathcal{O}(2^{512})$ pre and secondary and $\mathcal{O}(2^{256})$ collision resistances.

As a result, as long as there is no specific weakness in the (unspecified) hash function the larger the output the better the resistance they will have.
When the hash function is specified then one can talk about their resistance in all directions. For example;

Standard Merkle–Damgård constructions (MD) (MD5, SHA-1, SHA-2) are vulnerable to length extension attacks, however, sponge constructions (SHA3) and HAIFA based (e.g. BLAKE(2)) are not. Note that after SHA3, there are variants of SHA-2 that have resistance against length extension attack like SHA512-256,

Herding attack for MD constructions is introduced by Kelsey and Kohno in 2005 and applied to MD5 Finding Preimages in Full MD5 Faster Than Exhaustive Search with Chosen Target Forced Prefix Pre-image resistance

Chosen-prefix collision on SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust, 2020. List of attacks on SHA-1 can be found 1,2

The relations of the generic resistances are, in simple terms,

Collision resistance implies 2nd-preimage resistance of hash functions, see a detailed work on our site

2nd-preimage resistance implies preimage resistance, see the proof on this site.

The formal definitions of the resistance and modern cryptographic deal of the above facts and more provided in the novel article; Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance by P. Rogaway and T. Shrimpton on 2009.

1 The term generic is used when a resistance ( or the attacks) applies all of the hash functions. This term similarly used in other cryptographic contexts, too.


Using an AES-256-GCM key as a salt to SHA-256 Assume 256 bit keys are randomly generated and data is encrypted using AES-GCM-256 prior to being sent to a server.

The goal is to enable the server to determine uniqueness of data it receives without actually revealing the plaintext data.

Would it be safe to use SHA-256 where the input to the hash function is the key in addition to the plaintext data -- so SHA-256(key + plaintext)? By safe I mean does doing this reduce the safety properties of the key by a significant margin?

If not safe, how large of a random byte string is needed to make the SHA sufficiently difficult to brute force?

I'd split the key into two 256 bit keys using HKDF, and use one key for the GCM mode, and the other for the hash over the plaintext. However, I then would use HMAC rather than SHA-256 as it accepts and the key as a separate entity in the application.

The advantages of the HKDF key derivation function is that there is more "distance" between the keys used for the authenticated encryption and hash function. That said, just reusing the key is not likely to introduce direct vulnerabilities. It's also more "neat" using a KDF to derive other keys for other purposes, from a single shared secret key.

The advantage of using HMAC is that you are protected against length extension attacks. Furthermore, HMAC explicitly accepts a key rather than just data, so the key may be better protected against attacks, depending on the system that it is used on of course.

Otherwise, yes, using a hash over the shared secret and data may be used to determine uniqueness (well, with a high degree of certainty in the case of cryptographic hashes, of course), assuming that the key doesn't change during the time that this property is required. So yeah, I don't see how this would not work (but please don't view that as scientific proof).


Designing a simple challenge-response symmetric mutual authentication protocol I am designing a protocol that 2 devices will use to mutually authenticate over an unreliable, unsecure channel. The system must be fast and low-power, so symmetric cryptography is a requirement. I was thinking of using a challenge-response protocol, but cannot find existing ones that offer mutual authentication and use keys instead of passwords; so I decided to design my own and wanted your opinion.
Let Alice and Bob be 2 parties, with their respective identities encoded as $id_A$ and $id_B$. They share a symmetric key $K$ of 128 bits or more. Note: it's a key, not a password. $n_A, n_B$ are true-random nonces. $hash$ is a secure one-way function without length-extension vulnerabilities, like SHA3 or HMAC-SHA256.
The "simple version" of the protocol would be this one:

$A \rightarrow B: id_A, n_A$ --- challenge
$B \rightarrow A: id_B, n_B, hash(K||n_A)$ --- response and 2nd challenge
$A \rightarrow B: hash(K||n_B)$ --- 2nd response

I also have a "hardened version" like the following, where I'm adding better MACs, binding between messages and hardcoded values (1, 2 and 3) in the hashes to enforce a message order and difference between them.

$A \rightarrow B: id_A, n_A, hash(K||1||id_A||n_A)$ --- authenticated challenge
$B \rightarrow A: id_B, n_B, hash(K||2||id_A||n_A||id_B||n_B)$ -- response and authenticated 2nd challenge
$A \rightarrow B: hash(K||3||id_A||n_A||id_B||n_B)$ --- response to 2nd challenge

My question is: which one should I use? Is the "simple" enough? Is the "hardened" overengineered? Is there a better protocol out there with this level of simplicity?

You probably want to use HMAC instead of any hash function.
I will use the notation $H(K, x)$ to denote a keyed MAC.
Your simple protocol version seems to allow a reflection attack.
First the adversary $A$ initiates a session with $B$:
$A \to B$: $\mathrm{id}_A$, $n_A$
$B \to A$: $\mathrm{id}_B$, $n_B$, $H(K, n_A)$
Then $A$ initiates a second session with the nonce $n_B$:
$A \to B$: $\mathrm{id}_A$, $n_B$
$B \to A$: $\mathrm{id}_B$, $n_B'$, $H(K, n_B)$
Now $A$ sends $H(K, n_B)$ to Bob in the first session:
$A \to B$: $H(K, n_B)$
You always want to include the message number, and additionally, who is sending the message and who is receiving the message. You also want to authenticate every piece of that information.


How to change the following commitment scheme to Pedersen commitment? In my question here Zero knowledge set membership protocol

The suggested solution allows a prover to choose a commitment $C$. Then, A trusted third party ($T$) can validate if $C$ is valid or not. The $C$ is in form of $C = rG + [age]H$. How to make a similar protocol with $C = g^{r}h^{[age]}$ as in Pedersen commitment scheme where $g,h$ are elements in a group $G$ of prime order $q$

Here is the answer form the previous question:
Notation:
$P$ is the prover, $T$ is the trusted party, $V$ is the verifier, $a$ is the information to convince $T$ of $P$'s age, $A \rightarrow B: x$ means that party $A$ send information $x$ to party $B$.

$P$ chooses a random $r$ and calculates the commit $C = rG + [age]H$.
$P$ signs $a$ with $r$ as private key
$P \leftarrow T: C,a, signature_a$
$T$ looks up $P$'s age, calculates $R=C-[age]H$, verifies $signature_a$ against $R$ and sign's $C$ using $T$'s private key.
$T \rightarrow P: signature_c$
$P \rightarrow V: C, signature_c, proof$

My answer one the other question assumed that you use elliptic curves as they usually are more common when it comes to ZKP because of their size and speed, however, you can easily change the notation since

$xG$ is equivalent to $g^x\ (mod\ p)$
$A+B$ is equivalent to $A\cdot B\ (mod\ p)$

I will not explicitly write $(mod\ p)$ from now on.

$P$ chooses a random $r$ and calculates $C=g^r h^{[age]}$.
$P$ signs $a$ with $r$ as private key.
$P \rightarrow T: C,a, signature_a$
$T$ looks up $P$'s age, calculates $R = C \cdot h^{-[age]} = g^rh^{[age]}h^{-[age]}=g^r$, verifies $signature_a$ against $R$ and signs $C$ using $T$'s private key.
$T \rightarrow P: signature_C$
$P \rightarrow V: C, signature_C, proof$


Hill Cipher known plaintext attack I know a plaintext - ciphertext couple of length 6 for a hill cipher where its key is a [3x3] matrix.

Based on what I've read and learned, to attack and crack keys of [n x n], if we know a plaintext - ciphertext duo of length $n^2$ then we have our set of n equations with n variables, and this is generally solvable. However in my case there is only length of $6$ instead of $n^2 = 9$ .

My question is, how will I solve this problem and find the key? Or, since this is an obvious homework question, what should be my way of thinking? I cannot think of anything else but matrix multiplications and inverses but they do not help me at all.

Well, I went and solved the puzzle using brute force and Maple.  I won't spoil the actual answer, but here are some tips that ought to make the process a bit more quicker.

Solving the linear system modulo 2 gives you the parity of the second and third letters of the unknown plaintext.  Note that all vowels in the English alphabet map to even numbers using the standard Hill cipher encoding!
Conversely, solving the system modulo 13 tells you the fourth letter of the unknown plaintext (up to rot13).  This, together with the mod 2 solution, should help you guess what the second and third letters could be.
Even after correctly guessing the second and third letters, and ruling out any non-invertible decoding matrices, the modulo 2 solution will still not be fully determined.  Thus, some brute force and/or guesswork will be required to decode the remaining letters.  Hopefully, however, one of the possible plaintexts will show up as obviously more plausible than the others.

Ps. One more hint: 007.


Oblivious transfer where neither party learns the index of the message In a traditional oblivious transfer setting, the sender has a list $(x_1, x_2, ... , x_n) \in G$ where $G$ is the chosen group. The receiver has $b \in \mathbb{N}$, such that engaging in the protocol the receiver is given $x_b$ and the sender does not learn $b$.
Presume I want a slightly different procedure, where the receiver gets a random $x_i$ and neither the sender nor receiver learns $i$.
Is there a name for protocols with this behavior?

The simplest way to do this would be to have the sender randomly shuffle the elements. The receiver chooses a random element to request. That way the receiver has no idea which of the original (before the shuffle) elements he got.


Why a Blockchain cannot confirm "Membership Proof" as can a Merkle Tree? I'm currently reading the Princeton Blockchain Book, and came across this concept:

  Proof of membership. Another nice feature of Merkle trees is that, unlike the block chain that we built before, it allows a concise proof of membership.

The idea(from what I understood) is that, in the Merkle Tree, when we have a data block we can simply traverse the path towards the root, and then confirm that the root is indeed the correct one, hence confirming membership of said block. Why would one not be able to do that in a Blockchain, since it's an acyclic data structure and any valid block would allow us to reach the root?

Nevermind, I just realised that the statement says

  a concise proof of membership

Indicating that the Blockchain has indeed proof of membership, just one not as efficient.


Attacks on elliptic-curve based cryptosystems through solving the Decisional Diffie-Hellman Problem with the Weil Pairing Are there any examples of practical attacks on cryptosystems set over elliptic curves which utilize the easiness of DDH for certain choices of curves $E(\textbf{F}_q)$, and as such their lack of semantic security? I'm looking for something along the lines of using the Jacobi symbol to narrow the set of possible plaintexts (and therefore cards) against the SRA algorithm in the original Mental Poker proposal.

For instance, Elliptic Curve ElGamal Encryption doesn't seem to omit one. As the ciphertext is $(rP, M + rQ)$, where $r \in \mathbb{Z}$ is random and private, $M \in E(\textbf{F}_q)$ is the plaintext, and $P, \, Q \in E(\textbf{F}_q)$ are public, even if an attacker who can solve the DDH can distinguish elements of the ciphertext, the randomness of $r$ would seem to prevent them from narrowing the search space.

My inclination is no, since the relevance of semantic security predates the advent of ECC and so such an attack would likely have at least been considered heuristically, but I figured I'd see if anyone was aware of anything.

Proposition  One-wayness of ElGamal encryption holds under the Computational Diffie-Hellman (CDH), and conversely.

CDH Problem (informally) Given $(P, [r]P, [s]P)$ find $[rs]P$.

Let the public key be $Q = [s]P$ where $s$ is the corresponding secret key.  Let also a ciphertext $C = (C_1, C_2)$ with $C_1  = [r]P$ and $C_2 = M + [r]Q$ for a message $M$ (viewed as a point on an elliptic curve).

Proof (of the proposition):

If you can solve the CDH then you can break the one-wayness of the encryption.
Suppose you are given a ciphertext $C = (C_1, C_2)$, the goal is to recover the corresponding plaintext. On input $(P,C_1,Q)$, you first obtain $[rs]P$ by solving the CDH. Next you recover the plaintext as $M = C_2 - [rs]P$.
If you can break the one-wayness of the encryption then you can solve the CDH.
Suppose you are given a DH triple $(P,[r]P,[s]P)$, the goal is to obtain $[rs]P$.  You define the ciphertext $C = (C_1,C_2)$ where $C_1 = [r]P$ and $C_2$ is a random point.  You define the public key as $Q := [s]P$.  You recover the corresponding message $M$ (because you can break the one-wayness) and find $[rs]P$ as $[rs]P = M - C_2$.


How to calculate y value from ((y*y) mod prime) efficiently i am working ECC-224 bit. can any one tell me, how to calculate y value from ((y*y) mod prime) efficiently for large bit numbers.

By "ECC-224", I suppose that you mean "NIST curve P-224". This actually matters.

To compute the square root of $z$ modulo a prime $p$, there are several methods which depend on $p$. If $p = 3 \pmod 4$ then it suffices to compute:

$$ y = z^{(p+1)/4} \pmod p$$

If $z$ is indeed a square, this will yield a value $y$, and the other square root will be $-y$ (to check whether $z$ is really a square, just compute $y^2 \pmod p$ and see if it yields back your value $z$ or not).

Now, in NIST curve P-224, computations are done modulo a prime $p$ which is such that $p = 1 \pmod 4$, and the method above does not work. You have to use Tonelli-Shanks algorithm which is slightly more complex, and, in the general case, requires knowledge of a value modulo $p$ which is not a square (half o values modulo $p$ are not squares, so finding one is not hard, but this is enough to make the algorithm, in all generality, probabilistic).


How do we guarantee plaintext is coprime in RSA? The specifications for RSA state: $P^{\phi(N)} \equiv 1 ~mod~N$ if and only if $P$ and $N$ are coprime. Here $P$ is the plaintext and $N$ is the product of two suitable primes $x_1, x_2$. My question is how do we guarantee that $P$, the plaintext will be coprime to $N$? Thank you in advance!

If you can efficiently find a $P$ that is not coprime to $N$, then you can easily factor $N$ (use GCD). If you know the factorization of $N$ (say $N=pq$), you can easily find a $P$ that is not coprime to $N$ ($kp$ for some constant $k$).

This established the fact that finding $P$ not coprime to $N$ and factoring are equivalent problems.

Now, how many numbers are there less than $N$ that are not coprime to $N$? Well, we know that there are $\varphi(N)=(p-1)(q-1)$ numbers less than $N$ that are coprime to $N$. So, there are $N-\varphi(N)=pq-(p-1)(q-1)=pq-pq+p+q-1=p+q-1$ such numbers. This is actually a fairly large number (for 2048 bit $N$, $p$ (and $q$) would each be 1024 bits). But, it is minuscule in comparison to $\varphi(N)$, which is the number of numbers that are coprime. So, a random number is, with overwhelming probability, not coprime to $N$. At the moment, the best method for finding such a $P$ is to first factor $N$.

So, to answer your question, you don't have to worry about $P$ not being coprime to $N$. If you ever find one that isn't, bad things will happen. Your odds of a $P$ not being coprime are smaller than winning the lottery and getting struck by lightning twice, all in the same day.


Blowfish encryption with different keys produces same ciphertext I have set up a test app with Blowfish encryption taken from someone else's library. I have been astonished to find that password "Test" gives the same encrypted text as password "TestTestTestTest". Is this normal behavior of the algorithm or is it a bug?

It looks like the library is treating the string as the key to Blowfish, which has a veriable key size; the way the keysetup is done (with a cyclical use of the key bytes, see more details on the Wikipedia page) implies that key $k$ of length $n$ and key $k||k$ of length $2n$ have the same expanded key and thus an equivalent encryption/decryption function. Your "Test" example also illustrates this.

Usually from a string a key is "derived" using a KDF, which is then input to an algorithm that accepts keys of some fixed sizes like 128 bits etc. But Blowfish can accept 1 byte keys, and 300 byte keys too, so libraries often don't do this an accept the key input 'as is', without KDF being compulsory. Or they "pad" a string like 'Test' to 16 bytes with 0-bytes etc. Be sure you know what a library does before using it. Keys should be random and unpredictable, not dictionary words.


Very difficult hashing function? I am looking for a very difficult/slow hashing function to hash secrets used to decrypt env files. Because it is used to log when the env files "keys" get recreated I don't need it to be fast, ideally close to a full second to calculate because I will be in trouble if the keys get stolen but I want to log when I changed them and log a hash of the keys so I can debug in the future.

Argon2.

Argon2 is the current standard for password-hashing schemes, which are designed to be slow and more importantly expensive to parallel adversaries, even if they have hardware support. You can tune its speed via the memory and the time parameter, either of which should affect run-time linearly. Anyways, the paper in the repository should contain a guide on how to experimentally configure the parameters for your application.


Automated security protocol verification tool for eCK model I want a tool that (runs on Win7 and) can perform automated verification of a protocol in the eCK security model as described in Microsoft Research's paper "Stronger Security of Authenticated Key Exchange".

Does anyone know such a tool?

Just wrapping my comment into an answer as it seems to be what you're looking for…

CryptoVerif can be used for verification of security against polynomial time adversaries in the computational model. It's available via http://prosecco.gforge.inria.fr/personal/bblanche/cryptoverif/cryptoverifbin.html

Related to your "it doesn't work on my computer", here's an example how to test if it works (which it will on Win7 - which you previously wrote you're using):

create c:\cv\ and decompress the contents of the downloaded package in there.
Open a command-line prompt and go to c:\cv\ where the cryptoverif.exe resides.
Run cryptoverif.exe c:\cv\examples\fdh.cv

As for your question about TEX output, it would go like this:

cryptoverif.exe -tex somefilename.tex c:\cv\examples\fdh.cv

The manual, which is included in the download package, will provide you with the rest of the commandline parameters and a detailed description on how to use it.

Here's a screenshot of the --help parameter:

EDIT

A bit late, but The Scyther Tool may come handy too.


Usage of GF(p^m) fields, where p != 2 $GF(2^m)$ Galois fields are widely used in different cryptographic algorithms, for example, in Rijndael.

However, $GF(p^m)$ fields are possible with any prime $p$, not only 2, but $GF(2^m)$ fields are, as Wikipedia puts it, "especially popular choices for applications", because arithmetic operations in $GF(2^m)$ are much easier to implement that, say, in $GF(5^m)$: polynomials in the former can be expressed as simple binary numbers, and addition and subtraction are simply bitwise $xor$, which gives a great performance boost.

The question is: are there any cases where a $GF(p^m)$ with $p \neq 2$ would be preffered over a $GF(2^m)$ field? Or do such fields have only theoretical value?

I'm asking this because part of my cryptography homework involves calculations with such fields, and the last two tasks are to calculate a message encrypted with ElGamal, and to calculate an ElGamal signature, using a $GF(31^3) = \mathbb Z_{31}[x]/(29*x^3+14)$ field. Is this an example of a practice that has some benefits (besides the "security through obscurity" principle)?

Yes, cryptosystems like ElGamal or Shnorr based on the intractability
of Dlog Problem are are indicated to be implemented on finite field,
which is not the case of the RSA for which a model was proposed in the
early $80^{ies}$, and immediatly broken. As you know, a finite field is denoted by $GF(q)$ where $q=p^m$ and p would be any Prime. But in the case there is no special advantage to use such q with $p\neq 2$, because the arithmetic on this field is a bit more complicated, and each party would beforehand agree on using the same irreducible polynomial for building the corresponding splitting field.

However, other applications could use these fields for specific attacks, as the MOV attack which was introduced to reduce the Dlog Problem on supersingular curves.


Example of the $Ω$−partite Consider the following definition from section 2.2 of this research paper

We write $\mathcal{P}()$ for the power set of the set $$. An $-$partition
$Ω=\{_1,\cdots,_\}$ of a set $$ is a disjoint family of $$ nonempty
subsets of $$ with $=_1∪ \cdots ∪ _$. Let $Λ⊆\mathcal{P}()$ be a family of
subsets of $$. For a permutation $$ on $$, we define
$(Λ)=\{():∈Λ\}⊆\mathcal{P}()$. A family of subsets $Λ⊆\mathcal{P}()$ is said to
be $Ω-$partite if $(Λ)=Λ$ for every permutation $$ such that
$(_)=_$ for every $_∈Ω$. We say that $Λ$ is $-$partite if
it is $Ω-$partite for some $-$partition $Ω$. These concepts can be
applied to access structures, which are actually families of subsets.

My doubt lies in $(Λ)=\{():∈Λ\}⊆\mathcal{P}()$ because the paper does not define the permutation function on a set, but used it. I didn't came through any standard defifnition of permutation function on set which gives another set which is different from the input set because the order of elements in a set is immaterial.
What I am clear from the context is
$$\sigma: P \rightarrow P$$
$$ \sigma(A \in \mathcal{P}(P)) = B \in \mathcal{P}(P)$$
but I don't know what exactly $B$ is.
What is the definition of a permutation function over a set?
In addition, can you give some example of the above $Ω-$partite ?

A permutation on a set is a bijection from the set to itself; thus $\sigma$ is a (bijective) map from $P$ to itself, not from $p(P)$ to itself (though it does induce a map from $p(P)$ to itself in a natural manner).

Also, if $f$ is a map from $A$ to $B$ and $X$ is a subset of $A$, then $f(X) = \{f(x), x \in X\}$. This is completely standard notation.

For a collection $\Lambda$ of subsets of $P$, $\sigma(\Lambda) = \{\sigma(A), A \in \Lambda\}$ is the collection of subsets of $P$ which is obtained by applying $\sigma$ to all the elements of $\Lambda$.

Example: $P = \{1,2,\dots,8\}$, $\Omega = \{\{1,2\},\dots,\{7,8\}\}$. Then $\Lambda = \{\{1,2,3,4\},\{5,6,7,8\}\}$ is $\Omega$-partite since clearly every permutation of $P$ that fixes each $P_i$ also fixes each element of $\Lambda$, so in fact we even have $\sigma(A) = A$ for all $A$. On the other hand, $\Lambda' = \{\{1,2,3\},\{4,5,6\},\{7,8\}\}$ is not; for instance $\sigma = (34)$ yields $\sigma(\Lambda') = \{\{1,2,4\},\{3,5,6\},\{7,8\}\} \ne \Lambda'$.


ECIES: Purpose of MAC? Assumptions:

$A$ wants to communicate with $B$
$A$ knows a public key $P_B$ which is trusted by a third party and belongs to $B$
$A$ knows the address of someone who pretends to be $B$

$A$ wants to send a message to $B$ using ECIES:

$A$ calculates a random private key $K$ and the related public key $P$
$A$ calculates a shared secret $Z$ using $K$ and $P_B$ according to ECIES
$A$ derives symmetric keys from the shared secret $k_1|k_2=\text{KDF}(Z_x)$
$A$ encrypts a message $c=\text{ENCRYPT}_{k_1}(m)$
$A$ tags the encrypted message $t=\text{MAC}_{k_2}(c)$
$A$ sends $P|c|t$ to someone who pretends to be $B$

Questions:

Can $A$ assume, that only $B$ can read the message? I think so.
As $B$ does not know anything about $A$ what is the cryptographic purpose of the MAC? As $K$ and $P$ are message specific anyone who knows $P_B$ could have sent this message with a valid MAC to $B$!?
Does removal of the MAC step reduce ECIES' security? I assume, but I don't get why.

Can $A$ assume that only $B$ can read the message?

Only someone with the private key corresponding to $P_B$ can read the message.  If $A$ can assume that only $B$ has it, that works.

  As $B$ does not know anything about $A$ what is the cryptographic purpose of the MAC?

So that someone else cannot modify the encrypted message.

What we want to prevent is someone can take the encrypted message $E_{P_B}{m}$, and modify it so that it successfully decrypts into a message $m'$, where $m$ and $m'$ are related.  Without the MAC, here is what someone might try:

Take the encrypted text $c = ENCRYPT_{k_1}(m)$
Replace it with a $c'$, that decrypts with $k_1$ into $m'$
Repackage it into $P|c'$ as the new encrypted message.

This is often feasible, because many encryption methods make modifying the encrypted message possible (even if you don't know the encryption key $k_1$).  One example of this is counter mode; if you flip any bit of the encrypted message, and the corresponding bit of the decryption will also flip (with no other change).

Because of this, then without the MAC, Eve might be able to take the encrypted message:

$ENCRYPT( \text{ "Transfer one million into Bob's account, password Rhinosaurus" })$

and change that into

$ENCRYPT( \text{ "Transfer one million into Eve's account, password Rhinosaurus" })$

With the MAC, this type of message modification is infeasible.

So in this case with the MAC Eve can still send "valid" messages to $B$, but as long as Eve does not have the password ("Rhinosaurus") Eve has no way to execute or modify a transaction.


How to derive a private/public keypair from a random seed? For RSA, my understanding is that large primes are found randomly to build a private/public keypair. If a static seed can be used in that random search process, it should be possible to derive the same public/private keypair reliably.
For a repeatable discovery of foundational large-primes, the search for random primes might begin with an initial random large number. Then a sequential evaluation of large numbers to detect if they are prime.
This could be used to virtually create a TLS-PSK kind of system but using the more widely deployed TLS algorithms (PSK isn't widely deployed). Therefore, TLS is leveraged and induced to work like a PSK-based system, by using the random seed to find the large primes. That is, the seed value is virtually the PSK "symmetric key". Both parties derive the same private/public keypair from the large primes from the shared seed.
Are there major security flaws with this approach? Are there existing schemes that accomplish such a random seed process?
Advantages achieved:

Simple central distribution (PKI) - a central control server distributes "seeds" in the same manner as "symmetric passwords" that could conceivably be changed every 15 minutes.
Tooling - TLS protection with common libraries (eg. C# .Net Framework) - with a "symmetric password" like framework. (DTLS isn't common)

Compared to central keypair generation and distribution:

Processing is decentralised and more scalable if the central control server only needs to generate a cryptographically-random seed. (The search for the primes happens N times, where N is the amount of nodes using the shared seed).
Fewer bytes to communicate. If the seed value is fewer bytes than communicating a public/private keypair.

I have a conceptual new secure communication system in mind that would use these advantages.

How to derive a private/public keyset from a random seed?

In principle: seed a Cryptographically Strong Pseudo Random Number Generator with the random seed, and use it to generate the RSA key pair "normally". For the later, we could use FIPS 186-4 B.3.2.

Are there major security flaws with this approach?

Yes, the obvious one: any entity knowing the seed can compute the private key. We need to trust every such entity beyond the designated holder of the private key to only use the seed to compute the public key.
As an aside, deterministic RSA key pair generation may need extra work to be protected from side-channel attacks (timing, power analysis).
There's also a functional issue: RSA key generation is rather slow, and implementations often have no firm stated upper bound on their execution time.


Digicipher and other proprietary systems? I've always been curious as to how Pay-TV and other Conditional Access systems actually stay secure for any amount of time, given that they are usually one way and (I'm assuming) use symmetric keys for encrypting the video/data streams.

Given that the decoder MUST be able to learn the control word keys via some means, and that the keys change so frequently (every 10 or so seconds), it would seem that the only way this and other systems like this are secure is through obscurity.

I've been under the assumption that "security by obscurity" isn't a viable long term solution. So, I would guess that because the key for decrypting the ECM and EMM messages (which themselves contain the key for the control words) must be known by the receiver, the only way that this system would be secure is if they physically secure access to that one key.

How do they keep these systems from being broken by someone just looking at the information in the smartcard that houses the key?

It would seem that by retrieving that one key, the whole system would be broken in one fell swoop, because then you could just listen for all the ECM/EMM messages and get the new keys for a given channel. I don't understand how this is all that secure, but then again, I don't know of a better way other than securing the card. Am I missing anything?

Don't think you've missed something.

  How do they keep these systems from being broken by someone just looking at the information in the smartcard that houses the key?

Those systems have indeed been (and frequently are) broken via Hardware reverse-engineering. Therefore I would chime in with your "not secure". OTOH: decrypting AV signals isn't like trying to break national security or anything. Multiple black-markets exist where you could (but legally shouldn't!) get rebuild decoder-cards for almost any system and channel(s).

As indicated, the law is the strongest protection for Pay-TV providers. The signal is merely "crippled" to keep the masses from intercepting and decoding them without additional hardware and (illegal) efforts.


Robust combiner for preimage resistance My question is about chaining two hash functions to create a robust combiner
for preimage resistance. @Zooko already gave a detailed answer here:

  $$H_{\circ}(x) = H_0(H_1(x))$$

  is as strong as the strongest of its two components.

However, in the comments below, @Arno Mittelbach showed the idea was dangerous: if $H_0$ is a random oracle and $H_1$ is a constant function (that maps every input to $0$), $H_{\circ}(x)$ is a constant function. However, he did not address @Paŭlo Ebermann's construction

  $$H_{\circ}(x) = H_0(H_1(x)|x)$$

  ...to have the improved preimage resistance, while still not having more collisions than with only one hash.

when $H_1$ is constant function, @Paŭlo Ebermann's construction

$$H_{\circ}(x) = H_0(H_1(x)|x) = H_0(0|x)$$

appears to be indifferentiable from a random oracle. However, I understand it might be impossible to know which function is the constant function. If it's $H_0$,

$$H_{\circ}(x) = H_0(H_1(x)|x) = 0$$

So I'm wondering if this knowledge gap can be remedied by using construction

$$H_{\circ}(x) = H_0(H_1(x)|x) \oplus H_1(H_0(x)|x)$$

In that case if $H_1$ is a constant function

$$H_{\circ}(x) = H_0(0|x) \oplus 0 = H_0(0|x)$$

On the other hand, if $H_0$ is a constant function

$$H_{\circ}(x) = 0 \oplus H_1(0|x) = H_1(0|x)$$

Is there any downsides to this construction outside speed? I understand it does not distribute trust on collision resistance, that is okay considering my use case.

Also, I'm unsure if this paper applies to my construction as one of my hash functions is Blake2 and another is SHA3-256 (which is wide-pipe sponge function, not MD/HAIFA). To my knowledge it was also the case none of the attacked constructions in the paper were against constructions that contained chained hash functions.

In your construction, if $H_0 = H_1$ (same function), then your $H_{\circ}$ is constant and equal to $0$. More generally, that kind of construction relies on the two underlying hash functions to be "different" from each other in a way which is very hard to define properly, let alone achieve. If $H_0$ and $H_1$ are independent random oracles, then most constructions are fine; but, there again, random oracles don't really exist.


Diffie-Hellman key exchange protocol with finite field GF(2^5) In a Diffie-Hellman key exchange protocol, the system parameters are given as
follows: finite field $GF(2^5)$ defined with irreducible polynomial $f(x) = x^5 + x^2 + 1$ and
primitive element $\alpha= x$ in the field.

Suppose that Alice selected random number $a = 5$ and Bob selected $b = 6$, show the steps
performed by Alice and Bob to obtain their shared key. What is the key?

For Alice:

$α^a = α^5 = x^5 = (x^2 + 1)$

For Bob:

$α^b = α^6 = x*x^5 = x(x^2 + 1) = x^3 + x$

Shared Key For Alice:

$α^{ab} = (x^2 + 1)^b = (x^2 + 1)^6\ldots$

Shared Key For Bob:

$α^{ab} = (x^3 + x)^a = (x^3 + x)^5\ldots$

The answer is $x^4 + x$ but I'm not sure how to simplify to this answer from both sides either Alice or Bob which should have the same shared Key

Three words Finite Field Arithmetic. The elements of the Finite Field (Galois field) can be represented by a polynomial, like in this case. We prefer it since it gave us good computing properties.

$GF(2^5)$ is a binary field extension with the base field 2, the binary field. To construct this field we need an irreducible binary polynomial [*] of degree  5[‡]. In your case it is $f(x)=x^5+x^2+1$. The field can be constructed by $GF(2)[x]/x^5+x^2+1$. An irreducable binary poynomial with degree 5 need not be unique, there is only 6 possibilities for constructing $GF(2^5)$ [#].

$f(x)=1+x^2+x^5$,
$f(x)=1+x+x^2+x^3+x^5$,
$f(x)=1+x^3+x^5$,
$f(x)=1+x+x^3+x^4+x^5$,
$f(x)=1+x^2+x^3+x^4+x^5$, and
$f(x)=1+x+x^2+x^4+x^5$

For the binary field extension and we prefer the ones with small degree monomials and with fewer monomials. So, $f(x)=1+x^2+x^5$  is a good choice.

The addition is polynomial addition with the coefficients are reduced to base field. Multiplication is a bit tricky, we need modulo reduction with the irreducible polynomial. In your case, whenever you see $x^5$ replace it with $x^2+1$. In this website, you can see the table for addition and multiplication. For small cases, generating the table and hardcoding it in a table can be helpful, however, be aware of the cache attacks.

One way is multiplying all at once then reduce
\begin{align}
(x^2 + 1)^6 &= x^{12} + 6 x^{10} + 15 x^8 + 20 x^6 + 15 x^4 + 6 x^2 + 1 \\
            &= x^{12} + x^8 + 15 x^4 + 1 \\
     \vdots &= \vdots\\
\end{align}

This is not the preferred method since it can scale too much, especially for large finite fields. The better method is the multiply-and-reduce paradigm as below.

\begin{align}
(x^2 + 1)^6 &= ((x^2 + 1)^2)^2 (x^2 + 1)^2  &&,\text{expand one level } \\
            &= (x^4 + \color{red}{2} x^2 + 1)^2 (x^4 + \color{red}{2} x^2 + 1) && , \color{red}{2=0} \text{ in } \mathbb{F}_2\\
            &= (x^4 + 1)^2 (x^4 + 1) &&,\text{work on left} \\
            &= (x^8 + \color{red}{2}x + 1) (x^4 + 1)  && , \color{red}{2=0} \text{ in } \mathbb{F}_2\\
            &= (x^8 + 1) (x^4 + 1)  && , \text{use } x^5 = x^2+1\\
            &= ((x^5)x^3 + 1) (x^4 + 1) \\
            &= ((x^2+1)x^3 + 1) (x^4 + 1) \\
            &= (x^5 + x^3 + 1 ) (x^4 + 1)&& , \text{use } x^5 = x^2+1\\
            &= (x^2+ \color{red}{1} + x^3 + \color{red}{1} ) (x^4 + 1)&& , \color{red}{2=0} \text{ in } \mathbb{F}_2\\
            &= (x^3 + x^2 ) (x^4 + 1) &&, \text{multiply}\\
            &= x^7 + x^6 + x^3 + x^2  &&,\text{use } x^5 = x^2+1\\
            &= (x^2+1)x^2 + (x^2+1)x + x^3 + x^2 &&,\text{expand } \\
            &= x^4 + \color{red}{2} x^3 + \color{red}{2} x^2 + x &&,\text{use }\color{red}{2=0} \text{ in } \mathbb{F}_2\\
            &= x^4+ x &&
\end{align}

And, for the other equation, you can see their equality by; $$(x^3+x)^5=x^5(x^2+1)^5=(x^2+1)(x^2+1)^5=(x^2+1)^6$$

We, actually, use bit vector to process the binary polynomials:

$ (x^2+1)= [00101]$, we can represent with 5 bits since the finite field $GF(2^5)$.

Whenever we see, 1 out of size 5 we reduce it.

$ (x^5)= [1|00000] = [00101]$, the reduction is shift and x-or. We can say, replace the 1 with position 5 with $[0|00101]$ and x-or. Similarly, we can write formulas for
$x^6 = (x^5)x = [01001]$ and
$x^7 = (x^5)x^2 = [10100]$, and so on. In your case 6 should be enough if you multiply one by one.

\begin{align}
[00101]^6 &= [00101]\cdot [00101]\cdot [00101]^4 \\
          &= [10001]\cdot [00101]\cdot [00101]^3 \\
          &= [10|10001]\cdot [00101]^3 \tag{use $x^6$}\\
          &= [11000] \cdot [00101] \cdot [00101]^2\\
          &= [11|11000] \cdot [00101]^2\\
   \vdots &= \vdots
\end{align}

[*] A polynomial is said to be irreducible if it cannot be factored into nontrivial polynomials over the same field. (Wolfram defn.)

[#] The list is taken from Wolfram, too.

[‡] There is a sequence on the number of binary polynomials on the degree; OEIS A059912


How are points on an elliptic curve discretized? I'm a working programmer (read: a person without a maths degree) trying to get a better grasp on elliptic curves specifically in the context of elliptic curve cryptography (though to be clear, this is for personal development — I'm in no way trying to roll my own crypto).
One concept that's difficult to grasp for me is that curve points in the ECC context are often discretized over a finite field — specifically, a finite field having cardinality of the form $P^n$ for some large prime $P$. This gives points on elliptic curves a congruent behaviour under modular arithmetic whose value I can understand in this setting.
My question here is, how is the set of discrete points on elliptic curves determined for ECC applications? I'm entirely willing to do the legwork in terms of getting more math context, but I think I've got a lack of mathematical vocabulary which has made searching for papers explaining this difficult.

How is the set of discrete points on elliptic curves determined for ECC applications?

One common method to define a point on an elliptic curve over a suitable finite field $(\Bbb F,+,\cdot)$ is that such point is one of

any pair of coordinates $(x,y)$ with $x$ and $y$ elements of the field that obey an equation $y^2\,=\,x^3+a\cdot x+b$, where $a$ and $b$ are suitable constant elements of the finite field;
an extra point called the point at infinity, noted $\infty$ (or $\mathcal O\,$), often assimilated to $(0,0)$, where $0$ is the additive neutral for the field and $b\ne0$.

That defines a finite (discrete) set: in principle, we can enumerate all the $(x,y)$ (say, with two nested loops) and for each pair test if the equation is met; then throw in the extra $\infty$. That form $(x,y)$ is a standard discrete expression of a point on the curve: Cartesian coordinates.
We can define a binary law on the curve, using the same equations¹ as for a continuous elliptic curve group law, only operating in the finite field. We'll note that new law $\boxplus$ (in order to distinguish it from the addition $+$ in the field, though $+$ is often used for both laws), such that for all points $U$, $V$, $W$ on the curve (including $\infty\,$)

$U\boxplus V$ is a well-defined point on the curve.
$(U\boxplus V)\boxplus W\,=\,U\boxplus(V\boxplus W)$ (that is: $\boxplus$ is associative).
$U\boxplus V\,=\,V\boxplus U$ (that is: $\boxplus$ is commutative).
$U\boxplus\infty\,=\,U$ (that is: $\infty$ is neutral for $\boxplus\,$).
There exists a point $I$ on the curve with $U+I\,=\,\infty$. That $I$ is uniquely defined, and can be noted $\boxminus U$ (that is: the inverse of $U$ is $\boxminus U\,$). $U\boxplus\,\boxminus U\,=\,\infty$ becomes $U\boxminus U\,=\,\infty$. When $U\ne\infty$, $U$ is $(x,y)$ with $x$ and $y$ in the field and meeting the curve's equation $y^2\,=\,x^3+a\cdot x+b$, and $\boxminus U$ is $(x,-y$), also meeting the curve's equation since $(-y)^2\,=\,y^2\,$. If holds $\boxminus\infty\,=\,\infty$. Thus when $\infty$ is noted $(0,0)$, it holds $\boxminus(x,y)\,=\,(x,-y)$ for all $(x,y)$ of the curve.

In the above construction, we "discretized" a continuous elliptic curve and it's addition operation $\boxplus$ by

changing from an infinite field to a finite field;
keeping the curve's equation and the addition formula.

We can define² multiplication of an integer $k$ and a point $U$ of the curve, by using repeated addition:
$$k\times U\,\underset{\text{def}}=\;\begin{cases}
\infty&\text{if }k=0\\
((k-1)\times U)\boxplus U&\text{if }k>0\\
(-k)\times(\boxminus U)&\text{if }k<0
\end{cases}$$
It follows $0\times U\,=\,\infty\,$, $1\times U\,=\,U\,$, $2\times U\,=\,U\boxplus U\,$, $-1\times U\,=\,\boxminus U\,$.
It can be shown that there exists a point $G$ such that the set of all $m$ points $U$ on the curve is precisely the set of $U=k\times G$ for $k$ from $0$ to $m-1$. And when we take any point $G$ of the curve, the set of all $k\times G$ forms a group of $n$ distinct elements of the curve under the law $\boxplus$, with $n$ dividing $m$. In cryptography, we typically arrange things so that $n$ is prime, either because $m$ is prime and $n=m$ (the whole curve is used), or by choosing an appropriate $G$ of prime order $n$ (the group is a subgroup of the whole curve).
The construction as $U=k\times G$ with $k$ from $0$ to $n-1$ is another (discrete) way to express a point of the elliptic curve (sub)group, and the one used to construct a public key $U$ from a private key $k$. However, $U$ is not made public in this form, for that would reveal the private key. $U$ can be revealed as a pair $(x,y)$.
There are other common (discrete) ways to express a point of the elliptic curve. In particular, when the field is $\Bbb F_p$ (the integers modulo prime $p\,$), any point $U$ other than $\infty$ can be expressed as $x$ and the parity of $y$ (in this construction, not all $x$ yield a valid point).
Another common way is as a triplet $(x,y,z)$ of elements of the field with $z\ne0$ and $y^2\cdot z=x^3+a\cdot x\cdot z^2+b\cdot z^3$, which makes the evaluation of $\boxplus$ simpler. We can get back to the curve in Cartesian coordinates by projecting to $(x/z,\,y/z)$ when desired.

¹ These equations are:
$$U\boxplus V\underset{\text{def}}=\,\begin{cases}
U&\text{if }V=\infty\\
V&\text{if }U=\infty\\
\infty&\text{if }(x_U,y_U)=(x_V,-y_V)\\
\big(\lambda^2-x_U-x_V,\lambda\cdot(2\cdot x_U+x_V-\lambda^2)-y_U\big)&\text{otherwise}
\end{cases}$$
with in the otherwise case
$$\lambda\,\underset{\text{def}}=\;\begin{cases}
(3\cdot {x_U}^2+a)/(2\cdot y_U)&\text{if }U=V\\
(y_V-y_U)/(x_V-x_U)&\text{otherwise}
\end{cases}$$
Note: $/$ is division in the finite field, such that for all $r$ and $s$ in the finite field with $s\ne 0$, it holds $(r/s)\cdot s=1$. Here $1$ is the multiplicative neutral for the field; $2$ is $1+1\,$; and $3$ is $2+1\,$. When the field is the integers modulo prime $p$, the quantity $r/s$ can be computed as r*pow(s,-1,p)%p in Python starting with version 3.8 ( r*pow(s,p-2,p)%p works in more versions).

² This definition involves a number of field operations linear with $k$. For efficiency, an implementation can use
$$k\times U\,=\;\begin{cases}
\infty&\text{if }k=0\\
(-k)\times(\boxminus U)&\text{if }k<0\\
U&\text{if }k=1\\
((k/2)\times U)\boxplus((k/2)\times U)&\text{if }k>1\text{ and }k\text{ is even}\\
((k-1)\times U)\boxplus U&\text{if }k>1\text{ and }k\text{ is odd}
\end{cases}$$


How long would the 100 Year Cryptography Project have secured its data had it been started 100 years ago? The goal of the Tahoe-LAFS 100 Year Cryptography project is to "enhance Tahoe-LAFS's cryptographic system so that Tahoe shipped today/next year might remain safe from cryptographic attacks for a 100 years."  Its developers are openly collaborating knowledgeable experts in the field, with at least all the information on the internet today at their disposal.

How long would such a project have secured its data had it been started 100 years ago?

Is the length of the secure period monotonically increasing as we ask the question with starting points less distant in the past?

In 1911, there was no computer either. With much more modest goals of security for the next few months, the German army came up with the Enigma, which was broken. Before the 1970s, cryptography was essentially a military-only domain, so there were no "openly collaborating knowledgeable experts". The situation was qualitatively different. So it is a bit unfair, and of limited scientific value, to try to compare cryptographic systems before and after the seventies.

Moore's law was published by Gordon Moore in 1965, and thus was quite well known 10 years later. In 1976, people trying to build a system which would still be safe 100 years later would have accounted for Moore's law, meaning an extra 100 bits for symmetric keys, and 200 bits for hash functions (there are several variants of Moore's law, but one of the most optimistic says that every two years you can put twice as many transistors on a given die and clock them twice faster, leading to a doubling of CPU power every year). Symmetric encryption was beginning to be understood; DES had just been approved as a US standard, so, presumably, people aiming for 100-year security would have proposed something like 5-DES. They might have missed the point about block size: DES has 64-bit blocks, making it unsuitable for securely encrypting more than a few dozen gigabytes with a given key. Even if believing Moore's law, the sheer volume of today's data was not envisioned at that time.

In 1976, there was no hash function worth speaking of. The Merkle-Damgård construction was published in 1978. Even MD2 did not appear until 1989.

Digital signatures may have been a problem. In 1976 there was no efficient digital signature system. When RSA was published in 1978, the article contained an overly optimistic comment about how a 512-bit integer would resist attacks for millions of years (this became breakable in 1999). Also, appropriate padding techniques were not developed until the early 1990s.

So a "100-year cryptographic system" developed in 1976 would have been partially broken by now; but some parts would have kept well (probably symmetric encryption). Also, the system would have become inadequate for our evolving needs, in the same way that even a very fast Enigma machine would still encrypt characters out of a very small set (only letters, no space and no digits !), making it unsuitable for encrypting bytes.

This shows that we tend to get wrong ideas about what the future will hold (we are in 2011, where is my flying car ?). In particular, we do not understand what we will need 40 years from now, and we have relatively little grasp of the threats that will appear at that time. Right now, the trendy fearsome threat is the Quantum Computer.

(This is all an intricate way of saying that your question cannot be answered.)


Is it possible to hand-negotiate an SSL/TLS session? I'm interested in trying to hand-negotiate an SSL/TLS session. Similar to how one would use telnet to port 80 and type GET / HTTP/1.1. I know there's a lot of steps involved, and I'm aware of the structure that should be used (per RFC 5246). I know eventually I'd have to start doing my own crypto, (which I suppose I could use an external source for) but I'm not concerned about that. I'm just wondering if there's a way I could do this seeing as connecting on 443 over telnet just causes the connection to be immediately reset.

No, this is not possible, even if you copy & paste data to/from another program. The reason is that SSL is a binary protocol, and telnet won't pass through arbitrary binary data. Moreover, upon connection, it does some protocol negotiation, and this is probably the reason for connection reset.

There are programs, like openssl s_client, which set up SSL connection for you and let you type the data by hand. For example, you can use it to connect to a HTTPS server and type the request manually, as you do with HTTP and telnet.


How re-encryption can be done through RSA Both RSA and Elgamal have homomorphic properties. So both can re-encrypt the ciphertext. Re-encryption with Elgamal works as seen here.

How does re-encryption work using RSA?

What modification / addition is needed to transform simple RSA to RSA with re-encryption?

The keys for RSA:

Public key: $e$ & $n$

Private key: $d$

Encryption: $C=M^e \bmod n$

Decryption: $M=C^d \bmod n$

I read this answer and it's very similar to what I am looking for. But I have practically a few limitations (as it is textbook RSA, and I have security flaws).
I have an arbitrary length (large) plaintext. I want to encrypt it with RSA. I want to re-encrypt the ciphertext (independently and multiple times). Also I don't understand this formatted plaintexts in this question.

Is there a practical scheme / implementation available?

What changes are there needed in RSA to re-encrypt a ciphertext without compromising security?

Both RSA and elGamal have homomorphic property. So both can re-encrypt the cipher text

That doesn't follow.

Re-encryption means being able to take $E_{a}(m)$ and $F(a, b)$ (that is, a function of both private keys), and being able to generate $E_{b}(m)$ (that is, the encryption of the same message under a different private key), but (and this is the critical part) it not being able to recover $m$ from those two.  That is, $F(a, b)$ is a key that allows you to "switch keys", but is not sufficient (without the private keys $a$ or $b$) to allow you to decrypt.

What the homomorphic property of RSA is allow you to take $E_{a}(m)$ (and the public key), and allow you to generate $E_{a}(G(m))$ (for certain functions $G$).

That doesn't allow you to switch RSA keys (which would imply changing modulii), and there is no obvious way to do so...


CPA and pseudorandom generator Just started learning about Cryptography and Network Security in general, and I can't seem to grasp the understanding of the following question. Please correct me if I am misunderstanding anything.

Imagine that there exists a Pseudorandom Generator that simply doubles all key length, G(n) = {0,1}^n -> {0,1}^2n. If I have a key k and send it over to G, I now have an encrypted G(k) = k', and k' is twice the length of k. If I have a message m, encrypt it with k' with m XOR k', is it CPA secure or not?

I understand that with a CPA attack, the attacker can send any plaintext into the encryption mechanism and receive a ciphertext out of it.

My confusion is that, in the case above, what exactly is the attacking sending the plaintext into? Is it the Pseudorandom generator? Does the attacker know what type of pseudorandom generator it is? But since the attacker doesn't even have the original cipher-text or the original key, what use is it for the attacker to keep on sending his own plain-texts and get back his own cipher-texts?

Sorry if this is very confusing, but I really want to understand this before moving onto more advance topics.

I want to make this clear: You're defining $E_K(m):\{0,1\}^{2n}\times \{0,1\}^n\rightarrow \{0,1\}^{2n}$ as $E_K(m):=G(K)\oplus m$. This construction is well-known in the literature. It can't be CPA secure because it is a deterministic algorithm. However as discussed in Katz' and Lindell's book Introduction to Modern Cryptography it is secure against passive eavesdroppers only observing a single messages.

As for your questions:

  What exactly is the attacker sending the plaintext into?

He sends the plaintext into the encryption function and gets the ciphertext in return. He doesn't learn $K$ at any point but learns encryptions using $K$. The process of acquiring the ciphertext to a given plain text is called "querying the encryption oracle for X"

  Does the attacker know what type of pseudorandom generator it is?

Yes, the attacker may know which primitive is used to instantiate the PRG and in a good system usually does. But this won't help him breaking the scheme as the security fully relies on the key(s) as per Kerckhoff's principles.

  But since the attacker doesn't even have the original cipher-text or
  the original key, what use is it for the attacker to keep on sending
  his own plain-texts and get back his own cipher-texts?

The usual CPA scenario indeed hands a challenge cipher text over to the adversary which he has to decrypt. (It's a little different but being able to decrypt always counts as a break).

Here's a quick outline on how to break the scheme:

Suppose you want to decrypt a cipher text $c$. You query your encryption oracle for a random message $r$. You'll get $c'=G(K)\oplus r$ in return. You are now able to compute $G(K)=r\oplus c'$. As $c=G(K)\oplus m$, you can obtain $m$ as $m=G(K)\oplus c=r\oplus c' \oplus c$.


How To prove Any Change to $v=a\cdot y+b$ maks $y=(a)^{−1}\cdot (v−b)$ Uni. random value This question is related to data integrity.

Let a finite field be $\mathbb{F}_p$, where $p$ is a prime number.

I have a fixed value $y$ and two uniformly random values $a$ and $b$.

Hypothesis: $a,b,y,v \neq0$

I consider the server as an attacker who may modify the value $v$. The change to value $v$ may apply a clever change to value $y$ (see below).

I compute $v=a\cdot y+b$, and send it to the server. The server can do any change to $v$. So it computes a function of $v$, as $f(v)$.

Assume that I can magically detect if $y$ becomes a uniformly random value. So as long as the server cannot change $y$ to an arbitrary value $y'$ the security property is satisfied.

I can download $f(v)$ and remove the random values to obtain $y$, so I can do: $y=(a)^{−1}\cdot (f(v)−b)$

Question: How can I prove that ANY change to $v$ makes $y$ a uniformly random value?

To clarify I want to make sure the server cannot modify $v$ to apply an arbitrary change to $y$. In other word, my security needs would be satisfied if the server only can change $y$ to a uniformly random $y'$ (by changing $v$)

Well, there is not much to prove.

  The server can do any change to $v$.

So actually, this means the server with throw away your $v$ and just choose a new random number. Or alternatively, he chooses $w$ uniformaly random and sets $v'=v+w$, which is now also uniformly random.

When you get back that value, you have your (for you known/fixed) values $a,b$ and do your calculation $y' = a^{-1}(v'-b)$. With he existence of $a^{-1}$ (i.e. $a\neq0$), this is also uniformly distributed for fixed values $a,b$.


Secure, patent-free alternative to NTRU I'm working on a P2P communications and chat framework, and am looking for a quantum-secure asymmetric key exchange algorithm which I can use to perform a key exchange of an AES-256 bit key. This is an open-source project which will be licensed under GPL-3.0, and I have considered using NTRU. However; I have discovered that NTRU is a patented cryptosystem, and is therefore not compliant with the licensing constraints that apply to my application. Are there any asymmetric key exchange systems other than NTRU which are not patent encumbered, and secure against quantum attacks?
UPDATE in response to NTRU answer
Turns out that the patent grant may not be in fact in compliance with the GPL. The patent grant document the answer refers to (PATENTS.md) states that

  Businesses and enterprises that wish to incorporate NTRU cryptography into proprietary appliances or other commercial software products for re-distribution must have a commercial license

In contrast to the GPL, which permits commercial usage of a work if the commercial product is also licensed under the GPL. See the official FAQ on the matter of commercial use. This same FAQ page also clarifies, under a different section that the licensor cannot ban commercial/military use of a GPLd work as doing so is contradictory to the GPL.

UPDATE 2 -- Response from Security Innovation
The issue regarding GPL compliance has been sorted out. Below is an e-mail I have received clarifying the issue. I have decided to use NTRU under the GPL in my solution, and will be marking this answer as accepted.

  Thanks for getting in touch. You're absolutely right, our patents.md file isn't correct: it specifies GPL but then contrasts GPLed use with commercial use of the patents, even though as you point out commercial use isn't precluded by GPL. So our patents.md file is not in fact consistent with GPL 2.0. This was an oversight on our part. The intent was to have language identical to what's in our licence.md file at https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/LICENSE.md, specifically: "Parties who wish to distribute ntru-crypto, or components thereof, under licenses other than the GPL or the FOSS Exception must obtain a commercial license." This wording makes it clear, I hope, that in this context we use "commercial license" to mean "license for non-GPLed use". The intent is to be fully GPL compliant, including supporting commercial use under GPL. I'll work to get this language clarified on the site. Thanks for your eagle eyes, this is a good one to get sorted out.
  Hope this helps and let me know if you have any more questions.
  Cheers,
  William

I work for Security Innovation, which owns the NTRU patents. All NTRU-related patents are freely usable under GPL 2.0 and 3.0 -- in other words, they should fit in with your license requirement as given above. If you have specific license requirements beyond GPL please let me know and we'll accommodate them if we can.

There's an open-source C and Java implementation available from https://github.com/NTRUOpenSourceProject/ntru-crypto that you're welcome to use; it includes protection against CCA2 attacks and some features that reduce timing variability, so it's probably better to use that implementation than roll your own.

License statement about GPL is at https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/LICENSE.md. The GPL licensing of NTRU is an irrevocable grant by Security Innovation, Inc. and cannot be withdrawn by Security Innovation, Inc, and/or any future owners of the Patented NTRU Algorithms.

List of covered patents (which is all the NTRU-related patents) is at https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/PATENTS.md.

Hope this helps, and I'd be glad to help if you had any other questions about it.


Fast Forward Hash Signatures As a follow up to the Q/A session:
Small Quantum Signatures - Reality check needed

I have implemented the discussed idea for a new short-quantum-safe signature system using fast-forwarding hash.  It creates 32 byte public keys and 129 byte signatures.
It is as good as I could get it in the little time I had available.

I have uploaded the source code to GitHub (Java) under MIT licence for the benefit of crypto exchange.
https://github.com/MKAXLACOR/FastForwardHashSignatures

My question then is : are there any obvious errors with the algorithm I have chosen to provide the fast-forwarding function?

I wouldn't mind forwarding this on to Bernstein etc so they can also take a crack at it - however if there are any obvious issues that I need to correct first - would appreciate knowing!
Many thanks.

It is easy to find preimages for the hash function you designed. Remember, to break the scheme it is enough to find any preimage. It is not necessary to find the one used to compute the image. Now, you got public integers $a,b,c,d,$ and $f,g$ as well as a modulo $M$. An $n$-th image is
$$P(n) = a*x(n) + c*y(n) \mod M$$
$$Q(n) = b*x(n) + d*y(n) \mod M$$
with
$$x(n)= (f * P(n-1) ) + n$$
$$y(n)= (g * Q(n-1) ) + 1$$
hence
$$P(n) = afP(n-1) + an + cgQ(n-1) + c \mod M$$
$$Q(n) = bfP(n-1) + bn + dgQ(n-1) + d \mod M$$
leading
$$P(n) - an - c = afP(n-1) + cgQ(n-1) \mod M$$
$$Q(n) - bn - d = bfP(n-1) + dgQ(n-1) \mod M.$$
Lets rename to get some more readability. For an attacker knowing an image $y_1 = P(n) - an - c \in\mathbb{Z}_M$, $y_2 = Q(n) - bn - d \in\mathbb{Z}_M$, $a_{1,1}=af$, $a_{1,2}=cg$, $a_{2,1}=bf$, $a_{2,2}=dg$ are all known integers mod $M$. The two unknowns are the primage parts $x_1 = P(n-1)$, $x_2 = Q(n-1)$. Rewriting the system gives
$$a_{1,1}x_1 + a_{1,2}x_2 = y_1 \mod M$$
$$a_{2,1}x_1 + a_{2,2}x_2 = y_2 \mod M.$$
I guess from here on you know yourself how to determine $x_1, x_2$. This is one more example why you should not try to cook up something yourself when it comes to crypto.


Why does bootstrapping (R)LWE homomorphic encryption produce small noise? Why does homomorphic evaluation of the decryption circuit produce a ciphertext with "fresh" or small noise?
Rough description of bootstrapping homomorphic encryption:
Suppose we have a somewhat homomorphic encryption scheme that can only evaluate circuits of small depths including its own decryption circuit. In (R)LWE schemes, this is due to the growth of the noise in the ciphertext produced by homormorphic evaluation, which eventually makes the resulting ciphertext undecryptable.
Bootstrapping is the procedure that homomorphically evaluates the decryption of the current ciphertext, which produces a new ciphertext encrypting the same message. Supposedly, the new ciphertext should have smaller noise, which allows for further homomorphic evaluation.
I understand that bootstrapping produces a new ciphertext of the same message. But why does it have any smaller noise? It's still just evaluation of a circuit, which in general, increases the noise.

The output of bootstrapping has relatively small noise because it starts from an encryption (of the secret key) that has very small noise, and performs some homomorphic operations on it. These operations increase the noise somewhat, but it starts out so small that the result still doesn’t have much noise.
It doesn’t really matter that the ciphertext being bootstrapped has large noise, because that ciphertext only defines the function we (homomorphically) evaluate, namely, decryption of that fixed ciphertext by the (encrypted) secret key. In other words, the secret key is the input to the function we homomorphically evaluate, and it is encrypted with very small noise, so the result has only moderate noise.


Whats AES-256 max input size? Does the AES-256 encryption standart
have a max input length?

If not, does it mean we can even translate a book to it? Like md5 doesnt care max input length?

AES input size is exactly 16 bytes. But you can apply AES endlessly if you divide your data into a stream of blocks of 16 bytes. – rustyx

rustyx is party right. Just splitting the data is called ECB mode and it is insecure as you can detect repeated plaintext blocks. AES is not a full cipher, it is a block cipher. To create a real cipher from it you need to use it within a mode of operation. To have full CPA security this also requires a unique IV.

The amount of data that can be processed depends mainly on the mode of operation and the width of the block cipher (the block size). Generally modes of operation can handle at least 64 GiB of data in the worst case scenarios (e.g. for authenticated mode of operation such as GCM.


Invalidate a hash of a sequence of values given only the first N elements of a sequence? I want to develop a system where before some activity is performed, the user is sent a hash of a sequence of values which will be an inputs to the activity.
The number of possible values is fixed and values are not repeated in the sequence.
This I can do:
After the activity, the actual full sequence is sent to the user, so that the user can validate that the sequence of inputs was the sequence promised by computing the hash themselves.
Caveat:
During the activity, not all of the data from the sequence is consumed. Ideally, I don't want to send ALL of the original sequence to the user. I want to only to send first N elements that were used. Of course I cannot have the values in the sequence somehow discoverable using the hash.
Is this possible?
I see there is something called a Merkle Tree which seems to be able to prove set membership but it is not clear to me if this can prove order as well. Also this seems to be potentially leaky if there is only a limited set of values.

Ok, here's how to generate a commitment to a sequence of values, where it is easy to open the commitment to any initial subsequence.
Here's how it works; suppose the values you are committing to are $M_1, M_2, ..., M_n$.  Then, the committer picks a random value $R$, and with a preimage-resistent hash function, recursively computes the sequence:
$$I_{n} = R$$
$$I_{k} =  \text{Hash}( I_{k+1}, M_{k+1}) \text{ for $k \in \{0, ..., n-1\}$}$$
Then, the commiter publishes the value $I_0$.
Then, when the verifier gets the values $M_1, M_2, ..., M_N$, the committer can prove those are the first $N$ values of the commitment by publishing the vlaue $I_N$.  The verifier can then compute the series of hash functions to verify that the end hash is the same as the commitment.

I see there is something called a Merkle Tree which seems to be able to prove set membership but it is not clear to me if this can prove order as well.

A Merkle tree can verify it; the above suggestion can be viewed as a Merkle tree (just a rather oddly shaped one), optimized for proving the initial sequence.  If you need to prove more general subsets (e.g. the values $M_N$ through $M_N'$), a balanced Merkle tree would be more flexible (but with higher complexity)

Also this seems to be potentially leaky if there is only a limited set of values.

Nope; because $R$ is selected randomly, the verifier cannot test a potential sequence of $M_i$ values based on the commitment.


Are there any NIST curves with pairings? NIST FIPS.186-4 has standardized 5 ECC curves on field  (P-192, P-224, P-256, P-384, P-521) and 10 elliptic curves on binary fields. None of them seem to have pairings. Are there any standard curves which support pairings?   Are there any libraries which support those curves?

Are there any standard curves which support pairings?

No, there are currently no pairing-friendly NIST curves; NIST has not announced any plans to approve of either a pairing-friendly curve, or any cryptographical operation that involves a pairing operation.


I made an encryption device for school how can I make it better? (All programmed in Visual Basic) How it works is it gets a random number from 1 to 30000 and changes the first character by it in Unicode then it uses that number to change the first character of the key then it gets a new random number and repeat so that the key is entangled in to the end result. Which is how it is decrypted by guessing the number for each of the key values till it is the same as what we know the key should look like the then the corresponding letter from the message is decrypted with the same number. Boy is it hard to explain and I am bad at writing I will link to the git hub when I do it https://github.com/VeryG00dName/Encrypter

The folks here aren't keen on performing analyses of encryption algorithms, and a load of code in git doesn't help much with that either unfortunately.

What I would say though is that you seem to have yourself a stream cipher.  Have a look at chapters 5 & 6 of Handbook of Applied Cryptography.

One of the issues will be your random numbers.  Consider that any computer can easily just try all 30,000 of them sequentially until the message makes sense. We can just do this and it's called a brute force attack.


What is the likely cause the RSA algorithm gives back plain text in this case? Text book question of Chapter 9 of "Crypto and Network Security" by William Stallings:

When using the RSA Algorithm — if a small number of repeated encodings give back the plain text, what is the likely cause this happens?

The question is about the "cycling attack" against RSA. The attack needs to be considered, in principle, for any deterministic asymmetric cipher with the same input and output domain, including RSA (without padding): the attacker repeatedly encrypts the ciphertext, until she obtains the ciphertext again; the last value enciphered is the plaintext.

This is discussed in the paper Are Strong Primes Needed for RSA? by Ronald L. Rivest and Robert D. Silverman. They conclude that it simply does not work in practice: "Cycling attacks are extremely unlikely to be effective as long as the primes used are large. Indeed even probabilistic factoring attacks will succeed much more quickly and with higher probability than cycling attacks".

Hence the answer to the question is in practice: the RSA key is not the product of big-enough random-like primes with proper relation to $e$; or/and the input to the RSA exponentiation is not a random-like integer, but rather crafted with knowledge of the factors of $n$, implying that RSA is used without proper padding. Any of these would be Real Bad.


How can Peggy prove she knows one of Victor's passwords in zero knowledge? Say Peggy wants to prove to Victor that she knows one of his passwords. She doesn't want Victor to know which password she knows, because she knows that some passwords are more valuable to Victor than others, and wants to keep the advantage that Victor doesn't know which of his passwords she knows.

Victor wants to verify that Peggy knows one of his passwords to ensure she's not lying, but he also doesn't want Peggy to trick him into giving her any knowledge of what passwords he has/doesn't have. That is, he doesn't want to send her anything that she could use to verify that she actually does have one of his passwords, or that she could use to perform a brute force attack and reveal any additional information about his passwords.

Is there a way to prove this in zero knowledge?

Yes, there is.

Assuming Peggy and Victor will be honest about their inputs, they can achieve exactly this functionality with garbled circuits. Victor can generate a circuit which will check for equality between Peggy's input and his list of passwords, then he proceeds to garble the circuit. Victor and Peggy cooperate in oblivious transfers for Peggy to get the circuit keys related to her input and she proceeds to evaluate the garbled circuit. She returns her output to Victor who can then clearly see whether or not the input Peggy provided is actually equal to one of his passwords, and he does not know which one. Such a protocol can be made maliciously secure as well.

It can also be implemented with secret sharing as well as other secure multiparty computation algorithms, but garbled circuits is usually one that is fairly intuitive for many.


Post quantum security of the BLAKE family Is there any proof that BLAKE (including 2 and 3) is post-quantum secure? We know that as Merkle–Damgård (with proper padding) preserves collapse sha2 is post-quantum secure. I know that the sponge-based winner of the sha3 competition does not have such a proof. Since BLAKE uses neither of these constructions has there been any research as to whether it's construction is post-quantum secure?

There is no proof, there are only advancements. BLAKE2 is not completely MD, it is HAIFA which extends the MD to eliminate the problems and BLAKE3 is a parallel hash.
Quamtum collision attack costs
The best know generic quantum collision is the takes $\mathcal{O}(2^{n/3})$ time due to Brassard–Høyer–Tapp (BHT). It is usually advertised (even by the NIST) with only the time but we have other costs, too. BHT builds a huge table of size  $\mathcal{O}(2^{n/3})$ then runs the Grover's algorithm with the cost  $\mathcal{O}(2^{n/3})$ and this make a total cost $\mathcal{O}(2^{2n/3})$
None of the variants, including the Ambainis algorithm which has still cost around $\mathcal{O}(2^{2n/3})$, doesn't lower the cost barrier of the classical attack cost $\mathcal{O}(2^{n/2})$
We already know that there is a lower bound on number of queries a generic algorithm mus take $\Omega(2^{n/3})$
So there are no threats from QC that we can see.
Quantum Pre-Images attack cost
Grover's algorithm is the best generic algorithm with $\mathcal{O}$-time and doesn't use much space as the BHT or others. But the sequential evaluation of the hash function is the problem there. Even you evaluate one in a nano-second you can get at most $2^{54}$ in a year and you need $2^{64}$-year to find the pre-images. The other cost is not included. One can run Grover's algorithm in parallel, however, the advantage not the same as the classical one, you will get $\sqrt k$ speed up from $k$ machines.
Therefore if you have 256-bit output, you will be safe from quantum attacks for hash functions.

Collapsibility
Collapsibility is defined by Unruh as a quantum equivalent of collision resistance of hash functions.

2016, Computationally Binding Quantum Commitments

Informally, for cryptographic hash functions, collapseability requires an adversary that outputs a hash value together with a superposition of corresponding preimages is not able to tell if the superposition gets measured or not.

The result of Unruh is this

showed that there is a hash function that is collision-resistant and thus can safely be used in a classical commitment scheme, but is not secure when the commitment scheme is used in a quantum setting

so we have a one-way relation;
-Collapsability implies Collision resistance.
Fer showed that

He applied the approach to the Merkle-Damgård and sponge hash construction, proving that they are collapsing if the underlying compression function is.

Gunns and Manning showed that

Binary tree hash of fixed length is collapsing.
Variable Length tree hashing with Domain Separation is collapsing.


Why are processes requiring (almost) as much work as brute force considered an "attack" on a hash function? In the literature on attacks against hash functions, I frequently come across algorithms requiring $2^n$ work described as being preimage or collision "attacks" on a hash function with only marginally more than $n$ bits of output$^1$.

Have I grievously misunderstood the terminology here?

If the result of the attack is an $n$-bit value then brute force takes $2^n$ tries; how can anything only slightly better than this be considered a meaningful enough "attack" to be worthy of publishing?

It seems to be making article titles nearly useless; a well peer-reviewed article titled "an attack against AES" in a reputable publication could be anything from irrelevant to cataclysmically internet-shattering in its consequences.

Here's an example from the Wikipedia page for Salsa20:

  In 2007, Tsunoo et al. announced a cryptanalysis of Salsa20 which breaks 8 out of 20 rounds to recover the 256-bit secret key in $2^{255}$

or key-recovery "attacks" against a symmetric cipher having only marginally more than $n$ bits of secret key, although I've been reading mostly hash function papers lately.

It's just a matter of terminology, which (as often in mathematics and related disciplines) may not match your intuitive interpretation of the words.

An attack is any algorithm that performs better than the "obvious" brute force algorithms. Cryptographic primitives are designed to admit no attack better than generic ones, so any proof that this goal is not met constitutes a break (but maybe not a complete break) to a theorist. For more practically-minded people, it demonstrates attack vectors and techniques which may be useful in constructing more efficient algorithms.
If an attack is effectively breaking the system for realistic key sizes, it is often referred to as a practical attack. (And people usually proudly put this term into their paper's titles if their attack performs this good.) For well-studied primitives, this luckily does not happen very often.
Some papers describe attacks against round-reduced variants of a cipher: this again serves as a demonstration of attack techniques and (just like any other kind of cryptanalysis) is an important step in cipher design, because it provides an estimate for the number of rounds the cipher should have. Papers should (and usually do) clearly point out that they're attacking non-standard variants.

Then of course, unfortunately some (if not many) people have a tendency to oversell their results — there's nothing you can do against that, but the above should help in filtering for the kind of attacks you're interested in.


LMS Security Proof Paper Is there any LMS security proof besides the one mentioned in RFC 8554? Does LMS actually have a paper which describes a proof?

In addition to the works that fgrieu cited, there is also Edward Eaton's paper analyzing LMS in the Quantum Oracle model.


Who said "32 round Rijndael" in the third AES Conference This is a historical question. In the third AES Conference of NIST (AES3), April 13-14, 2000, New York, near the end of the conference, one representative for each of the last 5 candidates sit on a table and people asked questions to them.

One interesting question was;

Except for your proposal for AES, what is your candidate?

As far as I can remember, the representative of Rijndael was the last to answer, was sitting on the right end. The first 3 were simply said The Rijndael. But, the 4. person said I want 32-round Rijndael

Was he Bruce Schneier? See his suggest on his Blog.
What was the choice of the representative of Rijndael?

This answer is based on Morris Dworkin's report of the conference, so it ultimately relies on its accuracy (it is probably more reliable than memory, though).

Regarding the question "Except for your proposal for AES, what is your candidate?", the report states (page 15):

  The panelists were asked which algorithm, other than their own, they
  would choose for the AES. Rijmen liked RC6; the other four panelists
  said Rijndael if it was extended to 18 or more rounds.

So this suggests that the representative for Rijndael (Vincent Rijmen) chose RC6.

During his presentation at the conference, Bruce Schneier is reported to have ended with the following suggestions (page 15 as well):

  He [Schneier] recommended  that  NIST choose  either  Rijndael  extended  to  18
  rounds,  Serpent,  or  Twofish  for  the  AES;  he  favored Twofish
  for its efficiency across the board, its unique flexibility, and its
  speed-security tradeoff.

Since he suggested 18 rounds here, it would surprise me if he would argue for 32 rounds later the same day.

So the representative who answered "Rijndael with 32 rounds" was either Shai Halevi (MARS), Ron Rivest (RC6) or Ross Anderson (Serpent).
My personal guess would be Ross Anderson (this would make sense because Serpent has 32 rounds). In fact, on page 16 of the report there is some weak evidence pointing in this direction:

  Anderson  responded  to  a  suggestion  to  transfer  some  of
  Serpent’s rounds to Rijndael by reiterating his support for 32 round
  Serpent with 256 bit keys.


Is there an efficient algorithm that allows to construct a cryptographically secure $n$-bit hash function based on two unkeyed $n$-bit permutations? Let $f(x)$ and $g(x)$ denote two independent, “ideal”, unkeyed, public $n$-bit permutations (two publicly known bijective functions that produce $n$-bit outputs from $n$-bit inputs), where $n$ is an arbitrary natural number greater than or equal to $3$ (the number $3$ is here because it is the minimal size of a “cryptographically significant” S-Box).

Does there exist an efficient iterative algorithm (based on $f(x)$ and $g(x)$ as the underlying functions) that allows to construct a cryptographically secure $n$-bit hash function for $k$-bit inputs, assuming that $k$ is an arbitrary natural number greater than or equal to zero (that is, there should be no limit on the maximum length of the input)?

It is impossible to construct a collision-resistant hash function from one-way permutations, via a black-box construction. Thus, the answer in principle is no; such a construction is impossible. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? by Simon (Eurocrypt'98). This answer does not relate to heuristic constructions, but you cannot do this with a proof of security (unless it's not black box).

The question here actually relates to "ideal" permutations, and under such an assumption it may be different. (Although, I'm not sure what is meant by "public" ideal.) My answer referred to (non-ideal) one-way permutations.


Should HMAC-SHA3 be preferred over H(C(k,M))? If I understand correctly SHA-3 (Keccak) is resistant against more attacks than SHA-2. This would make it possible - again if I understand correctly - to use SHA-3 with a simpler scheme than HMAC.

Would there still be a reason to use the HMAC construction with SHA-3? Would it be a better idea to simply use $H(C(k, M))$ where $H$ is simply SHA-3 and $C$ is a function to create a canonical representation (encoding) of the key $k$ and the message $M$ to set them apart?

Of course I imagine that HMAC-SHA3 will be used in the majority of protocols anyway as SHA-3 was created as a drop in replacement of SHA-2. But is there any security related reason to use HMAC-SHA3 over an (even) simpler scheme?

HMAC does not provide an obvious security improvement over the KMAC construction, which is optimal for Keccak based functions. HMAC is designed to create a secret initialization vector or IV for Merkle-Damgård type hash functions, KMAC does the same for sponge based hash functions but much more efficiently. HMAC also needs to deal with the length extension property

KMAC extends the key to the block size and prepends it to the message. I believe this will be standardized (if it has not already) as the default MAC construction for SHA-3. Because it extends the key to the block size, an F iteration is performed over the key prior to message absorption, creating a secret keyed state.

This is the basic sponge MAC construction discussed during the Keccak design phase, and in later discussion of both Keccak and SHA-3. There needs to be some kind of encoding or padding to effectively separate keys of different sizes, but this is not discussed in those documents; the $C$ function you mention would perform such separation. KMAC as discussed during the August 2014 SHA-3 workshop shortly after the publication of FIPS 202 uses the "keypack" function to pad the key and encode the byte-length of the key block as an 8-bit value, using a minimum of 9 additional bits beyond the length of the key: $\operatorname{Keypack}(K, l) = \operatorname{enc}(l /8) | K | 1 0 ^{l-\operatorname{len}(K)-9}$ where $l$ is the block size.

The "block size" of SHA-3 is at least 576 bits for all variants, meaning a 512-bit key can key the state with only one additional iteration of $f$. Additionally, since there is no block or bit counters, a device with low computational resources but enough memory can simply keep the keyed state as its default state for MAC computations and suffer no performance hit when compared to plain hashing.

Update: Since this answer was originally written, NIST has published SP 800-185 standardizing KMAC and a few other useful Keccak-derived constructions.


secure multiparty computation for multiplication Suppose there are $N$ parties $p_j$, each with a binary $b_j\in{\{0,1\}}$. The problem needs to compute the multiplication of number of ones times that of zeros, that is, $R=(\sum{b_j})\times(N-\sum{b_j})$.

The computation should be secure in the sense that no party can know more than the final result $R$. For example, it's not ok to perform secure sum, because then $\sum{b_j}$ is known, which is sensitive in my problem. So, is there any existing secure computation protocol that fits my demand?

Well, I am unaware of any published work on this precise problem, however I believe I do have a solution.

First of all, I would note that your problem is equivalent to the problem "if each party has a bit $b_i$, can they securely compute a value $k$ with either $k = \sum b_i$ or $k = N - \sum b_i$ (without giving any further information, including which of those values it might be)".  So, we can use a secure sum as part of the solution, as long as we're careful not to give any information about which sum it is.

Here is how my protocol works; it takes 4 rounds and $4N$ messages between party members.  In each round, the party members arrange themselves in a cycle; each party member takes a value from the previous party member (or the data from the start of the cycle for the first party member), does some computation on the values, and then passes it along to the next party member.  I also do not assume that the message between party members are private.

In an initialization phase, the party members agree on a group where the Diffie-Hellman problem is hard, and two group members $A$ and $B$ such that $A \neq 2^k \cdot B$ and $B \neq 2^k \cdot A$ for any value of $0 \leq k \leq N$ (note: I'm using additive notation for the group, if you're using a multiplicative group, that would normally be written $A \neq B ^ {2^k}$ and $B \neq A ^ {2^k}$)

Now, round 1: we start with the data consisting of the pair $(A, B)$.  Each party member takes the pair that they get $(X, Y)$, selects an integer $c_i$, randomly selects either $(c_i \cdot X, c_i \cdot Y)$ or $(c_i \cdot Y, c_i \cdot X)$, and sends that pair to the next party member.

The point of this round is that the output from the final party will be either $(c \cdot A, c \cdot B)$ or $(c \cdot B, c \cdot A)$ (for some blinding factor $c$) without anyone being able to determine which.

Now, round 2: we start with the data from the last round.  Each party takes the pair they get $(X, Y)$, selects another integer $d_i$, and then if their bit $b_i$ is zero, computes $(2 \cdot d_i \cdot X, d_i \cdot Y)$, and if their bit $b_i$ is one, computes $(d_i \cdot X, 2 \cdot d_i \cdot Y)$, and sends that pair to the next party member

The point of this round is to gather the votes; the first of the pair collects the zero vots, and second of the pair collects the one votes (again, with a blinding factor so no one can see what someone else voted).

Now, round 3: we start with the data from the last round.    Each party member takes the pair that they get $(X, Y)$, selects an integer $e_i$, randomly selects either $(e_i \cdot X, e_i \cdot Y)$ or $(e_i \cdot Y, e_i \cdot X)$, and sends that pair to the next party member (except the last party member; they random select either $(e_N \cdot X)$ or $(e_N \cdot Y)$ and sends that

The point of this round is to disguise which of the pair was the '0' vote, and which was the '1' vote; the last member returns one of them, but no one knows which one it has.

Now, round 4: we start with the data from the last round.    Each party member takes the value that they get $(X)$ and removes the blinding factors they applied; that is, computes $((c_i \cdot d_i \cdot e_i) ^ {-1} \cdot X)$, and passes that to the next part member.

The result of the last party member will be either $2^k \cdot A$ or $2^k \cdot B$; we can recover the value $k$ in $\sqrt N$ time, and that is our result.

Note that:

It will be $2^k \cdot A$ if an even number of party members decided to swap during round 1, and $2^k \cdot B$ if an odd number decided to swap.  Because each party member selected this randomly and independently of anything else, tthis is unbiased, and uncorrelated to anything.
The computed $k$ will be $\sum b_i$ if an odd number of party members decided to swap during round 3, and $N - \sum b_i$ if an even number decided to swap (and for the last party member, we count him as swapping if he selected $(e_N \cdot Y)$.  Again, because each party member selected this randomly and independently of anything else, this is unbiased, and uncorrelated to anything.