Why does this SHA-1 relation hold? In De Canniere & Rechberger's 2008 paper "Preimages for Reduced SHA-0 and SHA-1", the following statement appears on page 6:

  Suppose that we restrict ourselves to the first $j$ + 1 bits of each expanded
  message word $W_i$ (denoted by $W^{j...0}_i$), and that we keep all state bits constant except for those at bit position $j$ + 2 (referred to as $a^{j+2}_i$). In this case, we can derive a simple relation (by collecting all constant parts into a $j$ + 1-bit word $C^{j...0}_i$ and a 1-bit variable $c^j_i$), which holds as long as $0 \leq j < 25$:
  $$
W^{j...0}_i = C^{j...0}_i − (f(c^j_i , a^{j+2}_{i−2} , a^{j+2}_{i−3}) \ll j) − (a^{j+2}_{i−4} \ll j).
$$

I've been trying to understand why this relation holds for many hours, and still can't figure out how it can be true.

The $f$ function takes three inputs: $a_{i-1}^{j}$, $a_{i-2}^{j+2}$, and $a_{i-3}^{j+2}$.  Therefore, $c_i^j = a_{i-1}^{j}$, but the text indicates that $c_i^j = a_{i}^{j+2}$.  How is this possible?
What has happened to the $A_{i+1}$ and $A_i$ terms?  Have they somehow been incorporated into $C_i^{j..0}$ by the text "collecting all constant parts"?

I'd be grateful for anyone who can point me in the direction of source code that implements a preimage attack like this, but if no such thing exists, then I'll be happy for an explanation of the above, and I'll try to work out the rest of the details myself.

Edit: is there a typo?  If so, what is the correct relation?  I ask because I've just noticed that on the previous page, the error word relation is definitely incorrect.  It should be

$$
E_i = W_i \oplus ((W_{i+3} \oplus W_{i+8} \oplus W_{i+14} \oplus W_{i+16}) \ggg s)
$$

First let's write the original relation that they are deriving this one from:

$$
W_i = A_{i+1} - (A_i \lll 5) - f(A_{i-1}, A_{i-2} \ggg 2, A_{i-3} \ggg 2) - (A_{i-4} \ggg 2) - K_i
$$

So, if everything in the state bits are fixed except the ones in position $j+2$, all the operations on the fixed bits could be gathered together and we can simplify the relation to the variable ones. Now, let's derive the new relation.

For now, let's put the $c_i^j$ aside and write the term related to $f$. Then the variables in $A_{i-2}$ and $A_{i-3}$ (which are $a_{i-2}^{j+2}$ and $a_{i-3}^{j+2}$) are mixing with the fixed value of $A_{i-1}$ (which is $a_{i-1}^j$), and the rest is fixed. Thus the term $f(a_{i-1}^j, a_{i-2}^{j+2}, a_{i-3}^{j+2})$, and the result is in position $j$, so the $\ll j$ is added. We can add the term $(a_{i-4}^{j+2} \ll j)$ (corresponding to the last term in original relation).

The remaining terms can be collected in the $C_i^{j..0}$. Although both of the $A_{i+1}$ and $A_i$ have variable bits at position $j+2$, they do not contribute to the value of bit positions $j..0$ of $W$. The only way they get involved is that by left rotation of ($A_i \lll 5$), the variable bit gets rotated and falls in $j..0$. It happens if $(j+2) + 5 > 31$, but they restrict the $j$ to $0\le j \lt 25$, so it doesn't happen.

And about the $E_i$ relations. Your relation is not quite right.
We know that:
$$
W_{i+16} = (W_{i+13} \oplus W_{i+8} \oplus W_{i+2} \oplus W_i) \lll s
$$
Therefore:
$$
W_{i+16} \ggg s = W_{i+13} \oplus W_{i+8} \oplus W_{i+2} \oplus W_i
$$
and in other words:
$$
W_{i+13} \oplus W_{i+8} \oplus W_{i+2} \oplus W_i \oplus (W_{i+16} \ggg s) = 0
$$
if there is no error in calculating $W_i$s.
So they define the error bit vectors as:
$$
E_i = W_{i+13} \oplus W_{i+8} \oplus W_{i+2} \oplus W_i \oplus (W_{i+16} \ggg s)
$$
with the goal of making all $E_i$ equal to zero.


How can a system be non-deterministic? Newbie here, so forgive me if this is a stupid question.
In math class we learned about RSA encryption (as a practical application of what we learned about the Euler phi function and Fermats little theorem), and I wondered that since the same input always yields the same output, if eve had a couple of guesses for what the message is (for instance a yes or a no), she could try encoding them herself and compare that to the ciphertext. I googled how to get around this, and I gathered that a process can be non-deterministic, meaning it yields different results if done repeatedly. However, when I looked into how this was possible, I never really understood the explanations, they got really complicated really fast.

So what I'm asking is, can anyone explain fairly simply (high-school level math) how a ciphertext can be generated with an element of randomness, but still be decipherable. Surely the receiver can't easily undo those random changes, if the same message could come in in many different forms?

As a high level concept, nondetermistic encryption is where the encryption function takes three inputs, the key $k$, the plaintext $P$ and a random value $R$, generating a ciphertext $C = E_k(P, R)$; the idea is that a) two different random values $R$ gives completely different ciphertexts $C$, even if the plaintexts where the same (or related), and b) no matter what value $R$ we picked, decryption still works, that is, $P = D_k( C )$ (where, in an assymetric system, $k$ may be the private key).

All this should have been covered in your math class; your question is "how does this work in practice?"  Since you mentioned RSA, I'll give you a simple version of it:

RSA has a relatively large plaintext size; for example, 2048 bits.  So, to encrypt a 256 bit plaintext $P_{256}$, what we do is select 1784 random bits $R_{1784}$, and generate an RSA block:

$$01 || R_{1784} || P_{256}$$

The initial byte is a fixed 01 value (so that the resulting plaintext will always be less than the modulus size); the resulting block is precisely 2048 bits long.  We can then give it to RSA, which converts it into a ciphertext.

$$(01 || R_{1784} || P_{256})^e \bmod N$$

We can see that:

Depending on what values we select for $R_{1784}$, the resulting ciphertext will look completely different
The decryptor can easily recover the original plaintext (by decrypting the ciphertext, and just looking at the last 256 bits).

Now, it turns out simple RSA padding schemes like this tend to have issues with chosen ciphertext attacks, and so in practice, we generally use more sophisticated ways of padding the message (that is, don't use the simple scheme I mentioned directly).  However, it should clarify how deterministic encryption can work in general.


Implement the joint-feldman DKG algorithm I am looking for a work implementation of joint-feldman DKG or at least some library that can help me in the implementation
Anyone can help me?

You can look up at the Kyber library, in the package share, there is a the Feldman version as well as the Rabin version.
You can later on use this to make distributed schnorr signatures or TBLS signatures. You can lookup  these types in the sign package.

PS: I'm one of the authors of these libraries. Happy to help if you have any questions :)


Is secp256r1 more secure than secp256k1? Curves secp256r1 and secp256k1 are both examples of two elliptic curves used in various asymmetric cryptography.

Googling for these shows most of the top results are Bitcoin related. I've heard the claim that…

  Satoshi picked non-standard crypto which conventional wisdom says will be cracked in 5-10 years.

There is this discussion on bitcointalk with various opinions to both sides of the argument (also check out this article). I would like to take it away from Bitcoin and into the general cryptographic question: is secp256r1 indeed more secure in some sense than secp256k1?

The main difference is that secp256k1 is a Koblitz curve, while secp256r1 is not. Koblitz curves are known to be a few bits weaker than other curves, but since we are talking about 256-bit curves, neither is broken in "5-10 years" unless there's a breakthrough.

The other difference is how the parameters have been chosen. In secp256r1 they are supposedly from random numbers, however, it is impossible to prove that's really the case. See e.g. these slides from Bernstein and Lange for an easily understandable treatment.

The Koblitz curve, on the other hand, has had its parameters chosen relatively rigidly. The post runeks linked in the comments has an explanation for why they were chosen.

So rather than saying one is more secure, I would say that the risks are different. If neither curve has backdoors or accidental weaknesses, both are secure. The few extra bits of security secp256r1 has won't matter unless you happen to own e.g. a moderately sized quantum computer that can just manage one but not the other. It would have been easier to backdoor the secp256r1 curve, but on the other hand, Koblitz curves as a class could be completely weak in some way not currently known.

I.e. which to prefer is somewhat subjective. If you don't like Koblitz curves but are afraid secp256r1 is backdoored, there's always the option to use some other curve designed according to criteria you like. (Though you cannot, of course, change what BTC uses.)


Why can't AES-GCM be used in IKEv1 phase 1? I was configuring a VPN on a firewall (fortigate) and realized that I could use AES-GCM for encryption in the IKEv1 phase 2 but not in the phase 1 and I was wondering why knowing that in IKEv2 we could use it in both phases. I have already checked the RFC articles but there was no explanation. Is it only because AES-GCM came after IKEv1 or something like that?

With IKEv2 all payloads are generally sent in a single Encrypted Payload (SK) whose data is both encrypted and integrity protected/authentication (that protection covers the complete message, including the header and optional unencrypted payloads). That works quite nicely with modern AEAD algorithms like AES-GCM, the additional authenticated data (AAD) are the headers (IKE and SK) and any unencrypted payloads, the resulting authentication tag is what's sent as Integrity Checksum Data in the Encrypted payload.

On the other hand, IKEv1/ISAKMP handles encryption and integrity protection of IKE messages quite differently. For integrity protection of Phase 2 messages (Quick Mode/Informational), the message ID and the payloads are hashed (a PRF is used actually) and the result is added to the message in an additional Hash payload (during Main and Aggressive Mode it's similar but slightly differs based on the authentication method). The complete message, including that Hash payload, is then encrypted. So that does not really match with how AES-GCM works, unless the protocol would have been changed significantly (like getting rid of the redundant Hash payloads and handling integrity protection only via combined-mode cipher). But I guess there really was no point in doing that for an already obsolete protocol.

After writing this answer, I noticed that this is actually described in the introduction to RFC 5282.


what are the most common stream ciphers algorithms? say that we have an unknown stream cipher which output bytes and which have more than 10 years of existence. What can be the most probable algorithms if we consider the most 'populars' stream cipher algorithms?

In order to find the most 'popular' stream ciphers, where can I find some statistics about the most implemented stream ciphers since 2000?

By far, RC4 is the most popular stream cipher that's been around for 10+ years.  ChaCha20 has just turned 10, and is now becoming popular, but was essentially unheard of 10 years ago.


What Are Advantages and Disadvantages of SHA-256? I'm a newbie to Cryptography. I'm learning about SHA-256 hash function now and I wish to have an overall look on it. What are its advantages and disadvantages comparing to other hash functions, like X11, Scrypt,...?

All three of the hashes you list serve very different purposes. Asking what their relative advantages and disadvantages ar is like asking about the same about a screwdriver, hammer, and drill.

SHA-2 is a cryptographic hash function, and is typically a building block for other cryptographic constructs. In satisfying the requirements of cryptographic hash, it's a one-way function that is deterministic, fast to compute, resistant to pre-image and second-preimage attacks, and is collision resistant.

scrypt is a password-based key derivation function. It's used to turn a low-entropy password into a cryptographic key or verifier with effectively higher entropy by being intentionally slow to compute. It's tunable to require larger amounts of CPU and/or memory as technology advances, making hardware dedicated to computing it en masse expensive.

X11 from what I can gather is a proof-of-work function for blockchain-based currencies. It appears to be little more than inelegantly mashing of a bunch of unrelated hash functions together in the naïve hope that that will somehow make it ASIC-resistant and more secure. I don't think it's received any analytic attention from cryptographers.


A simple client/server authentication protocol Some days ago I asked for a help to find and correct the problems of an authentication protocol. I closed the post because I was convinced I can correct it but, unfortunately I'm having some troubles. The "old" post is the following:I'm dealing with this problem: establish if the following protocol is 'secure' and, if it isn't, modify it to make it secure.

I will use the subsequent notation to describe the protocol:

$N$ is a nonce
$X \longrightarrow Y: \space   M$
to indicate that $X$ sends $M$ to $Y$
$K_{XY}$ to indicate the symmetric key shared by $X$ and $Y$
and $K_{XY}(M)$  to indicate that the message $M$ has been encrypted with the symmetric key $K_{XY}$.

The protocol allows a client $C$ to authenticate itself to a server $S$ using an authentication service $A$.

$C \longrightarrow S:\space  C$
$S \longrightarrow C:\space   N$
$C \longrightarrow S:\space   K_{CA}(N)$
$S \longrightarrow A:\space   K_{SA}(C, K_{CA}(N))$
$A \longrightarrow S:\space   K_{SA}(N)$

$S$ authenticates $C$ if and only if the nonce received $N$, got by the authentication service ($A$), is equal to the nonce sent to $C$.

Assuming the communication channel is not secure, an attacker (called Eve) can impersonate $C$ simply sending the message "C" and $K_{CA}(N)$ whenever $C$ tries to authenticate himself.

How to avoid impersonation and offline nonce-guessing in this case? Any suggestion? I don't want the answer to the problem, just a few tips to continue on my own. At the end, I want to say that I know how to make the protocol secure but my answer consists in completely change the protocol described above, and so I think my answer is not the most appropriate. Recently I thought to modify the protocol as follows:
$C \longrightarrow S:\space  C$
$S \longrightarrow C:\space   K_{SA}(N)$
$C \longrightarrow S:\space   K_{CA}(K_{SA}(N))$
$S \longrightarrow A:\space   K_{SA}(C, K_{CA}(K_{SA}(N)))$
$A \longrightarrow S:\space   K_{SA}(N)$ Can it work now?

If Eve knows $C, \space N, \space K_{CA}(N)$ then she is able to impersonate $C$ just by following the protocol you described above.

If she just knows $K_{CA}(N)$ for a single $N$ then the effectiveness of the attack depends on the set wherein $N$ is picked.

But as you are supposing that the communication channel is not secure, an attacker could spy several authentication session to get a sufficient number of pairs $(N, K_{CA}(N))$ to successfully attack with high probability.


Working on subgroup of $\mathbb{Z}^*_p$ in practice It is said that, given a group $\mathbb{Z}^*_p$, we can always have a subgroup whose order is prime. To this end, for a safe prime $p=2q+1$, compute $x_i^2 \bmod p$ for all $x_i \in \mathbb{Z}^*_p$.

Questions:

Do we need to only work on the values that exist in this subgroup (whose order is prime)?
What if we need some values that do not exist in the subgroup, but they are in $\mathbb{Z}^*_p$?
To work on the elements of subgroup do we do $\bmod q$?

Because this way limits our choice of elements and we cannot work on any arbitrary values.

When using any cryptosystem that relies on the Decisional Diffie-Hellman assumption (e.g., ElGamal, ECIES, Diffie-Hellman key exchange, etc.) then you need a group of prime order. Note that $\mathbb Z_p^*$ where $p$ is prime has order $p-1$. However, if $p=rq+1$ where $q$ is also a large prime, then you have a subgroup of $\mathbb Z_p^*$ of order $q$. If you take $r=2$, then these are the so-called safe primes (once it was thought that for RSA it's best to use these types of primes, and that's why they are called "safe"; however, today, it is accepted that it's best to just choose random primes for RSA). In order to get a subgroup of order $q$, indeed you just take the squares.

Answering your specific questions:

For the cryptosystems that I mentioned above, YES you MUST work in the subgroup.
You need to map any value that you need into the subgroup. You can map any value between 1 and q-1 by just squaring it.
No, you do not do $\bmod q$ on the elements (you do $\bmod q$ when working on values in the exponent).

I recommend that you take a book that gives the number-theory background necessary for crypto...


How to create and send a symmetric key using GPG I want to communicate with a friend (he lives in another country so we can't exchange fingerprints or keys physically, I could post him a USB disk but I'm sure I can do it through the web).

I'm pretty familiar with public key cryptography but this is the first time I've decided to use a symmetric approach. There are a few things I'm wondering:

Do I need to generate a special type of key for this, or can I just generate a 4096 bit RSA key pair with gpg --full-gen-key like I usually would?
Does it make a difference whether I use my private key or public key? Is there any real difference between these two keys. meaning if I encrypted a file using my private key would it be the same quality as if I had used the public key?
So in addition to the password for the message I sent him, my friend needs a copy of the key I use to decrypt it so we then have a shared key. Would it be a good idea to send both keys (the private and public) so when a third party encrypts something with our public key, we can both decrypt it. Have I got the right idea there, or would that introduce any security risks to this symmetric communication system?

This is just a practice exercise, we're both interested in cryptography and want to make our online communications 100% encrypted and secure, in order to develop a practical understanding of cryptography, steganography and security. This is step 1, we will send exchange email addresses and secure IM service account details. And from there we can discuss how to step things up and gradually reach our goal of being 100% encrypted and secure. I would greatly appreciate any tips, insights, methods, pointing out flaws in my methods and things I haven't thought about yet.

One challenge which is a fun one is getting the key to him. I'm not gonna complicate it too heavily, but heres what I'm thinking:

Compressing the key pair into a password protected zip archive, and embedding it into a PDF file or PNG, or whatever file type won't seem weird with the extra size.

A more secure way would be to post a USB key to him of course, but we wanna do this entirely via the web for now.

First of all let me answer your specific points:

No, generating a symmetric RSA key makes no sense. RSA is not symmetric. It is a public key algorithm.
There is a HUGE difference between the public and private key. The public one can only be used to encrypt and the private one is needed for decryption.
Usually in a public key setting you keep the private key private and don't send it anywhere.

I'm afraid I have to disagree with your statement that you are pretty familiar with public key cryptography. You should probably read up on the difference between symmetric crypto and public key crypto again.

Even if you use public key crypto, you need to somehow verify that the person whose public key you are using is actually the person you want to reach. Otherwise anybody could give you their public key and MitM your connection. If you know somebody only over the internet how do you know who they are anyway?


Is XSalsa20-Poly1305-SIV a reasonable choice for nonce-misuse-resistant authenticated encryption? Consider XSalsa20-Poly1305-SIV.  This is obtained by:

computing a MAC $t_{secret}$ of the plaintext from the key and nonce, as in ChaCha20-Poly1305 except that the plaintext, not the ciphertext, is MAC'd.
compute $t = F(K,t_{secret})$, where F is the ChaCha20 core (or any other PRF).
use $t$ as the auth tag and as part of the XSalsa20 nonce.

Questions:

Is this secure?
Is this provably secure, assuming that the ChaCha20 and Salsa20 cores are strong PRFs?

This can be a secure construction, if by MAC you mean universal hash family, like Poly1305.  Call this hash family $H_r$ and the short pseudorandom function family $F_k$.  Rough justification for why this is secure:

The function $m \mapsto F_k(H_r(m))$ is a long-input, short-output PRF.
A good PRF makes a good MAC.
A good PRF has birthday-bounded collision probability, so the probability of nonce reuse for the stream cipher is small.

In a bit more detail: Let $\varepsilon_F$ be a bound on the PRF-distinguisher advantage of any algorithm making $q$ queries against $F$, and let $\varepsilon_H$ be a bound on the collision probability $\Pr[H_r(x) = H_r(y)]$ of $H$ for any $x \ne y$ and uniform random $r$.

The PRF-distinguisher advantage for a $q$-query attack against $m \mapsto F_k(H_r(m))$ is bounded by $\varepsilon_F + \binom{q}{2} \varepsilon_H$ (proof).
For fixed-size keys, the collision probability $\varepsilon_H$ grows linearly with the maximum message length.  So this figures into the concrete numbers.
The probability of a synthetic nonce collision (i.e., a collision in $m \mapsto F_k(H_r(m))$) is higher than the probability of a collision in $H$, because either a collision in $H$ or a collision in $F$ means there's a nonce collision—whether this matters depends on how large the output of $F$ is, and in particular on the birthday bound for $F$ which may be much smaller than the collision probability of $H$.

There's some practical details to work out.

Here $q$ represents the number of messages that you are willing to send or receive in your application.  For example, if $\varepsilon \approx 2^{-100}$, the bound above means nothing unless your application's total bandwidth is limited to $q \lll 2^{50}$ messages.  (And you don't want to mess with collisions in $H$.)

Is the Poly1305 collision probability bound $\varepsilon_{\operatorname{Poly1305}} = 8\ell/2^{106}$ for $16\ell$-byte messages comfortable enough for trillions of megabyte-long messages?  Maybe it is, maybe it isn't—for now I leave it as an exercise for the reader to compute specific bounds for specific data volumes.  (See a similar table for AES-GCM.)

What should you choose for $F_k$?  If you're already using XSalsa20, the obvious choice is XSalsa20 truncated to 128 bits or similar.  Of course, you'll have to quantify the probability of a collision between the XSalsa20 nonce used for encryption and the XSalsa20 input from $H$.  But maybe you can do better than multiple the HSalsa20 invocations this would imply, each of which adds overhead to small packets.  Maybe you should use a 192-bit or 256-bit hash $H$, and a 192-bit authentication tag, so that the probability of a synthetic nonce collision is negligible even for extremely large volumes of data.


Custom crypto library in C I will be making (in the near future) an app that will contain some pretty heavy crypto. As it is possible that my app will be ported to different devices (initially it will be iOs only, but Mac, Android & maybe even Windows ports will eventually exist). The question is how to make the crypto library as portable as possible. I'm thinking about writing it as a C11 header & .c implementation. That way it would be easy to integrate on every platform ( I may use Androids NDK to access the C code from Java). As I understand, Visual C++ can use C headers and functions.  Then I will just write a wrapper class in the platforms default language (Objective-C 2.0 for iOs) that will access the cryptographic primitives from the C library...

Is this an ok design?
I will be using sleep() to make all operations last the same time (anti-timing attacks); does this work the same on all platforms? Should this be done in the wrapper rather than the C library?
Should I use open source implementations of the algorithms, or just write my own? (I would like all the code in the crypto library to be 100% C11)

BTW: I'm going to use some non-standard algorithms that most public libraries don't have (Serpent, TwoFish, ThreeFish, as a key derivation function I'm thinking about scrypt) ...

It's generally strongly recommended you use an existing library for your crypto, instead of trying to reimplement it.  One big advantage of a widely used existing library is that it's been improved over time to deal with new threats.  You may be aware of timing attacks as a current weakness, but these libraries have already solved those problems and many others, and fixed them.

OpenSSL is written in C, widely used and trusted, and could meet your needs.  Cryptlib is distributed under the Sleepycat license (sort of compatible with the GPL) and is also written in C, and has a paid support team.  GnuTLS is LGPL, if you really want GPL compatibility.


Non interactive Zero Knowledge Proof for Satisfiability of Pairing Product Equations In the paper "Simulation-Sound NIZK Proofs for a Practical Language and
Constant Size Group Signatures" from Groth, the section 6 describes a NIZK proof for pairing product equations.

I only know the basics in the domain of zero knowledge proofs and I saw some basic algorithm. What I would like to know is if there is a way to implement the prover and verifier algorithm ? By using some already existing implmentation like the Schnorr one or another one that I could adapt ?

In summary, I would like to know if there are ways to implement the algorithms shown in the paper. Or is it just a theoretical state at the moment?

I have read some part of above paper, definitely you can find implementations of such prover and verifier algorithms, even more complicated ones. For example, you can find implementations of prover and verifier in several zero-knowledge proofs in Libsnrak library.

By the way, you can also find implementation of Groth-Maller simulation-extractable zk-SNARK from Crypto 2017 in Libsnark that considers quite similar concept to the paper that you have mentioned.

I would also recommend to look at implementation of Pinocchio, a practical verifiable computation system, that has implementation of a prover and a verifier in a zero-knowledge SNARK that are particular type of none-interactive zero-knowledge proofs.


Constant time multiplication in GF(2^8) I am trying to implement AES in C; I would like to make it resistant to side-channel attacks but I can't implement the multiplication in constant time. My current code:
static uint8_t GF28_Mult (uint8_t Poly0, uint8_t Poly1) {
    uint8_t Result = 0;

    for (uint8_t Shift = 0; Shift < 8; Shift++) {
        if (Poly1 & 0x01)
            Result ^= Poly0;

        if (Poly0 & 0x80)
            Poly0 = (Poly0 << 1) ^ 0x1b;
        else
            Poly0 <<= 1;

        Poly1 >>= 1;
    }

    return Result;
}

Is it actually necessary to have this in constant time if GF28_Inverse is in constant time?

In C, multiplication in the field $\operatorname{GF}(2^8)$ with reduction polynomial $x^8+x^4+x^3+x+1$ can be coded as one of these three functionally equivalent functions:
uint8_t mult1B_compact(uint8_t a, uint8_t b) {
    uint8_t r = 0, i = 8;
    while(i)
        r = (-(b>>--i & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    return r;
}

uint8_t mult1B_fast(uint8_t a, uint8_t b) {
    uint8_t r;
    r = (-(b>>7    ) & a);
    r = (-(b>>6 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>5 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>4 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>3 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>2 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>1 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
 return (-(b    & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
}

uint8_t mult1B_shift8(uint8_t a, uint8_t b) {
    uint16_t r,s;
        r  = (-((s = b+b)&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
 return r ^( (-((s +  s )&256))>>8 & a);
}

Try It Online!. The first two versions extensively uses a generic technique, applicable to many other languages: it

moves a bitof interest to the low-order bit of a byte using right-shift >>
isolates it with & 1 if necessary,
applies the unary operator - to change 1 to 0xFF…FF (leaving 0unchanged),
then uses the outcome as a byte mask.

For most platforms, this generates code free from data-dependent timing variation¹. I know no exception, but still that should be checked, e.g. by inspection of the generated code, and in theory invoking/verifying considerations about what influences the execution time of an instruction on each of the target CPUs.
On many platforms, mult1B_fast (perhaps, made inline) is close to the fastest portable C code free from data-dependent timing variation. However, especially on CPUs lacking a barrel shifter, it may be worth trying the mult1B_shift8 variation, which only shifts by a whole byte: the above technique is applied on the high byte 16-bit variables, hence & 1 becomes &256. Assembly language often allows further gain, including thanks to direct access to the carry bit.
Note: These techniques leave other side channels wide open, in particular power analysis.
Note: demonstrating the absence of data-dependent timing variation is very difficult in some non-compiled languages. The most minute details about the runtime environment in theory needs to be taken into account; like, what heuristic a Java JITC uses.
Note: Bogus compiler/tool warning on the tune of «unary minus operator applied to unsigned type, result still unsigned» can be silenced, perhaps by changing the occurrences of -( to 0-(. Add parenthesis to satisfy any enforced convention.

Is it actually necessary to have (this field multiplication code) in constant time if GF28_Inverse is in constant time?

No, because full field multiplication is not necessary (also see note¹). Except for computation of the S-box, a natural implementation of AES encryption² (including AES decryption in CTR mode) only needs field multiplication by the field element $x$, encoded 2. Using the same technique as above, that can be coded as one of:
inline uint8_t mul1B_x(uint8_t a) {
    return (-(a>>7) & 0x1B) ^ (a+a);
}

inline uint8_t mul1B_x_shift8(uint8_t a) {
    uint16_t r = a+a;
    return ((-(r & 256))>>8 & 0x1B) ^ r;
}

¹ For security, we do not need constant-time code, which is next to impossible to achieve on many modern computing platforms because of the various caches and background interrupt activity. It is enough that any timing variations there may be is independent of the data manipulated.
² One such natural implementation is there. It is typically free from data-dependent timing variation on CPUs without a data cache when the two 256-byte tables are aligned to a 256-byte boundary. One of these tables is replaceable by mul1B_x, the other is the S-box.


NFC with AES : how works the exchange of key I'm trying since days to understand the security protocols on NFC devices. I'm not a professional in security, I'm just a student and want to understand (additionally, English is absolutely not my mother tongue ^^).

I see that AES-128 is implemented on several devices, like the MIFARE DESFire EV1 (and2) but I don't understand several things :

How is the key exchanged with the reader and the tag ? AES-128 is a symmetrical protocol, so the private key must be shared between the two devices. I can't understand - reader the documentation - how does it work.
For instance, I can read here http://www.ti.com/lit/an/sloa213/sloa213.pdf the process of authentication with AES. I'm sorry, I don't understand how the key can be shared and formally, what functions are used :/
I'm not sure neither to understand the meaning and utility of the UID (or RID with DESFire). It is only a unique number to avoid the cloning ? But in the case of a RID, how does it work to ensure that the card is not cloned ?
Finally, is the random generator known ? I think it is a 16 bits generator, is that possible to know what function is implemented on it, and how is chosen the salt (I know that in the past, the RGN was a big issue with CRYPTO-1, I guess that the method is know different but is that known ?) ?

Thanks a lot :)

As in most Smart Card systems using symmetric cryptography, the reader does not hold a key shared with a card. It somewhat holds a master key which, combined with a card identifier (e.g. some serial number), can produce a so-called diversified key, which is in the card. This is known as key diversification (diversification is derivation using a master key and device ID). This insures that even extracting a key from a card can't compromise the key of other cards.

The reader-side cryptography is typically performed by a SAM, perhaps similar to this one.

Thus UID/RID might be the device ID used for diversification. Or not. It is not secret, most often can be read (at least in EV1) and thus cloned; but the associated diversified key can not be read, and that's what prevents cloning.


Given a hash function; assuming domain % codomain = 0 and uniform collision distribution; how is entropy lost by collisions (not output truncation)? Assuming our domain and codomain both have 4 elements, the uniform distribution of inputs to outputs means the function is injective. It is widely agreed that randomly selecting a domain element results in log2(4) = 2 bits of entropy in the selection, and that because of being injective, the output of said function input this selection will also contain 2 bits of entropy.

If we double our domain element count to 8, then a random selection will have log2(8) = 3 bits of entropy. Because of pigeonhole principle there are collisions, but we defined a uniform distribution, so each of the 4 codomain elements has two domain elements mapped to it.

In the second case, clearly the 3 bits of entropy of the input can't be preserved in the output, but why would fewer than two bits of entropy be preserved? Isn't it still just equiprobably selecting an element from the codomain, given the lack of bias as defined by the uniform distribution of collisions?

In both cases, is it not preserving the entropy of the input up to the bit length of the output? Which is log2(4) to cover the 4 elements of the codomain.

Assuming our domain and codomain both have 4 elements, the uniform distribution of inputs to outputs means the function is injective.

You seem to be using the standard technical term ‘uniform distribution’ in a confusing way.  Normally the uniform distribution on a finite set $A$ means the probability distribution $P$ with $P(x) = 1/\#A$ for all $x \in A$, where $\#A$ is the number of elements in $A$.

But you haven't mentioned a probability distribution so far; you seem to be abusing the term ‘uniform distribution’ to mean a function $f\colon A \to B$ with the following property: There is a single number $n$ such that for every $y \in B$, the number of elements in the domain mapped to $y$ is $\#f^{-1}(y) = n$.  (One might call such a function ‘balanced’, particularly if it's a boolean function—i.e., a function defined on bits whose output is a single bit—but this nomenclature is not standard like ‘uniform distribution’ is in probability theory.)

  It is widely agreed that randomly selecting a domain element results in log2(4) = 2 bits of entropy in the selection,

When you say ‘randomly selecting’, that doesn't specify what probability distribution you're randomly selecting by.  But if the entropy of the selection is log2(4), then clearly you mean the uniform distribution on the domain.  I recommend you specify a distribution whenever you talk about a random selection.

  and that because of being injective, the output of said function input this selection will also contain 2 bits of entropy.

Yes, if $f$ is injective then $H[f(X)] = H[X]$ for all random variables $X$ with any probability distribution, including the uniform distribution.

  If we double our domain element count to 8, then a random selection will have log2(8) = 3 bits of entropy.

Again, only if the random selection is uniformly distributed over the whole domain.

  Because of pigeonhole principle there are collisions, but we defined a uniform distribution, so each of the 4 codomain elements has two domain elements mapped to it.

Yes, if by ‘uniform distribution’ you mean a function that has the same number of preimages $\#f^{-1}(y) \subseteq A$ for any element $y \in B$ in the image.

  In the second case, clearly the 3 bits of entropy of the input can't be preserved in the output, but why would fewer than two bits of entropy be preserved? Isn't it still just equiprobably selecting an element from the codomain, given the lack of bias as defined by the uniform distribution of collisions?

Let's take a concrete example.

Define $f(x) = x \bmod 4$ on $\{0,1,2,\dotsc,15\}$.  You can easily confirm that $f$ has the property you called ‘uniform distribution’—every element of the image $\{0,1,2,3\}$ has exactly four preimages.  That is, under $f$, the following sets of inputs obviously collide:

$\{0,4,8,12\}$
$\{1,5,9,13\}$
$\{2,6,10,14\}$
$\{3,7,11,15\}$

Consider the following two probability distributions on the domain of $f$:

$P(x) = 1/4$ for $x \in \{0,1,2,3\}$, and zero otherwise.
$Q(x) = 1/4$ for $x \in \{0,4,8,12\}$, and zero otherwise.

Clearly $P$ and $Q$ have the same entropy—2 bits.  What is the effect of $f$ on the entropy?

Let $X \sim P$.  Then $f(X)$ has four possible outcomes each with equal probability 1/4, so the entropy is the same: $H[f(X)] = H[X] = 2\,\mathrm{bits}$.
Let $X \sim Q$.  Then $f(X) = 0$ with probability 1.  So $H[f(X)] = 0$.

Obviously neither $P$ nor $Q$ is the uniform distribution on the domain of $f$.  If we define $U$ to be that distribution—that is, $U(x) = 1/16$ for each $x \in \{0,1,2,\dotsc,15\}$, and draw $X \sim U$—then sure, $H[f(X)] = 2\,\mathrm{bits}$, the maximum possible.


Is there an algorithm for factoring N, which is just as simple as this one, but faster? I found a simple algorithm for factoring semiprime numbers, you can read about it in Factoring Semiprimes and Possible Implications for RSA (paywall-free).

It basically works like this:

You reverse the digits in $N$, let's call this value $Ň$
You pick an integer, $k$ (normally 1, but can be other values)
A variable, $Δ$, can be any integer value between the square root of $N$ and the square root of $Ň$

You then calculate four values, if any return a value other than 1, then you have one of your prime factors:

$\gcd[N, (k × Ň) + Δ]$
$\gcd[N, (k × Ň) - Δ]$
$\gcd[N, (Δ × Ň) + k]$
$\gcd[N, (Δ × Ň) - k]$

Using this algorithm and the GMP library, it would factor 18014417929109603 in 3 seconds.

I was wondering if there were any other algorithms which were faster than this, but just as easy to implement? I know the GNFS is the fastest, but it is also incredibly hard to implement.

Pure nonsense. For choosing the random $\Delta$ between $\sqrt{\min(N, Ň)}$ and $\sqrt{\max(N, Ň)}$ there are too many possibilities for it to work. For example whenever the first and last digits of $N$ differ, you get something like $\frac{1}{10} \cdot \sqrt N$ possibilities (the exact formula doesn't matter).

So you can replace the first formula $\gcd[N, (k × Ň) + Δ]$ with $k=1$ by this one: $\gcd[N, \Delta]$. Try all $\Delta$ between $1$ and $\sqrt N$, the number of possibilities is within some small factor.

Compared to the division, computing $\gcd(N, x)$ has the advantage that at each attempt you try all factors of $x$. This is good in case $N$ has some small factors, which in case of RSA is surely not true.

I see no advantage of the linked algorithm to trial division. Trying all primes up to $\sqrt N$ is probably faster, terminates also when $N$ is prime, and has a bounded time.

Summary: pure nonsense.


What is the advantage of Pseudosquare? Pseudosquares ,which are not square but Jacobi symbol are still 1, are used in some cryptographic algorithm. What is the advantage of them over the exact squares? If we used squares instead of pseudosquares, what would we lost?
I think,factorization can be hard and so security is ensured. But I am not sure about certain reason

Your question is a bit broad for a completely detailed answer: pseudosquares is essentially a subgroup of $\mathbb{Z}_n$ (for an RSA modulus $n$) with particular properties, based on which a considerable number of cryptographic protocols have been designed. Nevertheless, having done some work on primitives that rely crucially on the properties of pseudosquares, I will try to give you an intuition of some aspects that I found important:

Protocols involving sending a square are inherently more difficult to be made secure against malicious adversaries. This is because when dealing with malicious adversaries, you must ensure that they remain honest. However, given an element of $\mathbb{Z}_n$ with Jacobi symbol $1$, it is computationally infeasible to determine whether this number is a square or not (this is the quadratic residuosity assumption). Hence, to ensure that a player indeed send a square, you must rely on expensive zero-knowledge proofs to check it. If, however, your protocol can be directly built using pseudosquares instead of squares, you remove this burden: checking whether a number is a pseudosquare (ie computing the Jacobi symbol) can be done in polynomial time (even without the factorization).
There is a very natural cryptosystem associated with the group of pseudosquares: to encrypt 0, send a random square, to encrypt $1$ send a random non-square pseudosquare. More formally, the public key is a non-square pseudosquare $y$, and encrypting a bit $b$ is done by computing $c = y^{2r+b}$ for a random integer $r$. With the factorization, one can recover $b$ by chechking whether $c$ is a square. The security comes from the quadratic residuosity assumption. This is the Goldwasser-Micali encryption scheme. Actually, this scheme has many good properties: it s randomizable, homomorphic for the xor operation, lossy (id est, the public key can come in two forms, either $y$ is a square and the encryption perfectly masks the bit, or it is a non-square and $b$ can be decrypted; this property is very useful to make security proofs of cryptographic schemes). It also allows for the design of oblivious transfer protocols (hence multiparty computation), among a considerable number of other applications.
Another example of the power of pseudosquares is identity based encryption. Primitives used in classical cryptography - such as ElGamal and RSA - are powerful tools, but they do not have enough structure to allow for some more involved cryptographic constructions, such as identity-based encryption. Indeed, IBE seems to require groups with more structures, such as pairings, or lattice-based cryptography. In this field, the Cock cryptosystem is an OVNI: it's an identity based encryption scheme based solely on the quadratic residuosity assumption, hence dealing with pseudosquares. Its existence suggests that pseudosquares enjoy very interesting and non-trivial features that cannot be found in, e.g., groups of squares, prime order fields ore elliptic curves without pairings.


What is the difference between the standard representants of $\mathbb Z/q\mathbb Z$? The symbol $\mathbb Z/q\mathbb Z$ (given that $q$ is prime) represents the prime field $\mathbb Z_q$. Basically, the elements of this field are represented by $\{0, 1, \dots, q-1\}$, let's call this the "normal representation". However, in lattice based crypto, the elements of the field are represented by $\{-(q-1)/2, \dots, (q-1)/2\}$, let's call this the "lattice representation".
What is the difference between these two representations? Why is the second one used in lattice crypto? Would it work if the normal representation was used instead?
I would also be very grateful if someone could show an example of how $\mathbb Z_7$'s elements $\{0, 1, 2, \dots, 6\}$ are mapped into the other representation.

When decrypting in lattice-based cryptosystems, one computes a value $v \in \mathbb{Z}_q$ that is guaranteed to be congruent to a "small" integer $e \in \mathbb{Z}$, where $e$ encodes the message (e.g., as the parity of $e$ modulo 2).  By using the integer representatives between $-q/2$ and $q/2$, one can recover the small integer $e$ (and thereby recover the message) simply by "lifting" $v$ to its integer representative.

If we instead used the representatives $0$ through $q-1$, then the representative of $v$ would often be a little smaller than $q$ (specifically, when $e$ is negative), and would not have the proper parity.

Geometrically, using the correct representatives corresponds to "decoding" the lattice $q\mathbb{Z}$ under small error: given the coset $(v + q\mathbb{Z}) \in \mathbb{Z}_q$, we find the smallest element in the coset, which is $e$.

Many papers conflate $\mathbb{Z}_q$ with its set of representatives, but this can cause confusion about what operations are legal and meaningful. Values that are known to be "small" should be seen as elements of $\mathbb{Z}$, which are then reduced mod $q$ when combined with values from $\mathbb{Z}_q$. When we later want to recover a small value from its coset modulo $q$, we lift/decode to $\mathbb{Z}$ using the proper representatives.


What is the name of an attack where the compromise of one key compromises the whole system? Consider the following: A whole system depends on the security of one private key and if this key is, for any reason, compromised, the whole system will be compromised.

What's a suitable name for such an attack?

The whole system depends on the security of one private key (..that gets..) compromised.
  Give a suitable name for such an attack.

I would call this class of attacks: Master key compromise.

Examples of such attacks (as asked in comment) include

The master key is revealed to an attacker by physically stealing a backup copy, bribery or duress (obligatory XKCD) of a holder of the master key. Mitigations use safes, and/or k-out-of-m secret sharing.
The adversary extracts the master key from a device holding it (the most obvious example of that is when the master key is in every device, which is not unseen). Mitigations include using security-certified device at least for master keys (HSMs, SAMs, Smart Cards). Method of extraction include

directly reading the memory/medium that stores the key,
examining memory where the device using the key copies it, perhaps temporarily (e.g. with a debugger, a JTAG port, exploitation of a buffer overflow vulnerability somewhere in the code..)
timing attack, (differential) power analysis and similar side-channel attacks (including fault attacks)

Cryptanalytic attack or/and brute force attack, where a secret key (including private) is inferred from public material, like ciphertext, plaintext made available to an adversary, public key. Mitigation include using larger security parameters for master keys.


How can one turn a malleable encryption to not malleable An encryption algorithm is "malleable" if it is possible to transform a ciphertext into another ciphertext which decrypts to a related plaintext. That is, given an encryption of a plaintext m, it is possible to generate another ciphertext which decrypts to f(m), for a known function f, without necessarily knowing or learning m.

And non-malleable is the adversary shouldn't be able to come up with a ciphertext whose underlying plaintext is related to the original message through a relation that also takes public keys into account.

My question is how can one turn a malleable encryption scheme into one that is not
malleable?

It seems like you are asking about converting an IND-CPA encryption scheme into an IND-CCA one.

In the symmetric-key setting, the standard approach that works is Encrypt-then-MAC.
In the public-key setting, this is a longstanding open question. There is no known black-box construction of IND-CCA from IND-CPA, nor is there a known impossibility of such a construction. However, there is such a transformation in the random oracle model: the Fujisaki-Okamoto transformation.


Using bcrypt derived keys for encryption? Sorry for this ignorant question but I am currently weighing up the advantages and disadvantages of BCrypt over PBKDF2 and from what I have read BCrypt is considered more secure but from what I have discovered BCrypt only derives as 248-bit key (Example: E2cP18g8DyWwg3emgpHOaPBZzrcRVrO) and the rest of it is the salt, however I require a 512-bit key so I can split it into two sub-keys on for a AES encryption key and the other for HMAC generation.

Would it be secure to take the sha-512 hash of the key produced by BCrypt and split that or should I just keep using PBKDF2?

BCrypt is considered more secure

The theoretical security of bcrypt has received less scrutiny than that of PBKDF2, SHA2 and HMAC.  PBKDF2 is thus widely standardised (e.g. in NIST SP800-132 and PKCS #5) while bcrypt is not.

In practice the security (resistance to brute force attack or dictionary attack) of bcrypt and PBKDF2-HMAC-SHA512 can be controlled by a workload parameter.  bcrypt is more secure than PBKDF2 in the sense that: if you select the workload parameters such that the algorithms use the same computing time on a general-purpose CPU, then an attacker able to choose their hardware (CPU, GPU, FPGA, or ASIC) can attack PBKDF2 4 to 6 times more effectively than bcrypt at the same cost (see the scrypt paper).

As a heuristic we could say that a password hashed with PBKDF2 should have 2 to 3 bits more randomness than a password hashed with bcrypt to achieve equivalent security (against a brute force attack; for equivalent workload parameters).

  Would it be secure to take the sha-512 hash of the key produced by BCrypt and split that

No, but you're on the right path by splitting the operation into a step that produces a key, and a step that expands the key.  The trick is to select the right primitives for these operations.

To expand a key - that is, to produce using one key a stream of derived random output suitable for use as key material - you need a Pseudorandom Function Family (PRF).  SHA-512 is not a PRF, but HMAC-SHA512 is.  Using HMAC-SHA512 would be a secure - but not ideal - solution.

A better solution is to use HKDF which splits key derivation into extraction and expansion steps.  By using bcrypt or PBKDF2 you have already extracted a pseudorandom key (HKDF calls this a PRK) from the password.  You can apply the HKDF expansion step to that PRK to produce derived keying material of any length; equivalently you could use one of the Key Derivation Functions from NIST SP800-108.

See also Do any security experts recommend bcrypt for password storage? for more on PBKDF2 vs bcrypt.


uniquely identify a symmetric key Is there a safe way to uniquely identify a symmetric key?  I know with asymmetric keys you typically use a hash of the public key, but I assume that using a hash of a symmetric key would reveal too much information.  Would you simply have to assign a GUID to each key and ensure that those GUID/key pairs never get lost or mixed up?

I'm just wondering, because if you have hundreds of keys stored someplace, how do you know which one to use?

Any unique identifier would do the trick, including using a hash of the key (assuming you are using a good hash function). Personally I would not use a hash of the key though as it makes an offline attack theoretically possible. If the ID has nothing to do with the key, however, and an attacker steals the ID, there is no advantage gained by the adversary. A simple counter would do the trick. If you indeed need the ID to be globally unique though, simply having everyone generate a random 128 bit number would also work.


Relation between the correlation coefficients $\widehat F(w) = C(f(a), w^ta)$ and $(-1)^{f(a)}$ In the paper Correlation Matrices by Joan Daemen et. al., the authors state (on page 3) that if the correlation coefficients $C(f(a),w^ta)$ of a Boolean function $f$ are denoted by $\widehat F(w)$ then $$\widehat f(a) = \sum_w \widehat F(w) (-1)^{w^t a},$$
with $\widehat f(a) = (-1)^{f(a)}$.

Can someone explain why this formula is correct?

Kodlu already gave a hint, but here are a bit more details (since I don't think this is homework). By definition (or equation 3 in your reference),

$$\widehat F(w)= C(f(a), w^t a) = 2^{-n} \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x) + w^t x}.$$

Hence

$$\sum_{w \in \mathbb{F}_2^n} \widehat F(w) (-1)^{w^t a} = 2^{-n} \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x)} \left(\sum_{w \in \mathbb{F}_2^n} (-1)^{w^t (x + a)}\right).$$

The inner sum is zero whenever $x \neq a$ and equal to $2^n$ otherwise. Hence

$$\sum_{w \in \mathbb{F}_2^n} \widehat F(w) (-1)^{w^t a} = \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x)} \delta_{x, a} = (-1)^{f(a)} = \widehat f(a).$$

I've used the same notation as in your reference. If you want a more general understanding of this result, you should read about Fourier transformations on (locally compact) groups.


Can we say that if $P=NP$ there is no CPA secure public key encryption? I've learned that public key encryption is based on the problem of Discrete Log (as regard to group theory) which believed to be hard.

But, can we say that it doesn't matter on which problem our public encryption rely and say that it couldn't be CPA secure anyway?

There is no direct inference from $P = NP$ or $P \neq NP$ to security or insecurity of any particular encryption algorithm. As far as practical consequences are concerned, the "$P = NP$" problem is severely overhyped.

If $P = NP$ then any problem for which a solution can be verified in polynomial time can also be solved in polynomial time. "Polynomial time" does not automatically mean fast, for two reasons:

Complexity classes like $P$ and $NP$ are about asymptotic behaviour: they give us values for sufficiently large instances of the problem. Nothing tells us that a specific instance is large enough for the asymptotic behaviour to be an accurate description of the computational cost of solving that instance. For instance, asymptotically speaking, GNFS is a faster integer factorization algorithm than Quadratic Sieve; but, in practice, QS is faster than GNFS for integers of less than 300 bits. Proving $P = NP$ would imply that there exists a polynomial algorithm to solve integer factorization (or discrete logarithm), but it would not follow that this algorithm is indeed efficient for a 1024-bit integer.
"Polynomial" means "with cost proportional to $n^x$ for a problem of size $n$ and some constant integer $x$". Nothing guarantees that $x$ is small. A $O(n^{20})$ algorithm is completely polynomial, and completely out of reach of our technology for a size $n \geq 32$ bits...


Homomorphic Evaluation of Pseudo Random Function I'm looking for a special Pseudo Random Function (PRF) $F_k()$ which follows the below.

For fully homomorphic encryption (FHE), $\mathit{FHE}(F_k(x)) = F_k(\mathit{FHE}(x))$.

Or is there any homomorphically evaluable doubling pseudorandom number generator algorithm? (because Goldreich-Goldwasser-Micali PRF construction is based on the doubling pseudorandom number generator.)

Thanks.

There is an Eurocrypt'15 paper published by Albrecht et al. which creates a cipher minimizing the number of multiplications needed to produce an encryption. This cipher is called LowMC and it can also be used as a PRF with almost same parameters as in the block-cipher - check out LowMC section in this paper.

Fortunately, there is open-source code which evaluates LowMC homomorphically with HElib. To evaluate the cipher homomorphically is to compute $\mathsf{Enc}_{\mathsf{k}}(\mathsf{LowMC}(x))$ from $\mathsf{Enc}_\mathsf{k}(x)$.

So you can plug in the PRF parameters given by Grassi et al. (for 128 bit PRF security) in the script provided by Albrecht and there you have it: LowMC becomes a PRF and your question is solved - compute $\mathsf{Enc}_\mathsf{k}(\mathsf{PRF}(x))$ from $\mathsf{Enc}_\mathsf{k}(x)$. And I think this is the state of the art for computing PRFs in HE land.


Questions about Symmetric Encryption part of TLS In TLS, we use DHKE for establishing the session key & then encrypt the actual communication with session key using symmetric encryption. While reading about DHKE, I learnt that you could use the key as a AES Key & encrypt the session with AES. Or you could use something like Elgamal encryption.
So in practice, what is used more commonly? Is it something like AES or is it something like Elgamal?
AES seems to be quite complicated as compared to Elgamal - Elgamal is just multiplication with the key modulo. So how come it provides security comparable to AES with all it's s-boxes, p-boxes etc? Is it because for every message a new session key is used with Elgamal?

I learnt that you could use the key as a AES Key & encrypt the session with AES. Or you could use something like Elgamal encryption.

Elgamal encryption could be used directly with a static private key. The key type would be identical to the one used for (static or ephemeral) Diffie-Hellman. However, it would not be efficient both when it comes to space nor CPU.

So in practice, what is used more commonly? Is it something like AES or is it something like Elgamal?

AES is used much more. Elgamal is not used much because it has drawbacks even compared to e.g. RSA encryption using PKCS#1 or ECIES. One main issue is mapping the message to the cyclic group G, another is the required ciphertext expansion.

AES seems to be quite complicated as compared to Elgamal - Elgamal is just multiplication with the key modulo.

No, that's an oversimplification, please check the Wikipedia page on Elgamal encryption. Beware that these calculations are using huge numbers. Exponentiation and multiplication over such inmense values are not very fast. And, unfortunately, unlike DH, it's not easy to use Elgamal with Elliptic Curves - ECIES is more useful for encryption with Elliptic Curves.

So how come it provides security comparable to AES with all it's s-boxes, p-boxes etc? Is it because for every message a new session key is used with Elgamal?

No, Elgamal is not used with session keys at all. Session keys are symmetric keys derived from a shared secret. Elgamal is for asymmetric encryption. As mentioned, AES is now commonly used within authenticated encryption, which provides semantic security, something that is really important in a transport protocol.


CBC - Cipher-text stealing decryption (I asked in stackoverflow and I should ask my question here not there, sorry about that)

The graph shows CBC- with cipher-text stealing and (b) is the block length. The output cipher-text is c1,...,c4 How is the decryption for this graph? I hope that someone can explain it to me with a graph because I checked the explanation in wikipedia and it was confusing to me.

Let's say we have a ciphertext of length $(N-1)B < n < NB$, for $B$ the blocksize at hand (typically 128 for AES), where the ciphertext is made with $C_1, C_2, C_3, C_4$, with $C_3$ being shorter that the rest.

In order to decrypt a ciphertext made using ciphertext stealing as you drafted, you have to:

Decrypt the ciphertext just like you would for CBC without ciphertext stealing for the $N-2$ first blocks.
Take the latest two blocks ($C_3, C_4$ in your example), and compute the length of the "stolen" ciphertext by computing $n-(N-1)B=a$ and deducing its length $B-a$.
Decrypt the latest block, e.g. $C_4$ into its unencrypted value $E_4$
Xor $E_4$ with the concatenation of $C_3$ and $B-a$ 0s like $C_3 | \underbrace{0\cdots 0}_{B-a}$, to obtain $M_4 | C'_3$
Take the last $B-a$ bits of it, which is $C'_3$ and concatenate it with $C_3$, which you can finally decrypt just like you would usually.

I've committed a cri diagram, using the same colors as you, hope this helps:

Notice that this is assuming the same construction as you used in your graphic. (There are other ways to do it, too.)


Best password hashing strategy with Argon2 in a web app What are reasonable parameters for Argon2 to hash passwords in a web application? On the one hand we need good performance, fast responses and DDoS resistance, but on the other hand we need protection from brute force on modern GPU, ASIC, FPGA etc. I see an example in Django - they use Argon2i with p=2, t=2 and 512kb of RAM, so is it enough nowadays?

Update: Basically I need to keep response time as low as possible, say 5ms for a user to hash his password. Taking into consideration theoretical throughput of RAM I can afford from 2 till 8Mb per password, so I can either spend more time doing calculations on CPU or consume more RAM with less calculations. What is the best strategy for such a case (do more CPU calculations or consume more RAM per password) to get as maximum brute force resistance as possible? The password hashing algorithm is Argon2, as it's mentioned in the title.

Update 2: Those who vote against some answers please do describe your point in comments.

Only peripherally related, but consider doing somewhat expensive hashing on the client side as well as on the server, and arguably instead of on the server. This increases the costs of an attacker brute-forcing passwords, but scales better, and depending on your clients this could be viable - for example, browsers expose built-in PBKDF2 via webcrypto APIs.


What's an entropy measure for the sequence $0, 1, 0, 1, 0, 1, ...$? I'm puzzled by the measure $$E(S) = -\sum p(i) \lg p(i)$$ because I'm considering a source emitting $0, 1, 0, 1, 0, ...$ and having the maximum entropy as given by $E(S)$.  Shouldn't $E(S)$ measure the quantity of information?  The sequence that just repeats $1$ after $0$ seems to me to convey very little information --- contained in this very phrase.

Where am I wrong in my understanding of entropy and of $E(S)$?

Let's just fill it in! Your generator has two possible outcomes, both with certain probabilities. For the every element of your sequence, you're certain about its outcome, thus:

\begin{align*}
E(S)&=-p_0\log p_0 - p_1\log p_1\\
    &=-p_0\log p_0 - (1-p_0)\log (1-p_0)\\
    &\mathrel{\mathop{=}_{p_0\to1}} -1\log 1 - 0\\
    &=-1\cdot0=0
\end{align*}

Seems like your source does not convey any information (zero bits), because indeed you already know what it will produce! Talking about entropy of a source only makes sense when the source has a stochastic behaviour; when it has an element of unpredictability.


Cryptanalysis on Kasumi in A5/3 GSM algorithm-- why is it broken in 2G and not in 3G? I have read the Wikipedia article that states Dunkelman, Keller and Shamir managed in 2010 to mount a related-key attack in a pretty decent time (2hrs) with a Core 2 Duo.

Why was Kasumi breakable in 2G (A5/3), but not in 3G?

KASUMI is not "broken in 2G". In fact it is not even used in 2G. 2G systems use algorithms A5/1 and/or A5/2, which are unrelated to KASUMI (which is A5/3).

The 2010 attack is a "related-key attack": it is a rather esoteric kind of attack in which the attacker obtains plaintext/ciphertext pairs that are encrypted with different keys, but such that the keys differ in a specific and attacker-known way. In that kind of setup, Dunkelman, Keller and Shamir can rebuild the key after some computations (the two hours worth of computation time). However, this still relies on the exact situation with the keys that differ by known amounts; such a situation does not arise in 3G networks. In fact, related-key attacks almost never apply in practice, and in general we don't care much about them (e.g. they were not part of the AES selection criteria); they still count as noteworthy, at least academically speaking, because an ideal cipher, defined as a uniform selection of the cipher among the whole set of possible permutations over the space of block values, should not have even related-key attacks.


Is F_k_1(x) \xor F_k_2(x) a pseudorandom function? I'm trying to determine if $F_{k_1, k_2}(x) = F_{k_1}(x) \oplus F_{k_2}(x)$ ($k_1 \neq k_2$ because that would be lame) is a pseudorandom function. My hunch is that it is. My reduction proof proceeds like this (but I get stuck halfway through)

Suppose $F$ is not secure. Then there is a PPT distinguisher D' s.t. for all $negl(n)$ we have:
$|P(D'^{F(\cdot)}(1^n) = 1) - P(D'^{f(\cdot)}(1^n) = 1)| \geq negl(n)$

We then construct a distinguishers $D_1, D_2$ that break $F_{k_1},F_{k_2}$.

So $D_1$ gives a message m to oracle $O_1$. $D_1$ wants to find out if $O_1$ is random or if it is actually $F_{k_1}$. It receives back output $y_1$. It then asks D' if $y_1 = F_{k_1}(m) \oplus F_{k_2}(m)$. If D' says yes then we know that either $F_{k_2}(m) = 0$ or $O_1$ is random since:

$0 = y_1 \oplus y_1 =$ $F_{k_1}(m) \oplus y_1 $ $= F_{k_1}(m) \oplus F_{k_1}(m) \oplus F_{k_2}(m) = F_{k_2}(m)$.

Since we learn something about $F_{k_2}$ which can be used to break $F_{k_2}$.

Working symmetrically we can learn something about $F_{k_1}$.

Basically if you run both tests, and D' says that both $y_1$ and $y_2$ are
$F_{k_1}(m) \oplus F_{k_2}(m) $ you can check if either $y_1$ or $y_2$ are 0. If neither are 0, both oracles must be random.

Am I on the right track with this? How would I write up a formal proof?

The simplest way to show something like this would be to take advantage of the triangle inequality with a hybrid argument:
$$
\Delta(A, B) \le \Delta(A, C) + \Delta(C, B)\,,
$$
where $C$ is some intermediate construction.

In this case, you begin with $F_{k_1}(x) \oplus F_{k_2}(x)$, where $k_1$ and $k_2$ are sampled independently and uniformly at random. We can replace $F_{k_1}$ by a truly random function $f_1$, and now we have
$$
f_1(x) \oplus F_{k_2}\,,
$$
and the distance from the original construction is the distance from $F_{k_1}$ to $f_1$ which is, by definition, $\mathrm{Adv}^{\mathrm{PRF}}_{F_{k_1}}(D_1)$ for some distinguisher $D_1$ that makes $q$ queries to $F_{k_1}$ and has runtime $t$.

Doing the same for $F_{k_2}$, we have
$$
f_1(x) \oplus f_2(x)\,
$$
adding the distance $\mathrm{Adv}^{\mathrm{PRF}}_{F_{k_2}}(D_2)$ similarly as before. Since the xor of two uniformly random strings is just as uniform as a single one, we can move to the random function
$$
f_3(x)\,,
$$
without any degradation in advantage. The total advantage is the sum of all these steps:
$$
\mathrm{Adv}^{\mathrm{PRF}}_{F_{k_1,k_2}}(D) \le \mathrm{Adv}^{\mathrm{PRF}}_{F_{k_1}}(D_1) + \mathrm{Adv}^{\mathrm{PRF}}_{F_{k_2}}(D_2) + 0\,.
$$


What does it mean when 1 bit goes into an s-box but two (or more) come out? I am trying to understand how bits are spread in the PRESENT cipher. The bits that enter the permutation of PRESENT return to their original position after only three rounds. But I am told that in fact the S-boxes also affect how they spread. Specifically, when one bit enters the S-box, two or more come out. I cannot understand this as I see four going in and four coming out. A short numerical example using the PRESENT S-box would be much appreciated.

It's very simple.  You've just gotten the wrong end of the stick.  Yes, the s box is 4 bits wide.  That means it contains 2^4 lookup values as:-

So it can accept any input ranging from 0000 to 1111 in binary.  When we say one bit goes in, we mean an active bit.  This refers to the  bit representing input data to the cipher that's not a zero.  Think of the inputs to the s box as physical wires.  Not all wires carry information all the time, but there are 4 wires permanently attached to each s box.  For example, the value 0010 entering the s box is considered to be one active bit.  There's just one "1", no matter it's position in the nibble.  If 0010 goes in, 0110  comes out as per the PRESENT substitution above (2 → 6).  There are now two "1"s to propagate further.

The concept of the active bit is important, as the combination of s boxes and permutation layers means the active bits can appear, disappear and wildly change relative position.  In the above example, one active bit went in and two came out.  The wires return to their original positions in three rounds, but the active bits will be all over the place as they will have effectively jumped wires.  This is substitution and permutation leading to Shannon's confusion and diffusion.

There's an s box tag that will show you a huge list of related questions that might flesh out what I've written, as well as detail the nuances of a good s box.  Not all s boxes are created equal.


Does DTLS in WebRTC protect from active Man-in-the-Middle? I wonder if it does. It seems to me that there is no way for participants to authenticate each other securely. There are, though, signaling servers, but I don't think that they are capable of key distribution.

Is there something I've missed?

WebRTC uses DTLS-SRTP and according to RFC 5764 DTLS-SRTP supports certificates for both client and server.
However in the context of WebRTC the direct connection established between the users is established by dynamically downloaded software running in the browser.
In other words the user does not control the software so even if the software did provide him with ways to secure the connection it could be replaced by other software that does not.

This is the same problem as faced by all kind of web based mail encryption systems.

It's nicely treated in this RFC draft:

  In general, it is important to understand that unlike a
  conventional    SIP proxy, the calling service (i.e., the Web server)
  controls not    only the channel between the communicating endpoints
  but also the    application running on the user's browser.  While in
  principle it is    possible for the browser to cut the calling service
  out of the loop    and directly present trusted information (and
  perhaps get consent),    practice in modern browsers is to avoid this
  whenever possible.


Inverse single element permutations Let's say we have a set of ordered elements $D=[x_1,x_2,x_3,x_4,x_5]$. We apply a random permutation on them with a $PRP=P_k: P_k(D)=D'=[x_3,x_2,x_5,x_1,x_4]$

My question is: can the owner of the key $k$ recover a single position of the original element without having to recompute all the permutations? Is there an inverse $PRP, PRP'_K$ such that:

$PRP'_K(3)=x_3, PRP'_K(2)=x_2$ and so on and so forth or given the result of the permutation and the key to recover the original element of this positions:$PRP'_K(x_3)=x_1, PRP'_K(x_2)=x_2$ ? without keeping either $D$ or $D'$

No, in general, knowing the key $k$ allowing efficient computation of a keyed permutation $P_k$ does not allow to efficiently compute the inverse permutation.

Here is a concrete example where the inversion is (conjecturally) computationally infeasible:

Let $D$ be the set of 4096-bit bitstrings, assimilated to integers per big-endian conventions.
Let $p=2^{4097}+3^{2579}+863880\;$. This is such that $p$ and $(p-1)/2$ are prime, and $2^{(p-1)/2}\equiv-1\pmod p$. The function $x\to(2^x\bmod p)$ is an efficiently computable public permutation of the set $\{1,2,3\dots p-3,p-2,p-1\}$, but the reverse permutation is hard to compute for arbitrary input (that's a Discrete Logarithm problem).
For $k\in D$, let $P_k$ be the permutation over $D$ defined for input $x$ by

$x\gets (x\oplus k)+8192$
note: here $8192\le x<2^{4096}+8192<(p−1)/2$
repeat

$x\gets(2^x\bmod p)$

until $8192\le x<2^{4096}+8192$
output $(x-8192)\oplus k$

The repeat/until loop (known as the cycling trick) creates a public (conjecturaly) hard to invert (that is, trapdoor) permutation of the set $\{8192,8193,\dots,2^{4096}+8190,2^{4096}+8191\}\;$. Combined to XOR with $k$, that forms $P_k$, which is keyed, and (conjecturaly) hard to invert and computationally indistinguishable from a random permutation without knowledge of $k$.

The above $P_k$ is an example of a PRP which members are trapdoors even to one choosing the key $k$. That's not the case of all PRPs: we also have block ciphers, which are PRPs invertible by anyone able to compute the function; and textbook RSA encryption, which is computable by anyone knowing the public key, but invertible only by one knowing the private key (textbook RSA encryption alone is not quite a PRP on a fixed set, but it is possible to build such PRP from textbook RSA encryption, e.g. using a cycling trick as above).


Does AES specify error messages when using the wrong password to decrypt? I am writing a small program which uses AES. In testing it with wrong passwords, I get error prompts from Microsoft C# component saying "the padding is bad"; whereas I expect wrongly decoded texts. Do these errors come from the original AES spec or not?

AES in general does not specify that it should return a bad padding message. In fact, AES in general says nothing about padding. Padding schemes are external to AES. Therefore, the message you are getting is .Net specific.

That said, be careful with these messages, as they can lead to a padding oracle attack.


Is authentication more computationally expensive than encryption? newbie in crypto here. I've a application that needs integrity protection. Confidentiality would be nice but has  less priority over performance throughput. So I test "openssl speed" on my laptop, and find out sha256 is actually slower than chacha20. About the same speed as chacha20+poly1305. I assume this sha256 is about the same speed as HMAC(sha256), is that correct?
Also in openssl, chacha20+poly1305 is faster than blake2b512.

Is it the general case that integrity protection  is much more computationally expensive than encryption? By using aead algorithms I get confidentiality for free?

SHA-256 is designed to be collision-resistant, which is much costlier than pseudorandomness or unforgeability.  It should come as no surprise that it is slower.  The difference between SHA-256 and HMAC-SHA256 for bulk data is negligible: a call to HMAC-SHA256 on a long input costs the same as one call to SHA-256 on a long input plus one call to SHA-256 on a short input.  The same goes for SHA-512, BLAKE2, SHA-3, etc.  You can use HMAC-SHA256 as a MAC for unforgeability, but you're paying a huge tax for unnecessary collision resistance.

In contrast, polynomial evaluation message authentication codes such as Poly1305 are some of the fastest crypto primitives available.  These are essentially chains of 128-bit additions and multiplications, with considerable flexibility in the order of operations to maximize vector unit utilization by virtue of working in a convenient prime field.  For MACs, collision resistance is not relevant.  Of course, you can't use Poly1305 for applications where collision resistance is necessary.

In chacha20+poly1305, the Poly1305 computation is easily the fastest part.  The speed of Poly1305 is a large part of why chacha20+poly1305 is much generally faster than, e.g., AES-CBC with HMAC-SHA256.  Another part is that software AES is slow, and software AES without timing side channels is horrifically slow—and worse for AES-CBC, which must work on arbitrary inputs, than for AES-CTR with highly structured inputs.

Similarly, for AES-GCM, there is a catch that most CPUs don't easily support fast binary field multiplication in software, whereas most CPUs do easily support fast prime field multiplication in software, so AES-GCM is also much slower than chacha20+poly1305 without dedicated hardware support—and horrifyingly slow without timing side channels.

As for whether AEAD gives you confidentiality: Yes, AEAD means authenticated encryption with associated data.  If you skip the authenticated part, then often you don't get confidentiality in the scenario of active attacks.  You should generally always use authenticated encryption; forget about unauthenticated encryption schemes as anything more than an implementation detail for authenticated encryption.


Calculate all possible keys for AES 128 encryption to exploit hardware encryption Some background: I am using the MicroChip ATAES132a for hardware encryption/decryption. The ATAES132a is very configurable and can be misconfigured in such a way that the encryption/decryption will be performed using the same nonce. In theory, if the nonce is known I can do an encryption of the plain text and get the same ciphered text result. Based on this, I could possibly try to encrypt the same plain text with the known nonce and compare to the generated ciphered text until I get a match.

For example, in theory my target key could be some thing like this (see below). I would need to calculate every possible key, use the known nonce and the same plain text until I get the same ciphered text result.

const uint8_t g_key0[] = { 0x01, 0x08, 0x0E, 0x91, 0xe2, 0x64, 0x8f, 0x49, 0x0c, 0xe9, 0x80, 0x45, 0x38, 0xb5, 0x85, 0x3f };

This would exploit how the device was configured incorrectly. The ATAES132a does all its encryption with AES in CCM mode. I can perform the attack either on the ATAES132a or on any PC using any standard AES library.

Is this attack plausible using a modern PC?

Is this attack plausible using a modern PC?

No. For AES-128 (or any secure 128-bit symmetric cipher for that matter), there are $2^{128}$ possible keys. You would have to try on average half of those keys before finding the right one, which is $2^{128}/2=2^{127}$. At $100,000,000$ attempts per second (or around $2^{26}$), it would take around $2^{101}$ second. The universe is around 13.7 billion years old (about $2^{59}$ seconds). So the amount of time it would take you is $2^{42}$ times the age of the universe.

There are other ways you can calculate this, but the end result is the same. See How much would it cost in U.S. dollars to brute force a 256 bit key in a year?.

Finally, the relevant XKCD:


Is adaptive security the same as full security? This question contains a great answer about adaptive security, but I haven't yet found a proper definition what full security is. Does a stronger security than adaptive security exist or are the two synonymous.

If they are different, what is the difference? If they are not different, why are they referred to differently?

I don't know what you mean by "full security", but "adaptive" just means that the oracle queries from the attacker depend on the results of previous queries. In contrast, "non adaptive" means that the attacker simply makes all the queries in batch, that is, without adapting his queries from previous results.

Update: based on the paper from your comments, it seems that "full security" is opposed to "selective security". Both "full" and "selective" security are defined in Chapter 2.3.3 of that paper. According to that definition, both models are adaptive, since queries from Phases 1 and 2 are adaptive.


Is this problem same as discrete logarithm? Given $g,h\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$ Discrete logarithm problem is to find $z$ such that $g^z\equiv h\bmod p$ holds.

Take the problem given $g,g',h$ where $g^z\equiv h\bmod p$ holds at some $z$ find $h'$ such that $g'^{z}\equiv h'\bmod p$ holds.

If we know $y$ such that $g^y\equiv g'\bmod p$ then $g'^{z}\equiv h'\bmod p$ is known or if we know $z$ then $g'^{z}\equiv h'\bmod p$ is known.

If we know $g'^{z}\equiv h'\bmod p$ and $g^z\equiv h\bmod p$ then is it easier to find $z$?
What is the best way to find $g'^{z}\equiv h'\bmod p$ if we only know $g,g',h$ with $g^z\equiv h\bmod p$?
What is the best way to find $f$ such that $f^{z}\equiv 1\bmod p$ if we only know $g,h$ with $g^z\equiv h\bmod p$?

This is exactly the Computational Diffie-Hellman (CDH) problem. Rename $h=g^z$ and $g'=g^y$ in what you wrote, then the problem becomes:

  Given $g$, $g^z$, and $g^y$, compute $g^{yz}$.

See this discussion to address your question about the relationship between CDH and discrete log.

edit:

  Q1: If we know $(g′)^z$ and $g^z$ then is it easier to find $z$?

No, it is just as hard as discrete log. If you are given just $g$ and $g^z$ then you can generate other pairs with the same discrete log relationship yourself, via $g' = g^r$ and $(g')^z = (g^z)^r$. So having extra such pairs doesn't add any new information.


Encrypted key- determining type and properties If I was given an encrypted .key file (no further information about the key), called "abcd.key.enc," how would I start characterizing and identifying information about the key, its encryption/ cipher used, etc...?

My ultimate goal is to decrypt the key, but I can't find any trivial ways to determine anything about the key itself, especially since I can't read the cipher text.  The best I can think of is to run linux "strings" against the key file which gives me the output

3Nj3
!/'i9

thanks for any help!

In general, if the file has been encrypted using a secure modern cipher and contains no metadata to indicate the encryption method used, you cannot determine the method just by examining the file.  See e.g this answer by Thomas Pornin for more information.

At best, the size of the file may put some constraints on both the length of the encrypted key and on the encryption method used (since different encryption methods have different amounts of overhead), but such constraints are necessarily rather broad.  If you know that the file is very old (say, from the 1980s or earlier), that may also narrow down the possible options.

Probably your best bet, however, in the absence of actual documentation about the encryption used, is to try to reverse engineer the software (or hardware!) that knows how to encrypt and/or decrypt the key file.  After all, something must know how to decrypt the file, for it to be of any use to anybody at all.


Zero knowledge proof for identity Quoting a blog authored by Vitalik Buterin regarding ZKP and Ethereum

  One natural use case for the technology is in identity systems. For
  example, suppose that you want to prove to a system that you are (i) a
  citizen of a given country, and (ii) over 19 years old. Suppose that
  your government is technologically progressive, and issues
  cryptographically signed digital passports, which include a person’s
  name and date of birth as well as a private and public key. You would
  construct a function which takes a digital passport and a signature
  signed by the private key in the passport as input, and outputs 1 if
  both (i) the date of birth is before 1996, (ii) the passport was
  signed with the government’s public key, and (iii) the signature is
  correct, and outputs 0 otherwise. You would then make a zero-knowledge
  proof showing that you have an input that, when passed through this
  function, returns 1, and sign the proof with another private key that
  you want to use for your future interactions with this service. The
  service would verify the proof, and if the proof is correct it would
  accept messages signed with your private key as valid.

I don't quite get why this would be considered a ZKP and not "simple key pair"

The key pair used to sign the proof is just a means of securely communicating with the service (it doesn't prove anything, it just establishes a means of proving data integrity, i.e. "I'm really the one who just sent you this proof, see, I signed it with my private key? -Oh, OK, I just verified with your public key; all good")

Now for the first key pair (since I don't know which key pair you are referring to by saying "simple key pair"):
Same thing, except here it's to prove the integrity of the passport. It was signed by a government, so all the data contained within it are certified by that government (one can't just modify his digital passport to appear older and whatnot).

The ZKP part of your question is hard to answer since it's very abstract in the quote you provided, but put simply:

You're not going to send your birthdate contained in your passport (as that would not be zero knowledge). A zero knowledge proof protocol would take (i), (ii), (iii) as input and provide a proof (to the service), without disclosing any of (i), (ii), (iii). Through such a protocol, the service would know (/be convinced of with a high probability) that you are indeed over 19 years old and that this information inside your digital passport has been certified by your government.

The difficulty here would be the ZKP protocol itself that would be able to provide such a proof.

The service won't receive your passport data, signature, or birthdate (encrypted or not with a key pair), but a proof of the statement "I am over 19 years old".

I hope I helped clarify this though I'm not sure. With a reference to the blog post I could maybe see the ZKP (if he provided it) he imagined to achieve this.


Elgamal Encryption: Why does Bob get to reuse his keypair while Alice has to generate a new one for every message? From Christof Paar's book

The protocol consists of two phases, the classical DHKE (Steps a–f) which is followed by the message encryption and decryption (Steps g and h, respectively). Bob computes his private key $d$ and public key $β$. This key pair does not change, i.e., it can be used for encrypting many messages. Alice, however, has to generate a new public–private key pair for the encryption of every message. Her private key is denoted by $i$ and her public key by $k\,E$. The latter is an ephemeral (existing only temporarily) key, hence the index $E$. The joint key is denoted by $k,M$ because it is used for masking the plaintext.

So why does Bob get to use the same keypair while Alice has to generate a new keypair every time?
Also, in case of TLS/HTTP, between a Browser & a Website - which one is Alice & which one is Bob?

So why does Bob get to use the same keypair while Alice has to generate a new keypair every time?

Because ElGamal is insecure if Alice picks the same keypair repeatedly.
ElGamal is a public key encryption system; Bob has a long term public key, which he generates once, and hence Bob has to select once private key $b$ and a long term public key $B = G^b$ (note: I don't have the Paar book, hence I don't know what notation he uses).
In contrast, Alice encrypts a message $M$ using Bob's public key $B$; what she does is select a random value $r$ and produce the pair $G^r$ and $M \cdot B^r$.
This is fine; however suppose Alice encrypts a second message $M'$ also to Bob and uses the same random value $r$; this second ciphertext would be $G^r$ and $M' \cdot B^r$.
Why is this bad?  Well, someone seeing both ciphertexts can reconstruct $(M \cdot B^r) (M' \cdot B^r)^{-1} = M \cdot M'^{-1}$. This is more information than we want someone listening in to obtain; in particular, if they happen to know one of the messages (say, $M'$), they can recover the other ($M$).
If Alice selects a fresh random value each time, this does not happen.


Key derivation function in theory & practice I am implementing a cryptographic protocol and I'd like to generate a set of seeds using a seed for a pseudo-random function. The reason is that I can pass on only one seed and it can be used to generate the other seeds.

As we know each derived seed is used to generate a set of pseudo-random values.

According to pseudo-random function definition, the seeds must be truly random (and not pseudorandom). So if I use a master seed to generate some other seeds the derived seed would not be truly random (according to the definition).

Question 1: How can I fill the above gap (i.e. satisfy the pseudorandom function) and have a secure key derivation function?

Question 2: Are the key derivation functions deterministic (i.e. given a master key it always generates a set of derived keys)?

Do NOT generate your own key derivation function.  Use one of the known and trusted ones... industry standard ones, such as PBKDF2 https://en.wikipedia.org/wiki/PBKDF2

Use your starting (pseudo-random) value, and plug it into PBKDF2 for different numbers of iterations for each desired output (new seed) that you need.


Is there a way to easily encode a message without a computer on either end? I enjoy making notes and passing them to my friends, and I also like making them encrypted for no reason. My friends enjoy it too, but it's a bit annoying to use the Caesar cipher for everything because its repetitive and takes forever. Is there a better pen-and-paper way of encrypting messages?

Most of the classical crypto algorithms used in the pre computer era can be doable with pen and paper!! Lot of there are in the list see here http://practicalcryptography.com/ciphers/classical-era/ . Try Vigenere and change you keys frequently.


Has anyone implemented a public-key encryption scheme using a universal one-way function? There exists a function $f$ such that if one-way functions exist then $f$ is a one-way function.  Such a function is called a universal one-way function.
Now the public-key encryption schemes that I’ve come across use functions for which it is an open problem whether they are one-way functions even under the assumption that one-way functions exist.  My question is, has anyone implemented a public-key encryption scheme based on a universal one-way function?
If not, what makes a universal one-way function impractical to use?

We don't know of any construction of PKE based on a universal OWF. Actually, we do not even have any plausible candidate PKE that would be based on an arbitrary OWF. Obtaining such constructions is a major open problem. We know that there is no black-box construction of PKE from any OWF by a seminal result of Impagliazzo and Rudich. Of course, we cannot rule out all possible constructions: since we believe that both PKE and OWF exist, a valid construction of PKE from any OWF is: ignore the OWF and take a PKE which exists.
In any case, universal OWFs are too inefficient to be really useful in practice. Levin's initial construction is really, really super-duper inefficient. Levin also gave a more combinatorial construction based on tiling in this paper, but that would still be way to inefficient for any practical purpose (though perhaps "implementable in theory", unlike his first candidate).
There are constructions of universal PKE (that are secure if any PKE exists), see for example the pointers in this paper, paragraph "Brief history of combiners and universal cryptographic primitives" in the introduction.

EDIT: answering the question in the comment
Universal cryptographic primitives are closely related to cryptographic combiners. A $(1,n)$-cryptographic combiner takes $n$ candidate cryptographic primitives, where one of them is guaranteed to be correct and secure (but we do not know which one), and produces a single combined correct and secure primitive.
Combiners and universal constructions have been formally studied in this work. The authors formally prove that the existence of a $(1,n)$-combiner for a primitive implies a universal construction of the primitive.
Then, their paper also provides a $(1,n)$-combiner for key agreement protocols; by their previous result, this implies a construction of universal key agreement. Furthermore, their construction is round-preserving: the final key agreement has the same round complexity as the candidate which had the highest round complexity in the combination.
This is actually more general than the result you are looking for, because a PKE is just a 2-round key agreement. Indeed, take a 2-round key agreement protocol between Alice and Bob, where Alice speaks first. Define the first flow of Alice to be the public key, and the secret state that she keeps to be the secret key. Given this first flow, Bob can compute his output, i.e., the shared key (since he will not receive any further message). An encryption of a message $m$ can then simply be defined as (second flow of the protocol, $K \oplus m$) (where $\oplus$ denotes the bitwise XOR): given the second flow and her secret state, Alice can recover $K$ (by the correctness of the key agreement), from which she can unmask $K \oplus m$ and retrieve $m$. Security of the encryption scheme follows from the unpredictability of the key in the KA protocol.
Furthermore, this is actually a 2-way equivalence: given a PKE, it is straightforward to build a 2-round KA protocol (I'll let you check it).
Summing up: there is a $(1,n)$-combiner for two-round key agreements (hence in particular for PKE) by the result of the work I pointed to above, where the result of the combination is still a 2 round KA. By their other result, this implies a universal construction of two-round key agreement. By the simple reduction I gave above (which is a standard exercise), this implies a universal PKE.


Does "hash than sign paradigm" apply to ECDSA cryptography? From wikipedia https://en.wikipedia.org/wiki/Digital_signature#How_they_work
and other articles I see that: "There are several reasons to sign such a hash (or message digest) instead of the whole document."
But they are related to RSA.

Does it make sense to follow this rule for Ed25519 signature scheme?

Quick answer: You do not have to hash the inputs to Ed25519 because hashing is already part of Ed25519 itself.  If you do hash inputs in advance, you become vulnerable to collisions in the hash function you use.

Longer answer:

This rule does not make sense, period, because hashing is an integral part of a secure signature scheme.  It is a design principle to use a hash function to compress a message into an element of a mathematical structure that can be combined with a private key to yield a signature verifiable by the related public key.  This was first described by Michael Rabin in 1979.  Today, every serious signature scheme involves a hash of the message as a first step, with some variations.  Any system or textbook that tries to separate the steps of ‘hashing and then signing’ is dangerous.

Here's an example of an RSA-based signature scheme: A signature on a bit string $m$ under a public key $n$, a large integer with large prime factors, is an integer $s$ such that $$s^3 \equiv H(m) \pmod n,$$ where $H$ is a random function from bit strings to positive integers below $n$.

The hash $H$ is an integral part of this signature scheme because if you didn't use it, and instead used the equation $s^3 \equiv m \pmod n$, then I could trivially forge the signature $s = 0$ on the message $m = 0$, or $s = 2$ on the message $m = 8$.  The use of $H$ means I can't use the advanced technique of computing integer cubes on my pocket slide rule to forge signatures, because I don't have a hope of finding an $m$ with any prescribed hash value.

In the case of Ed25519, a signature on a bit string $m$ under a public key $A$, a point on an elliptic curve, is (roughly, with details of encoding and cofactors elided; see the Wikipedia article for more detail and references) a pair $(R, s)$ of a point $R$ on the curve and an integer $s$ such that $$[s]B = R + [H(R, A, m)]A,$$ where $B$ is a standard base point on the curve, $H$ is a random function from two curve points and a bit string to an integer below the order of $B$, and $[s]B$ etc. denote scalar multiplication on the curve.

Hashing a per-signature randomization and the public key together add some security beyond the simple RSA-based scheme above: hashing in per-signature randomization obviates the need for $H$ to be collision-resistant in practical realizations (the lapse of which in practical systems using MD5 has had serious consequences), and hashing in the public key mitigates multi-target attacks and prevents key malleability—finding two distinct keys under which a signature is valid.