Breaking zero knowledge protocol for graph hamiltonicity The FLS zero knowledge protocol for graph hamiltonicity proceeds as follows.

The prover (proving graph hamiltonicity of graph G) picks a random cycle graph C, and sends its commitment to verifier.

Verifier picks a random bit b and sends it to sender.

If b = 0, then prover decommits all the edges of graph, and verifier verifies if its a cycle graph.

If b = 1, then prover computes isomporphism between hamiltonian cycle of G and cycle graph C. It then decommits all the edges in C that are not present in the isomporphism of G.

This protocol is proven to be honest-verifier zero knowledge in many places.
How can a dishonest verifier break ZK property of this scheme? A dishonest verifier can break ZK property only if he can compute bit b depending on commitment(C) and learn some info. But that would violate hiding property of commitment scheme right?

The protocol for Hamiltonicity is by Blum and not FLS (FLS indeed use it). The protocol as you presented it is zero-knowledge for a malicious verifier as well. However, it is not known to be zero-knowledge when run in parallel (in order to get negligible soundness error). On the flip side, we also do not know how a dishonest verifier can do anything.

What do we know about the parallel repetition of Hamiltonicity?

First, we know that it is not black-box zero knowledge; see On the Composition of Zero-Knowledge Proof Systems.

Second, it is possible to prove that $log^2 n$ repetitions of the proof is actually zero knowledge in the unlikely case (not believed to be true) that Circuit-SAT on $n$ variables can be solved in time $2^{\sqrt{n}}$. This demonstrates that it would be very hard to prove that this protocol is not zero knowledge, without proving strong lower bounds on CSAT (note one could theoretically prove this under such an assumption, but no one knows how to do this). This proof can be found in Section 8 of Lower Bounds for Non-Black-Box Zero-Knowledge.

Third, we can prove that parallel Hamiltonicity is witness indistinguishable.

Finally, it is clearly honest-verifier zero knowledge.


Perfectly secure shift cipher Prove that if only one character is encrypted using a shift cipher, then the shift cipher is perfectly secure.

I want to show that $P(P=p | C=c)=P(P=p)$. But I don't know how to relate. Can anyone guide me?

Since you encrypt just a single letter, there are $26^2$ combinations of $p$ and $c$ where $c=E(p)$. This is because there are $26$ possible shift keys in the key space, an therefore each $p$ can be mapped to one of $26$ letters in the code space. Now, assuming that the key is distributed uniformly in the key space, each of those combinations of $(p,c)$ has a probability $\frac{1}{26^2}$. From base low we have:
 $$P(P=p\mid C=c) = \frac{P(P=p\text{ AND }C=c)}{P(C=c)}.$$ Now,
 $$P(P=p\text{ AND } C=c) = P(p,c) = \frac{1}{26^2},$$ and assuming uniform distribution $P(C=c) = 1/26$, you get $P(P=p|C=c) = \frac{1}{26} = P(P=p)$. QED


What use cases would benefit from a faster RNG? The paper “Explicit Two-Source Extractors and Resilient Functions” (PDF) by Eshan Chattopadhyay and David Zuckerman is described by some as being a technological leap in RNG – opposed to slow and incremental benefits over time.

What benefits would a faster RNG have for cryptography in general? Does this make some formerly implausible scenarios possible?

This paper isn't about a faster RNG, and it's mostly only of interest in a computer science context rather than in an applied cryptographic context. These results reduce the theoretical requirements needed from two weak sources of randomness in order to combine them into a source of true randomness. However, in the applied world, we already have "enough" — a few bytes can seed a CSPRNG that will generate effectively infinite computationally-random bytes.

When systems today fall over due to randomness issues, it's usually due to systems-engineering failures: a good RNG wasn't used (despite them being widely and easily available), or not enough initial randomness was seeded (e.g., /dev/urandom on an embedded device), or a virtual machine was copied and restarted with the same initial random seed. These classes of problems aren't solved by improving our sources of randomness.

To your question directly, a faster RNG isn't of much practical use. A stream cipher seeded with enough randomness is effectively a DRBG, and can produce random bits extremely quickly — far more quickly than is needed for the overwhelming majority of use-cases. The operations that use that randomness typically execute far more instructions than do the operations to generate it.

Thomas Ptacek's response to this story on Hacker News is how I expect most crypto people feel about this.


TLS AES_XXX_CCM mode of operation is encrypt-then-mac or mac-then-encrypt? There are number of definitions completely confusing me.
in https://en.wikipedia.org/wiki/CCM_mode we have

"As the name suggests, CCM mode combines the well known CBC-MAC with the well known counter mode of encryption. These two primitives are applied in an "authenticate-then-encrypt" manner, that is, CBC-MAC is first computed on the message to obtain a tag t; the message and the tag are then encrypted using counter mode. One key insight is that the same encryption key can be used for both, provided that the counter values used in the encryption do not collide with the (pre-)initialization vector used in the authentication."

again in NIST  800-38C specification and RFC6655 we have

"In generation-encryption, cipher block chaining is applied to the payload, the associated data, and the nonce to generate a message authentication code (MAC); then, counter mode encryption is applied to the MAC and the payload to transform them into an unreadable form, called theciphertext"

but RFC7366 states than TLS should follow encrypt-then-mac policy

Given a specific block cipher such as AES, CCM is a specific AEAD scheme: authenticated encryption with associated data, with IND-CCA3 security, loosely meaning it resists eavesdropping and forgery simultaneously.

Encrypt-then-MAC is a generic way to compose an AEAD scheme out of a cipher and a MAC.  It always works, in the sense that if the cipher has the standard IND-CPA security expected of it, loosely meaning it resists eavesdropping, and the MAC has the standard UF-CMA security expected of it, loosely meaning it resists forgery, then the encrypt-then-MAC composition has the standard IND-CCA3 security expected of it.

MAC-then-encrypt is another generic way to compose an AEAD scheme out of a cipher and a MAC.  But it doesn't always work: there exist IND-CPA ciphers and UF-CMA MACs whose MAC-then-encrypt composition is not IND-CCA3.  And it has very sharp edges: some ciphers, such as AES in CBC mode, reject certain messages on decryption due to padding, but the MAC rejects them differently, and the difference reveals information about the plaintexts of messages.  This led to the Lucky 13 attack on TLS.

However, while MAC-then-encrypt doesn't always work, it sometimes works, and in the specific case of AES-CCM, which is a MAC-then-encrypt composition of the cipher AES-CTR and a length-tagged variant of the MAC AES-CBC-MAC, it turns out to have IND-CCA3 security and fewer sharp edges.  (Safety of randomly chosen nonces, and reuse of nonces, are left as a story for another day.)

Traditionally TLS used a generic MAC-then-encrypt composition for a cipher and a MAC negotiated independently between the server and the client.  Eventually the TLS designers realized this was a mistake, and the IETF adopted two remedies for TLS 1.2:

RFC 5246 ‘TLS 1.2’, §6.2.3.3 ‘AEAD Ciphers’: Let the server and client negotiate a specific AEAD scheme, such as AES-GCM or AES-CCM.
RFC 7366 ‘Encrypt-then-MAC for TLS and DTLS’: Let the server and client negotiate cipher and MAC independently as before, and also let them negotiate the use of encrypt-then-MAC composition instead of MAC-then-encrypt composition.

In TLS 1.3, RFC 8446, all cipher suites are AEAD; there is no generic composition at the layer of the TLS protocol, making the protocol substantially simpler.


Is my proof of Asmuth-Bloom scheme's perfection correct? I am trying to understand how Asmuth-Bloom's secret sharing is perfect. My "proof" so far (in a 3 out of 4 scheme):

$y=s + a * m_0 \bmod m_1 * m_2 * m_3$

Having $k-1$ shares, it will yield a valid solution for the CRT, but not a unique one. 2 shares yield $x = y' \bmod m_1 * m_2$
Therefore, we know that $y = y' + z * m_1 * m_2$ and also that $y = [0;m_1*m_2*m_3]$
But since we do not know the exact range of $y$, since $m_3$ is missing, we can not just simply guess $z$ and therefore guess $y$.
However, I see a sequence of following primes used a lot, so when we know $m_1$ and $m_2$ we could just assume $m_3$ is the next prime and guess values for $z$ and therefore $y$ right?

Example with numbers:
$m_0 = 43,\space m_1=131, \space m_2=137, \space m_3 = 139, \space m_4=149, \space s=42, \space a = 476$
$y = 42 + 476 * 43$
$y = 20510 \bmod 2494633$

$s_1 = (74, 131), \space s_2 = (97, 137), \space s_3 = (77, 139), \space s_4 = (97, 149)$

CRT with two shares:

$x \equiv 74 \bmod 131$
$x \equiv 97 \bmod 137$
$x \equiv 2563 \bmod 17947$

So now we could start guessing

$y_0 = 2563 + 0*17947$
$y_1 = 2563 + 1*17947$
$y_2 = 2563 + 2*17947$
$y_n = 2563 + n*17947$
and, with the knowledge (or assumption) that $m_3$ is the next prime after $137$, a max value of
$y_{138} = 2563 + 138 * 17947$
since $2563 + 139 * 17947$ exceeds $m_1*m_2*m_3$

So we have $138$ values to guess the secret from.
$s_n = y_n \bmod 43$

From my conclusion, this would not be a perfect scheme, but everyone states it is. So where am i wrong?

Okay, so i was finally able to figure out a solution for this.
The scheme does indeed yield 138 valid results to guess the secret from. However, since they already know the secret lies in $\mathbb{Z}_{m_0}$ there are only (in the example above) 42 possible secrets anyways. Since $a$ is uniformly distributed, the scheme does indeed leak some probabilistic information about the secret when you apply $\bmod 43$ to all 138 possible values, as seen in:

So for example, an attacker could determine that 2,3 or 4 are more likely than for example 0 or 1.
However, there is no information leaked about the secret itself.


1/4 oblivious transfer construction from 1/2? I have a question about OT?
we assume that sender has $m_0,m_1,m_2$, and $m_3$ and selects random $S_0, S_1, S_2, S_3, S_4, S_5$
and compute this statement than sends to receiver.

$C_0 = S_0 \oplus S_2 \oplus m_0$

$C_1 = S_0 \oplus S_3 \oplus m_1$

$C_2 = S_1 \oplus S_4 \oplus m_2$

$C_3 = S_1 \oplus S_5 \oplus m_3$

Can i change above statement into this?

$C_0 = S_0 \oplus S_2 \oplus m_0$

$C_1 = S_0 \oplus S_3 \oplus m_1$

$C_2 = S_1 \oplus S_2 \oplus m_2$

$C_3 = S_1 \oplus S_3 \oplus m_3$

No, your proposed alternative allows the attacker to deduce things beyond the value he selects.

For example, suppose that during his OT transfers, he decides to learn the values $s0$ and $s2$, allowing him to recover $m0 = c0 \oplus s0 \oplus s2$.  That is intended to be allowed, and so is fine as far as it goes.

However, the receiver can also deduce the value $m1 \oplus m2 \oplus m3 = c1 \oplus c2 \oplus c3 \oplus s0 \oplus s2$.  As the receiver is supposed to learn only the value he selected ($m0$ in this case), and nothing about the other messages, this is a violation of the OT properties.


Why does a Hashing Function produce good Random Numbers if Input is random? I've heard about using a hash approach to create random numbers based on two independent entropy sources A, B:

$h_{i} = H(a_i+b_i)$

$H$ could be for instance SHA-1, or SHA-256.

My questions are:

1)

I read that hashing an input of s Bits to an output of n bits will reduce entropy because of truncation. The accepted answer in

How much entropy is lost via hashing when you add known or low entropy data?

sounds totally reasonable for me. But what does it mean in terms of quality of randomness? When an input of, lets say, 1024 bits is hashed to 256 bits, of course entropy gets lost. But can't I say, that the "remaining" 256 bits are still good random numbers and not comromised by the truncation of length? Isn't it just the rate of available random bits which is reduced, not the quality of randomness?

2)

Why is a hash function $y=f(x)$ like SHA-1 a random oracle at all?
So far I know, it means, that the set of arguments x is mapped to a set of results y, distributed equally over $2^{256}$ values in the case of SHA-256. Why is this the case? Is there a rigorous proof for that or is it only a working assumption? It would mean for my feeled understanding:

An s-bit value $x_1$ feed into Hash results in n bits $y_1$,
An s-bit value $x_2$ feed into Hash results in n bits $y_2$,
When $x_2$ differs from $x_1$ in only one bit position, all bits of $y_1$ are totally "uncorrelated" to the bits of $y_2$, regardlesss of the changed bit position.

Is that right?

Although I feel that this should be the case for a good hash of course, I wonder if the goal is only approximately achieved or really accurate?
(Even the word "uncorrelated" is difficult to grasp for me, since, in fact,  there is some kind of correlation over the hash-algorithm)

I mostly agree with your statements.
To answer your questions:

Obviously the entropy reduces if the entropy of $s$ is greater than $2^n$. Using a good hash will however result in that maximum amount of entropy.
Indeed, SHA-1 is not a random oracle. It is a common assumption that a hash function acts like one. Since collisions for SHA-1 have now been practically found that assumption is clearly wrong. The practically used primitives, like compression functions and block ciphers, are thoroughly cryptanalyzed but not proven secure.


Using hashed password as shared secrets. Good or bad idea? I built a system that allowed users to generate an unlimited number of email addresses.

Instead of storing each one in a db, I created addresses dynamically and made the address an hmac signed message with the shared secret being the bcrypt hashed version of their account password. e.g. 1948417:11eea538fdc926e38ff97689d913d34da152b072@example.com

Security wasn't critical and it worked pretty well, but I'm considering using the same strategy for something a little more delicate.

So, the question is... Is using a hashed password as the shared secret a good idea or bad idea?

I'm not sure about your specific system; this only addresses "can a key derived from the password make a good shared secret?"

The most common password hashing functions are actually designed for exactly this purpose -- deriving a cryptographic key from a (weak) password. That's actually what PBKDF2 stands for: "password-based key derivation function #2" (scrypt and bcrypt don't have it in their name, but are also key derivation functions). It's also used in GPG, and for file and disk encryption, etc. Kerberos does so as a login mechanism - when you send the KDC your username, you get information that lets you authenticate as that user, encrypted with a key derived from the user's password.

Passwords tend to be low-entropy, far below that required of a cryptographic key. PBKDFs mitigate that by having a salt (to prevent dictionary attacks, for instance by having a list of the keys derived from the 10000 most common passwords) and by being as time-consuming as you please, which means that while an attacker doesn't have to try as many possibilities as with a random key, it takes them a long time to try each possible password.

So in general, password-derived keys make fine shared secrets. There are some catches (notably: if an attacker compromises them, they've compromised the shared secret; this is why Kerberos KDCs have to be so secure). But there's nothing generally wrong with the concept.


Unique/Fast Hash for fixed size strings I have a need to generate a unique hash for millions of Strings of same length.
Would prefer a non cryptographic hashing algorithms for performance reasons.
The hash can be of length upto 24 bytes, but hash collisions are a strict no.
A dumb implementation I can think of is to use the String.hashCode() method in java as 4 bytes [of the allowed 24 bytes]

First 4 bytes = String.hashCode(string)
Second 4 bytes = String.hashCode(reverse of string)
Third 4 bytes = String.hashCode(first half of string)
Fourth 4 bytes = String.hashCode(last half of string)

Thats just 16 bytes of hashes... and as the size of the string is fixed, would this give a unique 16byte hash for every different string? This is similar to using a bloom filter, but I need to ensure there are absolutely NO hash collisions.
Keeping this hash is memory if more efficient than keeping the entire string in memory.

It's mathematically not possible for a hash function to guarantee an exact probability of zero collision if it shrinks space, just by virtue of the pigeon hole principle.
This means that if, for example, targeted input is on average ~20 bytes, and content can be anything within these 20 bytes, but then you want to map that "space of all possibles" into a fixed-size space of 16-byte, thanks to a 128-bit hash function, it "shrink" the space, and therefore it is mathematically necessary for many entries to share the same hash value.
That being said, it's possible to make the probability of such collision to occur so small that it does not make sense to worry about it. For example, using a 128-bit hash, the probability of collisions between millions of elements is so ridiculously small that one would have more chances to get biten by a shark and striken by a comet and win the lottery ticket all together at the exact same time. If you start to worry about that, then you have to worry about a hidden bit-flip happening inside the cpu due to a rare X-ray interaction from solar flare, which is much more probable. And of course, there are myriads of other problems, starting with software bugs, which are way way more probable than that. So focusing on the infinitesimal risk while being blind to much more common sources of issues is an incorrect stance.
Side note : not sure if it matters in your case, but note that in the case of expanding space, or even identical space, it's possible to guarantee no collision with some hash functions. For example, XXH64 and XXH3_64bits guarantee no collision for 8-bytes->8-bytes hashes. Similarly, XXH3_128bits guarantees no collision for 16->16 hashes. It's even easier when expanding space, for example for mapping 6-bytes input into 64-bit hashes results in no collision.
Not all hash functions guarantee this outcome though. Select the ones advertising bijective transformations.


Weak key schedule IDEA Why was such a weak key schedule chosen for IDEA?

The key schedule of IDEA works like this:
Divide the key (128 bit) into 8 round keys, each 16 bit long. This are the first 8 "round" keys (6 keys per round). Rotate the original key by 25 bit to the left. Repeat this until we got the needed 52 round keys for 8.5 rounds. (4 keys for the last "half" round.)
This key schedule is fully linear and patterns in the key exist even in the last round keys with nearly no change. A high number of zero bits in the key is very problematic for the cipher because the number stays the same through the whole key schedule. Many attacks exploit this behavior.

This can be seen with a small example encryption. (Key ($K$) and plaintext ($P$) in hexadecimal formatting, leading zero bytes were omitted. )
  $$ K = 00, P = 00, \operatorname{IDEA}(K,P) = \text{0001 0001 0000 0000} $$
  $$ K = 00, P = 01, \operatorname{IDEA}(K,P) = \text{0013 fff5 0012 0009} $$
  $$ K = 00, P = 02, \operatorname{IDEA}(K,P) = \text{0191 0059 011c ff32} $$
  $$ K = 00, P = 03, \operatorname{IDEA}(K,P) = \text{038f 0099 02d6 fe33} $$
  $$ K = 00, P = \text{01f0}, \operatorname{IDEA}(K,P) = \text{1841 fbc1 ef20 f270} $$
  $$ K = \text{0d50}, P = 00, \operatorname{IDEA}(K,P) = \text{3fb2 5ff2 055d 16a6} $$
(Source: IDEA calculator (Java))

Further analysis of the data and the encryption process shows very slow avalanche effect when high amount of zero bits were in the plaintext or ciphertext. Why was this not recognized and solved? Was this kind of problem not known at the time as IDEA was invented? Or is this no real problem because of the low probability of this effect on random keys?

The paper "Weak Keys for IDEA" (1993, PDF) shows that even a small correction could solves this problem, like the XOR of a constant to every round key before using it. The constant $\text{0dae}$ (16 bit, hexadecimal notation) was chosen as an example, but the exact value is not critical to solve the problem as stated by the paper.

Are there any papers which descripe the development process of IDEA? Maybe they could explain some thoughs about the key schedule.

Such a weak key schedule was chosen since the key schedule "theory" was not well developed by that time. Designers just modified the key schedule of DES a bit. Remember that these key schedules had to be optimized for hardware, and any extra operation would cost something in terms of area.


Stream vs Block cipher: Synchronising and the receiver I am learning cryptography at school and I was wondering:

How are the blocks/streams after decryption synchronized at the receiver to form one long meaningful message?
Am I right by saying that stream cipher will incur a LOT more overhead while synchronizing?

The answer to your question will very much depend on implementation details, but you might not be versed enough in cryptographic protocol development to know exactly what to ask, so I'll take a stab at answering this and hopefully my attempt will help you refine the question as needed.

  How are the blocks/streams after decryption synchronized at the receiver to form one long meaningful message?

Sychronization is often done before decryption. Wrap the ciphertext with a protocol header, throw a sequence number into the protocol header, authenticate the entire thing (header and ciphertext). The receiver, after checking authentication, can order the ciphertexts using the sequence number and then decrypt.

  Am I right by saying that stream cipher will incur a LOT more overhead while synchronizing?

If you look at my description of how synchronization could be done, you'll notice that it is symmetric-key cipher agnostic. Thus the synchronization will be the same whether we are using a block cipher or a stream cipher.


Monotonicity of min-entropy Let $Z^t = (Y_1,\ldots,Y_t)$ be a sequence of random variables each taking values in $Y$. The random variables are not necessarily i.i.d but we know the joint distributions. i.e for every $z = (z_1,...,z_t)$ we know $P^{Z^t}(z)$

The min-entropy of a random variable $X$ is defined as $-\log_2(\max P(x) )$ for x in the value set of $X$.

Finally, we define a sequence of values $H^\infty(t) =  -\log_2(\max P^{Z^t}(z))$ for $Z^t$ defined as above.

How can we show that $H^\infty(t)$  is monotonically increasing in t? i.e for $t' \geq t$ it is the case that $H^\infty(t') \geq H^\infty(t)$.

What I am trying without success is to show that $\max P^{Z^t}(z^t) \geq \max P^{Z^{t'}}(z^{t'})$ where $t \leq t'$.

Let's make it slightly simpler by proving the case of two variables with no tuple indexing to clutter it up.  Fix two random variables $X$ and $Y$.  Is $H_\infty[X] \leq H_\infty[(X, Y)]$?

For each $x$, we have $$\Pr[X = x] = \sum_y \Pr[X = x, Y = y].$$  Note that since probability masses are always positive, $\max \Pr[\cdots] \leq \sum \Pr[\cdots]$; then the sense will get reversed because $p \mapsto -\log p$ is a decreasing function:

\begin{align}
  H_\infty[X]
  &= -\log \max_x \Pr[X = x] \\
  &= -\log \max_x \sum_y \Pr[X = x, Y = y] \\
  &\leq -\log \max_x \max_y \Pr[X = x, Y = y] \\
  &= -\log \max_{x,y} \Pr[X = x, Y = y] \\
  &= H_\infty[(X, Y)].
\end{align}

Then to prove that $t \mapsto H_\infty[(Z_1, \dots, Z_t)]$ is increasing, take $X = (Z_1, \dots, Z_t)$ and $Y = Z_{t+1}$.


Asymmetric code signing also tied to a device I have an asymmetric key pair.  The public key is stored in many targets.  Is there a way to take that private key K, derive a new private key K' with a known value x, sign the code, and then each target can take the same value x and derive a public key that pairs with K' and verify the code?

I want to authenticate code for only a specific device, but only have the ability to store a common public key in many targets.  So the known value x would be some kind of hardware serial number.

This is sometimes called a hierarchical signature scheme or a blinded signature scheme.  Examples of the idea are being considered or adopted in Tor for next-generation onion services, in Bitcoin BIP32 for cheap many-address single-private-key wallets, and possibly by the IETF for standardization.  There was a good summary discussion with references on the CFRG mailing list a few months ago.  But the idea is not currently standardized, and implementations aren't littering the roads like implementations of ordinary signature schemes are.

$\newcommand{\Z}{\mathbb{Z}}$The basic idea of an elliptic-curve signature scheme using an order-$\ell$ group of $k$-rational points of an elliptic curve $E$ is that a private key is a secret scalar $a \in \Z/\ell\Z$, a public key is the curve point $A = [a]P$ where $P$ is a standard $k$-rational order-$\ell$ base point, and a signature is some point and scalar that satisfies some verification equation involving $A$.

Typical examples in this design space are ECDSA, for an archaic slow error-prone one, and EdDSA, for a modern fast safe one.  They can both be adapted to hierarchical/blinded schemes.

The basic idea of an elliptic-curve hierarchical/blinded signature scheme is to ‘tweak’ the public key and private key in the same way by another scalar $t \in \Z/\ell\Z$.  The derived private key is the scalar $a_t \equiv t a \pmod \ell$, and the derived public key is the curve point $A_t = [t]A = [t a]P = [a_t]P$.  The signature verification equation is the same as in the underlying signature scheme.  Anyone who knows the tweak and the original public key can verify signatures using the derived public key; anyone who doesn't know the tweak can't tell a derived public key from any other curve point.

A devil lurks in the details like Sean Spicer in the bushes: you may need to pay attention to cofactors, malleability of signatures and public keys, etc.—that's why some people want the IETF to standardize a hierarchical signature scheme for the internet, so that individual application developers need not learn the hard way about covfefe or other similar pitfalls of novel developments in public-key cryptography.


How to determine the signature type of RSA with a hash function? I have the following function:

  rsaSha512Sign(arg1, arg2) - arg1 is the private key PEM,
  arg2 is the data to sign using SHA-512 with RSA.
  Returns the signature as a Base64 String.

With no additional documentation or source code available.

I assumed the description above meant to first hash with SHA-512, then apply RSA. However the signature is much longer than the hashed arg2.

How can I determine which algorithm was used?

It is extremely likely to be either RSA with PSS padding or RSA with PKCS#1 v1.5 padding, the latter being the most likely.

Although there are many signature schemes, PKCS#1 v1.5 seems to be the most used. When many crypto libraries were devised it was the only scheme that was described by the RSA labs (that created the PKCS standards), so many older libraries forgot to document it. There are however other schemes, such as the aforementioned RSA-PSS and RSA with (partial) message recovery, defined in ISO/IEC 9796-2.

If you sign two times and the output is twice the same then it is not PSS and PKCS#1 v1.5 would be the main suspect:

  RSASSA-PSS is different from other RSA-based signature schemes in
     that it is probabilistic rather than deterministic, incorporating a
     randomly generated salt value.

Both PSS and PKCS#1 v1.5 are defined in RFC 3447. And yes, the hashing itself is almost always included in the method, so usually you just feed it the message itself.

Both PSS and PKCS#1 v1.5 first perform modular exponentiation which produces a signature size that is bounded by the size of the modulus. However, after that the function I2OSP is performed, which makes the signature the same size as the modulus in bytes. As the modulus defines the key size, the signature is the same size as the key size in bytes.

So you cannot use the resulting signature size to determine the signature algorithm.

If you have the RSA public key you could perform a raw modular exponentiation (called textbook RSA, "none with RSA", "raw RSA" or similar) with the public exponent on the (decoded) signature. Then you could compare the result with the padding format. Usually it is easier to just try PKCS#1 v1.5 and PSS though.

Base 64 converts a signature to the base 64 alphabet, expanding the size with about 33/37% compared to the key size, assuming that the string is encoded as ASCII or compatible.


Is rubberhose cryptanalysis a sidechannel - formally? I recently was engaged in a discussion in Sec.SE where somebody used the term "sidechannel" to actually mean "circumvent the encryption".

By what he said it was clear, that he wanted to not bother with crypto at all and this is - in my view - not a sidechannel. However, rubberhose cryptanalysis was also mentioned and it was argued that rubberhose cryptanalysis is a sidechannel because the definition of sidechannel includes the physical implementation of the cryptosystem and the human is part of the physical implementation.

So ultimately my question:
Can rubberhose cryptanalysis formally be considered a sidechannel?

The definition of sidechannel quoted in this context:

  In cryptography, a side-channel attack is any attack based on
  information gained from the physical implementation of a cryptosystem,
  rather than brute force or theoretical weaknesses in the algorithms
  (compare cryptanalysis).

I've also seen Wikipedia:

  Attempts to break a cryptosystem by deceiving or coercing people with
  legitimate access are not typically called side-channel attacks

But I'm asking if it is allowed by the definition of sidechannel attacks to include rubberhose cryptanalysis.

Yes. A human surely is a physical component of the cryptosystem. Even if we ignore the "physical" aspect, we have

  implementation of a cryptosystem, other than brute force or theoretical weaknesses in the algorithms.

If a key is not secure (ie. in the mind of a human who can be persuaded to divulge it), acquiring this password and bypassing the crypto would be a side-channel attack IMO.


Is exponentiation of a fixed generator modulo a prime collision-resistant? Let $p$ be a prime number, and $g$ a generator of $\mathbb Z/p\mathbb Z$. For a message $m$, define the hash function $$h(m) = g^m \pmod p.$$  Is $h$ collision-resistant?

Let $m$ be arbitrary. Then $m'=m+p-1$ yields a collision with $h(m)=h(m')$ as $m\equiv m'\pmod{p-1}$ and thus by $p-1$ being the relevant group's order $g^m\equiv g^{m'}\pmod p$.

Or formulated differently (using $g^{p-1}\bmod p=1$): $$h(m')=g^{m+p-1}=g^m\underbrace{g^{p-1}}_{1}\equiv g^m=h(m)\pmod p$$


Most influential/illuminating papers/books/courses on lattice based cryptography? I'm interested in some sort of "compendium" on lattice-based crypto. There are a bunch of maths behind FALCON and other stuff. A lot of articles are devoted to lattice crypto, but not of them are of paramount importance. The other problem is that there are papers that are obviously influential, but they are hard to understand "from scratch".

To start with something I may notice some of them:

GPV framework:

"How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Constructions".

Cryptanalysis:

"Learning  a  Parallelepiped:  Cryptanalysis  of  GGH and NTRU Signatures"

Basic courses :

winter school on lattice-based crypto (https://cyber.biu.ac.il/event/the-2nd-biu-winter-school)
Regev course on lattices in CS (https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/)
Vinod's course (http://people.csail.mit.edu/vinodv/6876-Fall2015/index.html)

Surveys:

"Lattice-based Cryptography" part from the book "Post-Quantum Cryptography".
"A Decade of Lattice Cryptography", Peikert.

Unfortunately, I didn't find anything on discrete Gaussian distributions and properties of continuous Gaussians (why is it "not far from" uniform over any "small" parallelopiped), how to generate them; on smoothing parameter and its "intuitive" meaning. Also, reductions from average to worst-case are somewhat tricky and uneasy to understand form Ajtai papers. And there is a direction of research on ideal lattices, which somehow related to integer rings of number fields ($\mathbb{Z}_K$), this is completely obscure.

You seem to have a few questions:

  Why are Discrete Gaussians "not far" from the uniform distribution when you work mod the lattice?

This is worked out in the paper they are introduced in (Miccancio Regev 2004). See Lemma 4.1 in particular.

  How to generate them?

It depends on whether you care about constant-time generation or not. Either way, there are a few techniques. These include using "generic samplers" (that work for any discrete probability distribution), including:

Inverse CDT (cumulative density table) --- If $F_X(x)$ is the cumulative density function of $X$, and $U\sim \mathcal{U}([0,1])$, then $F_X^{-1}(U)\sim X$. This can be used to generate samples from any distribution.
Knuth-Yao sampling --- You create a certain binary tree, then preform an unbiased walk on it, and return a sample based on what leaf you end up in. Very entropy efficient (and where the "Entropy is equal to the # of coin flips you need to sample from a distribution) comes from, but hard to make constant time without destroying the entropy efficiency.
Alias sampling. A little harder to explain, but you can reduce sampling from any distribution to sampling from a uniform distribution, then sampling a (pre-computed) biased coin depending on the uniform value sampled.

There is a non-generic sampler known as Karney's method as well. Moreover, there's a sampling technique known as "convolution sampling", which allows one to generate discrete gaussians of larger parameters from discrete gaussians of small parameters, so one can restrict to the small parameter case.

Recent work can be seen here, and the references can be useful pointers for the rest of the literature (it misses out on some recent work trying to make KY sampling constant time, but that's about it).

  Smoothing Parameter's intuitive meaning

Intuitively, it's the amount of Gaussian mass one has to place on each lattice point such that it "blurs" throughout space.
One can think of the lattice $\Lambda$ as initially a set of points (having discrete gaussians of parameter $\sigma$ of "0" on each point).
As you increase $\sigma$, these points "blur" out.
If you increase $\sigma$ enough, they'll "cover" the whole space (and then, when working mod the lattice, will approach the uniform distribution).
The smoothing parameter measures when a "phase transition" of this form happens, between being quite close to uniform, and non-uniform.

If you're more familiar with geometric notions of the lattice one could think about continually increasing balls around lattice points (instead of gaussians), until one finally covers all points of the ambient space in some ball.
This has another quantity associated with its phase transition known as the "covering radius".


Function families from lattices On this course, Micciancio talks about function families (functions parametrized by some value) that can be used in cryptography.

On page 2, he presents the following function family parametrized by bases of full-rank lattices:

For any invertible $ \mathbf{B} \in \mathbb{R}^{n \times n}$, let $f_\mathbf{B}(\mathbf{x}) = \mathbf{x} \mod \mathbf{B} = \mathbf{B} \left(\mathbf{B}^{-1}\lfloor \mathbf{x} \rfloor \right)$.

Clearly, there is a typo there, because $\mathbf{B} \left(\mathbf{B}^{-1}\lfloor \mathbf{x} \rfloor \right) = \lfloor \mathbf{x} \rfloor$ and this is at the same time independent of the basis and useless for cryptography.

So, maybe the correct definition must be $f_\mathbf{B}(\mathbf{x}) = \mathbf{x} \mod \mathbf{B} = \mathbf{B}  \lfloor \mathbf{B}^{-1} \mathbf{x}   \rfloor$. But in this case, the codomain $f_\mathbf{B}$ is the lattice $\mathcal{L}(\mathbf{B})$, but the text just below the definition says

  In other words, $f_\mathbf{B}(\mathbf{x})$ rounds $\mathbf{x}$ to the corner of the fundamental parallelepiped $f_\mathbf{B}(\mathbf{x}) + \mathcal{P}(\mathbf{B})$ containing $\mathbf{x}$. As defined, $f_\mathbf{B}$ is a function with domain $X \subseteq \mathbb{R}^n$ and codomain $\mathcal{P}(\mathbf{B})$.

So, do you have any idea of what the actual definition should be?

As pointed out by Chris Peikert in his comment, the actual definition must be

$f_\mathbf{B}(\mathbf{x}) = \mathbf{x} \mod \mathbf{B} = \mathbf{x} - \mathbf{B} \lfloor\mathbf{B}^{-1} \mathbf{x} \rfloor$.

we can see that the codomain of such $f_\mathbf{B}$ is the fundamental region $\mathcal{P}(\mathbf{B})$ as follows:

Write any given $\mathbf{x}$ as a linear combination of the columns $\mathbf{b}_1$, ..., $\mathbf{b}_n$ of $\mathbf{B}$, that is:

Let $\mathbf{x} = \mathbf{B}\mathbf{z}$ for some $\mathbf{z} \in \mathbb{R}^n$ (it's possible because $\mathbf{B}$ is fullrank, so its columns  span $\mathbb{R}^{n}$).

Let $\mathbf{t} = \mathbf{z} - \lfloor \mathbf{z} \rfloor$, so $\mathbf{t} \in [-1, 1)^n$ and $\mathbf{x} = \mathbf{B}(\mathbf{t} + \lfloor\mathbf{z} \rfloor)$.

Thus,

$f_\mathbf{B}(\mathbf{x}) = \mathbf{x} - \mathbf{B} \lfloor\mathbf{B}^{-1} \mathbf{B}(\mathbf{t} + \lfloor\mathbf{z} \rfloor) \rfloor = \mathbf{x} - \mathbf{B} \lfloor \mathbf{t} + \lfloor  \mathbf{z} \rfloor \rfloor = \mathbf{x} - \mathbf{B} \lfloor  \mathbf{z} \rfloor = \mathbf{B}\mathbf{t}$

and $\mathbf{B}\mathbf{t} \in \mathcal{P}(\mathbf{B})$ by definition of $\mathcal{P}(\mathbf{B})$.


Bit Commitment - from any One Way Permutations In the Wiki Page on Commitments, it is given that a commitment scheme may be perfectly binding or perfectly concealing but not both.

But in the following section about Bit-commitment from any one-way permutation, they mention that "This scheme is concealing..." and  "Perfect binding follows..."

It does seem like this commitment scheme is both binding and concealing. What am I missing here?

It is "computationally" concealing --- that is it conceals only to a computationally bounded adversary. Note that computationally hiding, perfectly binding and computationally binding, perfectly hiding commitment schemes are, both, possible.


How is Blakley's Secret Sharing Scheme perfect? Currently, I am trying to understand Blakley's secret sharing scheme. However, there seem to be multiple descriptions of it, which are very different from another, but everyone states that the scheme would be perfectly secure.

From my understanding it works like this:

a point $S$ in $t$-dimensional space is created with one coordinate being secret and the others randomly selected
$n$ hyperplanes through the point $S$ are created and distributed
to reconstruct the secret, $t$ hyperplanes are required, which will intersect at the point $S$.

However, from my understanding, if someone would possess one or more hyperplanes, they would know that $S$ lies somewhere on that hyperplane (or the intersection of multiple hyperplanes)

So my question is;

how is Blakley's scheme considered perfectly secure when an insider knows that the secret lies on his plane?

Okay so SEJPM's comment just gave me an answer or better made me realize my flaw:

Since the secret is only one coordinate (e.g. $x$) the information that the secret is on a specific infinite line is as much information as having none at all, since guessing $x$ of a point on $y = 5*x$ is worth as much as guessing $x$ of a point on $y = z * x$

The information would only be revealed if the secret would be the entire point, not just one coordinate.


Prove Vigenere cipher isn't perfectly secret As part of a homework assignment I have to prove/disprove that a Vigenère Cipher with a key of length n, uniformly distributed in the alphabet, on a plain text of length 2n, also uniformly distributed in the alphabet, is perfectly secret.

The only theorem we have seen so far concerning perfect secrecy uses entropy:
if the plain text and the cipher text are statistically independent (H(PlainText) = H(PlainText | Ciphertext)), the encryption is perfectly secret.
Computing H(PlainText) is quite straightforward given the text is uniformly distributed on an alphabet of 26 elements.

But I don't know how to compute the conditional entropy of the plain text given the ciphertext to prove that these two aren't equal (I understand that this type of encryption isn't perfectly secret, mainly because the key is of length n and not 2n).

What is the way to approach this?

One way to approach this is to look at the decryption process; the plaintext is a function of the ciphertext and the key.  The conditional probability says you know the ciphertext (entropy 0), you don't know the key (entropy $n \log_2 26$); what's the entropy of the decrypted plaintext (which is a function of those two)?  How does that compare to the entropy of an arbitrary plaintext of length $2n$?


Homomorphic encryption for multiplication (AND) on bits only? I am reading the Wikipedia article https://en.wikipedia.org/wiki/Homomorphic_encryption
and it lists unpadded RSA, ElGamal, Goldwasser-Micali, Benaloh, Paillier as possible partially homomorphic encryption (PHE) schemes.
Of these, only Goldwasser-Micali seems to be for bits and it is XOR-homomorphic. The other encryption schemes seem to be for group elements, and it seems like if you say you only encrypt 0 or 1 then the operations won't hold (because, e.g., $1+1 =2$ now).
Assuming that I only want to encrypt 0 or 1, is there a partial HE that can do ANDs (aka multiplication)? Or, is it only possible to do multiplication on a larger group?
I understand that many fully homomorphic encryption schemes do just work on bits, but then there's issues with noise growing/boot strapping. (Whereas, for example, multiplying two ElGamal ciphertexts together is a "clean" operation).
Is there a simple PHE that works on bits only and allows you to do an unbounded number of ANDs? Or is FHE required?
To try to give some context: what if there are $n$ people who are voting yes/no with 1 or 0 and you want to find out if the vote is unanimous for yes? I guess here there's some issue with having to do some sort of threshold decryption or multi-key encryption as well, and from my understanding from 2016/196 or 2017/956that makes the ciphertext be of size $n$ also, which seems like a big hassle for a simple operation. That's why I thought perhaps a PHE would be enough, and perhaps give you the chance of having smaller ciphertexts.

Assuming that I only want to encrypt 0 or 1, is there a partial HE that can do ANDs (aka multiplication)?

Yes.
In fact, there is a generic way of converting any additively homomorphic encryption scheme with large plaintext space into a PHE for AND with plaintexts in $\{0,1\}$.
Here is the idea: let $(\mathsf{KeyGen}, \mathsf{Enc},\mathsf{Dec})$ be an additively homomorphic encryption scheme; for simplicity, suppose that the plaintext space is $\mathbb{Z}_p$ for some large prime $p$. Define $(\mathsf{KeyGen}^*, \mathsf{Enc}^*,\mathsf{Dec}^*)$ as follows:
$\mathsf{KeyGen}^*$: same as $\mathsf{KeyGen}$.
$\mathsf{Enc}^*(m)$: if $m=0$, sample a uniformly random value $R \gets \mathbb{Z}_p$. If $m = 1$, set $R \gets 0$. Output an encryption $\mathsf{Enc}(R)$ of $R$ with the original scheme.
$\mathsf{Dec}^*(C)$: decrypt $C$ with $\mathsf{Dec}$ to get $R$. If $R = 0$, output $1$; else, output $0$.
Claim: $(\mathsf{KeyGen}^*, \mathsf{Enc}^*,\mathsf{Dec}^*)$ is a multiplicatively homomorphic encryption scheme over $\{0,1\}$, with negligible correctness error; the procedure for homomorphic multiplication is just the procedure for homomorphic addition of the original scheme.
This is easy to check: a sum of any number of encryptions of zero is still an encryption of zero. However, if a single ciphertext encrypts a nonzero value, the result becomes nonzero. In terms of the scheme $\mathsf{Enc}^*$, this translates to the fact that the AND of many 1's is still 1, but if a single bit is zero, the result is zero.
Since the addition is done mod $p$, there is a tiny chance that a sum of nonzero values will give a zero, hence the homomorphic algorithm has imperfect correctness; however, if $p$ is large enough, this happens only with negligible probability.
Two additional comments:

The above transformation gives an additional useful property: if the original encryption scheme is rerandomizable, then so is the new encryption scheme. Said otherwise, you canc guarantee that the homomorphic AND of $n$ ciphertexts only leaks the AND of the plaintexts, and nothing about the individual values of the plaintext (a generic PHE does not necessarily satisfy that, but this is often needed in applications - for example, this is needed in the example application of unanimous voting in your question)
The additively homomorphic variant of ElGamal (a ciphertext is of the form $(g^r, h^r\cdot g^m)$) can be used here: it does not enjoy efficient decryption, but it is easy to check that it is not important in this transformation, since we only need to be able to check whether a ciphertext decrypts to 0 or not, and this can always be checked given $g^m$ (which is what you get when decrypting ElGamal).


How long does a good AES encryption take? I am encrypting large file sizes (>1GB) using AES encryption with a key size of 256 and over a 1000 hash iterations. To make the program memory efficient I'm reading the file from the stream, chunk by chunk (of specific buffer lengths) and encrypting them.

However, to encrypt a file of roughly 1GB it just takes me ~6 secs on a Mac with 16GB memory and 2.2 GHz i7 processor. Is it normal that it takes only this much time? Or should I be concerned? does it usually take longer? Or (as I read) is it given AES's quality to be fast?

Any help in understanding the scenario will be appreciated.

Thank You

From this answer Different ways/algorithms for implementing AES you can see that AES is already pretty fast. By using the hardware instruction you can even get down to $\sim1.3$ cycles/byte[1].

$1 GB = 2^{30} B \approx 10^9 B$

Your CPU is working at $2.2$ GHz, in other word $2.2 \times 10^9$ cycles per second. To encrypt $1 GB$ you need $1.3 \times 2^{30}$ cycles. In other word, it would take $\frac{1.3 \times 2^{30}}{2.2 \times 10^9} = 0.634$ seconds. So clearly AES is super fast.

read more:

[1] Breakthrough AES Performance with Intel® AES New Instructions


Digital Signature Algorithm (DSA) with medium fields I understand it when we have to solve Discrete Logarithm Problem $a^x\equiv b\pmod p$, where $a$ and $b$ are given integers and we have to find secret integer $x$ that makes the equation true for some given modulus $p$.

I do not understand it when $a$ and $b$ are polynomials and we are working not only modulo integer but also modulo another polynomial.

Can you give me an explicit working example of DSA applied to this context?
What attacks against it are known?

EDIT: In the original standard, finite field has characteristic 2. By "medium" fields I mean field GF(p^n) where prime $p$ is bigger. Instead of $p=2$ it is around $10^{10}$ and $n=17$ or so.

EDIT 2: My own example:
$$a=4 x^6+10 x^5+11 x^4+3 x^3+x^2+15 x+7$$
$$b=12 x^6+4 x^5+8 x^4+4 x^3+9 x^2+6 x+7$$
$$m_1=x^7-2$$
$$m_2=17$$

Find $e$ that
$$a^e\equiv b\pmod{m_1}\pmod{m_2}$$

I am not sure whether my example is relevant, there are some criteria on choosing polynomial $m_1$ and prime $m_2$. I chose them arbitrary. But I can say $e=103$ is a solution since I brute-forced it.

The question deals with the finite field $\mathrm{GF}(p^n)$. It wants to study/attack a variant of DSA in (the multiplicative subgroup of) that field, rather than $\mathrm{GF}(p)$. Whatever that DSA variant is, it can be attacked by solving the Discrete Logarithm Problem in $\mathrm{GF}(p^n)$.

The multiplicative subgroup of $\mathrm{GF}(p^n)$ has order $p^n-1$, and the order of any element divides that. If the order of $a$ has no large prime factor, then the Pohlig-Hellman method allows reduction to easier subproblems, that a general DLP algorithm like Baby-Step Giant Step or Pollard's rho can solve. DSA blocks such attacks by working in a multiplicative subgroup of large prime order $q$ (e.g. at least 256-bit). That also keeps signature size to the minimum (twice the bitsize of $q$).

The parameters envisioned are $p\approx10^{10}$ and $n=17$, thus $p^n$ about 565-bit, making such subgroup plausible. If we want $p$ just below $2^{32}$ and $x^{17}-2$ irreducible modulo $p$ (which simplifies computations), we can use the 32-bit $p=\mathtt{ffe083f1}_\text{h}$, with $p^{17}-1$ having as highest prime factor the 262-bit $q=\mathtt{2a92bc16243adf3264304adf2adc292c32e64b569a5abfbd7be71d7a1816e3d8c1}_\text{h}$. To obtain an element of order $q$, we can select almost any arbitrary polynomial $u$; find the order $r$ of $u$ (we divide $p^{17}-1$ by primes in its factorization while raising $u$ to that power yields $1$); and use $g=u^{r/q}$ as the generator of a subgroup of order $q$.

Building a DSA analog from that and SHA-512 is easy. The only difficulty is when the original makes an exponentiation modulo $p$ followed by a reduction modulo $q$. Among many, one option to parallel this is to make the exponentiation modulo $x^{17}-2\pmod p$, then evaluate that polynomial in $\Bbb Z$ at the point $x=2^{32}$ (that is concatenate the coefficients expressed as 32-bit integers), then reduce modulo $q$.

That will make a working DSA, secure against all the aforementioned algorithms thanks to the large $q$. But that's nevertheless insecure, for other DLP methods are applicable to the case at hand. There's a summary of recent results in Razvan Barbulescu and Cécile Pierrot's The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields, in LMS Journal of Computation and Mathematics, 2014.

Tentatively: the algorithm of choice to attack that DSA analog could be Antoine Joux, Reynald Lercier, Nigel P. Smart, and Frederik Vercautere's The number field sieve in the medium prime case, in proceedings of Crypto 2006.

The musing with a small example at the end of the question attempts to work in $\mathrm{GF}(17^7)$, but uses a polynomial $m_1=x^7-2$ that is not irreducible modulo $p=17=m_2$, since$$(x+8)(x^6+9x^5+13x^4+15x^3+16x^2+8x+4)\\\quad\equiv x^7-2\pmod{17}$$

It follows that $(x+8)$ is not invertible, and we get a ring rather than a field.

If we change to $p=29$ that makes $x^7-2$ irreducible. I assume this in the following.

The multiplicative subgroup of $\mathrm{GF}(p^n)$ has order $p^n-1$, here $29^7-1$. This factors as $2^2\cdot7^2\cdot88009573$. The order of $a$ is bound to be a divisor of that. By computing $a^{(29^7-1)/2}=-1\ne1$, $a^{(29^7-1)/7}=-5\ne1$, and $a^{(29^7-1)/88009573}\ne1$, we get that $a$ is a generator of the full multiplicative group. $b\ne0$, therefore $a^e=b$ has a solution.


TLS ciphersuite without mode of operation Will there be any security concern if there is no mode of operation specified in the ciphersuite name?

For instance, there is no mode of operation in TLS_ECDHE_RSA_WITH_AES_256_SHA.

It is a security issue in the sense that it likely shows that somebody doesn't know what he is doing.

TLS_ECDHE_RSA_WITH_AES_256_SHA is not an officially supported cipher suite name (internet search results too quickly degenerate for that). It probably is present in misconfigured OpenSSL servers. I presume it will default to CBC for the actual security. It is extremely unlikely to use ECB mode as that has never been a supported mode, and it would need to somehow ignore the IV if it was to be used.

Just make it the only possible cipher suite on a test server, then connect to it with a client. You'll probably find out that it is actually the CBC ciphersuite TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA with ID {0xC0, 0x14}. The ID is what is actually communicated during the handshake; the name of the ciphersuite is just what you find in the configuration parameters of the server.

It is not possible to just make up a name for a ciphersuite: it needs to resolve to an ID to be communicated within the handshake. In developers language: the ciphersuite name is an enumeration. Unfortunately OpenSSL has the nasty habit of using their own names and patterns for allowing / disallowing enumeration values.

I'd prefer a TLS 1.2 specific GCM ciphersuite and SHA-256 or SHA-512 over that particular ciphersuite.


Proof of application of $f(x)$ without disclosing input $x$ I have three nodes in a network: $\mathcal{S}$,$\mathcal{T}$,$\mathcal{R}$.

$\mathcal{S}$ supplies data $x$ to $\mathcal{T}$. $x$ is signed so $\mathcal{T}$ knows it actually comes from $\mathcal{S}$. $\mathcal{T}$ computes $f(x)=y$ and sends $y$ to $\mathcal{R}$. $\mathcal{R}$ uses the result $y$ in some computation. $f$ Is implemented in code and the code is public.

Question: Is there a way for $\mathcal{R}$ to know for sure that $y$ is the result of the correct application of $f$ to data supplied by $\mathcal{S}$, without disclosing $x$?

In other words: Can $\mathcal{T}$ prove that it correctly applied $f$ to trusted data when computing $y$, without disclosing $x$?

Use a zk-SNARK, proving the following statement:

Private data: $x$.
Public data: $y, pk, \sigma$

I know an $x$ such that $f(x) = y \land \textsf{Ver}(pk, x, \sigma)$

Where $\textsf{Ver}$ is the secure signature scheme verifier algorithm, $x$ is the secret input, $y$ is the output of $f$ applied on $x$, $\sigma$ is the signature of $\mathcal{S}$ on $x$, and $pk$ is the public key of $\mathcal{S}$.

As long as your signature scheme does not reveal your message contents within the signature $\sigma$, your scheme will be zero-knowledge. If it does, you can hash it prior to supplying it to the protocol:

Private data: $x, \sigma$.
Public data: $y, pk, \sigma'$

I know an $x$ such that $f(x) = y \land \textsf{Ver}(pk, x, \sigma) \land H(\sigma) = \sigma'$

Where $\sigma'$ is the hash of the signature.


What’s the difference between a secret key and a seed? I always hear that if you have the seed then you can easily obtain the key. So, is the secret key just typically an expanded version of the seed? If so, via some key derivation algorithm?

Also, if you can easily obtain the key when you have the seed, why don't we just use the seed as the secret key instead?

I suspect that what you're referring to is the operation of a pseudo-random number generator (PRNG).  It takes a seed as input, and produces a random-seeming series of outputs.

If you derive a cryptographic key from the outputs of the PRNG, then the key chosen depends on the seed.   If an attacker knows the seed, they may well be able to (much) more efficiently guess the key.

If the seed is created using a source of randomness (as compared with a source of pseudo-randomness), then, at least in part, it is not predictable, and the resulting outputs of the PRNG are not predictable.  If you then throw away the seed (so that it can't be stolen after the fact), you should be able to use the key with some confidence.

You ask specifically:

  So, is the secret key just typically an expanded version of the seed?
  If so, via some key derivation algorithm?

I would say that while it is worded a bit oddly, you could probably look at the secret key as an "expanded version of the seed."  The process is slightly more complicated than just via the key derivation algorithm, because you omitted the PRNG.  So: seed -> PRNG -> key derivation algorithm -> key

  Also, if you can easily obtain the key when you have the seed, why
  don't we just use the seed as the secret key instead?

The short answer is that the seed has a small amount of real randomness that takes time and effort to acquire.  By contrast, the PRNG changes that seed into significantly more pseudo-random output very quickly / cheaply.

You can definitely use the seed (or, a series of seeds, presumably, since you probably need more data than just one seed contains) as a data source to generate your key.  (seed1 + seed2 + seed3 + ... + seedN) -> key derivation function -> key, omitting the PRNG.

The reason it isn't done that way is because:

True random (as distinct from pseudo-random / PRNGs) sources are much much slower and more expensive
Key derivation functions are potentially very sensitive to any predictable information in the input data.  That means that input data (e.g. your seed) that is even partially predictable is dangerous.  So you would need the seed to be generated completely from a slow, expensive, true random source rather than just having a fraction of the seed be truly random.
You need a significant amount of data, so you need more than just one seed.  See above about each one being expensive by comparison to PRNG output.


O(1) EC Linkable Ring Signature Without Group Manager I'm looking for a practical example for creating an EC Ring Signature, very much at the level of detail as found in the CryptoNote Whitepaper but with O(1). I saw Short Linkable Ring Signatures for E-voting, E-cash and Attestation, but I'm not sure about two things:

Does it actually require a group manager or did I miss something? I need a solution where the signer sets-up the signature with no need for a trusted party.
The paper's Appendix A doesn't include a setup for the SLRS, and I don't trust myself with an implementation, I prefer something that went through some public review. I'm looking specifically for EC, not RSA.

I'd appreciate any help in either clarifying these issues about the above paper or alternatively suggesting some reviewed source for another implementation.

So, non-interactive zero knowledge proofs, including the ring signature zero-knowledge proof that you want, are impossible in the standard model, as shown by Goldreich and Oren somewhere on this stylish webpage.

So this means we need some trusted party like the group manager, or we need some trusted setup in order to generate a common reference string, or we need to model hash function as random oracles in order for security definitions to hold. I linked an article in the comments (here it is again... :D) that gives constant size ring signatures, which also offers membership revocation (which might be something useful to you depending on the use case).

The other option at this point in time is using a signature scheme in which the signature grows logarithmically with the size of the group over which it is signed -- even with constant size ring signatures, the verification may be O(n) in which case a group of 1 million would be infeasible. If log(n) sized signatures are okay, then something like this could be used, which doesn't need a trusted setup/group manager (the protocol is secure even if the CRS is generated maliciously).

I don't think you're going to be able to find an actual peer reviewed implementation of something like this though -- even Monero, a cryptocurrency which is worth ~$ 400 million at the moment, hasn't been peer reviewed, except kind of by this paper, which reviews the blockchain metadata more than the code anyway...

If privacy of resources is really necessary, and proof generation time doesn't matter too much, looking into using something like libsnark might be your best bet, as their signatures are ~288 bytes, I think (+ ~700 byte verification key). The time taken to generate a proof can be upwards of a minute, though.


Amplifying PRF Advantage I am trying to solve this question and I have no idea how to find the value for $q$. I know that I am supposed to find the probability of $q>3q/512$ in terms of the equation $q$, but not sure how?

Any help is appreciated.

Alice has a function $$F: \{0, 1\}^k × \{0, 1\}^n \to \{0, 1\}^n$$
 that she intends to use as a PRF. However, this $F$ has a serious weakness: for any fixed key $K$, if we pick a random
message $$x \leftarrow \{0, 1\}^n$$, then the first byte of FK(x) will be $0^8$ with probability $1/128$, instead of the
desired probability $1/256$.

Adversary Eve wants to break the PRF security of F., Of course, it’s trivial to have advantage 1/128−1/256 =1/256 using just a single random query. However, being greedy, Eve aims for more. She makes q random
queries x1, . . . , xq to the oracle Fn to receive answers C1, . . . , Cq.

Let T be the number of ciphertexts
Ci whose first byte is 0^8
. Note that in the real world, E[T] = q/128, whereas in the ideal world, E[T]is much smaller, q/256. Based on that observation, Eve will output 1 if T ≥1/2[q/128 +q/256] =3q/512, and output 0 otherwise.
How big should q be so that Eve’s advantage is at least 0.99?

The general question is, "what is the probability that $T$ is significantly far from its mean?" This is a question about the "tail" of a distribution.

Your random variable $T$ can be written as a sum of indicator variables, $T = \sum_{i=1}^q T_i$, where $T_i=1$ if the $i$th query begins with 8 zeroes. Hence, $T$ follows a binomial distribution $B(q,1/256)$ in the ideal world and $B(q,1/128)$ in the real world.

The standard way to estimate tail probabilities for binomial distributions is through the Chernoff bound. For example, in the ideal world, $T$ has mean $q/256$:
\begin{align*}
\Pr[ T > 3q/512 ] &= \Pr[ T > (1+0.5) q/256]
\end{align*}
So you can use the multiplicative Chernoff bound with $\delta=0.5$ to get:
\begin{align*}
\Pr[ T > 3q/512 ] &\le \left( \frac{ e^{0.5} }{ 1.5^{1.5} } \right)^{q/256} \approx (0.999577)^q
\end{align*}

You can do a similar computation to get a bound on $\Pr[ T < 3q/512 ]$ in the real world, and from that get a lower bound on the advantage.


Does OpenTSA support PKCS11 to talk to HSMs? We are planning to implement the time-stamping service (RFC 3161) using OpenTSA wanted to know: Does OpenTSA support PKCS-11 (Cryptoki) to talk to HSMs?

BTW: I did not find documentation or much information on OpenTSA. It would be really helpful if you could comment on the support of PCKS 11 by OpenTSA.

I think that you're asking how to generate a timestamp response as defined in timestamp-protocol: RFC3161, with openssl to generate and sign the response using a PKCS#11 (HSM in your case) as a TSA signer.
I think that there is no native way to use PKCS#11with openssl to do this. (maybe with some plugin like: opensc pkcs11 engine for openssl).
If you take a look on ts command documentation: https://www.openssl.org/docs/apps/ts.html. To generate a timestamp response you can use the follow command:
openssl ts -reply [-config configfile] [-section tsa_section] [-queryfile request.tsq] [-passin password_src] [-signer tsa_cert.pem] [-inkey private.pem] [-chain certs_file.pem] [-policy object_id] [-in response.tsr] [-token_in] [-out response.tsr] [-token_out] [-text] [-engine id]
The TSA signer certificate and private key are specified in the following parameters which specify that both must be in PEM format, so seems that use of PKCS#11 it's not possible.

-signer tsa_cert.pem
The signer certificate of the TSA in PEM format. The TSA signing certificate must have exactly one extended key usage assigned to it: timeStamping. The extended key usage must also be critical, otherwise the certificate is going to be refused. Overrides the signer_cert variable of the config file. (Optional)
-inkey private.pem
The signer private key of the TSA in PEM format. Overrides the signer_key config file option. (Optional)

However as I comment before, it can be possible maybe using opensc pkcs11 engine for openssl, I can't confirm if it works because I'm unfamiliar with it. Take a look on this quickstart guide which may put you on the right direction.
Hope this helps,


Consequence of $p\bmod e=2$ in RSA prime generation When generating a prime $p$ for use in an RSA modulus with public exponent $e$, it is necessary that $\gcd(p-1,e)=1$. When $e=3$, and since $p$ is a large prime, that implies $p\bmod e=2$.
Assume an RSA key generation procedure for 1024-bit primes used for a 2048-bit modulus is written to always generate primes with $p\bmod e=2$, for both factors, including for large $e$ supplied as a parameter at key generation.
For what values of $e$ does this have any dire consequence?
Note: I know no circumstance making this assumption hold, not even a CTF.  And that would not be a subtle way to rig the key generator, since that's externally detectable from the public key because $N\bmod e=4$ always holds.

Very large exponents $e$
Assuming that $e > 2^t$ where $t > 514$ we may use Coppersmith's attack to factorize $N$ efficiently. By this answer I only intend to exemplify that for some public exponents $e$ the given condition on the primes makes it significantly easier to factorize the RSA modulus. In particular it is worth noting that public exponents $e$ that conform to the FIPS 186-4 standard are less that $2^{256}$, and are therefore not susceptible to the following.

The following (essentially) appears in [1].
Theorem (Coppersmith)
Let $N$ be an integer of unknown factorization which has a divisor $b \geq N^\beta$, $0 < \beta \leq 1$. Let $0 < \epsilon \leq \frac{1}{7}\beta$. Furthermore, let $f(x)$ be a univariate monic polynomial of degree $\delta$. Then we can find all solutions $x_0$ of the equation $f(x) \equiv 0 \bmod b$ such that
$$|x_0| \leq \frac{1}{2}N^{\beta^2/\delta - \epsilon}$$
using a LLL-reduction on a lattice of dimension $\leq \frac{\beta}{\epsilon} + \frac{1}{\beta}$.
We will apply this theorem for $\beta = 1/2$, $\delta = 1$, $b = p$ where $p$ is the larger of the two prime factors of the public RSA modulus $N = pq$, and $\epsilon = (t - 514)/2046$. To find a suitable polynomial $f$ we note the following.
Note that $p \bmod e = 2$ implies that there is some integer $x$ such that $p = ex + 2$. If we can find this $x$ we can determine $p$. Now, note that
$$ex + 2 = p \Rightarrow e_0 ex + 2e_0 = e_0 p,$$
where $e_0$ is the modular inverse of $e$ modulo $N$ (which is expected to be easy to determine), say $e_0 e = 1 + \ell N$. Furthermore, note that the right hand equation may be rewritten as $x + 2e_0 = e_0 p - \ell N x$ which implies $x + 2e_0 \equiv 0 \bmod{p}$. Hence, we have that any solution $x$ to $p = ex + 2$ must also be a solution to $f(x) \equiv 0 \bmod{p}$ where $f$ is the monic degree 1 polynomial defined as
$$f(x) = x + 2e_0.$$
Now, applying Coppersmith's theorem, with the given parameter values, we get that we find all solutions $x_0$ such that
$$|x_0| \leq \frac{1}{2} N^{1/4 - (t-514)/2046}$$
using a LLL-reduction of a lattice of dimension $\leq \frac{1023}{t-512} + 2$.
Finally, we want to show that the $x$ such that $p = ex + 2$ is among the solutions found above. For this we have to show that such an $x$ must satisfy
$$|x| \leq \frac{1}{2} N^{1/4 - (t-514)/2046}.$$
We can do this by noting that since $p = ex + 2$ we have $x \leq p/e \leq 2^{1024-t}$. Now, $N = pq > 2^{2046}$ and thus
$$2^{1024-t} \leq \frac{1}{2}N^{1/4 - (t-514)/2046},$$
as desired. Hence, one of the solutions $x_0$ found by the LLL-reduction in Coppersmith's theorem is the sought after $x$. To determine which solution is the correct one all we have to do is a trail division of $N$ by each $ex_0 + 2$.

Remark: We can at least do some small improvemets to the above, e.g. by noting that $x$ has to be odd so really we may start with an equation of the form $p = 2ey + e + 2$ instead.
[1] May A. (2009) Using LLL-Reduction for Solving RSA and Factorization Problems. In: Nguyen P., Vallée B. (eds) The LLL Algorithm. Information Security and Cryptography. Springer, Berlin, Heidelberg


How does AES-GCM produce different ciphertexts, and how can the algorithm decrypt the values if they're random? The title explains it. How does AES-GCM (or other modes for that matter) generate random ciphertexts per execution, and how does the algorithm decrypt a random value since the sender randomizes the ciphertext?

If you will look at Probabilistic encryption in Wikipedia, that will explain shortly.

GCM mode internally uses CTR mode and therefore let's concentrate on CTR mode. CTR mode converts a block cipher into a stream cipher. In CTR mode, one encrypts the $(nonce\mathbin|counter)$ then x-or the plaintext then increments the counter like

$$C_i = P_i \oplus E(k, nonce\mathbin|counter+i)$$

If you select a random $nonce$ (IV) for each message, then even if you encrypt the same message you will get different ciphertext.

$$C'_i = P_i \oplus E(k, nonce'\mathbin|counter+i)$$ where $C'\neq C$.

In CTR mode, and therefore in GCM, the nonce must not be reused. It can have catastrophic results from leaking the messages to leaking the authentication key in GCM.

$$C_i = P_i \oplus E(k, nonce\mathbin|counter+i)$$
$$C''_i = P''_i \oplus E(k, nonce\mathbin|counter+i)$$
x-or both sides and use two-time pad attack as in One-Time Pad.

To prevent the random collision due to the birthday paradox (we expect a nonce collision with 50% probability after randomly selecting $2^{bit-of-nonce/2}$ nonces), incremental IV is advised, that is for each message you next nonce value so that you may prevent the IV re-use.

The nonce is not secret and it is usually prepended to the ciphertext. To decrypt, the other side uses this nonce that you send together with the ciphertext to initialize the mode in the same stage.

The other probabilistic encryption modes like CBC, OFB, etc., similarly uses and IV/nonce to randomize the encryption.

Note that to have semantically security the probabilistic encryption is necessary.


Difference between FleXOR and Free-XOR I would like to know the differences between FleXOR and Free-XOR. I searched in the web but I couldn’t understand the information I found. I understand that there are both cryptographic methods as well as optimizations for Yao's Garbled Circuits, but I don't practically understand their differences and which is to be preferred. What exactly is (or are) the difference(s) between FleXOR and Free-XOR?

I am an author on the FleXOR paper and can comment a bit. Let $A_0$ and $A_1$ are the false/true wire labels on some wire, and let $A_0 \oplus A_1$ denote the offset of that wire. The idea behind free-XOR is that when the 3 wires that touch an XOR gate have the same offset, then the XOR gate can be garbled for free. So you arrange for all wires in the circuit to have the same offset.

The idea behind fleXOR is to have not one global offset but several throughout the circuit. Again, whenever 3 wires touching an XOR gate have the same offset, you get that XOR gate for free. When only 2 wires touching the XOR gate have the same offset, you get that XOR gate for a cost of 1 ciphertext. So now we have made [some] XOR gates cost a little bit more. But it turns out by adding this flexibility you can make the AND gates cost less. In some cases it turns out to do better than free-XOR. (Another reason to favor fleXOR is because it can be instantiated in a way that requires a milder hardness assumption.)

I will point out that if the size of a garbled circuit is all you care about, then fleXOR has been made obsolete by the half-gates construction:

  Samee Zahur, Mike Rosulek, David Evans: Two Halves Make a Whole - Reducing Data Transfer in Garbled Circuits Using Half Gates. EUROCRYPT (2) 2015: 220-250

As for implementations, free-XOR is implemented probably in every GC library out there (JustGarble, etc). I'm not sure about implementations of fleXOR, its moment of fame was short-lived before it was superseded by half-gates. For the paper we implemented the circuit-analysis steps so that we could determine the concrete garbled circuit size, but we didn't implement the actual garbling/evaluation algorithms. Yehuda Lindell hangs around here; he has a recent paper with some followup work on the fleXOR techniques, which may have involved an implementation (I don't remember off the top of my head).

For more details about the differences between various garbled circuit constructions, you can check out a survey talk I gave about the topic: video, slides.


Which symmetric algorithm should I use for storing files in untrusted servers? I have gigabites of files, which I have to backup. I have some servers for storing this files. But these servers are untrusted. So I need to encrypt files, then backup files. When my PC  breaks down, I will dowload files from unstrucsted servers and restore them.

So, basically, I think about AES-256. Is it OK for me, or there is more suitable symmetric algorithms?

Just a note: AES is not a encryption scheme, it is technically just a block cipher; though it is a fine one.

To create a cipher you need to use it in a mode like counter mode.

To obtain chosen ciphetext security (which is the usual aim) you should use an authenticated encryption scheme such as Galois/Counter Mode.

As usual, don't try make it yourself, use a premade secure library.


What is novel about Seedless RNGs? Seedless Fruit is the Sweetest: Random Number Generation, Revisited introduces a theoretical framework for "seedless" RNGs.
AFAICT, this framework injects entropy directly into the underlying cryptographic primitive instead of treating the entropy collection/estimation and randomness extraction as two separate phases.  Is my understanding correct?
What quantitative benefits does this framework have over the more traditional seed-based design?

AFAICT, this framework injects entropy directly into the underlying cryptographic primitive instead of treating the entropy collection/estimation and randomness extraction as two separate phases. Is my understanding correct?

Yes, that's my understanding as well.

What quantitative benefits does this framework have over the more traditional seed-based design?

The benefit is that if the entropy source is under partial control of an attacker it will still be possible to create a secure random number generator, assuming that enough entropy is left of course. If you assume that the entropy pool is not under control and delivers enough entropy to a traditional PRNG using the seed(s) then the benefits seem non-existent. Here's where I struggle a bit, because "partial control" seems to be tricky to accomplish.
In the traditional approach you could argue that the PRNG requires another PRNG-like construction (such as a KDF or, in the case of Intel, a PRF/MAC) to create the short, universally random bit string to be used as the seed.


Convert numeric message from RSA ciphertext to alphabetic I have a set of numeric values that are supposed to represent a message encoded via textbook RSA. For example:

60889
37946
13359
61629
35960
13747

I've decrypted these values to find the corresponding messages:

1535
3109
2789
1191
2700
1829

Now I need to convert these values the alphabetic using the rule that each value represents a triplet of alphabetic characters as follows:

DOG -> 3*(262) + 14*26 + 6 = 2398
CAT -> 2*(262) + 0*26 + 19 = 1371
ZZZ -> 25*(262) + 25*26 + 25 = 17575

I'm not sure how to find the alphabetic characters once I have the original numeric message. The only way I could think to do it would be to calculate every possible triplet combination of letters then find the numeric match for each element. But this method seems way overly complicated.

Anyone have a better way to figure this out? I'm writing this all in Java, so a code example would be even better!

The term you are looking for is Modular Arithmetic.

In the case of 1535, if it is indeed a combination of 3 values ranging 0 to 25, you do the following:

1535 mod 26 = 1
(1535 - 1) / 26 = 59
59 mod 26 = 7
(59 - 7) / 26 = 2

The set of values that generated 1535 is 2,7,1 (c,h,b?), which can easily be verified.


Generating IV in TLS 1.2 I'm writing a TLS 1.2 implementation (in C#) using a custom protocol.
My question is how to generate the IV attached to each message, I don't want to use RandonNumberGenerator because I've heard it is slow.  Instead, I would like to use some PRNG. I'm only going to suppport AES-128/-256.
From reading around I understand that using a random IV and encrypting a counter (should start at a random number) and use that as the IV is OK.  Is that true? After how many uses should I use a new random IV? Can I use the same key for generating the IV and encrypting the message?
Is using .Net's Random class with a seed from RNGCryptoServiceProvider can do the work? After how many uses should I use a new seed?

To answer your specific questions:

  From reading around I understand that ... encrypting a counter and use that as the IV is OK,
     is that true?

For CBC mode, that is absolutely true, as long as the key that you use to encrypt the counter is secret (that is, not known to any possible adversary).

  Should I start in random number?

Actually, that's a matter of taste; you could start with 0 if you wished.

If you use a known counter, the attacker would learn the encryption of (for example)  [0], [1], [2], etc.  This isn't much of a problem with CBC mode; whenever you encrypt known plaintext, the attacker gets several more known plaintext/ciphertext pairs.  This helps the attacker only if in the future, the CBC mode happens to use the exact same plaintext (to generate the exact same ciphertext), with AES, you have $2^{128}$ possible plaintext/ciphertext pairs; accidentally reusing one is improbable (and so adding a few more because you encrypt a few known counters isn't going to be harmful.

Now, if it's convenient to start at a random number, well, that doesn't hurt anything.  However, I wouldn't do it unless it was easy.

  After how many uses should I use a new random IV?

There's no requirement to ever reseed your counter.  You'd run into problems if you encrypt more than $2^{64}$ messages or so; however CBC mode will already run into problems in that case (and you wouldn't be able to encrypt that many messages in a reasonable amount of time anyways).

  Can I use the same key for generating the IV and encrypting the message?

Not only can you, you're better off if you use the same key.  Remember where I said the key you encrypt the counter should be "not known to any possible adversary"?  Well, we already have such a key; the key you use to encrypt the message.  After all, if an adversary does have that key, he can read the message already; any weakness stemming from the IV being predictable is irrelevant.  Hence, by using the same key to do both, we reduce the number of secrets we need to keep from an adversary.

One small caveat: if you reuse the key in this way, the attacker shouldn't be allowed to choose or control the counter.  It would be fine to use a counter that starts at 0, or a counter with a random starting point (where the starting point is generated using RandomNumberGenerator) as you suggested.


How to get an output of SHA-1 with first 2-bit are zeros? Can someone explain what are the ways to get an output of SHA-1 with first 2-bits which are zeros?

Hash random values until you get a hash with two leading zeroes. We would expect  about 1 in 4 values to have a hash-value of that form.
So let's try this:
echo hello | sha1sum
f572d396fae9206628714fb2ce00f72e94f2258f  -

Nope.
echo hello1 | sha1sum
0ef562ff2d0c21358f9d289f1c908436714fc923  -

There we are, 4 leading zeroes.


Why is computational zero knowledge the most generic notion of zero knowledge? GMR88 (Goldwasser, Micali, Rackoff) in chapter 3 mentions that computational zero knowledge, in comparison to statistical or perfect zero knowledge is the most general amongst the three definitions.

Why is that the case? Why isn't perfect zero knowledge the most general notion of zero knowledge?

Because being perfectly zero-knowledge is a more stringent security requirement.

For a language to have a perfect zero-knowledge proof, you need to exhibit a proof of membership to the language so that the proof can be simulated perfectly without knowing the witness; i.e., even an unbounded adversary should not be able to see any difference between the real proof and the simulated proof. Hence, you are requiring a very strong security notion: security against an adversary with unlimited computational power.

Computational zero-knowledge, on the other hand, only requires that the simulated proof cannot be distinguished from the real proof by a computationally bounded adversary. This is a weaker security notion, hence easier to achieve.

If a language has a perfect zero-knowledge proof, then it has a computational zero-knowledge proof (the same one: if it's secure against unbounded adversaries, it's in particular secure against bounded adversaries). We do not know about the converse, and we suspect that it is not true (i.e., some languages can have a computational zero knowledge proof, but no perfect zero-knowledge proof). Hence, computational zero-knowledge is more general, because more languages can have such proofs. Denoting CZK / SZK / PZK the class of languages with computational / statistical / perfect zero-knowledge proofs, we clearly have PZK $\subset$ SZK $\subset$ CZK. Furthermore, we also know that if one-way functions exist, CZK $=$ IP $=$ PSPACE, which is immensely powerful.


Understanding definition of secure pseudo random number generator From my reading, a secure pseudo random number generator is called secure if, given a sequence of numbers generated by the PRNG, then if any one of those numbers from the sequence is removed an adversary could not determine the removed number via any method better than guessing.  Of course the existence of such secure PRNG's is unknown.

Reading such a definition however, I am unclear on a couple of things.  Assume $G$ is a pseudo random number generator so that an adversary could not determine the missing value in a sequence by any more efficient method other than guessing.  But also assume the output of $G$ is normally distributed: Then the adversary may still have to guess to determine the missing value, but with high probability the missing value will be in a particular interval.  Would such a PRNG still be called secure?

You'd do well to review your readings to see if they stipulate somewhere earlier that when they say "random" they mean uniform random (equiprobable).
But even without such a stipulation that I'd say the definition as you've loosely formulated it and are interpreting it seems to imply equiprobability.  If we follow your logic strictly, then we have to conclude that your proposed attack on the normally-distributed output of $G$ would imply that $G$ is not in fact a secure PRNG by your definition and application thereof.  And in fact you should be able to conclude that your definition and interpretation implies that the output of a secure PRNG must be uniform.
But the definitions used in theoretical cryptography are much more precise than this.  For example in Katz & Lindell's textbook (2nd edition), Definition 3.14 (p. 62):

DEFINITION 3.14. Let $\ell$ be a polynomial and let $G$ be a deterministic polynomial-time algorithms such that for any $n$ and any input $ \in \{0,1\}^n$, the result $G(s)$ is a string of length $\ell(n)$. We say that $G$ is a pseudorandom generator if the following conditions hold:

(Expansion:) For every $n$ it holds that $\ell(n) > n$.
(Pseudorandomness:) For any PPT algorithm $D$, there is a negligible function $\mathsf{negl}$ such that $$\bigg|\mathrm{Pr}\big[D(G(s)) = 1\big] - \mathrm{Pr}\big[D(r) = 1\big]\bigg| ≤ \mathsf{negl}(n)$$ where thre first probability is taken over uniform choice of $s \in \{0,1\}^n$ and the randomness of $D$, and the second probability is taken over uniform choice of $r \in \{0,1\}^{\ell(n)}$ and the randomness of $D$.

I'll repeat this bit that I boldfaced at the end:

the second probability is taken over uniform choice of $r \in \{0,1\}^{\ell(n)}$

If your reading materials are leaving you with questions like these, maybe have a look at something more rigorous.


Using the same private key to generate Schnorr and BLS signatures I am wondering if it is possible or if there are any limitations to using the same private key to generate Schnorr and BLS signatures. Specifically, assuming I have a private key $x$, I want to use it to sing some messages using Schnorr signature scheme and other messages using BLS signature scheme. The verifier should be able to tell that the signatures were generated with the same private key.

One way I can think of is to have a single public key $X$ on a curve $g$ and use it for both types of signatures. This probably limits the selection of $g$ to the curves that support BLS scheme (e.g. BLS12-381). But I'm not sure if there are any drawback to using Schnorr signatures on these types of curves.

There is a classic solution, applicable to any two public-key cryptosystems: deriving both private keys from a master key, which plays the role of a new common private key.

Start from a master key. Derive from it and two public constants the seeds of the CSPRNGs used for the key generators of the two public-key cryptosystems (use some Key Derivation Function like HKDF). Perform the two key generations (limited to public key if that help), to obtain the public keys. And, at each use of the master private key for one cryptosystem, perform the appropriate one of these two derivations, then the appropriate key generation (limited to private key if that helps), thus obtaining the private key for the cryptosystems, and use it as normal.

The main drawback is more complex/costly use of the private key, and that's an issue with RSA. But for Discrete Logarithm based cryptography, including Elliptic Curve Cryptography, the overhead tends to be minimal (relative to private key use), because the KDF has comparatively low cost, and reducing its output to a private key is usually essentially modular reduction (ECDSA) or bit extraction (Ed25519).

Note per comment: the requirement that "the verifier should be able to tell that the signatures were generated with the same private key" is met only as far as the verifier is certain that the two public keys used to verify the two signed messages have been generated from the same master key. The person preparing the public keys must thus be trusted. To avoid errors, it is possible to add a unique common identifier to the public keys. That can be obtained from the master key by derivation with another constant.


How to specify last $t$ bits are only sent when a signature is sent? I have read that in cases where there is a limit on the amount of data sent over the network, one idea is to sent only $t$ bits of data rather than sending all the bits. For example, in the Schnorr scheme this can be employed.

My question is, whether this can be specified by sending the $t$ bits along with the other information?

In general, this depends entirely on the signature scheme in question; usually however, the answer is that truncation is generally not possible.

For very short signatures, depending on your risk appetite for other kinds of somewhat novel public-key cryptography, you may find success with pairing-based BLS signatures or multivariate cryptography (GeMSS comes to mind).

For Schnorr signatures in particular, you generally either send:

the result of applying the group operation with the nonce $r$, $x = \alpha^r$ (or $[r]G$ in the elliptic curve case) and the scalar $y$, or
the tuple of the hash value $e=h(\overline{x}, m)$ and the scalar $y$.

EdDSA, a relative of Schnorr signatures, sends $([r]G, y)$ and thus doesn't lend itself to shortening unless you change your implementation to send $(e, y)$ instead.

If you send $(e, y)$, you can essentially truncate $e$ to an arbitrary extent in your scheme, but the security of the scheme also sinks by that much. Schnorr's original paper proposed using a $t$-bit hash for a $2t$-bit group order. The academic community still isn't sure whether this is a good idea, however, see e. g. Jeremiah Blocki and Seunghoon Lee. On the Multi-User Security of Short Schnorr Signatures, 2019 and Daniel R. L. Brown. Short Schnorr signatures require a hash function with more than just random-prefix resistance, 2015 and their references.


How is biometric data used to generate encryption keys? I understand that biometric data such as fingerprints and face patterns are matched for recognition with a certain degree of tolerance to account for differences given by empiric factors (positioning, aging, dirt, different measurement tool, etc.).

Given that's the case, how are biometric characteristics used to generate encryption keys to encrypt and decrypt data?

I.e. If you encrypt data using a particular reading of a biometric characteristic, wouldn't the small differences in future readings prevent you from successfully decrypting the data?

We do not know how to extract a cryptographically secure key $K\in\{0,1\}^k$ for traditional symmetric encryption from biometric data $b$ such as fingerprints, by way of a function $F(b)\mapsto K$. As noted in the question, problem is that when the biometric data is re-acquired, the naturally occurring $b'$ will be slightly different from $b$ and we'll have $F(b)\ne F(b')$ unacceptably often, for about uniform $K$ of cryptographic interest (e.g. $k\ge80$ bits). That's including if how $F$ operates (e.g. minutiae extraction) is carefully tailored to the characteristics of the biometric data [#].

Allowing $F(b')$ used for decryption to generate several guesses of $K$ (with the right one sorted out thanks to authenticated encryption) does not seem enough to get a workable system.

What does work is extracting a secure sketch as $S(b)\mapsto s$ so that

for naturally occurring variations $b'$ of $b$, with high likelihood, the same key $K\in\{0,1\}^k$ can be extracted from $(b,s)$ and $(b',s)$ (and some public nonce $n$ if we want multiple $K$), using a function $F(b,s)$ or $F(b,s,n)$
$s$ can be published without compromising the confidentiality of $K$ or/and $b$; including if $s'=S(b')$ gets published for several naturally occurring variations $b'$ of $b$.

A search for articles on secure sketch returns a lot of bibliography.

However the interest of biometric data as encryption key is dubious: biometric data, in particular fingerprint, is hard to keep secret, which is the primary attribute desired for an encryption key. Using fingerprints as a means of identification makes much more sense.

[#] Note: all claims to the contrary that I met fall into at least one of these pitfalls:

the error rate is unacceptable, like for >5% of a population, an attempt to obtain the same $K$ a day after fails, even will allowance of two retries;
some ancillary data (similar to $s$ above) is required along $K$ or stored in the scanning device (thus in the later case the number of users is limited, replacement of a failed single scanning device cause disruption, and multiple scanning devices must communicate in order to produce the same $K$);
$K$ has very low entropy (say <40 bits), making it vulnerable to better-than-brute-force key search, and even conceivable that two users accidentally end up with the same $K$ if nothing but their biometrics is an input;
some part of the method must remain secret, and is how the previous issue is masked.


How is message length involved in public/private-key encryption? I've just read this question regarding why to sign only the hash of a message. I kind of understood the answer, but the question arisen is now:

Why can I encrypt any text messages with the same method while it is needed to split up the message in order to sign it?

I mean, signing is taking the private key and encrypting e.g. message A and on the other side taking the encrypted message and using the public key to decrypt it. What is the difference that makes the other way around (public key for encryption, private key for decryption) (more) secure?

First let me emphasis again that signatures are something entirely different than public key encryption. Please read the comments to your question and keep those in mind.

That said, in both cases (signature & public key encryption) schemes are designed for fixed message sizes. For RSA signatures and encryption the maximum message length is determined by the size of $N = pq$ (assuming the school book notation for RSA). You can neither sign longer messages nor encrypt them.

What applications will do is using a cryptographic hash function in case of signatures to reduce the message length to a fixed small value. In case of encryption they will use hybrid encryption, i.e. the application will generate a random secret key for symmetric encryption, encrypt it using the public key scheme and encrypt the message using symmetric encryption with the generated secret key.


Key recovery after AES-ECB encryption of two blocks with some known plaintext/ciphertext I am analysing a small, bespoke end-to-end encryption service's source code, in particular their user registration process. I am finding some interesting things going on and I am wondering if there's some vulnerabilities here:

The client code generates a random Master Key for the user which is 128 bits. This is used to encrypt data on the service.
A password based key derivation function is run on the user's Password to produce a Password Derived Key of 128 bits. A salt is not used at all here.
The Password Derived Key is used to encrypt the user's Master Key with AES in ECB mode.
Some half-random Temporary Data is created of 128 bits. I am not sure what this Temporary Data is used for, I haven't seen it being used for anything in particular anywhere else in the code. Anyway, the first 32 bits are randomly generated, the second 32 bits are zero, the third 32 bits are zero, and the final 32 bits are randomly generated. The array as 32 bit words might look something like: [1502582904, 0, 0, 3153058828].
The same Password Derived Key is used to encrypt the Temporary Data with AES in ECB mode as well.
The encrypted Master Key and encrypted Temporary Data are concatenated together and sent to the server API to create the account on the server. The API then sends back to the user an email confirmation code that the user uses to confirm their email. The confirmation code is the Base64 encoding of this data concatenated (||) together:

"emailconfirmlink:" || some metadata || encrypted Master Key || encrypted Temporary Data

So the obvious vulnerability seems to be that they send the user's encrypted Master Key back to the user via email for no apparent reason instead of just randomly generating a token on the server side and expecting the user to return that in order to complete the email confirmation. That would allow anyone who can read internet traffic a chance at cracking many user passwords at once pretty easily as there is no salt in the key derivation process to prevent rainbow tables.

I am wondering about another vulnerability in that the Password Derived Key has encrypted the Master Key, but it has also been used to encrypt the Temporary Data as well. So we have:

AES-ECB(Password Derived Key, Master Key)
AES-ECB(Password Derived Key, Temporary Data)

We know AES-ECB is not good at encrypting multiple blocks under the same key. So it has encrypted two blocks now under the same key. Also the Temporary Data has 64 bits of known plaintext in the middle of the second block (all zeros). Also the attacker can see the AES-ECB ciphertext output of those 64 zero bits.

My questions are then:

With the encryption of the Temporary Data with 64 bits of plaintext known, does this allow an attacker to brute force the password and know when they got a plausible password because the decryption of the Temporary Data with AES and the derived key they are currently trying will result in 64 bits in the middle being zero which is statistically unlikely?
Can a cryptanalyst retrieve the full Password Derived Key more easily now that it has been used to encrypt multiple blocks in AES-ECB, some of which has known plaintext? How? And does this mean they could use that recovered Password Derived Key to decrypt the Master Key?
Can a cryptanalyst use the known encryption of the zero bits in the Temporary Data to recover the Master Key with less effort (perhaps using a known plaintext attack, differential cryptanalysis or two-time pad type recovery)?
What other cryptanalysis is possible if a cryptanalyst has access to this information?

With the encryption of the Temporary Data with 64 bits of plaintext known, does this allow an attacker to brute force the password and know when they got a plausible password because the decryption of the Temporary Data with AES and the derived key they are currently trying will result in 64 bits in the middle being zero which is statistically unlikely?

Yes. The attacker tries plausible passwords starting from most likely (1234, test), runs each thru the password KDF to get the corresponding Password Derived Key, use that to decipher the temporary data, and check that the appropriate 64 bits are zero. If that's the case, the right password has likely been found. This is selective enough that for a fair quality password (says 48-bit, more than XKCD propose), probability of false positive are low ($\approx2^{48-64}<1/65000$). Because there is no salt, the cost of the password KDF (if sizable entropy stretching is used) is incurred only once per password, regardless of the number of users (each user targeted add obly one AES decryption and test).

  Does this mean they could use that recovered Password Derived Key to decrypt the Master Key?

Yes, and from that the "data on the service".

With what we know, I see no other attack, and it is unclear what's the baseline for "more easily" and "less effort" in the question. Forget about brute-forcing AES-128. If there was known plaintext or redundancy in "data on the service", that could help (e.g. to confirm the password), but won't change the overall attack cost, which depends mostly on the password KDF and its parametrization; and the user choosing a hard-to-guess password.


In RSA encryption, can I calculate d given only m,n,c and e? Newbie here. Not familiar with cryptography; just interested and reading up about it from time to time.

We know that the RSA problem (let's say $c=m^e \bmod N, c^d= m \bmod N$) is about recovering $m$ given $N, c$ and $e$. However, if given $N, m, C$ and $e$ - can I recover $d$?

No!

RSA is public-key encryption and in public-key encryption, the known plaintexts are free. Given a public key $(n,e)$ we can find many $(p_i,c_i)$ such that $c_i = p_i^e \bmod n$. If this is a weakness, on the first day it will be broken.