Is there an algorithm to find the number of intersections of two sets? Suppose both I and my friend have a set of integer numbers. We want to know the number of common elements in our two sets but without knowing elements of the sets of each other. So I don't want my friend to know any element of my set and he don't want me to know his. But we want to know how many elements are in the intersection of our two sets (without also knowing which elements these are).

Are there any algorithm to achieve this goal? One that will calculate the number of common elements using data from which it is very difficult to compute elements of our sets? Or its just impossible?

All elements of our sets are integers so we can use algorithms of computational number theory.

Answer. Yes!  It is possible to do this, using the magic of secure multi-party computation.  The security property we get is basically the best one could possibly hope for: namely, your friend learns nothing more about your set of numbers than the maximum he could have learned by choosing his set in a clever way and learning the size of the intersection; and your friend gets symmetrical protection against you.

The particular problem you list is known as the cardinality set intersection problem or cardinality private set intersection problem, and there has been considerable research on protocols for this problem.

One way to solve this problem is using the standard general-purpose machinery for secure two-party computation.  The general-purpose tools for secure two-party computation can be applied directly to this problem, giving one way to do what you want.

Alternatively, researchers have devised special-purpose protocols designed especially to solve the cardinality set intersection problem.  These special-purpose protocols are considerably more efficient than what you get if you apply the general-purpose methods.  Here are some some pointers into the research literature in this area:

Lea Kissner, Dawn Song, Privacy-Preserving Set Operations, CRYPTO 2005.
Yingpeng Sang, Hong Shen, Efficient and Secure Protocols for Privacy Preserving Set Operations, ACM TISSEC 2009.  (Improves upon Kissner-Song.)
Michael J. Freedman, Kobbi Nissim, Benny Pinks, Efficient private matching and set intersection, EUROCRYPT 2004.  (An alternative to Kissner-Song.)
Carmit Hazay, Kobbi Nissim, Efficient Set Operations in the Presence of Malicious Adversaries, PKC 2010.  (Improves upon Freedman-Nissim-Pinks in the malicious model.)
Dana Dachman-Soled, Tal Malkin, Mariana Raykova, Moti Yung, Efficient Robust Private Set Intersection, ACNS 2009.  (Addresses the malicious model.)

Mathematical details. Here's the basic idea behind Kissner and Song's approach:

They encode each set as a polynomial: for example, the set $S = \{3,5,17\}$ is encoded as the polynomial $s(x) = (x-3)(x-5)(x-17)$, the set $T = \{4,12,17\}$ is represented as $t(x) = (x-4)(x-12)(x-17)$, and so on.  In general, a polynomial $p(x)$ represents the set of roots of $p(x)$, i.e., the set $\{a : p(a)=0\}$.
Given polynomials $s(x)$,$t(x)$ representing the sets $S,T$, we can compute a polynomial $u(x)$ representing the intersection $U = S \cap T$, by picking random polynomials $q(x),r(x)$ and computing

$$u(x) = q(x)s(x) + r(x)t(x)$$

Note that the roots of $u(x)$ are (with high probability) exactly the common roots of $s(x)$,$t(x)$, i.e., $u(a)=0$ usually happens only when $s(a)=t(a)=0$

For example, if with sets $S,T$ defined as in 1 above, we might pick $q(x) = 2x^3 + 7x^2 + x - 3$ and $r(x) = 14x^3 + 3x^2 - 2x + 5$.  Then we can calculate $u(x) = 16 x^6 - 502 x^5  + ... - 3315$, whose only integer root is $x=17$.  This corresponds to the fact that $U = S \cap T = \{17\}$.
They use Pallier's additively homomorphic public-key encryption scheme.  In particular, you and your friend jointly generate a Paillier public/private keypair, so that both of you know the public key but the private key is shared between you (it is only possible to decrypt if both of you jointly participate).  There are known ways to do this.
You take your set $S$, encode it as a polynomial $s(x)$, and encrypt each coefficient under the Paillier public key, and send the resulting encrypted polynomial to your friend.  Your friend takes his set $T$, encodes it as a polynomial $t(x)$, encrypt each coefficient under the Paillier public key, and send the resulting encrypted polynomial to you.  You jointly generate random polynomials $q(x),r(x)$ (there are known ways to do this).  Then, using the additively homomorphic properties of Paillier encryption, you can both compute an encrypted form of the polynomial $u(x) = q(x)s(x) + r(x)t(x)$, where you get the encrypted value of each coefficient of $u(x)$.  You each share the value of $u(x)$ you got with the other person.
For each element $a$ of your set $S$, you evaluate the encrypted polynomial at $a$, thus learning the encryption of $u(a)$, call it $E(u(a))$ (the additively homomorphic properties of Paillier encryption allow you to do this), and then you pick a random non-zero value $c$ and multiply to get $E(c*u(a))$.   You do this separately for each element of your set, so you get $|S|$ encrypted values, you shuffle them, and send them to your friend.  Your friend does the same with his set and sends you a shuffled set of $|T|$ encrypted values.

In the running example, you'd learn the encryption of $u(3)$, $u(5)$, and $u(17)$, you'd pick random non-zero values, say $8$, $2$, $5$, and you'd share $E(8\cdot u(3))$, $E(2\cdot u(5))$, and $E(5 \cdot u(17))$ with your friend in random order.  In this case $u(3)=-50904$, $u(5)=152880$, $u(17)=0$, so you'd be sharing $E(8\cdot-50904)$, $E(2\cdot152880)$, and $E(0)$, in random order. Your friend would do something similar with his set.
Finally, you and your friend jointly decrypt the encrypted values you've shared with each other, using the shared private key.  You count how many zeros you see in the decrypted values your friend sent you.  Your friend counts how many zeros are present in the decrypted values you sent him.  This is the number of values you had in common, i.e., the cardinality of $|S \cap T|$.

I've introduced some simplifications (e.g., all computations have to be done in an appropriate group, and many others).  Please don't try to implement based upon this description alone.  See Kissner and Song's paper for the full details.  You might also look into the subsequent literature; there have been some follow-on papers that claim to improve their scheme to get better performance, though I'm not familiar with all the details.  Also, in a real implementation, you'd need to add some zero-knowledge proofs at each step, to prove that each participant correctly performed their own computation (i.e., to lift from the honest-but-curious model to the malicious model).  There has been follow-on research on that problem as well.

Summary. As you can see, this gets highly technical -- but the bottom line is that this problem has been studied in detail before, and there exist clever, beautiful, efficient solutions to it.


Blowfish Encryptions in Bcrypt hashing algorithm I am trying to understand the ExpandKey function used in the bcrypt hashing algorithm. As per the documentation of bcrypt hashing algorithm on USENIX here:

http://static.usenix.org/event/usenix99/provos/provos_html/node4.html

There is only one invocation of the ExpandKey function with the 128 bit salt value.

After this, the invocations of the ExpandKey function in the loop (2 ^ work factor), all have the second argument as 128 0 bits.

ExpandKey(state, 0, key)
ExpandKey(state, 0, salt)

Using these as inputs to how the ExpandKey function works, there will be repeated blowfish encryptions of 64 0 bits of salt which are used to replace the contents of P-Array and Sboxes.

If we take, ExpandKey(state, 0, key) as an example:

First all the subkeys in the P-Array are Xored with 32 bits of the encrypted key one by one (treating the key as cyclic).

Next, the first 64 bits of the salt (all 0 bits) are blowfish encrypted and the result is stored in P1 and P2 (first 2 32 bit sub keys).

The above result is Xored with the second half of the 128 bit salt (remaining 64 0 bits). Then blowfish encrypt it and store the result in P3 and P4.

This process goes on till the contents of all the subkeys are replaced followed by S-box entry replacement.

I wanted to know if my understanding is correct or not? We are effectively blowfish encrypting 64 0 bits every time in the loop.

What is the purpose of using the second argument of the ExpandKey function as all 0 bits instead of the actual 128 bit salt?

The key schedule would be more expensive, had they chosen the same 128 bit salt (as in the first invocation) for the remaining iterations. Or would this make bcrypt hashing algorithm computationally infeasible?

Thanks.

It is not really clear what you propose instead of the original algorithm - using ExpandKey(state, salt, key) instead of ExpandKey(state, 0, key)? What about the second call ExpandKey(state, 0, salt)?.

You are right, each ExpandKey(state, 0, xxx) contains one XOR-ing of xxx into the P-array, and then Blowfish-encrypting multiple 64-bit blocks of zeros – in CBC-mode, if I read the description right - thus actually we are not encrypting zero, but the ciphertext of the last block – but each block is encrypted with a different cipher state (as the result of each encryption replaces some of the P- or S-boxes).

Using salt as input instead of 0 would not be very more difficult, but (if I understand the argumentation on your linked page right) it might need some registers more to store the salt, and thus might slow down the execution on processors which are low on register count. Also, with zero salt, this is identical to the standard ExpandKey of Blowfish, so an existing (maybe optimized) implementation can be reused here, and all analysis of Blowfish can be applied, too.


What is SHA-512's input space, taking into account variable message size? The SHA-512 hash function accepts any message from a single bit to $2^{128}$ bits. Because the function takes into account the message length, I can't just represent every message as a $2^{128}$-bit integer. I'm sure this is a very basic question, but my math background is limited so this isn't coming easily to me.
How do I calculate the number of distinct inputs?

There is one zero-length message, two 1 bit long messages, four 2 bit long messages, eight 3 bit long messages, and so on. Since these messages are distinct, you can simply use the formula:

$$1 + 2 + 4 + 8 + \dots + 2^{n-1} = 2^n-1$$

Note that the maximum message length is the same as the maximum value of a 128-bit integer, ie. $2^{128} - 1$, not $2^{128}$. That makes $n-1 = 2^{128} - 1$, so $n = 2^{128}$. That makes the total number of distinct inputs

$$2^{(2^{128}-1)} - 1 $$


Can someone explain to me the concept of hashing versus the concept of encryption? I'm a bit confused over the difference between hashing and encryption. Could someone help explain this to me in simple and concise, yet comprehensive layman's terms?

I'm not asking for any specifics in how they work, but rather how the essential concept of each work in layman's terms

The important difference is that encryption is intended to be undone, hashing isn't. Let's say I have a secret password called "pass001." If encrypted, pass001 would be scrambled with a key to be something unrecognizable like "a8d89sI." Using the exact same key, "a8d89sI" can be reverted back to pass001. Hashing scrambles the secret password in much the same way, but there is no key involved and there is generally no way to turn the computed hash back into "pass001." Why might this be useful? Assume you stored password hashes in your database. If a hacker were to steal the contents, then he would be left with hashes that he can't do anything with. Not even the owner of the database can see the original password. When a user logs in, the password they enter is hashed on the spot and this hash is compared to the hash stored in the database to check if they put in the right password. If they did, both the calculated hashes should be the same. Hashes are used for many things, but in this case, it's just an extra layer of security.


Key size for HMAC-SHA256 After reading a bunch of past stack exchange posts like this one and RFCs 5869, 2104, and 4868 I felt comfortable that a 32-byte key was sufficient for HMAC-SHA256.  However, I am implementing my code in C# and someone pointed out to me that the Microsoft HMAC-SHA256 documentation recommends a 64-byte key:

  The key can be any length. However, the recommended size is 64 bytes.

Is there any good reason to use a 64-byte key instead of a 32-byte key?

Short answer: 32 bytes of full-entropy key is enough.

Assuming full-entropy key (that is, each bit of key is chosen independently of the others by an equivalent of fair coin toss), the security of HMAC-SHA-256 against brute force key search is defined by the key size up to 64 bytes (512 bits) of key, then abruptly drops to 32 bytes (256 bits) for larger keys; that's because in the later case, the key is hashed to 32 bytes before use. It is an argument to use a 64-byte key: it's the size giving the maximum resistance to brute force key search; and beside the key being harder to manage than a 32-byte one, using 64 bytes does not harm security, and leaves speed almost unchanged (there is no additional hashing done).

On the other hand, 256 bits of security is way more than enough for anything even vaguely foreseable, including quantum computers. If MACs are computed at a rate of $2^{88}$ per year (requiring hashing effort slightly superior to what's devoted to bitcoin mining), and they could be checked among known MACs for $2^{32}$ different keys at that rate (arguably requiring more additional effort than hashing), and we wanted residual odds of $2^{-35}$ that any key is found within 32 years, 160 bits of key entropy is enough, ignoring quantum computers.

HMAC-SHA-256 is designed for 256-bit (32-byte) cryptographic resistance in mind, with no strong argument that using a key with more entropy improves the security; beyond that, there is no assurance given by the best security proof available (Mihir Bellare: New Proofs for NMAC and HMAC: Security without Collision-Resistance, with extended abstract in Crypto 2006 Proceedings).
Thus if the key is full-entropy, there is no strong argument to use a key of more then 32 bytes.

If the key is not known to be full-entropy, there is an obvious, reasonable argument that large keys are necessary. For example, if the key was a diceware passphrase, which has an entropy of $5\log_2(6)\approx12.9$ bit/word, there needs to be 20 words in the key, that is up to 139 characters (with 6 characters per word, and space between words), to reach 256 bits of entropy.


Show How to Efficiently Solve the Computational Diffie-Hellman Assumption given an Algorithm that Solves the Square-DH Problem Let $q$ prime number, $G$ a cyclic group with order $q$ and let $g \in G$ be a generator of $G$. Suppose that you have an algorithm $A$ who takes input the element $g^a$ of $G$ and gives as output the element $g^{a^2}$ (i.e., it solves the Square-DH problem). Describe a fast (polynomial time) algorithm who takes as input the elements $g^a$,$g^b$ and gives as output the element $g^{a \cdot b}$ (namely an algorithm that solves the Computational Diffie-Hellman Problem).

This is a reduction showing that if you can compute $g^{a^2}$ given $g^a$, then you can solve the computational Diffie Hellman problem. Here is the reduction.

Let $A$ be an adversary that given $g^a$ for a random $a$, outputs $g^{a^2}$ with probability $\epsilon$. We construct $A'$ who receives $u=g^a$ and $v=g^b$ and works as follows. $A'$ runs $A$ three times on input $u$, on input $v$ and on input $u\cdot v$. If $A$ returns a correct answer each time then $A'$ will have $A=g^{a^2}$, $B=g^{b^2}$ and $C=g^{(a+b)^2}=g^{a^2 + 2ab + b^2} = g^{a^2}\cdot g^{b^2} \cdot g^{2ab}$. Thus, $A'$ outputs $\sqrt{\frac{C}{A\cdot B}}$, where the square-root is of course modulo $p$.

It remains to compute the probability with which $A'$ succeeds. Naively, we would like to say that since $A$ has to succeed on all 3 inputs, $A'$ succeeds with probability $\epsilon^3$. The problem is that the inputs given by $A'$ to $A$ are not independent. This is solved by having $A'$ choose random $r$ and $s$ in ${\mathbb Z}_p^*$ and giving $A$ the inputs $g^{ra}=u^r$, $g^{sb}=v^s$ and $u\cdot v$. This will ensure that all inputs are completely independent. Now $A'$ outputs $\sqrt{\frac{C}{A^{1/r^2}\cdot B^{1/s^2}}}$ and this will be correct with probability $\epsilon^3$.

We conclude that if the original problem can be solved with non-negligible probability then so can the computational Diffie-Hellman problem.


Are oracles needed in security proofs to prove that one problem is equivalent to the other? I have seen a few security proofs where they show that solving one problem is equivalent to solving the other, via use of an oracle.

For example, when proving that problem A is equivalent to problem B. We assume an oracle which can solve problem A in polynomial time. Are there any other ways to prove that two problems are equivalent without an oracle?

As Squeamish Ossifrage pointed out in the comments, if you define "B is at least as hard as A" by "there is an algorithm that solves A given an oracle that solves B", which is a relatively standard way of defining "as hard as", then the oracles show up naturally in the reduction.

Yet, it should be pointed out that this is not always the definition. What Squeamish Ossifrage discussed corresponds to black-box reductions between primitives A and B. Put otherwise, saying "A and B are black-box equivalent" is exactly the same as saying that one can solve A with an oracle for solving B, and the other way around. Intuitively, a black-box reduction is a reduction that looks only at the input/output behavior of the primitive/attack, and does not use any specific details of its concrete implementation. In this case, it makes perfect sense to represent it by an oracle, since we do not care about how it's concretely implemented.

There are, however, many non-black-box reductions in cryptography. Black-box reductions are still by far the most common; they are much easier to find (non black-box techniques are often very advanced), often more efficient, and allow for proving separations (for example, we know that one-way functions and public-key encryption are provably not black-box equivalent: we can demonstrate that there is no black-box construction of PKE from OWF). A non-black-box reduction would not involve any oracle. It would be of the following form:

If there exists an algorithm $\mathsf{Alg}_A$ that breaks the primitive $A$, then there exists an algorithm $\mathsf{Alg}_B$ which, given the code of $\mathsf{Alg}_A$ as input, can break the primitive $B$.

(or, equivalently, you can also talk about a provably secure construction of a primitive using the code of a secure construction of another primitive)

Example of non-black-box reductions in cryptography include the construction of PKE from iO and OWF; the construction of maliciously secure computation from semi-honest secure computation and zero-knowledge proofs; a bunch of specific zero-knowledge proofs by Barak; the construction of IBE from CDH; the construction of iO from functional encryption; the construction of IND-CCA-secure encryption via IND-CPA secure encryption and NIZKs (the Naor-Yung paradigm); and many others. Some of these actually achieve constructions which are provably impossible to obtain via black-box reduction (see e.g. the paper of Barak).


Are MD5 possibilities really $2^{128}$? I have a simple question:

Are we certain that the md5 hashing algorithm can produce $2^{128}$ different outputs ?
If so, how ?

Note: Sorry if this has already been asked, I really couldn't find it.

MD5 processes a message into a fixed-length output of 128 bits, typically represented as a sequence of 32 hexadecimal digits.

This process is not random, but it’s a so called „pseudo-random“-process (A pseudo-random process is a process that appears to be random but is not 100% random).

There is actually no proof that every hash-value of the MD5-process is reachable for some input, but it is expected to be true.

So MD5 can hash every input to an „arbitrary“ hash-value of 128 bits, bits can be 1 or 0, so $2^{128}$ possible outputs.


Commutative Hash Function for Password Challenge? I had an idea. Could anyone tell me if this is a thing, if they see any problems with it, and if they know of a commutative hash function that would make it work?

Suppose you had a pair of cryptographic hash functions, one of which could take an a key in addition to its regular input, and that these functions were commutative. So:

hash1(hash2(key, input)) = hash2(key, hash1(input))

I think this could be used to implement a very effective challenge-response password system:

Server stores storedHash = hash1(password)
User requests login
Server generates random key, sends to user. (Alternatively: User and hub use trust-less protocol to agree on random key.)
User returns sentHash = hash2(key, password)
Server compares hash1(sentHash) == hash2(key, storedHash)

The upside to this system is that even if the communications are intercepted, the users password remains safe, even for future use on the same server. Even if the user were tricked into trying to log in to a malicious fake server, the credentials they sent would be useless for impersonating them to the true server.

So... anyone see a problem with this? Anyone know a hash function that would make it work? (Or is there a reason any hash functions that's key-able and commutative would not be secure?)

If you are storing $h_1(password)$ and I break into your database, I will simply sort all the hashes I find. The one that appears most often will be $h_1($"123456"$)$, closely followed by $h_1($"password"$)$. In other words: you're storing unsalted hashes.

This is why you use special key derivation functions like scrypt and not plain cryptographic hashes on passwords.

If you are doing a man-in-the-middle attack, you generate your own key $k$ and send it to the user, who replies with $h_2(k, password)$. You know $k$ (this is still the case if you use a "trust-less protocol" to agree on $k$) so you can now try $h_2(k, x)$ for all $x$ in the 10 million most common passwords list at your leisure - even without breaking into the server.

If we're talking about key-based authentication, where collisions are unlikely to be a problem, there is an authentication protocol that uses a commutativity property a bit like you mentioned: Schnorr ZK proofs.


ClientKeyExchange in static DH I am confused about the content of ClientKeyExchange in case if the key-exchange is static DH. The TLS 1.2 standard says under section 7.4.7 in https://tools.ietf.org/html/rfc5246#page-57:

  If the client is sending a certificate containing a static
        DH exponent (i.e., it is doing fixed_dh client authentication),
        then this message MUST be sent but MUST be empty.

Is it always the case that static DH means that the client will send the static DH in a client Certificate? What is the client does not have a certificate?

Is it always the case that static DH means that the client will send the static DH in a client Certificate? What is the client does not have a certificate?

If the client does not have a certificate, then the requirement you quoted doesn't apply, as the condition "If the client is sending a certificate ..." is not met.

Instead, the DH public key is sent in the ClientKeyExchange handshake (exactly as if your DH wasn't static).


How to implement homomorphic multiplication for Elgamal? I want to add the homomorphic property to Elgamal in libgcrypt.

This is the core code I added to the library.

static void
do_homo_mul (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t data1_a, gcry_mpi_t data1_b, gcry_mpi_t data2_a, gcry_mpi_t data2_b, ELG_public_key *pkey)
{
  mpi_normalize (data1_a);
  mpi_normalize (data1_b);
  mpi_normalize (data2_a);
  mpi_normalize (data2_b);

  mpi_mulm (a, data1_a, data2_a, pkey->p);
  mpi_mulm (b, data1_b, data2_b, pkey->p);
}

But I cannot get the right result. What is wrong with my code?

If $(R_1,c_1)=(g^{r_1}, A^{r_1}m_1)$ and $(R_2,c_2)=(g^{r_2},A^{r_2}m_2)$ are ciphertexts (with respect to the same public key $A$) corresponding to two messages $m_1$ and $m_2$, then
$$(R_1R_2,c_1c_2)=(g^{r_1+r_2},A^{r_1+r_2}m_1m_2)$$
is an encryption of the message $m_1m_2$ (note that the calculations are performed in $\mathbb Z/p\mathbb Z$, that is, modulo $p$).

Assuming that mpi_mulm(r, x, y, m) denotes the computation $r=xy\bmod m$ (which quick inspection of the GnuPG source code seems to confirm), this implies that (a, b) should indeed decrypt to the product of the plaintexts corresponding to (data1_a, data1_b) and (data2_a, data2_b).

This, in turn, likely means your correctness checks are flawed. If you care to post some example data and/or code, I can take a further look at the problem.


Symmetric key in homomorphic encryption over the integers Much like this question:
Public key in fully homomorphic encryption over the integers

I am also reading I'm reading Fully Homomorphic Encryption over the Integers, but I'm working on implementing the symmetric key implementation.

It says on the first page:

  The key is an odd integer, chosen from some interval $p ∈ [2^{η−1},2^η)$.

Where $η$ is the number of bits in the key and $p$ is the secret key.

Why is it that the high and low bit must be set to 1?

I've read the answer to the other question in regards to the low bit (the key being odd), but I don't see how it applies in this case so am a bit stumped.

It turns out that just like the question linked to in the question, the key needs to be an odd number so that the encrypted number doesn't have the same parity (odd or even-ness) as the plain text value.  When it has the same parity, the encryption failed because you can tell exactly what the plaintext bit was!

As for why the high bit needs to be set, I'm going to just assume that it's to make sure the key is large, which helps security.  If someone knows differently, please inform me!


In ECC, how do I prove that point addition is commutative? I am studying elliptic curve cryptography and this question is related to the commutative property of point addition operation.

Point addition $P_3(x_3,y_3)$ of two points $P_1(x_1, y_1)$ and $P_2(x_2,y_2)$ is given by the following rules:
$$x_3 = (\lambda^2 - x_1 - x_2) \bmod n$$
and
$$y_3 = (\lambda (x_1 - x_3) - y_1) \bmod n$$
where
$$\lambda = \frac{y_2-y_1}{x_2-x_1} \bmod n.$$

To prove that the point addition operation is commutative, I simply interchange $x_1$ by $x_2$, and $y_1$ by $y_2$, and what I get is:

$$x_3' = (\lambda^2 - x_2 - x_1) \bmod n$$
and
$$y_3' = (\lambda (x_2 - x_3) - y_2) \bmod n.$$

Now it can be seen that $x_3 = x_3'$ but $y_3 \ne y_3'$; that is, I am not getting the same point $(x_3, y_3)$. But I have read everywhere that point addition is a commutative operation.

Please help me understand the problem.


Finding tetration in a multiplicative group modulo p I have a variant on the discrete logarithm problem, involving finding tetration in a multiplicative cyclic group of integers modulo a large prime $p$:

$$a = x^x \mod p$$

Where $a$ and $p$ are known, and $p$ is not necessarily a safe prime. Can $x$ efficiently be found or is this at least as hard as the DLP?

As pointed out in the comments, it's not quite clear what the problem is, but here's an easy algorithm for the (arguably) most natural interpretation.

Given any prime $p$ and integer $a$, the following procedure finds an integer $x\in\mathbb Z_{\geq0}$ such that
$$ x^x\equiv a\pmod p \,\text. $$

Pick some positive integer $e$ coprime to $p-1$. (For example, $e=1$ always works.)
Write the prospective solution as $x=e+k(p{-}1)$ with $k\in\mathbb Z_{\geq0}$.
Since the order of $x$ must be a divisor of $p-1$, the equation becomes
$$(e+k(p{-}1))^{e}\bmod p=a \,\text. $$
Raise everything to the power of $f:=e^{-1}\bmod(p{-}1)$ to obtain
$$ e+k(p{-}1) \equiv a^f \pmod p \,\text. $$
Simply solve this congruence for $k$, that is, compute
$$ k := (e-a^f)\bmod p \,\text. $$
Output $x:=e+k(p{-}1)$.

Note that the expected size of $x$ is approximately $p^2$.


EL Gamal Attack without a secret key I have the following data where all the inputs are Big Integers,

group size $p$,
group generator $g$
public key of the receiver $y$
$c_1$ and $c_2$
Random Number as well

I am trying to execute an EL Gamal Attack (On a Weak Number Generator) without knowing the secret key $x$.

$$y = g^x \bmod p\quad  \text{where } x \text{ is the secret key.}$$

As we know $y,g$ and $p$. I am trying to compute $x$.I tried as follows $m$ as,

$$m = c_2 \times (c_1^x )^{-1}$$

By converting $m$ as ByteArray, I am not getting the desired output!

What I am missing out? What's the advantage of having this random number as input?

Actually,I tried finding x by taking log on both sides,

  log y = x log g mod p

Each y, g, and P are of 1024 bits. Java is not supporting this BigInteger computation. How can I solve this equation involving such a big number?

Or is there any other shortcut available to compute the secret key, if the public key and g are given? Also, how can I take advantage of the given random number?

$g$, $p$, and $y$ are of length 308 (decimal digits). How can I compute $x$ accurately from the equation?

Computations with integers this size (for example, verifying a guess of an integer $x$) are possible with Python's pow in its three-arguments form, Java's BigInteger modPow, GP/Pari, Sage, Mathematica…

  I tried finding $x$ by taking log on both sides

That method can give you a real $x$, but here we want an integer. Given 1024-bit prime $p$, generator $g$, and $y=g^x\bmod p$, there is no general and easy way to find an integer $x$. That may be possible if the order of $g$ is appropriately smooth, but nothing in the context suggests that. That also may be possible if $x$ was generated by a weak RNG, but since the nature of the weakness is untold, it is hard to tell how to proceed.

  Random Number as well

Perhaps that mysterious given helps to determine the nature of the RNG weakness. Or/and perhaps this given is somewhat related to the random number generated during the encryption, which knowledge would trivially allow to decipher without the private key $x$.


How to steganographically embed data in cropped/resized images? The problem:

An artist posts an image of their work online with a creative commons attribution licence (on site A), someone reposts the image with attribution on another site (site B), the internet happens and the image has been cropped resized and the attribution notice is lost.

The (tentative) solution:

The artists name, web site and attribution licence is steganographically embedded into the image. So consumers of the image or web sites who host these images can pull out the data (and display it).

The question:

How would I go about steganographly embedding data into an image, that will be resilient to resizing and cropping?

Things not to worry about:

Tampering of the data
Just using exif metadata (as that is often lost)
Convincing all the artists they should do this

This is a big research field with a lot of different techniques. The right term here is "watermarking". Similar to steganography but with different requisites: we hide only a mark and we want to be resistant to cropping, resizing and others (blurring, compression, noise addition, ...). One approach to resist cropping is to copy the mark several times in different positions of the image. One approach to resizing is to hide information by modulating the DCT coefficients.


Tactics available to help prove security of a new system? I believe that the accepted tactic to "prove" a system as secure is to allow the crypto-community to review it and if no vulnerabilities are found over a long period of time (5 or 6 years), then a new system can be accepted as secure until proven otherwise. Please correct me if I'm wrong.

That aside, are there any set of requirements a developer can proactively test their cipher system against before a public release?

I'm working on a large key (4096 bit), symmetric encryption system and I'm doing my best to be weary of the "anybody can make an encryption that they themselves cannot break" trick of believing that my cipher is unbreakable.

What kind of tests can I run on the process or the output? Are there good ways to measure entropy? What statistics should I expect after encrypting a section of data? I know there won't be some magic function that proves I'm secure, but I certainly don't want a public release followed immediately by being broken by a simple problem that some data analysis would have found.

Prove resistance to differential cryptanalysis.

For example, this presentation: Provable security against Impossible Differential Cryptanalysis. Or this paper:  ProvableSecurity Against a Differential Attack (1995)
Prove resistance to linear cryptanalysis.

For example: On Measuring Resistance to Linear Cryptanalysis
Run a bunch of statical tests against the cipher.

For example: Cryptographic Randomness Testing of Block Ciphers and Hash Functions


What is the correct way to notate elliptic curve properties When looking through elliptic curve and modulus posts i can see many examples of people referencing $p$ and $n$, in upper and lower case, and sometimes $Q$ is written instead of $p$ or $P$, and I think I've seen $N$ written as $Q$ once.

For example, this is one of the things I've seen for sepc256k1:

  $p$ = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
  $P$ = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
  $n$ = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
  $N$ = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
  $Q$ = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

I am confused about which is considered the correct way to write $p$, $n$ and $Q$. Is it considered better to use $Q$ instead of $p$? Is there an agreed standard? Does uppercase signify something different than lower case? I see a lot of things, and all of this wastes a lot of thinking energy worrying about the correctness of how to write a letter.

What is the correct way to notate elliptic curve properties?

There is no standard way, and I think it's impossible to find universal agreement.

However, it is pretty common to use lowercase letters for integers and uppercase letters for elliptic curve points.
And it is very common to indicate as p the prime defining the field $\mathbb F_p$ over which the curve is defined.

For the order of the curve you can use $\#E(\mathbb F_p)$, sometimes n is used but it is also common to use n to indicate the order of the largest prime order subgroup (note that if $\#E(\mathbb F_p)$ is prime then the two indicate the same value). Bernstein notably uses l to indicate the order of the largest prime order subgroup.

h is (I think) universally used to indicate the cofactor, such that $\#E(\mathbb F_p) = hl$

Also the curve's parameters are indicated as lowercase. For short Weierstrass curves you have a and b. For Twisted Edwards you have d and a.

For the points G, P, Q, B are quite common and if G is used then it indicates the generator of the largest prime order subgroup. Note that Bernstein uses B for the generator (Base).


Signature Verification: High level I'm trying to understand how certificate signing and verification works conceptually. I know the classic example with asymmetric cryptography- the sender encrypts data with public key of receiver, data goes over unsecure channel, receiver decrypts with private key.

When it comes to certificate verification that's where I start to get confused.

According to Wikipedia in the picture they show, the hash of the certificate is decrypted with signer's public key. So which is it?

I thought that maybe upon receipt, the contents of the certificate are hashed and encrypted with the public key and the result is compared with the provided "digital signature". But then I realized an attacker would be able to reproduce this process as well without knowledge of the private key.

Signature generation and encryption are two different concepts. The fact that both can use the same one way function does not change that fact. In the case of RSA, both signature generation and encryption (as well as verification and decryption) uses modular exponentiation. These are called the RSA primitives. They have however different inputs: one uses the private key, the other the public key.

Signature generation and encryption may relate differently for other one way functions. This is for instance the case for the primitives used for elliptic curve cryptography (ECC). In ECC the primitives used for ECDSA signature generation cannot directly be used for encryption/decryption.

The idea that signature generation and encryption should be seen as different concepts is actually made pretty clear in the PKCS#1 standard (of RSA laboratories): the signature generation primitive is called RSASP1 and the encryption primitive is called RSAEP. They do represent the same algorithm internally.

RSAVP1, the RSA verification primitive is indeed performed with the public key. But it doesn't really decrypt any confidential information. Instead it produces a padded hash. This padded hash is free for anyone to see - anybody may verify the message (in this case the certificate). If you require confidentiality you should encrypt the message and the signature value using a key or keyset where the secret key is known by the receiver.

The padding is validated and the hash is compared with the one computed over the (signed parts of the) certificate. If both the padding and hash are correct then the signature must have been created using the private key belonging to the public/private key pair. This is what establishes the trust.

As long as the private key is managed (held) by the signing party then the signing party must have been involved in generating the signature. This is called non-repubility; the signing party cannot claim that somebody else created the signature.


Is it possible to construct dataset for only another party to consult? Is it possible to construct a dataset made of some kind of probabilistic encrypted indexes such that anyone can update the information contained in the set but only the one with a secret key could be able to retrieve the information for a given index without the need to retrieve the whole set?

For example, if I have a set of messages sent to me hosted remotely, like an e-email service, indexed by dates, is it possible to obfuscate the dates such that anyone can still send me a message and index it (by inserting into the set), but no one with access to the set can gain no information about the dates distribution except for the ones with the secret key? With the restriction that when I want to retrieve messages from a given date, I only need to receive those and no others.

Answering my own question. I believe it is possible. We can use the scheme by Boneh et al. described here.

It uses pairing-based cryptography to be able to create a searchable, asymmetric, tagging scheme. In this scheme, queries are made through a trapdoor of the real key that we want to search, making it impossible for the set holder to retrieve information about the underlying queries.


Find encryption algorithm knowing input, output and secret Today on my PC I found some old backups; they contain also some pictures I encrypted years ago with a smartphone running Windows Mobile but I don't remember the application I used to cipher them.

I'm quite lucky, because I found a picture on the backup both in original and encrypted version. Is there any way of finding the algorithm/application to decrypt them knowing:

The original "plain" file (es. MyPicture.jpg, 7176 bytes)
The encrypted file (es. MyPicture.jpg.pmf, 7176 bytes, same size of the original)
The secret password I used to encrypt them (it's a 10 characters string)

I also tried to search on Google for the PMF extension but unfortunately I didn't find any helpful information.

Chances of finding the algorithm

It is relatively unlikely that you will find an answer. Ciphertext itself has been designed to be indistinguishable from random bytes (well, for modes based on block ciphers anyway).

The Kerckhoff's principle indicates that the encryption algorithm should not be depended on to keep the plaintext secret. But that doesn't mean that it is necessarily easy to find the algorithm; if the algorithm is used as as secret it may be impossible to find. Kerchhoff just states that it is unsuitable as a key because it will likely be leaked.

Although encoding modes, modes of operation, padding modes and ciphers have been standardized, there are a lot of them and the complexity of finding an exact match rises quickly, and you don't even know the key used.

Of course, if you don't have any experience doing this your chances decrease, as it is easy to make mistakes and e.g. overlook a possible solution or correct answer.

If a modern cipher was used

As a header is missing, it seems you're dealing with a file that is directly encrypted. AES is always a pretty good bet, and the mode is probably that of a stream cipher (CTR, CFB) as ECB and CBC would add padding. CBC ciphertext stealing is hardly used and requires at least one block, while files can be any size. Encryption / container protocols such as OpenPGP/ZIP/whatever can be safely skipped as they would expand the file size.

The really tricky part is how the password was transformed into a key. Normally you would use a PBKDF - a password based key derivation function - to derive a key from a password. However, a PBKDF requires a salt and iteration count. Generally those are stored with the ciphertext, but as your ciphertext size did not expand on the plaintext size, the salt is missing in action, making PBKDF less likely. You could try AES using the password directly as a key, extended with zero's on the right hand size.

Generally modes require an IV, so you may want to try an all zero IV instead of the normal one. Obviously the IV is not prefixed or, indeed, the ciphertext size would have expanded.

When trying to find the algorithm compare the beginning 8 bytes of the file, decrypting e.g. 32 bytes. Do not use padding when decrypting, as that will simply fail. If you have a match then use that information to continue.

Some other legacy options

As this is clearly not a standardized format the encryption can be literally anything, including classical ciphers. I'd certainly try e.g. the Vigenère cipher, using XOR with a repeated password in ASCII.

Another option is e.g. (PHP) mcrypt in ECB / CBC mode using two-key triple DES. Expand the key to 16 bytes by adding zero bytes at the end and then decrypt with an all zero IV. Blowfish, another 64 bit block cipher, may also be an option. Some bad libraries such as mcrypt do not pad if the plaintext is a multiple of the block size, and your (encrypted) image size is a multiple of 8 bytes (64 bit), but not 16 bytes (128 bit).

Trying RC4, another common cipher, could also be a good idea. It is a stream cipher that takes a key of configurable size. It doesn't take an IV; the key is supposed to be random each time (generally this can be established by simply concatenating the original key bytes and the IV bytes and use that as a key).


How unique and secure are verification codes created from different hashes? In order to construct a short, yet cryptographically strong verification code, I'm thinking about using the output of several hashes computed over the same data (device uuids + raw certificate data).

Pseudocode:

char *data[] = [clientUUID + serverUUID + certificateData];
uint16_t dataLength = length(data);
char *verificationCode[15];

sha256Hash[] = sha256(data, sizeof(data));
sha1Hash[] = sha1(data+sha256Hash, sizeof(data)+sizeof(sha256Hash));
md5Hash[] = md5(data+sha1Hash+sha256Hash, sizeof(data)+sizeof(sha256Hash)+sizeof(sha1Hash));

// Store length at start so the size of data can't vary
verificationCode[0] = ((char *)dataLength)[0]
verificationCode[1] = ((char *)dataLength)[1]

// Now fill the rest of the verificationCode with a mix of bytes from the different hashes
verificationCode[2] = sha256Hash[0] ^ sha1Hash[0] ^ md5Hash[0]
..
verificationCode[15] = sha256Hash[13] ^ sha1Hash[13] ^ md5Hash[13]

I'd then present the verification code as base64-encoded string to the user on both devices (computer + mobile device) to verify upon pairing. My thinking here is that it should be computationally very expensive to find a set of data with the same length that generates the same hash results across all three hashes - and hence the same verificationCode result.

However, I also see that using only a portion of the hashes should definitely weaken the protection.

Is a verification code like the one computed above secure for a short time window (think: couple of minutes)? Or is there an established and proven alternative I can use for a short, human-readable verification code ?

There should not be any need to use several different hashes. One such as SHA3 will provide what you need. A Hash, Salt, and Stretch configuration as provided by for example bcrypt or scrypt will add extra protection if you want it.

As for shortening the code, yes this will decrease security but the same length of a NIST recommended password should suffice: 8 characters


How trivial is it to derive a private key from two public keys? It turns out that what I was attempting to do was create a form of ECDSA threshold signature protocol by just giving away multiple public keys and then having the two parties solve for the private.

Original Question

I am currently working on building an application and I have a question about the triviality of deriving private keys from multiple public keys. I have read many places that it is possible to derive multiple public keys from a single private key but that publicly revealing more than one will jeopardize the private keys security. If I want to produce two public keys from a single private key (ECDSA) and derive the private key later using only the public keys, how much does knowing the two public keys help. Will two public keys easily yield a single private key? Will introducing more than two public keys reduce the amount of computation that it takes to derive a private key if it is computational difficult?

Responding to comment-implied intended question:

The RSA alternative public keys revealing the secret factors of $N$ is not a suitable means to implement threshold protocols. Instead you should be using actual threshold protocols, such as t-of-n or n-of-n signature schemes.

ECDSA uses DSA, not Schnorr, so my usual suggestions do not apply. Although a quick search for "threshold dsa" yields:

Securing Bitcoin wallets via a new DSA/ECDSA threshold signature scheme

Old answer (kept for alternative interest)

This sounds like key-blinding, where you derive a subkey from a master pair. Say you have the secret key $k$, public key $Gk$ and the blinding factor $b$, the subkey secret is $kb$ and the subkey public is $Gkb$.

$Gkb$ and $Gk$ cannot be used to recover $k$ nor $b$, without breaking Diffie-Hellman. $b$ may be derived from $Gk$ plus some contextual string, this allows someone with the master public and master secret to compute the subkeys respectively. These keys are tightly related, given $kb$ and $b$, you can recover $k$. If you give someone $kb$ but keep $b$ secret, they cannot recover $k$. If $kb = k * b$ then $k = kb / b$.

If deriving a subkey from a public key gave you any information useful to recover the secret key, the scheme is broken with only one public key.


Variant of Schnorr Protocol (Difference pair of response and verification) When I am trying to learn deeper to Schnorr Protocol. I found that for deference there is more than one response and verify pair. But I am not sure am I right.

We will use Schnorr Protocol to prove the knowledge of $x$ in $y=g^x$. Here is the details of Schnorr Protocol, first prover send $t=g^r$ where $r$ is a random number to verifier. Verifier send challenge $c$ to prover, next step prover will calculate response and let verifier calculate is it correct by a function. Here is the question.

For $y=g^x$, $t=g^r$ and $c$, we have 3 equation below.

$g^x g^{rc}=yt^c$ $\rightarrow$  $g^{x+rc}=yt^c$
$g^{xc} g^r=y^ct$ $\rightarrow$  $g^{xc+r}=y^ct$
$(g^x g^r)^c=y^ct^c$ $\rightarrow$  $g^{c(x+r)}=(yt)^c$

Can I say I can choose either one of that pair to finish the protocol?

response $s=x+rc$, verify $g^s=yt^c$
response $s=xc+r$, verify $g^s=y^ct$
response $s=c(x+r)$, verify $g^s=(yt)^c$

Am I correct?

response $s=c(x+r)$, verify $g^s=(yt)^c$

This one doesn't work; a lying prover can chose $t = y^{-1}g^n$, for an arbitrary $n$.  Then, when the challenger responds with a $c$, the lying prover can respond with $s = nc$, satisfying the relationship.

The other two are good; the second is the standard Schnorr, and the first is standard Schnorr proof of the inverse relationship, that is, if you're proving the knowledge of $y^{x'} = g$ (which is equivalent to knowledge of $g^x = y$)


CAPTCHA like mechanisms : Impact on confidentiality of Info Humans have  sensory and cognitive skills for solving simple problems that prove to be extremely hard for computer software. Such skills include, but are not limited to processing of sensory information.

One example of the above is randomised distortion of a text image so that it is easily recognisable by humans through their advantage in identification of objects and letters within a noisy graphical environment. This poses a sort of one way function ; where solution by a human is almost instantaneous but that by a computer takes a  lot of effort.

The preceding of course describes a CAPTCHA.

The questions are:

What kind of 'confidentiality' are we looking with such mechanisms? Simply put we have a text which is confidential to a machine. There is no key exchange involved.
Are their any tangible gains in using such a method and then enciphering the text through a deterministic crypto function (RSA, DES, etc.)
Any references in this regards?

What kind of 'confidentiality' are we looking with such mechanisms? Simply put we have a text which is confidential to a machine. There is no key exchange involved.

I'd put this down as a kind of obfuscation for machines. That is, unless you take all the knowledge of the world as key.

  Are their any tangible gains in using such a method and then enciphering the text through a deterministic crypto function (RSA, DES, etc.)

No, because you first would have to establish trust for a public key or share an (authenticated) secret. Besides that, it is unclear what this would defend against.

Using TLS could be beneficial, although not strictly necessary. The attack vectors probably do not include man in the middle or even eavesdropping. Basically it's just a challenge response protocol. I could see how eavesdropping lots of challenges/responses could make it possible to build up a table though.

  Any references in this regards?

Nope, sorry.


How does a Hashing algorithm always result in a digest in a fixed size? This question revolves around the Hashing Algorithm attribute that the resulting digest is always the same size (also known as Fixed Width). For example, whether you hash the word "hello", or 10gb file, MD5 will always return a 128 bit digest.

My question is, how do hashing algorithms always result in a constant length digest ?

The only operation I can think of is the MOD / remainder operation that regardless of the starting value, after doing a MOD operation using modulus X, the result is always a value between 0 and (X-1). But I am specifically curious if there are other operations that also serve in reducing (or increasing, I guess) the digest size to get to the desire digest length.

note: I am not interested specifically in how MD5 does it, but in what operations exist that any hashing algorithm might use to always ensure the same size digest

Basic Building Blocks of a Hash Function

The part of a hash function that leads to the digest always being the same size regardless of input length is called the compression function. The compression function is then linked whmacith a domain extender which extends the compression function to allow it to map across any length of input.

Construction From Block Ciphers

I am going to use the construction of the WHIRLPOOL hash function as an example of how a compression function and domain extender works.

Setup

It is very simple to construct a hash function from a block cipher. The first step in a block cipher algorithm would be to split the data to be hashed into blocks the same number of bits as the input to the block cipher being used. If needed padding is added to the input to make it a multiple of the key size. No difference here from normal block cipher operation.

Compression Function with Domain Extension

There is a lot of variation between different designs here but basically what they all perform though is some means of feeding each block into the chosen cipher and some combination of XOR or some other operation on the previous rounds output, the current rounds output, the input, or all of the above. For example the following is the compression function of WHIRLPOOL.

For the following let:
$$
\begin{align}
    m_i\:&=\:\mbox{Message or Input}\\
    H_i\:&=\:\mbox{Output}\\
    W\:&=\:\mbox{Block Cipher}\\
    g\:&=\:\mbox{Bit Mapping Function}
\end{align}
$$

To construct a new hash function it would be possible to simply plug a new block cipher into $W$ and the size of input and output would change with the input and output new cipher. There are many other forms of compression function structures with different properties also, and they mainly consist of changing when, what, and in what order things are combined. I would put a link here but reputation limit, so wikipidia's compression functions article has more on this.

The domain extension which allows it to operate over any amount of data is simply how the output feeds back into the cipher as the key as each subsequent block is encrypted replacing the key schedule. It will only output the result after all blocks have been fed through the block cipher effectively limiting output to the size of the ciphers output no matter the input size.

Other Constructions

There are also hash functions that are based on mathematical problems that are hard to solve and also stream ciphers. This is really a topic that an entire book could be dedicated to but they all use the basic structure of a compression function and domain extender. More info on the general construction of hash functions, compression functions, and domain extenders can be found here: https://eprint.iacr.org/2012/322.pdf


Rijndael S-boxes: Where do the $\mu$ and $\nu$ polynomial ring elements come from? I've asked some other questions before about Rijndael's S-boxes, and step by step I'm coming to an understanding; but those steps often guide me to new questions.

I did some lines of code to understand how these S-boxes work implementing $S(z) = f(g(z))$ where $g(z)$ is the transformation by multiplicative inverse in a polynomial field and $f(z)$ the affine mapping understanding a word as element in a polynomial ring following the expression.

\begin{equation}
    \begin{aligned}
        b(z) &= \mu(z) \cdot a(z) + \nu(z) \\
             &= (z^4+z^3+z^2+z+1) \cdot a(z) + (z^6+z^5+z+1) \;\bmod{(z^8+1)}
    \end{aligned}
\end{equation}

In the "AES proposal"(version 2 from 1999), section 7.2 explains that $\mu(z)$ was chosen from the set of co-primes with $z^8+1$ as the one with the simplest description. But what can be understood as "simple description"? The condition to select $\nu(z)$ looks to be much clear (no fixed points, neither opposite fixed points, isn't it?).

If I did it well, there are 129 co-prime polynomials to select 1 (and its inverse) and I cannot see what makes this special. $\mu(z)$ has 5 ones and its inverse $\mu^{-1} (z)$ has 3, and there are other pair candidates with a relation 3-3 or 5-5 of 1s. Another description of simplicity perhaps was palindromic representation, but it's neither the case. They are not the shortest or longest ones to highlight them over the others. What makes them special to be chosen?

Ps: In the mentioned "AES proposal" the $\mu(z)$ and $\nu(z)$ are not the ones above, neither are the ones shown in section 3.4.1 from "The Design of Rijndael" but with the 2 shown here I've reproduced the official S-boxes and the tables of the section C of the mention book. Would I be wrong?

Update 20150320 based on the comments received:

Based on the definition of the "simplicity" criteria to select $\mu(z)$, it cannot be evaluated what makes $z^4+z^3+z^2+z+1$ special. The only known requirement of this polynomial is that it must have a multiplicative inverse in the ring defined by $z^8+1$: there are 129 elements invertible.

The other parameter $\nu(z)$ has an evaluable criteria to do a selecting: it must not produce any fixed point, neither opposite fixed point. Checked this, the number of polynomial pairs that satisfies that in the ring are 21717. A big number. In a shorter view like fixing $\mu(z)$, the number of possible $\nu(z)$ that satisfies the seconds criteria are 223.

Even Rijndael usually is implemented storing the S-Boxes, the calculation times looks not very relevant, but perhaps they are, aren't it?

In those boxplots are represented average calculation for each of the candidate pairs. On the left using doing the modular product and on the right using the MDS matrix suggested in the Rijndael's documents.

Apart from the think that the matrix method is not better in general, the times for the official pair are represented by coloured dots. There are very many better candidates.

I did a seconds figure as a branch that assumes that the official $\mu(z)$ has something special I cannot see.

Here that data set are the 223 different $\nu(z)$ having $\mu(z)=z^4+z^3+z^2+z+1$. Again be careful with the scales on the y axis.

The calculation time for the official pairs have been also draw as coloured points. And here the official $\nu(z)$ doesn't show any timing property.

The code of this test is in a Rijndael project in github. From a command line it can be repeated by call $ python Polynomials.py --test-ring=8 and the basic things make with R are in a Polynomials subdirectory.

Finally I've went to the source and I've mailed the Rijndael's authors. They have answered very fast and very nice.

I've understood the other way around. The affine transformation is over the vector space $((GF(2))^8$ and what they've say as simplicity was that, between all the possible affine transformations they select one that can also be described as product and addition in the ring defined by modulo $z^8+1$.

There is no mathematical argument to select as $\mu(z)$ any of the invertible elements above the others. And for the $\nu(z)$ selection something similar happens but here exist the restriction to avoid any fixed or opposite fixed points.

Then the only argument to choose one or another can be the calculation time, but once the S-Boxes are pre-calculated it doesn't provides any extra advantage.


Is security against semi honest adversary inheritable? I have a two party protocol, let's call it $M$. At some point, there are $k$ steps, each one involving an oblivious transfer protocol, which is known to be secure against semi honest adversaries. These OT protocoles have independent input and outputs for different steps. Also, I have shown that $M$ is semi-honest if the parties ignore the inside states of each OT protocol.
Can I say that $M$ is also secure against semi honest adversaries? Or do I have to include in the view of each adversaries the 'tape' of values involved inside the subroutine OT protocol?

Is it possible to give an answer that does not depend on how OT protocols work. For instance, lets say that a protocol $P$ uses independent instances of $M$ as a subroutine, and suppose $M$ is in fact secure against semi-honest adversaries. Can we say $P$ is secure against semi-honest adversaries?

In general, no, you cannot do that. That is why frameworks like universal composability exist.

In the UC framework, you prove a protocol, $\pi_1$ is secure according to some adversary model. You do this by showing how $\pi_1$ is indistinguishable from some ideal functionality $\mathcal{F}_1$, where the ideal functionality is secure by definition (e.g., via the use of a trusted third party).

Then, say you are developing another protocol, $\pi_2$, that calls $\pi_1$ as a subroutine. You can replace the call to $\pi_1$ with a call to $\mathcal{F}_1$ in $\pi_2$. Prove the (UC-)security of $\pi_2$ run in this manner, which should be easier since you have taken a portion of it and replaced it with a "secure-by-definition" subroutine. The theorems behind the UC framework prove that if $\pi_2$ calling $\mathcal{F}_1$ is secure, then $\pi_2$ calling $\pi_1$ instead is also secure.

Without something like this, you cannot simply inherit security of protocols called as subroutines. The picture is different, however, if the protocols are run sequentially, as mentioned in the comment below.


Does knowing modular eth roots help in factoring n? Consider $x^e \equiv a\pmod n$, given $n$, $a$, and $e>2$, with $n$ being a composite integer and unknown $x$.
Can a hypothetical function $f(a)=x$, an $eth$ root extractor, be used / adapted to factor $n$, in the same way that the multiplicative order of $x \space modulo\space n$ can be used to factor $n$ like in the classical part of Shor's algorithm?

The RSA problem, which you describe, is not known to be equivalent to factoring and there is evidence both ways. In [BV] it is shown that this barrier might be inherent: using a black-box separation technique called meta-reductions, they show that certain restricted class of reductions are not possible. On the other hand, it was shown later in [AM] that in the generic ring model (see [JS]), these problems are equivalent. That is, any speed-up in breaking RSA has to exploit the representation of $\mathbb{Z}_N^*$.
You can read about more related works in §1.3 in [AM].
[BV]: Boneh and Venkateshan, Breaking RSA may not be equivalent to factoring, Eurocrypt'98
[AM]: Aggarwal and Maurer, Breaking RSA Generically Is Equivalent to Factoring, Eurocrypt'09
[JS]: Jager and Schwenk, On the Analysis of Cryptographic Assumptions in theGeneric Ring Model, Asiacrypt'09


Question about degree of regularity I have been reading some papers on cryptography based on multivariate systems and I have a question. How does one relate the difficulty of calculating Gröbner basis (GB) of a multivariate system with its degree of regularity?

From what I understand, for a lot of cryptosystems, there are ways of getting a system of polynomial equations, and a solution for such a system will give us the secret key (let us suppose this is unique). Once we have such a system, we can 'linearize' and solve them (like in Arora-Ge) or we can attack the system by calculating its GB and finding the root from there.

From Bardet's paper, for semi-regular systems, there is a quantity called a degree of regularity (there is also a way to calculate it) and she also gives how to estimate the difficulty of GB calculation using this quantity.

My question is: what if we don't know if our system is semi-regular? This degree of regularity seems to be roughly the highest degree term in the GB. If so, how can I estimate the highest degree term of the GB of a system of polynomials that I have in my hand?

There seem to be a few papers which go into any sort of detail in these topics, so I will be glad if I could also get some papers to read.

For random systems of multivariate polynomial equations, the assumption that it is regular or semi-regular is generally accepted. Here "random" means with every coefficient being sampled uniformly. An open question in this field is to determine the probability of a random system being regular or semi-regular as a function of the number of variables, equations, and of the degree. This assumption implies that this probability is cryptographically negligible, but until that is proven it is technically an assumption.

Unfortunately, for systems of multivariate polynomial equations that are not random, we don't even have such an assumption, much less a rigorous framework supporting it. The best you can do is instantiate the system of equations for various small parameters and observe to what degree, if any, the empirical degree of regularity deviates from that of random systems with the same dimensions.

Having said that, there might be a couple of interesting sources for you in this vein:

Faugère and Perret study the complexity of a direct algebraic attack on UOV, and observe that the degree of regularity of the resulting system of polynomial equations equals that of random ones. This result has since been used to justify the stronger assumption that attacking UOV in this way is the same as solving random systems of equations, which enables complexity estimation and hence parameter selection. IACR ePrint
Ding et al. study the first fall degree, which is similar to but subtly different from the degree of regularity, of Square systems which are $\mathbb{F}_q$-affine equivalent to the monomial $\mathcal{X}^2 \in \mathbb{F}_{q^n}[\mathcal{X}]$ for some odd $q$. They conclude that this degree is exactly $q$. This is surprising, because generally we observe that the degree of regularity is independent of the field over which the equations are defined. Unfortunately, Square systems are insecure due to structural attacks that have nothing to do with Gröbner bases. ScienceDirect
Ding and various co-authors study the same first fall degree in the context of HFE$_v^-$ systems. They achieve upper bounds on the first fall degree (which they confusingly call the degree of regularity) as a function of the degree of the hidden polynomial, the number of vinegar variables added, and the number of polynomials dropped. Unfortunately, this upper bound is not tight and so it cannot be used to argue that a HFE-like system is probably secure. Springer Journal page Author home page


Can a LFSR be cryptographically secure? I have been looking at an embedded microcontroller which has a cryptographic hardware engine (in particular the PIC32MZ family). These devices have what they advertise as a cryptographically secure PRNG, as well as a true random number generator.

The features of the random number generators are,

  TRNG:

  List item
  Up to 25 Mbps of random bits
  Multi-Ring Oscillator based design
  Built in Bias Corrector

  PRNG:

  LSFR-based
  Up to 64-bit polynomial length
  Programmable polynomial
  TRNG can be seed value

From what I've read about LFSR PRNG (in particular this answer) my understanding is that you only require 2*n bits to be able to determine the polynomial of the LFSR and hence all the random numbers that it generates.

If my understanding is correct, then only 128 bits (16 bytes) of random data are required before the random data is compromised - that is just enough for a single AES IV.

One way that I can imagine making the PRNG cryptographically secure is to reseed it after every 16 bytes using the TRNG - would this be secure?

Is it even possible to make a LFSR cryptographically secure?

With a 64-bit known polynomial, future output of an LFSR can be trivially predicted from the last 64 bits output. Even if the 64-bit polynomial is unknown, the last 128 bits are enough, using the Berlekamp–Massey algorithm. Thus indeed, the LFSR-based PRNG in the hardware described in a section 27 of the document linked to in question, with some additional info here, is unusable as a CSPRNG, just like any pure LFSR PRNG is.

It is possible to make a passable CSPRNG by combining LFSRs. One very simple example is the Alternating Step Generator, proposed by C. G. Günther in Alternating step generators controlled by de Bruijn sequences (Eurocrypt 1987). One LFSR decides which of two other LFSRs is clocked, and the output is the XOR of these two LFSRs. The three LFSRs are customarily non-stationary, maximal length, and of distinct but comparable size. The ASG has no published attack (that I know) that can be interpreted as claiming an effort better than $O(2^{n/6})$, where $n$ is the total number of bits in the three LFSRs (assumed of about equal size); and in fact I'm not sure this attack beats this one, which I read as more like $O(2^{2\cdot n/9})$.

I can't however recommend the ASG, or any generator easily described as a combination of LFSRs, because we now have better constructs, with more conjectured security per bit, and easier software implementation, like Trivum.

Addition (updated): If the 64-bit seed is from a good TRNG; and the LFSR is maximal-length, that is with a primitive polynomial; and the LFSR is reseeded after 64-bit; then the 64-bit output of the LFSR is not worst (or much better) than the 64-bit output of the TRNG. It is actually easy go from one 64-bit value to the other, with knowledge of the polynomial.

My understanding of the PIC32MZ PRNG is that it is more applicable to generating specific sequences defined using a prescribed LFSR, as might be desirable in some pre-existing protocols or applications, e.g. test sequence, CRC, or spread-spectrum radio; than it is as a CSPRNG.


Can I find the IV of a single block of SHA256, given the plaintext and digest? Each 512-bit block of SHA256 takes an initialization vector (IV) and message schedule and returns a digest. Knowing the message schedule and resulting digest, is it feasible to reverse the algorithm to find the IV?

My intuition tells me no because the IV is added to the working variables immediately before returning the digest, causing a dependency on the IV at both the beginning and end of the algorithm. Is this correct?

If we how to recover the previous state of SHA-256 with less than $2^{254}$ expected effort (as measured by number of hash compression operations), then we can find SHA-256 preimages with less than $2^{256}$ expected effort, and hence would be a weakening in the expected SHA-256 cryptographical strength.

Here's how this works; suppose that we can find the previous state with expected effort $M < 2^{254}$.  Then, what we do is select two blocks (with appropriate SHA-256 padding in place for a 56 - 119 byte hash), and find the previous state for those two blocks from the target state; expected effort $2M < 2^{255}$.

Then, we would try various initial 64 byte blocks, and compute a forward hash compression operation on them (using the standard IV); we "win" if the resulting state is either of the previous states from the previous step.  If we assume that the SHA-256 hash compression functions acts like a random number, then the probability of any guess of the initial block would succeed with probability $2^{-255]$; hence this takes an expected $2^{255}$ hash compression operations.

If we find a match, we can immediately construct a message (consisting of the initial block that won, along with the final block that matched it) that SHA-256 hashes to the target value.

Total expected effort: $2M + 2^{255} < 2^{256}$

Notes:

Obviously, if $M$ is significantly less than $2^{254}$, then we'd generate considerably more than 2 final blocks and intermediate states.
I did skip over the point that it's possible that there is no intermediate state that is mapped to the final state via the message block we chose.  This would decrease the limit that $M$ can be somewhat...


Can machine learning analyze random number generator? I'm studying for random number generators(RNG) and I saw about machine learning a few days ago.
So I searched analysis of RNG using machine learning.
But I couldn't find such fields.
Are there such examples for analysis of RNG using machine learning?
No matter some papers of articles.

The goal of an ideal cryptographically secure pseudo-random number generator (CSPRNG) is to produce a stream of numbers that no machine can distinguish from a truly random stream of numbers. Formally, it's impossible unknown whether it's possible to prove that a CSPRNG is truly random.

That being said, there exists a family of statistical tests that can measure whether a sequence of numbers appears to be uniformly random, and produce a probabilistic analysis as output. I'm not sure if these tests qualify as related to machine learning, but here are some examples:

Chi-squared distribution testing.
Statistical hypothesis testing.

If you are interested in trying out a CSPRNG, you can use:

AES-CTR with a random key acting as the seed.
Under Linux, Mac OS X, BSD, /dev/urandom.
window.crypto.getRandomValues() in your browser console (Chrome, Firefox).

Note that not all PRNGs are CSPRNGs.


Encryption that does not allow the encrypting party to decrypt I am very new to cryptography, and am having a lot of trouble googling my way to an answer to the following problem.

We have an external party (telephony provider) recording phonecalls for us. We would like to make very sure these can only be listened to when appropriate. The ideal solution would be for the external party to encrypt them using a key, that can not be used for decrypting them. We would then deposit the decryption key with a third party (ie. lawyer). That would mean that if I wanted to listen to a conversation illicitly, I'd have to convince both the telephony provider to hand over the recording and the lawyer to hand over the decryption key. separate instances, who would not know each others identities.

Does such an encryption scheme exist?

I've looked at asymmetrical decryption like RSA, but from my reading of http://logos.cs.uic.edu/340%20Notes/rsa.html it would seem like if I encrypt using a public key, then knowing that public key should be enough to decrypt a file, even without knowing the private key? Or am I misunderstanding this?

Yes, you're misunderstanding how public key encryption (such as RSA) works.  Indeed, the entire point of public-key encryption schemes is that the public key can be used to encrypt data, but not to decrypt it; for decryption, the private key is required.

However, there's a catch that you should be aware of: the public-key encryption schemes we currently know of are generally not suitable for directly encrypting large amounts of data, because:

they're really slow, especially when compared to symmetric encryption schemes like AES; and
they tend to produce ciphertext that is larger than the encrypted plaintext, often significantly so.

The usual solution to these problems is to use hybrid encryption.  Basically, what programs like PGP / GnuPG do to "encrypt a file with RSA" is that they generate a random "message key" for a fast symmetric cipher like AES, encrypt the file with that AES key, then encrypt the AES key (which is short, only 16 to 32 bytes) with RSA, and finally join the two ciphertexts together (along with various kinds of metadata) as the encrypted output file.

As long as the intermediate AES key used to encrypt the data is safely discarded, the only way to decrypt the encrypted file is to first extract the encrypted AES key from the encrypted file, decrypt it with the RSA private key, and then decrypt the actual data with the decrypted AES key.  But in principle, a malicious encryptor could save a copy of the AES key (or simply generate it according to some deterministic pseudorandom algorithm that they can later repeat), and thereby retain "back door" access to the encrypted files.

Of course, in principle a malicious encryptor could also simply save a copy of the unencrypted data before encrypting it, so in that sense, the problem is unavoidable.  However, a bunch of 32-byte AES keys is a lot easier to conceal than several mega/giga/terabytes of audio recordings (and an "accidental bug" in the AES key generation code that makes it at least partially repeatable could be even easier to hide, and to explain away if found).

In practice, giving your telephony provider an RSA public key and your lawyer the corresponding private key (or, better yet, asking your lawyer to generate an RSA keypair and to send you and your provider the public key), and having the provider encrypt the audio files with that key using standard off-the-shelf software like PGP / GnuPG is probably good enough.

While it would be theoretically possible for the provider to modify the software to insert a backdoor into it, that would take some non-trivial effort and programming / crypto knowledge, and would risk being caught in an audit (since any such modified software would stand out if compared to the standard version of the same program).  And in any case, they'd have to do that before encrypting the files they want to be able to decrypt; as long as they're initially honest, they won't be able to later decrypt any honestly encrypted files even if they later turn malicious (and/or are compromised by someone else).


Perfect secrecy theorem Let $E = (E,D)$ be a Shannon cipher defined over $(K,M, C)$. Consider a
probabilistic experiment in which $k$ is a random variable uniformly distributed over $K$. Then $E$ is perfectly secure if and only if for
every predicate $Φ$ on $C$, for all $m_0,m_1 2M$, we have

$Pr[Φ(E(k,m_0))] = Pr[Φ(E(k,m_1))]$

I dont understand the meaning of $Φ$ in this theorem

That predicate is basically telling you that the resulting ciphertext does not leak any information about the plaintext that has been encrypted.

Assume that there exists some predicate $\Phi'$ such that $Pr[\Phi'(E(k,m_0)] \neq Pr[\Phi'(E(k,m_1)]$, for some $m_0,m_1$ pair. Then, if you are given a ciphertext that corresponds to some of those two messages, computing that predicate you can tell whether $m_0$ or $m_1$ was encrypted, which means that your cipher does not provide perfect secrecy.

For a more precise enunciation, you can check Lemma 2.4 of Katz & Lindell's "Introduction to Modern Cryptography" and its proof, where the predicate used there is $\Phi(c)$ := "$E(k,m)=c$", for $k\in K,m\in M$. And then, you have $Pr[E(k,m_0)=c] = Pr[E(k,m_1)=c]$.

You can try to think of any other predicate. The important thing is that no such predicate must exist.


Is CTS necessary on a AES-CBC DRBG? As I understand it, CTS pads the last block and swaps it with the second last to compensate for a partial block of data. I have written a DRBG (Deterministic Random Bit Generator) using AES-CBC that only accepts an input size which falls on the block boundary.

Is CTS really necessary here? I can't imagine a way in which it's absence will affect the entropy of the output. Am I understanding this correctly?

Normally you don't want to reverse the encryption used within a DRBG. Schemes like PKCS#7 padding and CTS are required to deterministically reverse the padding during decryption. If you just want to have a final block, you should be fine by using zero padding until the end of the block.

Of course, if this zero padding is actually harming the output of your DRBG depends on the algorithm.


What are the “costs” to find a pre-image, weak collision, or strong collision? For a secure, n-bit hash function, what are the “costs” to find a pre-image, weak collision, or strong collision?

Definitions:

In the pre-image attack, given a hash function $H$ and a hash value $h$, we try to find $x$ such that $h = H(x)$. The $x$ need not be the original input value used to calculate the hash $h$.

In the second preimage attack ( weak collison); we are given $H,x,h$ with $h = H(x)$ and we need to find another $x'$ such that $h = H(x')$.

Collision attack (strong collision); we are looking for two different inputs $a$ and $b$ such that  such that $H(a)=H(b)$.

Costs:

The cost of pre-image and secondary pre-image is $\mathcal{O}(2^n)$
The usual search for preimage and secondary pre-image is either iterating from 0 to $c\cdot2^n$ or randomly testing $c\cdot2^n$ values from a larger space then $2^n$.

The cost of the collision is $\mathcal{O}(2^{n/2})$ with 50% probability and this is due to the birthday attack.
The naive way is generating $2^{n/2}$ input hash pairs and sort them according to hash values. This costs around $\mathcal{O}(2^{n/2})$ space.
A better way is using Pollard's Rho *;

Pick a random hash value $h_1$ and set $h_1' = h_1$
Compute $h_2 = H(h_1)$ and $h_2' = H(H(h_1'))$. That is one is slow one is fast.
continue the process $h_{i+1} = H(h_i)$ and $h_{i+1}' = H(H(h_i'))$ until we reach an index $j$ such that $h_{j+1} = h_{j+1}'$

We can visualize this algorithm as below; The algorithm eventually enter a cycle (the Rho-Shape)

The path to $h_5$ is a collision. The cycle length and the collision points can be found by Floyds algorithm.
This requires $\mathcal{O}(2^{n/2})$ operations to find the collision.
If we ask, what is the average cycle length is? If we model the hash function as uniform random then this is shown by Harris in 1960. For a hash function with $\ell$ bit output, the average cycle length is $\frac{1}{ 2} \sqrt{2 \pi \ell}$ for SHA256 that makes $2^{127} \sqrt{\pi}$. That makes it quite unreachable for a hash function with 256-bit output to run the cycle to find a collision

*In other context this is also known as Floyd Cycle detection algorith (Floyd's Tortoise and Hare).  Knuth attributing it to Floyd, without a citation. The origin is not known.


Securely re-using a shared key with NaCl I want to modify this peer-to-peer communications software to allow parties to specify a shared secret key and have all communications encrypted with it.

[The software uses tweetnacl.js for the cryptographic operations.]

Re-using the exact same shared secret key for every message does not seem very secure. I have two questions:

Is this concern addressed by the presence of the nonce in nacl.secretbox(message, nonce, key) thus making it safe to re-use the shared secret key as long as the nonce is different every time? (which is a requirement anyway obviously).
Would it be even safer to derive a unique shared key for each message by hashing some salt and sending the salt along with each message so that the other side can do the same to obtain the unique shared key for the message? Or is this redundant?

Is this concern addressed by the presence of the nonce in nacl.secretbox(message, nonce, key) thus making it safe to re-use the shared secret key as long as the nonce is different every time?

Yes. But you still have to be careful about protocol level attacks, such as replays or re-ordered messages.

  (which is a requirement anyway obviously).

Note that a nonce doesn't need to be unique by itself, it's only the key-nonce pair that needs to be unique. For example if you use a per-connection key you can use a simple counter as nonce, since each connection has a unique key.

  Would it be even safer to derive a unique shared key for each message by hashing some salt and sending the salt along with each message so that the other side can do the same to obtain the unique shared key for the message? Or is this redundant?

That's unnecessary if 24-byte nonces are sufficient for your purpose.

Internally xsalsa20 hashes a 32-byte key together with the first 16 bytes of the nonce into a 32-byte key, which is then used together with the remaining 8 bytes of the nonce.


Minimum input size of a hash function This is a theoretical question, to improve my understanding of hash functions. Hash functions have a one-wayness such that they are protected from the first preimage attack. From my understanding, if $H(X)=Y$, knowing $Y$, I should not be able to know $X$ is the fundamental behind the first preimage attack.

The question: Does the security of a hash function from the preimage attack also depend on the secrecy of the length of $X$?

If the adversary knows the length of $X$, then it can easily brute force $X$ for smaller lengths of $X$. I understand that smaller length of $X$ will get appended and pre-processed into larger blocks but that does not stop the adversary from brute-forcing since there are no secrets in the pre-processing.

The questions

Does the security of a hash function from the preimage attack also depend on the secrecy of the length of X.?

The preimage attack: given a hash function $h$ and a hash value $y$ the computationally bounded adversary tries to find a pre-image $x$ such that $y = h(x)$.
This is like an adversary trying to find a password given the hash of it with the known hash function. Note that one doesn't need to find the actual input value for the success of the pre-image attack. Any password with the same hash value will be work for the adversary.
There is no known practically successful pre-image attack on any cryptographic hash functions, even those that are practically broken with collision attacks like MD5 and SHA-1. There is a pre-image attack on MD5 that requires $2^{123.4}$ complexity by Sasaki and Aoki Finding Preimages in Full MD5 Faster than Exhaustive Search in 2009. This is still far from practical usage though it is faster than direct searching.
To hash a value one needs to apply the standard encoding of the message that includes the padding mechanism so that the hash fits into the block size of the hash function. NIST defines them for their standards. The block size can be like 512 bits in SHA256 or 1024 bits in SHA512.
If ever we find a successful pre-image attack, it will also reveal the size of the found pre-image and that was not necessarily the input used to generate the hash value. The padding mechanism, however, can prevent some attacks. Usually, the adversary has lots of freeness for the attack since hash functions can hash any size. This is used in SHA-1 collision attack (identical-prefix collision attack). If the size is limited, that can be a big problem too.

If the adversary knows the length of X, then it can easily brute force X for smaller lengths of X. I understand that smaller lengths of X will get appended and pre-processed into larger blocks but that does not stop the adversary from brute-forcing since there are no secrets in the pre-processing.

If the message space is small, then the adversary simply brute-forces all possible inputs. The current computational capabilities of the adversaries can be evaluated from public information. For example, the bitcoin miners reached $\approx 2^{92}$ SHA-256 hashes per year on 06 August 2019.
During the candidate input generation and testing the hash value, the adversary will also apply the padding mechanism.
for each candidate in [0..2^t]
    paddedCandiate = pad(candidate)
    if hash(paddedCandiate) == y
       return candidate

where $t$ is the predetermined bound. This search space can be easily parallelized by dividing space into segments.
The padding mechanism is not a secret and nothing to do with the secrecy of the mechanism. In unkeyed hash functions, there is no secret.
If you fear that your small input space is vulnerable, you might look at keyed hash functions like HMAC, KMAC.


Symmetric-like cyphers with several steps Are there any good symmetric-ish cyphers that involve three or more steps with independent key material for each step?

Formally, there should be a function $K(s)$ that returns a tuple $(k_1,..,k_n)$ and a function $P(k,d)$ such that if $d_i = P(k_i,d_{i-1})$ then $d_n=d_0$ but there are no known relationships between strictly fewer than $n$ of the $k_i$.

Stream cyphers provide this for $n=2$ of course, as the independence requirement becomes vacuous, but I'm unaware of anything with $n>2$ that's both secure and efficient as a symmetric cypher.

It's okay if we replace $P$ by another operation $P'$ for the $i$-th step for preferably at most one i but we do not want any relationship between $k_i$ and $k_j$ for $j \neq i$.

One could use secret sharing algorithms, or simply XOR, to do this quite securely, but that'd require key material as big as the original file, making it inefficient.

There are tricks for doing roughly this with asymmetric systems like elliptic curve scalar multiplication, but that's too slow for my purposes.

This is not possible with symmetric cryptography.
To show this, I will construct an asymmetric encryption algorithm from your scheme.
Consider $pub = (k_1, \dots, k_{n-2})$ as the public key and $prk = (k_{n-1}, k_n)$ as the private key.
The encryption algorithm will be $c = enc(pub, d) := P(k_{n-2},P(k_{n-3},\dots ,P(k_1,d)))$
The decryption algorithm will be $d = dec(prk, c) := P(k_{n}, P(k_{n-1}, c))$
Since there may be no relations in the sets $puk \cup \{k_{n-1} \}$ and $puk \cup \{k_{n} \}$ , the computation of prk from puk will be infeasible.
This is a property of an asymmetric cryptographic system.


Finding product of two unknown numbers each raised to a known power Let $G$ be a group, and let $a, b\in G$, and let $[3] = \{0,1,2\}$. Let $(x_i,y_i)$ for $i\in[3]$ be known constants. Assume that I know the elements:
$$c_i = a^{x_i}b^{y_i},\quad i\in[3]$$
Then, given $(x', y')$, is there a way to efficiently compute $a^{x'}b^{y'}$?

To say more about this, you need more assumptions on $(x_0, y_0),\dots, (x_2, y_2)$.
For example, if you write
$$B = \begin{pmatrix}x_0 & x_1 & x_2 \\ y_0 & y_1 & y_2\end{pmatrix}$$
to be the $2\times 3$ matrix of your known constants, and let:
$$\mathsf{span}_{\mathbb{Z}}(B) = \{(x', y')\in\mathbb{Z}^2 \mid \exists \vec{\alpha}\in\mathbb{Z}^3\text{ s.t. }(x', y') = B\vec{\alpha}\}$$
be the span of all of their integer linear combinations, then you can efficiently compute $a^{x'}b^{y'}$ for any $(x', y')\in\mathsf{span}_{\mathbb{Z}}(B)$ by writing:
\begin{align*}
\prod_{i\in[3]}c_i^{\vec{\alpha}_i} &= \prod_{i\in[3]}(a^{x_i}b^{y_i})^{\vec{\alpha}_i}\\
&=\prod_{i\in[3]}a^{\vec{\alpha}_i x_i}b^{\vec{\alpha}_i y_i}\\
&=a^{x'}b^{y'},\quad (x', y') = B\vec{\alpha}
\end{align*}
The above technically uses the assumption that $G$ is abelian (commutative), but this is likely intended.
So if $\mathsf{span}_{\mathbb{Z}}(B) = \mathbb{Z}^2$ (which is definitely possible), you can compute your desired function for any pair of $(x', y')$. But if the span of $B$ is not all of $\mathbb{Z}^2$, it is not clear how to compute your desired function for $(x', y') \in \mathbb{Z}^2\setminus\mathbb{span}_{\mathbb{Z}}(B)$ (at least the prior technique no longer works).


OpenPGP Signature Packet hashed data RFC 4880 describes the version 4 signature packet, tag 2, as

- One-octet signature type.
- One-octet public-key algorithm.
- One-octet hash algorithm.
- Two-octet scalar octet count for following hashed subpacket data.
Note that this is the length in octets of all of the hashed
subpackets; a pointer incremented by this number will skip over
the hashed subpackets.
- Hashed subpacket data set (zero or more subpackets).
- Two-octet scalar octet count for the following unhashed subpacket
data. Note that this is the length in octets of all of the
unhashed subpackets; a pointer incremented by this number will
skip over the unhashed subpackets.
- Unhashed subpacket data set (zero or more subpackets).
- Two-octet field holding the left 16 bits of the signed hash
value.
- One or more multiprecision integers comprising the signature.

and i assume that the second to last line means just take the string of the hashed subpacket and hash it with the hash algorithm and take its first 2 bytes. however, no matter what i do, i cannot seem to get it.

I generated this fake key a long time ago

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: BCPG v1.39

mQGiBE5B0h8RBAD533Z5bK1IpBx02QyQL0QoJE4uFRIMGDiwXuwmZzVl+R7Vlurd
GRLsCCbE6vOOh7XQVZGzLEBy9WNzZ9m+EbCfSVAYkjS6FhLws6hG6irrnS+b3JBf
gFJ8vNGF9Z7bhx+7y7NBk0IMyWkGnUkcnav73t5FQUI2faEBN4c/yAGJZwCgjcB7
3akWk9XVWvTCsiMXxpyvkukEALXsvB6cOoFEtQq9cQHjP63fBlvD94dhhMiM0cH6
hW9JotxdK+cxFGG9ZIWgoN2PWbMJka/H4W5EL6tS+YiNAR7I1Ozkt6X16GjnQUzZ
MlSpleK+KiKVN2anRaPEoOIinHrE3ZXd6QlJ/4+OJn4IVWmSEaJpFf4QNgvEu4rh
xinyBAD2RNzREOA+wpnFZ4lDt9NZXmXdxQME/l0J9XcvWhpGsxA/MATQKImy7N49
7GT/M38F+TrpBobag1O3buE99fOLyws4Tbc+sZMdHxoiGZDAIRNQS2rv475E6ktj
7vd5CYvOkA6+8sX1+hPcNlkHtHB1OFkJRsYp6k0zkyC9adjBM7QTYWJjIDxtYWtj
bUBhYWEuY29tPohGBBMRAgAGBQJOQdIfAAoJEDBSJUXPd92GRSQAoItbtbToOg7a
/hcg2sA/aBEQNwuxAKCGR69vmSoCWoBP5waPk0UsjM3BSbjMBE5B0h8QAgCUlP7A
lfO4XuKGVCs4NvyBpd0KA0m0wjndOHRNSIz44x24vLfTO0GrueWjPMqRRLHO8zLJ
S/BXO/BHo6ypjN87Af0VPV1hcq20MEW2iujh3hBwthNwBWhtKdPXOndJGZaB7lsh
LJuWv9z6WyDNXj/SBEiV1gnPm0ELeg8Syhy5pCjMAf9QHehP2eCFqfEwTAnaOlA6
CU+rYHKPZaI9NUwCA7qD2d93/l08/+ZtFvejZW1RWrJ8qfLDRtlPgRzigoF/CXbR
iEYEGBECAAYFAk5B0h8ACgkQMFIlRc933YZRrACfUnWTjHHN+QsEEoJrwRvFmvzj
bR4An24pTpeeN+I6R59O/sdmYsAhjULX
=sStS
-----END PGP PUBLIC KEY BLOCK-----

From pgpdump.net, i see that the left 2 bytes of the hash (SHA 1) value is 45 24 for the first signature packet and 51 ac for the second one. i am getting 52 f0 for both. obviously, im not including some information, but what is it? the hashed subpackets are identical, and all of the data before the hashed data are the same as well except they are different types of signature packets (0x13 / 0x18). i have been unable to get either of the correct hash values even when i add/take characters from the data packet. the key im generating is exactly the same as the key shown here except for the hash values.

what is the data that i should be hashing??

the key example up there is made up of packet 6 + packet 13 + packet 2 + packet 14 + packet 2. i have tried all sorts of combinations of packet 6, packet 13, and packet 2 (from version number to hashed data inclusive), but still cannot find the string that hashes to the correct values

EDIT: From Ilmari Karonen's suggestion that i read section 5.2.4, i still cannot get the answer

i have been using:

a = entire public key packet, header and all
b = entire user id packet, header and all
c = signature packet '\x04' ... '\x1f' (version ... end of hashed subpacket)

and hashing in all sorts of different ways. Depending on what hash context and data (for the user id: is it just the user info, or is it the entire packet? either way i try does not work) mean, the correct method can be anything, which i still cannot find.

how are the hashes of the body and two trailers combined? is that what hash context defines?

I believe the answer can be found in section 5.2.4, "Computing Signatures".  According to that section, what you actually need to hash is the concatenation of:

the key packet (with an old-style packet header with a two-byte length — but your sample key packet has that header type already),
for the first (certification) signature, the constant byte 0xB4, a four-byte number giving the length of the user ID packet body, and the user ID packet body itself,
for the second (subkey binding) signature, the subkey packet (using the same type of header as for the key packet above),
a "trailer" consisting of the beginning of the signature packet body, from the version number field to the end of the hashed subpacket data, and
a final six-byte trailer consisting of the bytes 0x04 and 0xFF, and a four-byte big-endian number giving the length of the "trailer" string from the previous string.

I haven't checked if that will actually produce the correct hashes for your packet, but I believe it should.

Note that I've simplified the description somewhat; you should actually read section 5.2.4 of the RFC carefully to figure out just what goes into the hash under various circumstances, since it appears to depend on many things.

EDIT: While simplifying, I accidentally left out some pretty major parts. :(  I've added them in now, hopefully this time I've got everything that's needed.  Alas, I can't really check it now either, and probably won't have much chance of participating here during this week.

(Oh, and yes, I agree, that all looks like an awful mess.  I assume there are reasons for all the quirks, and that it probably looks easier to read in source code form, but that doesn't make it any less messy.)

Ps. As for "hash context", other places where the term is used, particularly section 3.7.1.1, suggest that it basically means an object or data structure that contains the internal state of the hash function and supports methods for providing further input and for finalizing the hash and returning the output. (Most cryptographic hash implementations provide such an API.)

In particular, in various parts of the RFC, it is recommended that several hashes be computed in parallel by maintaining multiple hash contexts (i.e. hash object instances).


What's the name of this random number generation algorithm? I'm looking for the name of an RNG method or algorithm, described below. Combining multiple results of a non-uniform random number generator can produce a more uniform result. It seems like this would be a common method employed by RNG algorithms, and especially HRNGs, to produce more statistically random results.
It would be awesome if someone could help identify the math/stat/crypto name for this method
The code below demonstrates a simple implementation of this method, with the 'bad' RNG producing non-uniform results, and the 'good' RNG producing about 50/50 results.
import random

# Function representing a non-uniform random number generator
def bad_RNG():

    result = 0
    if (random.random() > .99):
        result = 1

    return result

# Function that repeatedly applies an RNG function to create a more uniform result
def good_RNG():

    result = 0
    for i in range(100):
        if (bad_RNG() != bad_RNG()):
            result = 1 - result

    return result

# Tests RNG functions by running them 100 times, and printing the distribution of their results
def test_RNG(RNG_func):

    zeros = 0
    ones = 0

    for i in range(100):

        result = RNG_func()

        if (0 == result):
            zeros = zeros + 1
        else:
            ones = ones + 1

    print(zeros, end="|")
    print(ones)

print("bad_RNG result:")
test_RNG(bad_RNG)
print("\ngood_RNG result:")
test_RNG(good_RNG)

Alternative English Explanation
Assume an RNG function F() that returns either 0 or 1. F() results are non-uniform, as it usually returns a 0. By summing several F() results, and applying modulus 2, the result approaches a 50/50 uniform distribution.

The algorithm described is an unbiasing algorithm, which is a type of randomness extraction algorithm.
Another method is von Neumann unbiasing where you
can take 2 bits $(X_n,X_{n+1})$ and output $Z=0$ if
$(X_n,X_{n+1})=(0,1),$ output $Z=1,$ if
$(X_n,X_{n+1})=(1,0),$ and discard the two
bits otherwise. This gives exactly uniform
output bits, if the sequence $X_n$ is independent and identically distributed since both the above $(0,1),(1,0)$ have probability exactly $p(1-p)$.