Under what conditions is broadcast possible? (Cryptographically, and in the model of Maurer 2006) In this paper, Ueli Maurer uses a very cool model to generalize a number of results about broadcast, secret sharing and secure multiparty computation. Rather than talking about an adversary being either active (malicious) or passive (semi-honest) and having a threshold on the number of parties it controls, instead there are sets of sets of nodes $\Delta$ and $\Sigma$  such that the adversary may have active control of any set $A \in \Delta$ and passive control of any set $B$ such that $A \cup B \in \Sigma$.

Maurer states (Theorem 1) that:

"The simulation of a broadcast channel is secure against a $(\Sigma,\Delta)$-adversary is possible if and only if $P \notin \Delta \sqcup \Delta \sqcup \Delta$."

Here $P$ is the set of all nodes and $X\sqcup Y = \{x \in X, y\in Y : x \cup y\}$.

A corollary of this is that for a fixed threshold, we require $t < |P|/3$, where $t$ is the maximum number of nodes that may be actively controlled by the adversary.

Is Maurer just referring to the information theoretic case? Because I seem to remember reading somewhere that assuming cryptographic signatures you can have broadcast with up to $t < |P|/2$ malicious parties.

If so what is the tight limit for broadcast using Maurer's notation in the case of a polynomially-bound adversary, secure signatures and some public key infrastructure?

This is a somewhat standard method for generalizing results based on threshold adversaries. Let $n$ be the number of parties and let $\mathcal{C} \subseteq 2^{[n]}$ denote the family of subsets that the adversary can corrupt. For example, in the case of honest majority, $\mathcal{C} = \{ C \subseteq [n] : |C| < n/2 \}$.

$\mathcal{C}$ has the Q2 property if no two corruptible sets $A, B \in \mathcal{C}$ satisfy $A \cup B = [n]$. In Maurer's notation, $[n] \not\in \mathcal{C} \sqcup \mathcal{C}$.
$\mathcal{C}$ has the Q3 property if no three corruptible sets $A, B,C \in \mathcal{C}$ satisfy $A \cup B \cup C = [n]$. In Maurer's notation, $[n] \not\in \mathcal{C} \sqcup \mathcal{C} \sqcup \mathcal{C}$.

Generally speaking, classical results that require honest majority will generalize to any Q2 corruption pattern. Results that require honest two-thirds majority generalize to Q3.

I think the first appearance of this generalization is in Complete Characterization of Adversaries
Tolerable in Secure Multi-Party Computation by Hirt & Maurer. It's generalized even farther in MPC vs. SFE: Perfect Security in a Unified Corruption Model by
Beerliova-Trubiniova et al. They consider an adversary that can corrupt any $S \in \mathcal{P}$ passively, or corrupt any $S \in \mathcal{A}$ actively, or corrupt any $S \in \mathcal{F}$ in a fail-stop way. These results are harder to state in a stackexchange answer.

Regarding the question about broadcast, the actual tight bound depends very heavily on the model (poly-time vs information-theoretic, [im]perfect security, PKI setup). Also agreement, consensus, and broadcast are all slightly different. But in general, information-theoretic broadcast with no setup requires honest 2/3rds majority (Q3 corruptions).


Cryptographic random numbers for key generation I am trying to understand how a cryptographic library works (for example, one that provides assymetric encryption such as RSA), but I'm running into a few problems about the key-generation. There are a lot of questions regarding the generation of random primes, but I'm interested in the generation of a random number. There seem to be some official guidelines by the government (for example, NIST FIPS 186-4 (PDF) is referred to in a couple of other answers to questions about random prime generation) for the generation of keys for certain protocols, but they are not an easy read and I don't think they answer my questions.

I think I understand the basic principles:
Entropy is gathered by the operating system or a daemon to provided a small amount of unpredictable data that is used as a seed for a cryptographically secure pseudo-random number generator (CSPRNG). The CSPRNG generates the random numbers that are used to generate random primes (either a probable or provable prime).

What is a good CSPRNG? I couldn't find the algorithm that OpenSSL uses (it's very well possible that there are multiple). Wikipedia lists a bunch, but doesn't provide sufficient information on implementation and performance.

Also, are there any additional constraints on the prime or prime pair that is generated? I vaguely remember reading something about prime products of a certain form that are no good for use in cryptographic keys (because they are easy to factor with some tricks).

There are many "cryptographically strong pseudorandom generators" and we know how to construct them well. If you have a strong 128-bit (or more) key $k$, then you can just use AES-CTR to get as much randomness as you need: $AES_k(0)||AES_k(1)||AES_k(2)||\cdots$. You can also do a similar thing with SHA256. The real problem that arises is where to get the key from in the first place. Typically, there is a source of entropy. This is turned into (almost) uniform randomness (a.k.a. a key) using a randomness extractor. In cryptographic applications, this is often achieved by just applying a hash function like SHA256 to the source.

When OpenSSL is run in Linux, it takes its initial random source from /dev/urandom. This is already a problem since /dev/urandom (unlike /dev/random) is not blocking, which means that it provides randomness even if the Linux entropy pool is empty. What makes it worse is that OpenSSL does not reseed if the entropy pool was originally low.

I just heard an interesting talk at BlackHat 2015 about this. The above claim about OpenSSL is based on their analysis of the code. You can see more information in their PPT and white paper (I don't agree with everything they say but it's very informative and good work).

I suggest that you reseed the OpenSSL generator yourself (using rand_seed) either by calling /dev/random yourself (you can query to see if the entropy pool has enough randomness in order to prevent blocking; use the command: # cat /proc/sys/kernel/random/entropy_avail), or by using RDSEED, which is a hardware generator inside all Intel chips from Ivy Bridge. See (https://software.intel.com/en-us/blogs/2012/11/17/the-difference-between-rdrand-and-rdseed for more info.)

It seems that due to Snowden fears, Linux does not use RDSEED. My opinion is that it should certainly be used, at least to add randomness to the OpenSSL generator.

One final note: if you generate a new process to check the available entropy, then you will modify the pool. It seems that the Linux operating system using 256 bits of randomness from the pool every time a process is generated (for random memory allocation etc.). This is huge overkill and means that the entropy sorely needed for crypto applications may be exhausted for things that don't need real randomness. Anyway, that's life. So, if you want to constantly poll, then generate a single process that will periodically check entropy_avail, and don't generate a new process every time.


Why do we use multilinear maps for obfuscation? I have recently developed interest about obfuscation, and I see that (all?) the proposals use multilinear maps. What's the reason to this? As I also that many of the multilinear map proposals get broken too. Are there any other approaches to achieve obfuscation, that use other mathematical structures?

Multilinear map is a very natural candidate to build obfuscation: it allows to perform operations on values in an oblivious way, and is in addition enhanced with a "zero-test" procedure, that can be used to obtain the result of a computation, but which should (hopefully) not reveal the intermediate steps of the computation. Hence, it gives a candidate for indistinguishability obfuscation (iO) of small enough circuits. From there, one can bootstrap to arbitrary circuits using fully homomophic encryption with a "small enough" decryption circuit: the circuit evaluation is done obliviously over the ciphertexts, and decryption of the result is performed using the multilinear map (informally).

So, the most obvious reason is that it feels natural. But there is a deeper reason: iO can be shown to imply multilinear maps, as proven is this recent paper. Some care must be taken here: multilinear maps are objects, like encryption schemes are. But one cannot talk about a primitive "implying" another primitive: the security properties that we considered must be taken into account. What the paper shows is that iO implies semantically secure multilinear maps, which were recently shown to also imply iO (see e.g. this paper). Therefore, up to some other classical primitives used in the various constructions, iO and semantically secure multilinear maps are essentially equivalent: if you have one, you have the other.

This does not mean that multilinear maps are necessarily the starting point of any iO construction, just that this starting point will necessarily be "as strong" as multilinear maps. For example, there is a rich line of works in building iO from functional encryption.

Finally, you mention that candidate multilinear maps have been broken. Again, one must treat this with care: one does not break an object, but a security assumption on this object. So, many security assumptions on multilinear maps have been broken, in various settings. For a long time, all these attacks relied on "encodings of zero", which are not used in iO constructions, so those attacks, while breaking mmaps in some sense, did not break iO. More recently, there have been some more powerful attacks (called annihiliation attacks) that threaten iO in some settings. But many of the most recent iO constructions, with more recent candidates of mmaps, remain unbroken. Still, these variety of attacks suggest that we are yet far from deeply understanding what can make iO secure; researchers do not show a considerable confidence in the security of current candidates, but recall that this is a young area, subject to many ongoing research.


How to guarantee every plaintext is in a rainbow table? This guide says that for a rainbow table or pre-computed hash chain, you can only get a probability that a plaintext is in a table, not a guarantee. Is there a way to guarantee every possible plaintext (of a certain length) is in a table? My thought would be by storing entire chains and generating more chains if a plaintext isn't in any of them, but I think that defeats the purpose of a rainbow table.

You could, but generating such a table may get prohibitively expensive. It may also prevent other optimizations, like merged chain removal.

If you had a data structure keeping track of the whole dictionary, you could tick off each entry when you add it to a chain at any point, then start each chain from an entry not already used. However, in the cases where you'd use a rainbow table, rather than a simple hash table, you may not be able to store all that. The extra space usage is proportional to the chain length.

Alternatively, if you already have a table with e.g. 99% probability, you could iterate over all the inputs, see if they are in the table, then add chains starting with those that are not. This should require relatively little extra space, but increases the number of hash function invocations by a factor of about $l^2$, where $l$ is the chain length, since you need about that many hash iterations for each input to check if they are in the table.

Once you had such a table, it wouldn't necessarily be that much more costly to use, except by virtue of being larger.


Generators and Multiplicative group $\mathbb{Z_7}$ In the multiplication table for $\mathbb{Z^*_7}$, each row has all the elements of the set

My questions are:

  is each element a generator here? if not why?
  is an element considered as generator only if $Order(G) = Order(g)$ i.e $Order(g) = 6$  hence $g=3$ is a generator.
  is there any formula to find the number of generators?
  Some website says phi(n) gives the order of group some says $\varphi(n)$ gives the number of generators some says $\varphi(n)$ gives the number of elements with a multiplicative inverse. Which of these is correct?

is each element a generator here? if not why?

Take the $2$ and calculate $2 \cdot 2 \cdot 2 \equiv 8 \equiv 1 \mod7$. Therefore, not every element is a generator.

  is an element considered as generator only if $Order(G) = Order(g)$ i.e $Order(g) = 6$  hence $g=3$ is a generator.

A generator must generate all the element. If the order of $Order(a) = x < g = Order(G)$ then it cannot generates all the elements. $a^x =1 $ and the cyclic sub-group generated by $x$ contains only $x$ elements:

$$a^1,a^2, \ldots, a^x = 1$$

  is there any formula to find the number of generators?

No, there is no formula.

  Some website says $\varphi(n)$ gives the order of group some says $\varphi(n)$ gives the number of generators some says $\varphi(n)$ gives the number of elements with a multiplicative inverse. Which of these is correct?

Remember the $\mathbb{Z_7}$ is a field.

$\varphi(n)$ gives the order of the multiplicative group. In your case $\varphi(7) = 7-1 = 6$
2 and 4 are not generators therefore $\varphi(n)$ cannot give the number of generators.
Being a field implies every element is invertible, thus  $\varphi(7)$ gives the number of invertible elements, also for the composite case $-\mathbb{Z_n}-$, where $n$ is a composite number,  $\varphi(n)$,  gives the number of invertible elements.


What are the correct order of operations for One Time Pad Cipher? According to Wikipedia the One Time Pad Cipher is unbreakable.  On the Wikipedia page it explains how to perform this simple encryption process by hand.  For the encryption it adds (+) the message and the key and then modulo by 26.
For the decryption it subtracts (-) the key and the ciphertext and then modulo by 26 again.

In another source it explains that for the encryption process one should subtract (-) and for the decryption process one should add (+).

Which one of these sources are correct and what will the security difference be between the two order of operations?

There is no difference.  In fact, any quasigroup operation will do.

Specifically, the only property we really need is that, for every ciphertext symbol $C$ and every plaintext symbol $P$, there exists one (and only one) key symbol $K$ such that encrypting $P$ with $K$ yields $C$.  This implies that, as long as the actual key symbols are chosen uniformly at random (so that each of them is equally likely to be correct), knowing the ciphertext symbol $C$ does not reveal any information about the plaintext symbol $P$ (since each $K$, and therefore each $P$, is equally likely).

In fact, we can generalize further and allow several key symbols to produce the same encryption, as long as the number of key symbols that yield $C$ is the same for every plaintext symbol $P$.

There are several common operations that can satisfy this property.  For example, we can use modular addition for encryption, and modular subtraction for decryption, or vice versa.  Or we could use e.g. bitwise XOR, which is its own inverse, and can thus be used for both encryption and decryption in the same system.  Or, if we wanted, we could use e.g. multiplication in a Galois field for encryption, and multiplication by the group inverse for decryption (or, again, vice versa).


Insecure MAC built on pseudorandom function this is a question about Katz-Lindell book, introduction to modern cryptography, 2nd edition, exercise 4.7, part c.

For (a) and (b) it is clear that the Macs are insecure, but for (c) I am struggling to see why.

For me, when the attacker will present his pair $(m^*, \langle r^*,t^* \rangle)$, the MAC will sample uniformly its own $r$ (before applying the $\operatorname{Vrfyk}(.)$ algorithm), and will prepend $r$ to the computed $t$.

So no matter how the attacker will choose $m^*$ (even if the attacker chooses $m^*$ randomly), the MAC (assuming that it is a deterministic MAC using a canonical verification) will always sample a random $r$ from ${0,1}^n$, independently from the one $(r^*)$ that the attacker output to it, and the probability that $r=r^*$ will be negligible. So it is still secure MAC, the one presented in part (c).

Can someone correct me if I am wrong please?

assuming that it is a deterministic MAC using a canonical verification

It is not, randomness is involved in the tag generation, therefore it is not deterministic and cannot use canonical verification.

This then means that an attacker doesn't have to follow the MAC algorithm but instead has to find $m',(r',t')$ such that verification suceeds, picking $t'=0$ is a good starting point for that.


Efficiency of finding sub group order vs factorization Suppose you got a prime $p = 2\mathbb\Pi_{i=0}^{n-1}q_i+1$, where $2^{k-1} \lt q_i \lt 2^k$ for some $k$ and all $0 \le i \lt n$, and that you also got a generator $g$ of one of the prime order sub groups of $\mathbb Z_p^*$. Also assume that the factorization of $\frac{p-1}{2}$ is unknown.

Question #1:

Are there ways to find the order of $g$ faster than using the elliptic curve and number field sieve methods for factoring $\frac{p-1}{2}$? The expected running time of the generic meet-in-the-middle algorithm for finding the order of $g$ is $O(\sqrt{2^k})$, which might be assumed to be greater than the running time of ECM.

Question #2:

Suppose Alice picks an element $x$ uniformly from $\mathbb Z_{q_0}$ and that $g$ is a generator of the $q_0$ order subgroup of $\mathbb Z_p^*$. Alice calculates $y = g^x \mod p$ and gives $(p,g,y)$ to Bob. Bob's goal is to find $q_0$ and he gets to do that either by factoring $\frac{p-1}{2}$, by finding the order of $g$ and $y$, or by collecting solutions $(a_j,b_j)$ to the equation $BS2I(a_j) \equiv xBS2I(b_j) \pmod {q_0}$ using the following protocol:

Bob: Pick an element $a_j \in \{0,1\}^k$ and send it to Alice
Alice: Calculate $c = x^{-1}BS2I(a_j) \mod {q_0}$. For some deterministic function $f:\mathbb Z_{q_0} \rightarrow \{0,1\}^k$ such that $BS2I(f(z))\equiv z \pmod {q_0}$ for all $z\in \mathbb Z_{q_0}$, calculate $b_j=f(c)$ and send $b_j$ to Bob.
Bob: Verify that $g^{BS2I(a_j)} = y^{BS2I(b_j)} \mod p$.

Question #3:

If we regard the protocol in question #2 as a simple instance of polynomial evaluation, where Alice picks two polynomials $r(), s()$ with coefficients in $\mathbb Z_{q_0}$ and provides Bob with the means to verify if $r(BS2I(a_j)) \equiv s(BS2I(b_j)) \pmod {q_0}$, where Bob picks $a_j$ and Alice provides the solution $b_j$ - would choosing polynomials with higher degree than 1 make it significantly harder for Bob to solve $q_0$?

Concerning question 3, here is an answer assuming that the coefficients of $r$ are known to Bob and the coefficients of $s$ hidden in an exponential representation. [This is unessential, it can be easily generalized to hidden $r$, but it simplifies the presentation].

To further simplify, let's also assume that $s$ contains no constant term. In this setting, each pair $(a_i,b_i)$ as in the question is equivalent to a pair $(A_i,b_i)$ together with the information that $s(b_i)\equiv A_i\pmod{q_0}$. This can be easily rewritten as a linear equation $$\sum_{k=1}^{\ell}s_kb_i^k\equiv A_i\pmod{q_0},$$where $\ell$ is the degree of $s$. Collect $\ell+1$ such equations and form the matrix:
$$
M=\left(\begin{array}{ccccc}-A_1 &b_1 & b_1^2 & \cdots &b_1^\ell\\
-A_2 & b_2 & b_2^2 & \cdots &b_2^\ell\\
\vdots &\vdots & \vdots & \ddots & \vdots\\
-A_{\ell+1}& b_{\ell+1} & b_{\ell+1}^2 & \cdots &b_{\ell+1}^\ell\\
\end{array}\right).
$$
By construction the system $Mx=0$ has a non zero solution vector (formed by a '1' followed by the coefficients of $s$) modulo $q_0$. As a consequence, $\det(M)$ is a multiple of $q_0$. Form two such matrices, take gcd and you can recover $q_0$ directly.

Note that this can be made more efficient by taking a rectangular matrix $M$ (with extra equations) and computing a Hermite normal form.


32-bit or 16-bits elliptic curves I would like test vectors for 32-bit or 16-bits elliptic curves like
$[p,
 a,
 b,
 G,
n,
 h]$
, to test the Pohlig-Hellman algorithm in order to attack ECDLP over a finite prime field $F_p$.

Does anybody know a method to generate small $F_p$ parameters or can anybody supply the test vectors?

Here is an example curve with smooth order $E/\mathbb{F}_p:y^2=x^3+ax+b$, generated with Magma.

\begin{align*}
p &= 2^{31}-1 \\
a &= 1456400922 \\
b &= 2005615003 \\
n &= 2^5\cdot 3^7 \cdot 5\cdot 17\cdot 19^2.
\end{align*}

I'd expect that if you are able to run PH, you should also be able to generate some test vectors yourself. The code is

p := 2^31-1;
Fp := GF(p);

repeat
    ct := 0;
    repeat
        a := Random(Fp);
        b := Random(Fp);
        D := 4*a^3+27*b^2;
    until D ne 0;
    E := EllipticCurve([Fp|a,b]);
    F := Factorization(#E);
    for f in F do
        if f[1] gt 25 then
            ct := 1;
        end if;
    end for;
until ct eq 0;


How to find the co-efficients of a function within Zp[x]? I am a newbie in Finite Field arithmetic and while trying to implement an Elliptic Curve Cryptography based ABE scheme in a programming language, I am unable to understand how to implement function fields.
I am given a function definition within a finite field of $p(i.e. Z_p[x])$ where $p$ is some large prime number. How do I find the co-efficient of $x^k$ in the expansion of $f(x)$?
Function definition:
$$f(x)=\prod_{i=1}^3 (x+H(i))^i$$
where, H(k) is a one-way hash function giving a large output.
Q1. Since the function is defined in $Z_p[x]$, should all the co-efficient be first calculated using elementary algebra and then taken modulus with $p$?
Q2. If we want to calculate the value of $f(\alpha)$, where $\alpha$ is some constant, can we do it using the final function polynomial of the previous step and substituting all x's with $\alpha$ and then taking a modulus $p$ again?

One thing you can always do in situations like this is "defer the reductions to the end".
By this, I mean do all of your calculations in $\mathbb{Z}[x]$, and then at the end "perform reductions until you no longer can", where the two kinds of reductions you do in $\mathbb{Z}/p\mathbb{Z}[x]$ are:

Modular reductions (of coefficients): $a\mapsto a\bmod p$
Reductions (of variables) according to Fermat's little theorem (if working mod $n$ for a composite number, instead use Euler's theorem): $x^k\mapsto x^{k\bmod \varphi(p)}\bmod p = x^{k\bmod (p-1)}$

As kelalaka points out, you can first expand $f(x)$ as a degree 6 polynomial. As $p$ is large compared to the degree (unless by "large" you mean something like 5), you will need no reductions of the second type, so can solely reduce the coefficients of $f(x)$ mod $p$.
If you have to do these computations on the fly this is not the most efficient thing to do (as the initial computation of $f(x)$ can potentially have a very large representation compared to the reduced version, and you may have to do arithmetic with very large numbers in computing this), but it can be useful both conceptually, and fine when you need to pre-process a polynomial (as you do now).
Essentially, arithmetic with polynomials $\bmod n$ can be split into (familiar) integer polynomial arithmetic, followed by applications of the above two reduction rules.


Encrypt user email but be able to find user by email Sorry for my dumb question, but it's better to ask dumb question than to do dumb things silently.

I want to encrypt user email in my DB so that if someone stole the DB (and not the key) - he won't be able to restore the email adresses. But I need to be able to find user by email in my DB. And I can't iterate over all the emails in the DB, decrypt each and compare - this is too slow (minutes, hours).

If I encrypt emails with AES with random IV - then each time I encrypt the same email - the encrypted value is different. This is great for security but this way I can't just encrypt the given email and search for a value. If the IV is the same each time - then as far as I understand if attacker have enough encrypted values - he can easily find the key, right?

I was thinking about storing original email hash alongside the encrypted value, but this way attacker will be able to recover original email values by encrypting emails from some dictionary with the same hash algorithm and comparing hash values with values in the DB.

I thought about storing hash of original email+some_fixed_secret. Is this secure? If not - is there a secure solution to my problem?

I ended up with the following solution:
For each email store two values: encrypted email and signature for the email.
For encryption I used AES in CBC mode with random IV.
For signing I used HMAC SHA256.
The keys used for encryption and for signing are different.

Later on I found the following link: docs.oracle.com. So looks like this is pretty standard approach.


Are there maximal rsa modulus keysize above which security start decreasing? Is there a rsa modulus size where security starts to decrease or is a larger rsa keysize always better? (of course I’m considering things like performance penalty)

With current known attacks increasing key size will improve security. Providing you follow current best practices for selecting p and q, not to close together neither to small. Etc.
It is possible but unlikely there will be some future attack on RSA or integer factorization which gets easier beyond a certain size. We already have different best algorithms for integer factorization depending on size but bigger is still better.
https://en.wikipedia.org/wiki/General_number_field_sieve is currently best for very large numbers (with no special form). But for numbers less than 100 digits or so https://en.wikipedia.org/wiki/Quadratic_sieve is faster.

Obviously standardized well known implementations are more secure than anything homegrown and this will likely trump key size.

Currently RSA is best attacked by integer factorization and this will likely remain in the near future, though there are no proofs RSA is as hard as Integer factorization.


Can two traitors safely reveal themselves to each other? Suppose Alice is a traitor and suspects Bob might also be a traitor. If Bob is a traitor, she would like to conspire with him together, if not she doesn't want to reveal that she is a traitor.
Is there a protocol Alice and Bob can engage in that would reveal that they are either:

Both traitors
Not both traitors

With a trusted third party, this would be be easy. Both Alice and Bob reveal their traitor/non-traitor status to the TTP and if both are traitors the TTP tells them so, if only one or none of them are traitors the TTP just says they are not both traitors.
But is there a way without a trusted third party?
I did some research and found this might be an example of a fair exchange and thus be technically impossible without a TTP. Most of the info I can find on fair exchange is over my head though and I thought this situation might be unique in that it involves agreement on potentially the same information, the protocol equivalent of an AND operation. And of course there is that feeling of "it's such a simple problem, how could it be impossible?" so I had to ask.

But is there a way without a trusted third party?

Sure, one of the simpler solutions is probably to use Yao's Garbled Circuit Protocol to compute the AND gate. Note that actually using the original protocol will do here because the modern speed-ups are only important for large numbers of ANDs and malicious security would also be somewhat useless as a dishonest party can just lie and claim 1 to learn the other party's input bit.
So here's the basic protocol:
Setup Phase (executed only by Bob):

Pick $6$ random 128-bit keys and call them $k_A^0,k_A^1,k_B^0,k_B^1,k_\land^0,k_\land^1$.
Define the encryption scheme $E_{k,k'}(m)=(r,F_k(r\|0)\oplus F_{k'}(r\|0)\oplus m,F_k(r\|1)\oplus F_{k'}(r\|1)\oplus 0^{128})$ where $F_k(m)$ is a single AES-128 block cipher encryption call and $r$ is a freshly randomly chosen 127-bit value. The corresponding decryption function returns an error whenever the XOR of the third entry with the re-computed AES evaluations doesn't yield 128 zeroes.
Compute the "garbled table", that is compute $T_{11}=E_{k_A^1,k_B^1}(k_\land^1)$ and $T_{xy} = E_{k_A^x,k_B^y}(k_\land^0)$ for $x,y\in\{0,1\}$ with $x\land y=0$.
Randomly permute the four table entries, call the result $T_0,\ldots, T_3$, eg using a Fisher-Yates shuffle fed by a cryptographic RNG.
Compute $H_0=H(r\|k^0_\land)$ and $H_1=H(r\|k^1_\land)$ using your favourite cryptographic hash function, e.g. SHA-256 and some 128-bit random string $r$.
Send $T_0,\ldots, T_3,H_0,H_1$ to Alice.

Input Phase (executed between both):

Bob sends $k^x_B$ to Alice where $x$ is his input bit.
Bob also picks a random Diffie-Hellman key (e.g. for P-256), call it $t$ and sends the public element $T=[t]G$ to Alice.
Alice picks her own Diffie-Hellman key, call it $k$, and computes $K_c=[k]G, K_{1-c}=T-K_c$ for her secret protocol input bit $c$ and sends over $K_0$ to Bob.
Bob computes $K_1=T-K_0$ and chooses two new DH keys $r_0,r_1$ with $R_0=[r_0]G, R_1=[r_1]G$ and sends over to Alice $E_0=(R_0,H([r_0]K_0)\oplus k_A^0), E_1=(R_1,H([r_1]K_1)\oplus k_A^1)$ using your favourite hash function, e.g. SHA-256
Alice selects $E_c=(L,R)$ from the two received ciphertexts corresponding to her input bit $c$ and computes $k_A^c=R\oplus H([k]L)$

Note: The last 4 steps are my adaption of the oblivious transfer protocol of Naor and Pinkas from "Efficient Oblivious Transfer Protocols" (2001).
Computation (executed by Alice)
Alice now tries to decrypt all 4 entries of the garbled table $T_0,T_3$ using $k_A^c$ and $k_B^x$. Only one decryption should succeed recovering $k_\land$.
Output Exchange (executed between Alice and Bob)

Alice sends $k_\land$ to Bob, Bob now knows the result of the AND gate computation by virtue of comparing the value with $k_\land^0$ and $k_\land^1$
Bob sends $r$ to Alice who can then also recover the evaluation bit by re-computing $H_0,H_1$ and checking which hash matches.


Is there an encryption algorithm that only adds minimal (if any) size compared to the size of the unencrypted data? We are working on a project in which we will need to encode and encrypt 1 - 1.3 kb worth of data at a time. We need the result of each piece of data to be the same size it was before, or be smaller, or be only slightly bigger. Basically as small as it can be while still being secure and still being able to get the original data back by decrypting and decoding.

If you were doing something like this how would you best approach it? Is there an encryption algorithm that only adds minimal (if any) size compared to the size of the unencrypted data?

This is in JavaScript and will run in browsers.

A steam cipher does not increase the size of the plaintext, but you need an IV (which then does increase the size) or different key each time, so effectively this doesn’t help. You can get a relatively small increase of size by using AES-GCM with a tag size of 10 bytes and IV of size 12 bytes.  So this increases by 22 bytes overall.

If this is too much, then it depends if you can guarantee that the same plaintext never repeats. If yes, then you could use AES-GCM-SIV with a fixed IV and save the IV bytes. Alternatively, if you don’t need authentication, then you can use XTS but this is far from ideal.

In general, an additional 22 bytes for about 1KB is only about 2% overhead so it’s not significant and your best using a full blown authenticated encryption mode.


Optimal threshold for passive and perfect security The authors of the book titled "Secure Multiparty Computation and Secret Sharing" claim that there exist functions which cannot be computed with passive perfect security for $t \geq n/2$ corrupt parties, where $n$ is the total number of parties. The authors prove this by showing that no protocol $\pi$ exists for secure 2 party AND with one corrupt party. However, for a 2 party protocol ($n=2$), the threshold of 1 can be written as a function of $n$ as $n/2$ or $(n-1)$, since $n=2$. So how can we guarantee that $n/2$ is the optimal corruption bound?

Can someone please help fill the gap in my understanding?

The way to extend the proof to arbitrary $t,n$ and this threshold is as follows. Assume that there exists a protocol for any $n$ parties that withstands a threshold of $t=n/2$ corrupted parties, for computing $f(x_1,\ldots,x_n)=x_1 \wedge x_{n/2+1}$. (If it withstands $t>n/2$ then it also withstands $t=n/2$, so that's fine.) I will now construct a two-party protocol for securely computing AND that is resilient to one corruption. This will contradict the known impossibility result.

The protocol works as follows. The parties simulate an execution of the $n$-party protocol. Party $P_1$ internally runs parties $P_1,\ldots,P_{n/2}$ and party $P_2$ internally runs parties $P_{n/2+1},\ldots,P_n$. Party $P_1$ puts its input as the input of $P_1$ in the $n$-party protocol, and party $P_2$ puts its input as the input of $P_{n/2+1}$ in the $n$-party protocol. The parties output whatever the multiparty protocol says to output.

In order to argue security, all you really need to notice is that if one party is corrupted then this is equivalent to $t=n/2$ in the multiparty protocol. Therefore, security is maintained.


One-direction same size encryption algorithm that allows for partial replay I am looking for a one-directional encryption algorithm that preserves the size of the input. Then I would like to be able to mix an encrypted with original data and to be able to receive the same result. It is probably hard to grasp, let me try to explain with an example: Let's say I have the input: This is some text to encrypt and the encrypted result with the same size says: xxxxxxxxxxxxxxxxxxxxxxxxxxxx. The algorithm should be able to calculate the same result from any input that mixes the original unencrypted bytes with the encrypted result: This is xxxx text to encrypt or This is some text xx xxxxxx. Note that providing a protocol that describes which area is the original and which is already encrypted is ok. It does not need it to determine this on its own.

An example use case that illustrates an application of such an algorithm: Alice and Bob play battleship. When Alice makes her choices, she encrypts them and sends them to Bob. Bob cannot make any sense of the data, else he will know where to attack. When bob plays his move, Alice reveals the field. Bob does not trust Alice that she did not change the order of the ships after he already told her his move - this is why Alice sends the board encrypted again with already stricken fields revealed. Bob now can apply the algorithm that can encrypt the revealed part to make sure that he will get the same result as the original send from Alice. NOTE: this is illustration use case - I am not looking for alternatives to solve this problem.

Can you give me ideas of algorithms that already provide this or something that I can base such thing on?

It sounds like you're describing a Commitment scheme.

A simple implementation would be that Alice makes a list of boat position + ":" + random 16 bytes (with a different random value per item). She sends Bob the hash of each list item at the start of the game, and later she can send Bob the plaintext of any of the hashes to prove the position of a boat is where it was when the game started. (The random value in the hash is to prevent Bob from brute-forcing the hash. If there only a small number of possible boat positions, then Bob could brute-force to reverse any hash easily if it weren't for the random value.)


What is the error in this collision probability approximation? Theorem: Choose $Q$ random natural numbers in the set $\{1,2, \dots, M\}.$ The probability of getting at least one collision is

$$P_C(Q) = 1 - \frac{M - (Q - 1)}{M} P_{\neg C}(Q-1).$$

Notation:  By $P_C$, I mean the probability of getting a collision.  By $P_{\neg C}$ I mean the probability of not getting a collision.

Remark: This is the birthday problem.

Remark: So $P_C(Q)$ is just being computed by using its complement. The reason I express the theorem this way is because its induction proof relates directly to it being enunciated this way.

Theorem:  $$P_C(Q) \approx 1 - e^{-\tfrac{(Q-1)Q}{2M}}.$$

Proof: We know
    $$e^{-x} = 1 - x + \frac{x^2}{2!} - \frac{x^3}{3!} + \frac{x^4}{4!} - \ldots$$

If we take the two terms of this expansion, we get $e^{-x} \approx 1 - x$.  Then

\begin{align}
  P_{\neg C}(Q)&= \prod_{i=1}^{Q-1} \left(1 - \dfrac{i}{M}\right)\\
       &\approx \prod_{i=1}^{Q-1} e^{-i/M} \\
       &= e^{-1/M} e^{-2/M} \dotsc\ e^{-(Q - 1)/M} \\
       &= e^{-\sum_{i=1}^{Q-1} i/M} \\
       &= e^{-\dfrac{1}{M} (Q-1)Q/2}\\
       &= e^{-\dfrac{(Q-1)Q}{2M}},
\end{align}

So $P_C(Q) \approx 1 - P_{\neg C}(Q),$ as desired.

Question:  How can I (at least) have some notion of how off the right number I am if I use this estimation to compute the probability of getting a collision in a concrete case?

Clearly, for $x\in (0,1)$ which is our case,
$$
e^{-x}-(1-x)< x^2/2,
$$
and thus the relative multiplicative error between the estimate and actual answer satisfies
$$
\frac{\widehat{P}_{\neg C}(Q)}{P_{\neg C}(Q)}<\prod_{i=1}^{Q} \frac{(i/M)^2}{2(1-(i/M))}\leq
2^{-Q} M^{-2Q} \frac{Q(Q+1)(2Q+1)}{6}\frac{1}{(M+1-(Q+1)/2))},
$$
by using the sum of first $Q$ squares on the numerator and the arithmetic geometric mean inequality in the denominator. So
$$
\frac{Q^3/3}{ 2^Q M^{2Q}(M-Q/2)}
$$
is a good approximation to the error.


Is there a strong cryptographic reason for GCM's 2^39 - 256 bit limit? In reading through the original GCM specification (McGrew & Viega '05), the composition of the 128 bit Initialization Vector as a concatenation of a 96b nonce and a 32b unsigned wrapping counter seems arbitrary and forces the scrambling pattern to repeat every 232 16-byte block.

Is the algorithm expected to be secure for significantly longer stream lengths if for example the IV were a 128b nonce XORed with a 64b or 128b counter, or are there known cryptanalysis issues that begin to arise?

With concatenation the caller only has to ensure the nonce is unique. For example they can use a counter that increments for each message. Incrementing a counter for each message is convenient in many scenarios, including encrypted network transports like TLS.

If you use xor or add nonce and counter you get overlaps, so a counter as nonce would be fatally broken.
The security of GHash, the MAC part of GCM, decreases as the length of the message increases. This means that it's a good idea to limit the maximal size of messages the receiver is willing to accept.

  forces the scrambling pattern to repeat every 2^32 16-byte block"

The pattern doesn't repeat, you simply MUST not encrypt a message longer than that size.

A 64 GiB message is a very unusual for authenticated encryption, since the receiver can't use the data before they verified the MAC on all of it. Typically you split long data into multiple messages, each with their own MAC. That way the receiver can verify individual blocks and then work with the plaintext, safe in the knowledge that it wasn't manipulated.


Technical term for hash value being uncorrelated to input message? Is there a technical term for the desirable property of hash functions. That a small change to the input message will produce a massive unpredictable and seemingly uncorrelated change to the output hash value? I keep getting stuck on words like pseudo-random and unpredictable but they don't seem to fit the property correctly.

That a small change to the input message will produce a massive
  unpredictable and seemingly uncorrelated change to the output hash
  value?

It sounds like you're looking for the avalanche effect.


Word-based stream ciphers vs "regular" stream ciphers? Could somebody explain what is the difference between "word-based" stream ciphers and the regular ones? Those last ones use pseudo-random sequences XOR'd bit by bit with the message, as far as I know. How does that change when it comes to "word-based" ciphers?

Examples of word based keystream ciphers include SNOW, PANAMA, SOBER, ORYX. I also read that word based keystream ciphers "allow greater efficiency in software than most bit based stream-ciphers".

A word-based stream-cipher produces the pseudo-random sequence one word (of several bits) at a time. For example RC4 is a word-based stream cipher, with the word size a byte. By contrast, a typical bit-based stream cipher such as one using the ASG produces the pseudo-random sequence one bit at a time.

Word-based stream ciphers may be better suited to fast software implementations than are bit-based stream ciphers, since CPUs typically process one word no slower than one bit.


Is a stream cipher and a (cryptographically secure) PRNG nearly the same thing? If I let the authentification tag aside (which is important), encrypting with AES-GCM and a fixed key and nonce:
import Crypto.Random, Crypto.Cipher.AES, numpy as np
key = bytes.fromhex('7d29ccf69c671775e17d4b9dd6485fd8')
nonce = bytes.fromhex('04972c7927042af0ee10c7e6ac56ddd3')
cipher = Crypto.Cipher.AES.new(key, Crypto.Cipher.AES.MODE_GCM, nonce=nonce)
print(cipher.encrypt(b'goodgoodcrypto').hex())     # e7e4d3b74617d78022376651ba3a

can be obtained with the same result by obtaining a cipherstream (encryption of a stream of \x00\x00... null bytes) to XOR with the plaintext
xor = lambda x, y: (np.frombuffer(x, dtype='uint8') ^ np.frombuffer(y, dtype='uint8')).tobytes()
cipher = Crypto.Cipher.AES.new(key, Crypto.Cipher.AES.MODE_GCM, nonce=nonce)
cipherstream = cipher.encrypt(b'\x00' * 14)     # 808bbcd32178b8e441451f21ce55
print(cipherstream.hex())
print(xor(cipherstream, b'goodgoodcrypto').hex())   # e7e4d3b74617d78022376651ba3a !! same ciphertext!

Here I only took 14 bytes of cipherstream because I only needed 14 bytes to encode plaintext.
Thus, it looks like in this context of AES-GCM that:

encryption here is equivalent to just having a long-enough stream of random-looking bytes (cipherstream above),
deterministically initialized with key and nonce (similar to the seed in PRNG terminology)
encryption is just this cipherstream XORed with plaintext

Question: can we turn a (cryptographically secure) PRNG into a stream cipher? (the PRNG's seed is the key / nonce)
The reciprocal seems also true: AES-GCM encrypting a flow of null bytes b"\x00\x00\x00\x00..." seems to give a cryptographically secure PRNG. The seed is the key+nonce pair.

Stream cipher and CSPRNG aren't the same thing. CSPRNGs must handle initial seeding, post-compromise reseeding, back-tracing resistance among other things; stream ciphers only need to be able to output something indistinguishable from random.
So can we turn a CSPRNG into a stream cipher? Possibly, if we make every generate requests to the CSPRNG idempotent, and drop reseeding. But that wouldn't be as efficient as just using the stream cipher directly - not only does CSPRNGs has extra code paths to execute, its internal state is often larger than that of stream ciphers.


Why doesn't GMAC/GCM encrypt its authentication tag? As most know, a duplicate nonce with GMAC/GCM allows key recovery attacks against GMAC itself and thus the ability to forge messages. This is because GMAC computes GHASH and then just XORs this with AES(j) where j is the GCM counter. If a nonce is duplicate you get identical AES(j) which lets you XOR and get the raw GHASH and then attack the GCM polynomial.

Why doesn't GCM encrypt its final authentication tag using AES in ECB mode (one ECB block)? If performance is a concern and you want to avoid doing two  AES encryptions why not do AES(GHASH(m) ^ j) or similar? GHASH(m) XOR AES(j) seems like it's begging for sudden death on nonce reuse. Why do that?

It seems like this simple design change would have made GCM/GMAC more resistant to nonce repetition. You'd still be able to XOR ciphertexts just like you can with any stream cipher when a nonce is repeated but you wouldn't be able to compromise the authentication key, right?

Latency, probably.

$\mathrm{GHASH}_K(m) \oplus \mathrm{AES}_K(n)$ lets you compute both in parallel, whereas encrypting the $\mathrm{GHASH}$ output would add significant latency for short messages. The authors go to great detail about this in Section 3 of the original GCM document.

A similar competing mode at the time, CWC, did indeed encrypt the MAC output but was not as efficient.


Exclusion proof cost I am trying to understand what is the cost of non-membership verification for a universal accumulator?

More specifically, how can I compute it?

Whether using an accumulator is more efficient than the Merkle Hash tree?

In section 5.3 of this paper you can find a comparison between an accumulator and MHT. The complexity totally depends on the scheme.

In general, MHT is linear in the proof of exclusion (in the order of depth of the tree). Because the verifier has to check all the possible paths to convince a leaf is not in the tree.


Why Rabin fingerprints assumes data is prefixed with a "1" bit? (I know that a Rabin fingerprint is not a cryptographic hash, sorry in advance if my question is considered out of topic)

In the paper Some applications of Rabin's fingerprinting method, it is written that implementations should prefix the data to hash by a '1' value.

Does anybody know why?

I think that it was to make sure that the leading zeroes in the data to hash are taken into account during the hash. Without the '1' prefix value, those leading zeroes would make the fingerprint stay to zero.

Without the '1' prefix, the following 2 list of bytes would have the same fingerprint:

[42, 5, 3]

[0, 0, 0, 0, 0, 0, 0, 0, 0, 42, 5, 3]


Difference between symmetric and asymmetric hash function? The Linux kernel supports symmetric and asymmetric hash functions. E.g. sha1, sha256, ...

See tcrypt.c and search for test_hash_speed and test_ahash_speed.

I know what the difference is between symmetric and asymmetric ciphers, where the encryption and decryption key is not the same.

Question

What is the difference between symmetric and asymmetric hash functions?

It is probably not the case of your example, but in some sense "asymmetric hash functions" do exists: they are called trapdoor hash functions (or also chameleon hash functions).

Very briefly, they are collision resistant only if you don't know their trapdoor secret key.
Such functions take 2 arguments (instead of the usual one), and the second argument is used as randomness.

So, without the trapdoor secret key it is infeasible to find 2 "messages" $m_1,m_2$ and 2 randomness values $r_1,r_2$ such that $H(m_1,r_1)=H(m_2,r_2)$; while, with the trapdoor key, you can efficiently compute (for any given triple $m_1,m_2,r_1$) a value $r_2$ such that $H(m_1,r_1)=H(m_2,r_2)$.

Hope this is clear enough. If you want, you can also see this  article by Shamir and Tauman or this one by Krawczyk and T Rabin


Is this a good way to encrypt a file? I need to encrypt a file, distribute it over an insecure channel, and decrypt it later. Using a symmetric-key algorithm. Here's what I intend to do:

Get a password P from the user. Generate a 16-byte random salt S. Derive a key K1 = PBKDF2(HMAC-SHA1, P, S, iter=2000, bits=256). Divide the data into blocks of 1024 bytes each. For each block, generate a random 16-byte IV. Encrypt each block with AES-256 with key K1 and this IV. For each block, calculate D = HMAC-SHA2 of the concatenation of IV and encrypted data. For each block, write out the IV, the ciphertext and D.

Now I need to store and distribute the salt too. For this, I derive key K2 = 1000 iterations of SHA2("somefixedtext" + P) and IV2 = 500 iterations of SHA2("someotherfixedtext" + P). The salt is then encrypted with AES-256 with key=K2, IV=IV2 and stored alongside the ciphertext.

OK, so is this secure enough?

First off, you are still missing some information. What encryption mode will you be using? What key are you using for the HMAC?

That said, my answer is no. This isn't a good way. The reason being is that unless you are a professional cryptographer, you shouldn't design your own cryptographic protocols/methods. There are too many ways to introduce vulnerabilities in both the design and the implementation that it is risky. Stick with published standards that the cryptographic community has been able to look at and analyze. You can encrypt files using PGP or the open source implementation GnuPG.


Merkle Signature Generation In the section 2 (page 42) of the book "Post Quantum Cryptography", it says:

  Then he generates the one-time signature $\sigma_{\text{OTS}}$ of the digest using the $s$-th one-time signature key $X_s$, $s\in\{0,\dots,2^H-1\}$.

My question: Is $s$ chosen in random form? Is it possible to have $s$ collisions to the signature process?

If he chooses $s$ at random, then the scheme will be stateless but will fail after using the same $s$ twice, which should happen after giving approximately $\:$$\Theta$$\big(\hspace{-0.05 in}$
$2^{H/2}$$\hspace{-0.01 in}\big)\:$ signatures.

If he chooses $s$ by applying a PRF to $g(m)$, then the scheme will be deterministic and stateless,

but can be expected to fail after giving approximately $\:\Theta\left(2^{H/2}\right)\:$ signatures.

If he keeps an initially empty list as state, chooses $s$ at random from the leaves that are not on the list, puts $s$ into the list, and makes the list empty again if at this point it contains all of the leaves , then the scheme will need to keep an amount of state that grows linearly with the number of signatures given.

In this case, the scheme will fail after giving $\:2^H\hspace{-0.045 in}+\hspace{-0.03 in}1\:$ signatures.

If he chooses $s$ to be one more than the previous value of $s$ when there is a previous

value of $s$ and such a leaf, and chooses $s$ equal to $0$ in all other cases,

then the scheme will be deterministic but will need to keep $H$ bits of state.

In this case, the scheme will fail after giving $\:2^H\hspace{-0.045 in}+\hspace{-0.03 in}1\:$ signatures, and until that point,

each signature will also reveal and authenticate how many messages were previously signed.

That will stop an adversary from reordering the messages but will also reduce the signer's privacy.

(The following option was suggested by Paŭlo Ebermann in the comments.)

If he chooses $c$ in the way the previous paragraph described him choosing $s$, and chooses

$s$ by applying a PRP to $c$, then the scheme will be deterministic and need to keep $H$ bits

of state and fail after giving $\:2^H\hspace{-0.045 in}+\hspace{-0.03 in}1\:$ bits of state. $\:$ In this case, the scheme will enable

anyone who has the PRP's key (this will usually just the signer, although anyone else who

learns the signing key will know the PRP key too) to determine how many messages were

signed before a specific signature was given, and hide that information from everyone else.

I suspect that the most important thing is that the scheme be deterministic and stateless.


Trial divisions before Miller-Rabin checks? I'm trying to understand prime number generation (more correctly, the primality checking) as described in Handbook of Applied Cryptography.

The context is circa pages 145 - 150, and specifically Table 4.4 (p. 148). The table presents (k,t) pairs, where 'k' is the number of bits in the candidate and 't' is the number of Miller-Rabin iterations that keeps the error rate below $2^{-80}$. From the table (partial shown below):

  k  |  t
=====|=====
 100 |  27
 200 |  15
 400 |   7
 450 |   6
 550 |   5
 650 |   4
 850 |   3
1300 |   2
2050 |   2

However, the discussion surrounding the table notes that "one is usually willing to accept an error probability of $({1\over2})^{80}$ when using Algorithm 4.44". Algorithm 4.44 (p. 146) states to use trial division to rule out low hanging fruit (sic).

But according to Note 4.45 (p. 146), Algorithm 4.44 bounds the trial division based on B, where B is based on the time it takes to perform a modular exponentiation versus time required to rule out a small prime by trial division.

If the "proper" number of trial divisions are not performed (for some definition of "proper"), then error rate may not be as expected. I'm reading that from the discussion on page 165, where its suggested to select 't' such that its equal to ${1\over2}\cdot\lg(k)$. Using this formula, it appears a 1024-bit candidate needs 5 or 6 Miller-Rabins test, and not the 2 or 3 advertised in Table 4.4.

Question: how many trial divisions against a table of primes should be performed before moving to Miller-Rabin? In essence, I'm asking how large the prime table used in trial division should be.

Is it enough to test all primes up to (and including) 17863? 17863 happens to be the 2048th prime.

Related Question: is the acceptable error rate still $2^{-80}$?

(Sorry about the tag. It does not appear there are tags for random-numbers, primality-testing, trial-division or Miller-Rabin)

EDIT (JUN-17-2014): The reason I asked was OpenSSL and Crypto++ random number generation. I did not want ot taint answers with too much context.

OpenSSL uses a prime table up to 17863 and Miller-Rabin according to Table 4.4. Crypto++ uses a prime table up to 32719 and either 1 or 10 round Miller-Rabin.

The OpenSSL source files of interest are openssl/crypto/bn/bn.{h|c}, and the Crypto++ source files of interest are cryptopp/nbtheory.{h|cpp}.

Update: the formula actually on page 165 in chapter 4 of the HAC is: $t=\lceil{1\over2}\cdot\lg n\rceil$, where $\lg$ is the base-2 logarithm; that is $t=\lceil{1\over2}\cdot k\rceil$; and that crude estimate asks for 512 Miller-Rabin tests for 1024-bit primes, not 5 or 6 tests as stated in the question based on the erroneous $t=\lceil{1\over2}\cdot\lg k\rceil$, or 3 tests as in Table 4.4. That crude formula $t=\lceil{1\over2}\cdot\lg n\rceil$ is based on the fact that a MR round has odds at most $1\over4$ to let a composite pass, is usable in practice with often acceptable speed penalty, but is way overkill for primes of size suitable for cryptographic keys.

The authoritative academic reference on the number of Miller-Rabin tests is this paper: Ivan Damgård, Peter Landrock, and Card Pomerance, Average Case Error Estimates for the Strong Probable Prime Test, Mathematics of Computation, v. 61, No, 203, pp. 177-194, 1993. That's reference [300] in the HAC, and used to derive their Table 4.4.

The authoritative normative reference, which also cites the previous paper, is FIPS 186-4 appendix F.1, with even more down-to-earth prescriptions in the context of generating FIPS 186-4 RSA keys in tables C.2 and C.3, reproduced at the end of this answer.

All the references above consider that $n$ being tested is a random odd integer of specified bit size. Using trial division by small odd primes combined with Miller-Rabin slightly increases the confidence we can have that the number tested is prime compared to MR alone, but that is usually neglected. The main reason to perform such trial division is as a speedup: most of the integers tested are going to be composite, we want to rule them out as fast as possible, and early trial division achieves that.

As an example suitable in many cases of cryptographic interest on modern desktop CPUs: in order to test if some large random odd $n$ is prime, noticing that $k=3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29$ is less than $2^{32}$, we can compute $r=n\bmod k$ efficiently using hardware 64-bit by 32-bit division; then skip Miller-Rabin if $\gcd(r,k)\ne1$. That leaves only ${{2\cdot4\cdot6\cdot10\cdot12\cdot16\cdot18\cdot22\cdot28}\over{3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29}}<{1\over3}$ of candidates to be tested by MR, and thus speeds up things by a factor of over 3 on many platforms (including most where MR is slow). We can do more trial division, but with severely diminishing returns (the speed-up is by a factor at most 1.14 for division by $31\cdot37\cdot41\cdot43\cdot47$). The above technique with $k=2\cdot3\cdot5\cdot7\cdot11\cdot13=30030$ is easy to code efficiently on most 32-bit embedded CPUs, already gives a speedup of about 2.5, and might be good enough. Experiment can be used to determine the optimum; trial division by the first 2047 odd primes will be beyond that point if there's a half-decent modexp.

Note: it is notoriously hard to validate primality-testing code, especially in a black-box setup. MR is popular because it is simple thus relatively easy to proofread, but caution! With large parameters, it is almost impossible to ever reach the second MR test, at least if the witness used is random! We can easily craft test cases that pass trial division, but ideally these should also be Carmichael numbers if we want a chance to catch some improper MR variations, and I do not know if the extensive literature on generation of large Carmichael numbers provides that.

In practice, in the context of RSA, one can do (very) little trial division, following by a number of MR tests according to the following table:

In this table, error probability (like $2^{-80}$ in the first box) is for the guaranteed residual odds of accepting a composite for any of the 6 (pseudo)primes involved in the RSA key generation process: $p$, $q$, and shorter intermediary primes $p_1$, $p_2$, $q_1$, $q_2$ such that $p\equiv1\pmod{p_1}$, $p\equiv-1\pmod{p_2}$, $q\equiv1\pmod{q_1}$, $q\equiv-1\pmod{q_2}$.


Efficient Symmetric Mutual Entity Authentication Protocol I am looking for an Authentication protocol for access control. Let's say both the client and server would share a symmetric secret (256 bit key) and the client wants to access the server. Access should only be granted to a registered client the server shares a key with and both parties should know whom they've talked to.

It should provide:

mutual authentication (client and server are both sure to talk to server resp. client)
freshness property to encounter replay attacks
efficiency: both parties should only have to execute a few cheap computations
the authentication token should change for every authentication attempt
the server should be prone (as much as possible) against DoS-attacks
no replay or pre-play attacks

I couldn't find any protocol like this except Janson-Tsudik's 2PKDP which is patented.
Thus, I had the idea to construct an own protocol from the protocols I have seen so far.
I know this is probably the worst idea, especially because I am not a professional cryptographer.

But nevertheless I want to share my idea to know the pros and cons.
I like the idea about Lamport's hash chains and want to use their hash values as one time authentication tokens (tickets). The advantages are mainly that the verification is really fast (just a hash-function) and the client needs to bring some information not yet known into the server.
Unfortunately the major disadvantage is that the client has to precompute all N tickets. Thus I looked up one-way permutations with a trapdoor like for instance chameleon hash functions to be able to go in both directions of the hash chain (also known as infinite, re-initializable or renewable hash chains).
Since I couldn't find any good implementation for such a function, I thought about just using RSA signatures: Client has a private key and the server his authenticated (beforehand) public key. The client initially generates a pseudorandom seed value which is then encrypted with the RSA private key (d, N), resulting in my first authentication ticket.
Given that the server has also received the initial seed value, it can then upon receiving the first ticket check it by verifying it, i.e. decrypting it with the RSA public key.
If the knowledge of the new ticket refers to being granted access, the
open problems are how to accomplish mututal authentication and freshness and how to securely transmit the newly generated ticket to the server each time you log in.
So far, I thought about something like:

client sends its client_id to server
server generates nonce N and sends it back
client calculates HMAC_T(N, client_id) xor T_new  (where T is the last ticket and T_new the new one - and T is used as key for the hash-keyed MAC function)
server can compute the HMAC_T(N, client_id) since the old T is still available
server can thus deduce T_new
server can verify T_new by calculating: RSA_verify(T_new, (e, N)) == T
(or in other words: decrypting T_new with the client's public RSA key and check if that yields in T.

Please note that the server needs to keep the last ticket saved because it's used for verifying the one handed with the next authentication request.

Please tell me in a merciless way which problems you see about it and where I haven't thought it through enough. Also if there is already a protocol/scheme that does what I want to, please point me into the right direction.

Thanks ahead

Please refer the well-known handbook of applied cryptography by Menezes et al.,you may find many symmetic key-based mutual authentication protocols (in Chapter 10), and more important, some pointers to the standards, e.g. ISO/IEC 9798 et al. Wish it helps.


Sequence of Encrypting RSA like Chaum Blinding scheme I'd be a noob in cryptography but reading up a little on RSA, I do get some understanding and I want to specifically resolve this issue.
UPDATED
Lets say we have the following values in place:
KEYSIZE = 512
HASHSIZE =  sha.digestsize*8
digest = some SHA 512 function

We calculate the pub_key,pvt_key e,d via n = pq
and totient function phy = (p-1)(q-1) in effect getting 1 < e < tot_func
and we get d=e mod tot_func
PS : pub and pvt keys are created as an RSA_function(KEYSIZE)
Implementing an RSA scheme, we have a token m
Now
c(m) = m^e mod n

Decrypting it would be:
m = c^d mod n

PS: m is a token number (instead of padding a m=token hash, converted from some m=f(M))
To be specific:
m = convert_str_to_long(sha_digest(M))

M itself is of random HASHSIZE bits

Chaumian Blinding
I want to know where I'm going wrong with this.
Given the same scheme as above for token id m, However I want to be clear with a Chaum's blinding scheme and implement that instead.
we have n,p,q,d,e,m
To blind quoting from Blinding

For example, in RSA blinding involves computing the blinding operation E(x) = xr^e mod N, where r is a random integer between 1 and N and relatively prime to N (i.e. gcd(r, N) = 1), x is the ciphertext, e is the public RSA exponent and N is the RSA modulus. As usual, the decryption function f(z) = zd mod N is applied thus giving f(E(x)) = x^dr^ed mod N = x^d*r mod N. Finally it is unblinded using the function D(z) = zr^−1 mod N. Since D(f(E(x))) = x^d mod N, this is indeed an RSA decryption. However, when decrypting in this manner, an adversary who is able to measure time taken by this operation would not be able to make use of this information (by applying timing attacks RSA is known to be vulnerable to) as she does not know the constant r and hence has no knowledge of the real input fed to the RSA primitives.

Blind requires creating a blinding factor,r.
while 1:
    r = random.getrandbits(KEYSIZE-1)
    Verify that GCD(r, n) ==1
    if gcd(r, n)==1: break;

Create a blinding factor, r
Create blinded_token = m * (r^e % n)

Questions:

What the heck do you do after that? Decrypt > Unblind Or Unblind > Decrypt to recover token m?
Also, if you want to sign the blinded_token do you Sign > Decrypt > Unblind OR Sign > Unblind > Decrypt ?
How do you Unblind actually based on above blinding?

My goal is to recover back m.
Please do tell me if you need some more info. I need this asap.
Thanks in advance!
UPDATE
I would like to credit both Rick and the OP here in my work regarding this.
I got the solution finally.

A much better way to choose r is

while 1:
    s = random.getrandbits(KEYSIZE+privacyparameter)
    r = 1+(s%(n-1))
    if gcd(r,n) == 1: break;

.
privacyparameter is chosen by the blinder.

If $\:$ gcd(m,n) = 1 $\:$ then the statistical distance between the distribution of blinded_token and

the uniform distribution on units mod n is less $\:$ n/((2^(KEYSIZE+privacyparameter+1))-(2*n)) $\;$.

The signer does not need to know or care what that value is.

It's much better to create $\;\;$  blinded_token $\:$=$\:$ (m * (r^e % n)) % n $\;\;$,

so that the size of the output won't leak much information about m.

The signer computes $\:$ (blinded_token)^d % n $\:$ and sends that to the blinder. $\:$ If the signer instead

signed or decrypted the token in the standard way, then the blind signature scheme wouldn't work.

If $\;\;$ (signers_response)^e % n $\:$=$\:$ blinded_token $\;\;$ then output

((signers_response)*modinv(r,n)) % n $\;$ as the unblinded signature, else reject.

There are two further subtleties for this blind signature scheme:

gcd(blinded_token,n) = 1 $\;$ if and only if $\;$ gcd(m,n) = 1

However, as alluded to in the one of the OP's comments to this answer,

the hash can to chosen to guarantee that $\:$ gcd(m,n) = 1 $\;$.

(So, hopefully, "sha_digest" is something that does so, rather than just one of the SHA functions.)

Also, if the RSA function does not define a permutation over $\mathbb{Z}_n^*$, then blindness

does not necessarily hold even if all relevant values of m satisfy gcd(m,n) = 1.


Is it safe to include the public certificate in xml digital signatures? My understanding of XML Digital Signatures:

Let's use a SAML token as an example.

  Note - for the sake of simplicity I'm omitting some details like CanonicalizationMethod, base64 encoding, etc.

In order for me to sign the <saml:Assertion> node I use a private/public key pair:

Create a hash of the <saml:Assertion> block and store it in a <ds:Reference> inside the <ds:SignedInfo> node.
Use the private key to encrypt the <ds:SignedInfo> node and store it in the <ds:SignatureValue> node.
Pass the public certificate in the <ds:KeyInfo> block.

To verify the signature I then:

decrypt the <ds:SignatureValue> node using the public certificate found in <ds:KeyInfo> and ensure that it is equal to the <ds:SignedInfo> block
ensure that the hash of the <saml:Assertion> node is equal to the digest stored in the <ds:Reference> node.

My question:

What I don't understand is that in my opinion this doesn't verify the sender, it simply verifies that the private key component of the public certificate sent in the <ds:KeyInfo> node was used to sign the token. An attacker could create his own certificate pair and sign the token with that.

This risk is probably resolved by ensuring that the certificate is either signed by a certificate authority, but if the sender uses self-signed certificates the verifying party should NOT use the public certificate sent in the <ds:KeyInfo>, but rather obtain the public certificate from another trusted source.

Could someone please verify or point out how I'm misunderstanding XML Digital Signatures?

The problem that you are having is how trust in the ownership of a public key can be created. That is a problem in all public key settings and independent of the format used (like XML signatures).

As you state correctly, the pure signature verification can only check, if some public key matches the private key used to sign a mesage. After that step, you need to check if you trust the ownership relation between the public key and the (claimed) signer.

There are quite a few trust models used in practice:

Certification Authorities An authority that you trust in advance (usually via a list installed in your operating system or software) signed a certificate containing the signers name and the public key
Trust on first use Whenever you communicate with a new entity for the first time, you trust the sender' public key and store that relationship
Web of trust Similar to 1. You trust a certificate, because someone else that you already trust does so.
Manual validation You have manually checked the ownership of a keypair by the sender previously via some out-of-band mechanism (like comparing the key's fingerprint on the phone)


Can public key cryptography be equivalent to asymmetric cryptography? If not, what's the difference? I'm currently studying modern public key cryptography course, and I'm confused whether public key and asymmetric cryptography are the same.

Yes, they are the same in most contexts. The asymmetry is in the keys used, public and private keys. It's definitely not in the encryption and decryption method; in (textbook) RSA the method for encryption and decryption (modular exponentiation) is completely the same. RSA is certainly used for public key cryptography and it is certainly also an asymmetric algorithm.

Key agreement and signature generation are also asymmetric cryptography. You could say that "public key cryptography" puts some more emphasis on the public key, probably hinting that the public key is generated by one party and trusted by another. This is usually the case for PKI(X), the underlying certificate based public key infrastructure used for e.g. TLS / HTTPS.

The public & private key may however not be static or trusted for Diffie-Hellman key agreement where the public / private key pairs are ephemeral (generated per key agreement operation).

Diffie-Hellman however also works with static/trusted keys, so that difference is feeble at best.

Note:

Asymmetric private keys are sometimes called secret keys. I think private keys is the better term. I use the term "secret keys" for symmetric keys (those may not be private to one party but must be kept secret by the parties holding them).


Geometric interpretation of an Edwards curve Addition on an elliptic curve in Weierstrass form (over the rationals) is typically depicted with the following figure:

(Image CC SA 3.0 https://en.wikipedia.org/wiki/File:ECClines.svg)

To add two points, one draws the line that connects these points. The third intersection point is mirrored to get the result of the addition.

A curve in Edwards form might look like this:

(Image CC SA 3.0 https://commons.wikimedia.org/wiki/File:Edward-curves.svg)

However, the classical geometric interpretation for addition on Weierstrass curves does not seem to work on these Edwards curves.
Take for example the point $(0,-1)$. When doubled, this becomes $(0,1)$, the neutral point, according to the addition law $$(x_1, y_1) + (x_2, y_2) = \left(\frac{x_1y_2 + x_2y_1}{1-dx_1x_2y_1y_2}, \frac{y_1y_2 + x_1x_2}{1-dx_1x_2y_1y_2}\right).$$

When using the "classical" Weierstrass geometric interpretation (case 4 in the first image), I would become the point at infinity (which of course does not exist for an Edwards curve).

Clearly, Edwards curves follow a different way of life. Does there exist a similar geometric interpretation of the addition law for Edwards curves?

The geometric interpretation of the "addition law" on Edward Curves is not the same as for Weierstrass Curves.

The correct interpretation for this kind of curves is "adding their angles".
It works as on a clock. Of course, as for the Weierstrass curves, the geometric interpretation stands for the curve over the real numbers and not in a finite field (useful for cryptography).

You can give a look to the ECCHacks: a gentle introduction to elliptic-curve cryptography (starting at page 6) by Daniel J. Bernstein and Tanja Lange


KDF followed by a Hash? It is my understanding that a KDF adds entropy, whereas a hash loses information.

I've read that KDF should be used to store passwords. I don't understand why we don't use a KDF and then a hash, so that – if the database of password is leaked – it would also be impossible to figure out the plain passwords.

So storing passwords in a database would be like this:

Use KDF to increase entropy (especially good if users are using short passwords),
Use a hash to lose information,
Store the hash.

Shouldn't this be the advised way to store passwords?

It is my understanding that a KDF adds entropy, whereas a hash loses information.

Password Based KDFs can be seen as hash functions (or families of hash functions, depending on your definition), just ones with a lot of complexity. It is sometimes said that they "add entropy" but that usually means either

they combine entropy from a salt into the password hash (which you can do with any hash function), or
they make the password more computationally difficult to crack as if it had more entropy (also called computational entropy).

PBKDFs and hashes are irreversible; meaning that it is impossible to find a password without performing a brute force or dictionary attack. PBKDF's make it computationally harder to perform a brute force search and the salt makes it impossible to find matching passwords within a database.

Both PBKDFs and hashes "lose information" in the sense that their image (output) is smaller than their input domain. That does not make them stronger, however, since if two passwords give the same output hash, either can be used as authentication.

So using a hash after a KDF is at best redundant and can lead to less security through e.g. increased collisions.


What is the state of cryptographic obfuscation in 2015? Cryptographic Obfuscation is a technique that allows one to obfuscate source code in a secure way (as opposed to insecurely mangling it into spaghetti code.) For example, here is a way to protect a piece of data with a password:

cipher_text = obfuscate("\key -> if input == SYMETRIC_KEY
then return \"Launch code is 7205872\" else return \"No launch codes for you!\"")

Or here is a public key cryptography scheme:

public_key = obfuscate( "\input -> obfuscate(\" \key -> if key == PRIVATE_KEY
then return " ++ input ++ " else return \\\"You do not have the public key!\\\")" )

My question is, what is the state of this technology? Is it available in any programming languages yet? (I provided my code samples in a haskell-like language, since haskell is very similar to lambda calculus. Indeed, GHC compiles Haskell into lambda calculus as an intermediate step. It is therefore likely that a language like Haskell, or perhaps a lisp, would be the first for which it is available.)

NOTE: I am not talking traditional obfusication of cryptographic programs, but cryptographic obfusication techniques.

This is really an ongoing area of research in the cryptographic community. So, no, I don't think anything of the sort is available in any programming languages. The DARPA SAFEWARE program suggests that a lot of research money is being put into the area and will give you a feel for some of the topic areas that the community is working on.

Matt Green's post you linked to provides a lot of good background material, but being a year old is outdated somewhat.

A recent survey paper goes over the current state, open problems, etc.

Here are some relevant quotes on the state of the technology:

Scope

  Learnable programs, i.e. the source code of which can be reconstructed by just executing it on different
  inputs, are clearly not interesting for obfuscation, although, most of the interesting programs are not learnable
  and the range of potential applications is extremely wide.

Efficiency

  The most complex function that they (Apon et al., in Implementing Cryptographic Program Obfuscation) obfuscated was a 16-bit point function containing 15 and gates. The process took 9 hours and resulted in an obfuscated program of 31.1 GB size, the evaluation of which on a single input takes around 3.3 hours on a machine with 32 cores and 244 GB RAM.

Dan Bernstein, Andreas Hülsing, Tanja Lange and Ruben Niederhagen broke Apon et al.'s scheme in 19 min on a cluster of 21 PCs. Section 3 of their paper contains some (partially quite obvious) optimizations to get a speed-up of about 50 for running the obfuscated program.

I'm making this a community wiki post so that others can updated it more easily as new results come out. This is a rapidly changing field in cryptography.


Dan Boneh's Cryptography lecture - problem with 802.11b I am going through Dan Boneh's Cyprography lectures on Coursera.

In Lecture 6
https://class.coursera.org/crypto-010/lecture/6

At 7:30 minutes, he discusses the problems with 802.11b design.
I understand his critique. However, he then moves on to what would be better design at 12:55 minutes.

He says that they could use a PRG to generate a very long key from the key and then use segments of the PRG(K) to encrypt each frame.

Even if you generate a very long PRG(K), considering the amount of traffic exchanged, wouldn't key still get repeated every few hours or so - i.e. you come to the end of the PRG(K), you have to start reusing first segment of PRG(K) again - which will lead to the key reuse problem. So what am I missing here?

...wouldn't key still get repeated every few hours or so - i.e. you come to the end of the PRG(K)...

This is where you are mistaken. Modern cryptographic PRGs simply do no repeat within any conceivable time frame. That is, starting from a seed, a well-constructed PRG (and this is true even when they are not so well constructed, like RC4) will simply never "come to an end" within our life time. You will have to run it for such a long time that the universe will probably have grown dark before you see it cycling back. Hence, for all practical purposes, cryptographic PRGs never repeat.

However, as noted in the video, this only holds true starting from some initial seed which is held fixed throughout the process. Note that the problem with WEP was that they reused the input (i.e. the seed) to the PRG, it was not because the output cycled around! Once you reuse the seed to a PRG then you will of course see the same output stream.


What is shared-input for Multi Party Computation? I heard shared input.
For example, original values $x,y \in M$ are divided into pairs of shares $(x_1,x_2)$ and $(y_1, y_2)$ such that $x_1 + x_2 = x \text{ and } y_1 + y_2 = y$.
Each share is distributed to two parties $P_1$ (who obtains $x_1$ and $y_1$) and $P_2$ (who obtains $x_2$ and $y_2$).

When $M = \mathbb{Z}_2$, addition is just XOR computation.

With additive shared input, can any computations be evaluated??

If so, what is the method used for the evaluation??

Is garbled circuit applicable to this scenario??

With additive shared input, can any computations be evaluated??
If so, what is the method used for the evaluation??
Is garbled circuit applicable to this scenario??

Yes, any computation can be evaluated. This is achieved by representing the functionality to be computed as an arithmetic circuit (not a garbled circuit) that consists of addition and multiplication gates. The addition gate can be evaluated by the parties locally because the shares are additively homomorphic. The multiplication gates can be evaluated by the parties interactively.
If you want to know more about it, there is a book: Secure Multiparty Computation and Secret Sharing, by Ronald Cramer, Ivan Damgård, and Jesper Buus Nielsen.
There are also some relevant papers if you are interested:
Ronald Cramer, Ivan Damgård, Ueli M. Maurer:
General Secure Multi-party Computation from any Linear Secret-Sharing Scheme. EUROCRYPT 2000: 316-334
Dan Bogdanov, Sven Laur, Jan Willemson:
Sharemind: A Framework for Fast Privacy-Preserving Computations. ESORICS 2008: 192-206
Ivan Damgård, Valerio Pastro, Nigel P. Smart, Sarah Zakarias:
Multiparty Computation from Somewhat Homomorphic Encryption. CRYPTO 2012: 643-662


W-OTS+ one-wayness property I am reading the "W-OTS⁺ – Shorter Signatures for Hash-Based Signature Schemes," by Andreas Hülsing, and I am stuck in understanding the success probability of an adversary, $\mathcal A$, against the one-wayness function of, $\mathcal F_n$; equation #1, page 7,

\begin{align}
  \operatorname{Succ}^{\operatorname{ow}}_{\mathcal F_n}(A)
    = \Pr [&k \stackrel$\leftarrow \mathcal K_n;\;
            x \stackrel$\leftarrow \{0,1\}^n,\,
            y \leftarrow f_k(x);\; \\
           &x' \stackrel$\leftarrow \mathcal A(k, y)
            : y = f_k(x')]
\end{align}

I read this as follows:
The success of a one-way function, $\mathcal F_n$, given a random key, $k$, from the space $\mathcal K_n$, and random $x$ such that $f_k(x) = y$ is …
I don't know how to read the rest of the equation and I don't know what is the probability here?

Inside the probability brackets, everything on one side of the colon describes the distributions of the variables used to define an event on the other side. In the case you described, the success probability of $A$ is the probability that $y=f_k(x')$ (which is the event) happens for $k,x',y$ sampled/generated from the left-side operations, i.e., sampling a random key $k$ and a random $x$, then computing the output $y=f_k(x)$, and finally giving $k,y$ to the adversary $A$ and getting its output. In English, that means the adversary $A$ wins if and only if it can find a preimage of $f_k(x)$ for random $k,x$, where $k$ is known to $A$.


What adequate tools are available for estimating entropy? This question seems to touch on the apparent fact that NIST SP 800-90B is not suitable for estimating entropy produced by sources that are not uniform, despite being IID or non-IID.  It also seems that most phenomena for producing entropy are not uniform.  If that's indeed right, then naturally one wonders what adequate tools are available for estimating entropy?
Clarification.  The question is asking for tools like NIST SP 800-90B.  What programs are out there that are ready to use, hopefully with a publication to introduce it?  It seems only NIST SP 800-90B is available.

I'm assuming that you're referring to physical entropy sources, rather than Shakespeare and such.
You can go the compressive approach using strong archivers as discussed elsewhere. However, that will always leave you with a feeling of whether it's accurate enough? And this is an uncommon approach though it works for me.
The standard way, is to simply calculate $H_{\infty}$ based on the most probable value in your data set. Autocorrelation? Remove it. So ironically, your tool is a pseudo random number generator. And ent.
There is the concept of $(\epsilon, \tau)$ entropy per unit time, where $\epsilon$ is the sampling resolution and $\tau$ is the temporal sample lag.  And it goes like this:-

Sample source at $(\epsilon, \tau^{-1})$ per second. Eg. 4 bits @ 10 kSaS.
Perform IID test on sample using permutation testing.
If sample = IID, run ent -c and get ${Pr_{max}}$.
$H_{\infty} = -log_2(Pr_{max})$. Done.
If sample $\ne$ IID, reduce $\epsilon$ or increase $\tau$. Eg. 3 bits @ 5 kSaS.
Goto 1.

Permutation testing is what's done by NIST's 90B ea_iid. Or roll your own. Or use mine. That link has a lot of NIST detail. The reason the bounds are tighter is that you set them yourself as to what constitutes IIDness.  NIST uses p=0.01 and my slow test uses p=0.1 rather than relying on the perceived strength of your compressor.


Signature verifying against multiple certified public keys? I'm wondering if and how the current public key certificate infrastructure is guarded against the following scenario:

Honest Alice obtains Eve's public key certificate Certe, made by honest CA Carol; checks it the usual way; and assumes she knows Eve's public kev Pube.
Alice generates a message M mentioning obligation by Eve, sends it towards Eve, and receives apparently from Eve a signature S; Alice verifies that M, S, and Pube match.
Later, Eve denies having approved M or produced S; suggests that S must be by Frida; and as argument asserts that S also checks against Frida's certified public key.
Alice obtain Frida's public key certificate Certf, made by honest CA Carl; checks it the usual way; and assumes she knows Frida's public key Pubf.
Alice verifies that indeed M, S, and Pubf match!
Pube and Pubf are different, and Alice finds them unremarkable, as well as Certe and Certf; these carry a certification date earlier than the generation of M by Alice; there was no certificate revocation.
Alice obtains other (M, S) pairs attributed to Eve and Frida; they verify against only one of Pube or Pubf, as intended.

Unless I err, that scenario could happen with 2048-bit RSA, usual e=F4=65537, and RSASSA-PSS as signature, assuming Eve and Frida are crooks operating as follows:

Eve and Frida jointly choose two distinct small close primes, say re=101 and rf=103; and jointly generate their respective RSA modulus Ne and Nf with Ne=re⋅p⋅q, Nf=rf⋅p⋅q, 22047<Ne<Nf<22048, p and q large random primes with gcd(p-1,65537)=1=gcd(q-1,65537).
Eve computes her private exponent de=e-1 mod LCM(re-1,p-1,q-1) matching her public key Pube=(Ne,e) with e=65537. Frida does similarly for df matching her public key Pubf=(Nf,e).
Eve and Frida obtain their certificate the normal way; the only caveat is that they avoid CAs that check for small factors in public modulus.
When Eve generates a signature using RSASSA-PSS, she proceeds normally, except that she additionally checks the signature against Pubf: about one signature among rf pass this test! Eve iterates signing until finding a signature for M matching her intention to later attribute the signature to Frida, or not. Frida does similarly.

Update: I asked again there, where questions about policies belong.

From a cryptography perspective, this works as advertised; Eve and Frita can generate signature keys where a nontrivial fraction of signatures for one key will validate with the other.

That said:

It is trivial to detect this, if anyone looks.  If we suspect that Eve and Frita are colluding (which we may, if someone demonstrates a signature that validates with both public keys), then a simple computation of $\text{gcd}( N_e, N_f )$ will reveal it.  Alternatively, if someone just checks either $N_e$ or $N_f$ for small factors, that'd show that something nonkosher is going on.  While I don't believe most CA's routinely check the public keys submitted to them for small factors, there might be some that do (and it certainly would not be expensive, compared to the other operations CA's must do).
It's not clear if this is actually an attack; $S$ is a valid signature for $M$ under $Pub_e$, and Eve cannot argue that it's not.  Eve's argument of 'maybe Frita did it' doesn't address the question of 'how did Frita forge a signature of Eve's key'.
Also, as for your question of 'maybe real signatures embed a public key identifier', no, they do not.


Is RSA-OAEP deprecated? I need asymmetric pub/private keypair encryption in JavaScript. Web browsers support RSA-OAEP, which works exactly as I need. But there is a table which lists supported algorithms for web crypto at https://diafygi.github.io/webcrypto-examples/ ... and RSA-OAEP is marked using red color (Discouraged, only use for backwards compatibility).

Is there any problem with RSA-OAEP? Should it be replaced by different algos?
Or do you think that the person who wrote the table was wrong by marking RSA-OAEP red? Thank you

RSA in general is often considered to be "discouraged" for new projects. For quite some years, the rallying cry has been "switch to elliptic curves", but nowadays there are calls for going straight for so-called "post-quantum" schemes.
RSA benefits from having survived a lot of public scrutiny (arguably, integer factorization is a problem that has been studied for three millennia at least), and while there has been substantial progress in cryptanalysis, 2048-bit RSA key are likely to remain secure for a long time. There are also good and bad ways to use RSA for asymmetric encryption, but RSA-OAEP is about as good as you can get with RSA, so that's fine.
Elliptic curves offer better performance (on the decryption side) and are more fashionable. What this means is that before being actually broken, RSA may become disused, meaning that you will get interoperability issues, and implementations will be poorly maintained at some point. In my view, none of this is critical.
Quantum computers eat RSA keys for breakfast; however, they also munge through elliptic curves at lunch time, so that's not a good argument for switching to curves. It's a fortunate thing that quantum computers don't really exist yet (and whether they will exist at some point is an open question). "Post-quantum" schemes are algorithms that appear to resist quantum computers (specifically, these are algorithms for which no efficient quantum-solving attack is known – which does not mean that such attacks don't exist!). There is no real post-quantum drop-in replacement for classic algorithms yet (there are good candidates, but a lot of standardization and implementation deployment is still needed).


If I compute the SHA-1 of all possible 40 digits hexadecimal strings, will I get all possible sha1 hashes? Wikipedia says sha1 produces a 160-bit (20-byte) hash value. So if I compute the SHA-1 of all possible SHA-1 values, which as far as I understand is at current time impossible both to calculate and store, will I get all possible SHA-1 values? Would I be able to collide anything?

No. And it's probably a good thing that that's not the case.

All cryptographic hashes (inc. SHA-1) are designed to have no obvious correlation between their input and output. If there is too much of a correlation, then they are considered broken.

If each string of 160 bits produced a different output, that would be a correlation.

That would also mean that all cryptographically secure pseudorandom number generators would have a small bias.

[It's very possible that there are some outputs that cannot be produced by SHA-1].


Difference between hash function In some paper, the terms "cryptographic hash function" and "deterministic hash function" would appear?
I'm wondering what's their difference, and are there some other types of hash functions?
Like the cryptonote whitepaper in 4.2.1

A hash function is a function taking an arbitrary length string as the input, and output a fixed length string. All hash functions are deterministic (correct me if I am wrong). Generally, a good hash function should map the inputs to its output range as uniformly as possible. Cryptographic hash functions have more requirements for security. The three most commonly used security properties are:

One-way: Given a hash value $h$ it should be difficult to find any message $m$ such that $h = hash(m)$.
weak collision resistance: Given an input $m_1$, it should be difficult to find a different input $m_2$ such that $hash(m_1) = hash(m_2)$.
collision resistance: It should be difficult to find two different messages $m_1$ and $m_2$ such that $hash(m_1) = hash(m_2)$.


Is it a bad idea to make multiple SHA-* with the same header? I'm trying to figure out a simple way to verify ownership over a short period of time (typically 8 - 24h), to be used in a mobile application.

One of the ideas I came up with is to hash the following concatenated sequence:

user pincode + user unique ID + payload
where
    pincode   is a 6 digit passcode, provided by user
    unique ID is a GUID identifying the device, generated once
    payload   is a rather long JSON payload, different each time

Provided I'm using an algorithm like SHA-512 or similar, what's the risk of using always the same header (pincode + ID) for multiple hashes?

Is it easier for an attacker to figure out a header if used for multiple hashes?

Optionally, do you think this would be a valid ownership verification, knowing an attacker could potentially replicate a payload.

The standard assumption in cryptography is that the adversary knows

methods used
what's physically transmitted (here, I guess payload and the SHA-512 hash);
any data other than the key(s)

Here pincode is clearly a key, and the default assumption would be that unique ID is not. With this hypothesis, a single hash is enough to allow an adversary to find pincode by enumeration, then break the system. Thus multiple hashes are not worrying, but the basic principle is insecure.

Additionally, SHA-512 is vulnerable to a length-extension attack, and with a few hypothesis about what's admissible as payload, that might allow computing the hash for an extension of the payload, without knowledge of unique ID (or even the original payload; only its length is required).

If some other hypothesis applies, please edit the question.


Find first two blocks of plaintext given a final plaintext block, the IV and ciphertext for CBC? I have the following:

complete ciphertext;
iv;
last block of plaintext including the padding which is 04040404.

The encryption was made using AES-CBC-256. I can find the intermediate block by XOR-ing C2 with P3
I cannot use padding oracle because there is no server to validate padding. I didn't find any help about plaintext attack for 14 rounds, only for 4.
Is there any way to find the rest of plaintext (P1, P2) or the key for (C2 ⊕ P3, C3)?

Let's consider what you know: you have the last block, the IV, and the entire ciphertext. What you don't know is the key or the plaintext. Since CBC-mode encryption uses the IV directly only with the first block you must find the first block, before the IV even becomes useful for your attack. Since the CBC mode uses AES(plaintext[i] XOR ciphertext[i-1], key) and you know the plaintext of the last block, as well as the ciphertext of the previous block you end up with a generic known-plaintext case. So what can you do?

Padding oracle attack:

You already said there's no server for a padding oracle attack so that's not possible

Find the key using a known-plaintext attack on AES itself:

AES is designed to be secure against known-plaintext attacks, so there's not really much you can do. Unless, of course, you know something that the rest of the cryptography community doesn't...

Knowing the IV won't help since the IV only applies to the first block.
You know AES(something XOR iv, key) = ciphertext[0] but since you don't know the plaintext or the key it might as well be AES(something, key) = ciphertext[0]. Knowing what (something) is won't help either since you'll simply end up with another known-plaintext scenario, so even if you got the first block of plaintext as well the key is unobtainable - that's the point of encryption, and a padding oracle is an issue with the mode of operation, not the algorithm itself.
I'm sorry to say, you're SOL.


Security when using same salt for different passwords, compared to using different salts? I have this question I am struggling about:

For example, someone suggested improving UNIX authentication by defining 3 different passwords for a user that are stored in the shadow file. All three passwords are stored with the same salt value.

When a user wants to authenticate to some system, he must provide in the $i$ attempt to login, the $i$ mod 3  password. For example, in the first attempt he will provide the first password, in the second and fifth attempt he will provide the second password. Is such alteration to UNIX system increases security or not? And what happens when all passwords are stored with different salt value?

For example, someone suggested improving UNIX authentication by defining 3 different passwords for a user that are stored in the shadow file. All three passwords are stored with the same salt value. When a user wants to authenticate to some system, he must provide in the i attempt to login, the i mod 3 password. For example, in the first attempt he will provide the first password, in the second and fifth attempt he will provide the second password. Is such alteration to UNIX system increases security or not?

I cannot see how it increases security. As long as you don't limit the amount of attempts the attack surface only increases.

  what happens when all passwords are stored with different salt value?

You cannot see if one of the three passwords is identical to one of the other three. The reason to choose an identical salt is presumably to make sure that each password is different from each other.

Note that the passwords could still be very similar. The only way to check that is to compare the three passwords and for that you need all passwords at the same time.

It would also decrease attack speed by a factor of three (as an attacker cannot check a candidate password against all three hashes). This is of course assuming that the attacker obtained the hashes in the first place or that the password validation is sufficiently fast.


Is it possible to actually verify a “sponge function” security claim? When using a “sponge function” to create a cryptographic hash, we can look at the flat sponge claim, which flattens the claimed success probabilities of all attacks using a single parameter: the claimed capacity cclaim

Is there any way to actually verify the probability of that claim - in this case: potential probability of collisions of the “sponge function”-based cryptographic hash - and what would such a proof formula/calculation look like?

After spending more than two weeks reading well over 750 pages while checking the following (PDF) documents…

Sponge Functions
Cryptographic sponge functions
Security Analysis of Extended Sponge Functions
Cryptographic Hash Functions: Recent Design Trends and
Security Notions
On the Implementation Aspects of Sponge-based
Authenticated Encryption for Pervasive Devices
On the security of the keyed sponge construction
Keccak and the SHA-3 Standardization
Computer Science and Its Applications: Csa 2012

…it turns out that the probability of the claim can only be "proven" theoretically. In other words: currently, there is no way to actually and/or practically verify the probability of the claim.

The current status quo states that collisions are theoretically proven to be very unlikely in a cryptographic sense. I guess that — as with all cryptographic theories — only time can tell if that actually provides a problem or not.

But, getting back to my question: no, it can't actually be verified currently.

I don't expect this to change anytime soon either, as the theoretical proof that collisions are very unlikely in a cryptographic sense, seems to be strong enough to regard sponge functions as (let's just call it) "secure". In fact, if you check the linked documents, you will find ample information on how to replicate the theoretical proofs in relation to collision probabilities using sponge functions under a multitude of conditions. As far as I checked, cross-checked, and even practically used those formulas to verify things myself, I got convinced that collisions are indeed very (very) unlikely.

I hope you don't mind that I'm sparing you a copy-and-paste job of more than a dozen of pages full of math code. Those who want to dive in deeper, can fetch the multitude of related formulas and a truckload of additional, interesting information from the linked documents I listed above.