Are there better alternatives to CRC32 for distributed download components hash calculation? Given a server with with download resume capabilities (byte range), we can download a file chunk by chunk. Multiple people will download different parts of the file.

If a file A.jpg has blocks 1, 2, 3, 4, 5, 6.

Following are the people who obtained the blocks

Alice - 1, 2
Bob - 3, 6
John - 4, 5

What kind of hashing algorithm can be used to calculate the hash of A.jpg given that Alice, Bob and John can only hash each block separately?

Assume that the hashes for each block are located in a place Alice, Bob and John can access. And they can combine them as they wish.

What I've found: Combine two sha512 hashes to a single hash cannot be used.

I also found that CRC32 can be used, Are there any more algorithm ?

Desired outcome

Everyone should be able to generate the same final hash, which should be more powerful than CRC32 to prevent collisions. In the end I want to join the blocks to get the final file. So that Alice, Bob and John have the same file.

I'll assume we want a cryptographic hash giving security in the Random Oracle Model; collision-resistance and preimage-resistance follows. Collision-resistance alone rules out CRC, regardless of size.

The standard technique would be to split the file into blocks, distribute them with index to the participants, which hash each of their blocks; then hash the hashes concatenated in order of increasing indexes, or use a Merkle tree, to form the hash of the whole file. However, with blocks distributed in haphazard manner (as in the question), most block hashes need to be exchanged, which can get sizable; and the distributed computation of the final hash is slightly hard to organize.

Rather, we can group the block hashes (made dependent of their index) using an order-independent hash, used by each participant over all the hashes of the blocks s/he is responsible for, then again to obtain the final hash. This simplifies the organization, and saves bandwidth when there more than a few blocks per participant: like 8 in the following simple example using $\Bbb Z_p^*$, but I conjecture that the overhead can be made negligible down to 1 block per participant using an Elliptic Curve Group instead.

For a 256-bit hash, marginally more costly than a regular one for large files, we'll use:

Some 512-bit hash $H$, e.g. $H=\operatorname{SHA-512}$.
Some 2048-bit prime $p$ making the Discrete Logarithm Problem in $\mathbb Z_p^*$ (conjecturally) hard; see final section.
Some public block size $b$ multiple of $2^{12}$ bit (512 bytes), e.g. $b=2^{23}$ for blocks of 1 MiB.
Implicit conversion from integer to bitstring and back, per big-endian convention.

To hash a file of $s$ bits (with $s\le2^{62}b$, which is more than ample):

Split the file into $\lceil s/b\rceil$ blocks $B_i$ of size $b$-bit, except for the last which may be smaller (but non-empty), with $0\le i<\lceil s/b\rceil$. Distribute the blocks $B_i$ and indexes $i$, such that each participant $j$ is assigned a block only once.
Have each participant $j$ perform:

$f_j\gets1$
For each block $B_i$ assigned to participant $j$

$h_i\gets H(B_i)$. That's a 512-bit bitstring characteristic of $B_i$.
$g_i\gets H(h_i\mathbin\|\widetilde{4i})\mathbin\|H(h_i\mathbin\|\widetilde{4i+1})\|H(h_i\mathbin\|\widetilde{4i+2})\|H(h_i\mathbin\|\widetilde{4i+3})$ where $\widetilde{\;n\;}$ is the representation of integer $n$ as a 64-bit bitstring.
Since function $H$ returns 512 bits, the concatenation of the 4 hashes makes $g_i$ a 2048-bit bitstring, characteristic of $B_i$ and $i$.
$f_j\gets f_j\cdot g_i\bmod p$.

$f_j$ is a 2048-bit bitstring characteristic of the $B_i$ and $i$ assigned to participant $j$.
If $j\ne 0$, transmit that $f_j$ to participant $0$.

Participant $0$ performs:

$f\gets f_o$
When receiving $f_j$ with $j\ne 0$

$f\gets f\cdot f_j\bmod p$.

$h\gets H(f)$ truncated to it's first 256 bits, where $f$ is represented as a 2048-bit bitstring when applying $H$.
Send $h$ to all participants.

Absent message alteration or loss, $h$ is independent of how the blocks have been distributed. That is a 256-bit bitstring characteristic of the whole file, computed in a largely distributed manner. The computation of $f$ and $h$ could be distributed too, at a small extra cost in message exchange.

The order-independent hash is borrowed from the multiplicative one in Dwaine Clarke, Srinivas Devadas, Marten van Dijk, Blaise Gassend, G. Edward Suh, Incremental Multiset Hash Functions and Their Application to Memory Integrity Checking, in proceedings of AsiaCrypt 2013, which is given a security reduction in appendix C. The security of the whole construction should follow.

On choice of $p$: our requirement is hardness of the DLP in $\Bbb Z_p^*$, as in classic Diffie-Hellman key exchange. We need a 2048-bit safe prime, with no special form $p=2^k\pm s$ that could make SNFS easier. Customarily, it is used a nothing-up-my-sleeves number based on the bits of some transcendental mathematical constant, as a good-enough assurance that $p$ is of no special form.

That can be $p=\lfloor2^{2046}\pi\rfloor+3617739$. The construction uses the first 2048 bits of the binary representation of $\pi$, then increments until hitting a safe prime. Hexadecimal value:

c90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aaac42dad33170d04507a33a85521abdf53ee2f

As pointed by Sqeamish Ossifrage in comment, we could use the 2048-bit MODP proposed by RFC 3526: $p=2^{2048}-2^{1984}-1+2^{64}\cdot\lfloor2^{1918}\pi+124476\rfloor$. That similarly uses as many of the first bits of the binary representation of $\pi$ as possible, but by construction has the 66 high-order bits (including two from $\pi\approx 3$) and 64 low-order bits set. The high-order bits simplify choice of dividend limbs in Euclidean division by the classical method, while the low-order simplify Montgomery reduction. This is believed few enough forced bits to not allow a huge speedup of the DLP.

ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aacaa68ffffffffffffffff


Thoughts on secure hashing and the "mds" algorithm Almost a decade ago Raymond Chen blogged [1] about the "hash reset
attack" cautioning developers to record the content length in addition
to the message digest.

Recently I came up with a variation on the MD5 hashing algorithm that
incorporates the file size. I've called this algorithm 'MDS' for
'Message Digest + Size' but hilariously "MDS" is a "cancer"... :P

You can see the javascript or PHP implementation of MDS [2].

So, is this a good idea? Do you think it would raise the bar for
collision generation? I'm way out of my depth... sort of seems like a
good idea, but I'm not armed with facts.

Perhaps, as I have been cautioned, I shouldn't be using MD5 at all..?

[1] http://blogs.msdn.com/b/oldnewthing/archive/2004/05/19/134937.aspx
[2] https://svn.jj5.net/jjrepo/mds/trunk/src/

That is an absolutely terrible idea, here is why.
His algorithm works as follows:

Hash the input data
Take the length of data (presumably in bytes)
TRUNCATE the hash so that the length value in bytes plus the truncated hash is the output length of a standard MD5 hash (128 bits)

Here is an example of a 1MB data file being hashed
MD5(data) = e319709e00ec584c412603b83f661b2b
len(data) = 40000000
MDS(data) = e319709e00ec584c412603b840000000

Most MD5 collision attacks are on signatures with a fixed length, this will only make it easier to create a collision, since you do not have to worry about the truncated bits at the end as part of your collision calculation.
The length of the input data for some applications is also a secret or can expose information about the data, so it is part of the input padding to the hash and not the output.


Encryption algorithm that produces dummy output on incorrect passwords Background:
  I've been thinking about using encryption in the context of backing up files to untrusted locations (to the point of making the file publicly and widely distributed for practically failsafe backup).

  The problem is, once a file is publicly available, it will forever remain so. And in 20 years, when computing power is unpredictably faster, AES256 bit encryption might be practically useless - and my private backup file readable to all.

I was thinking, as a deterrent to brute force attacks on encryption, what if when the wrong password was tried the algorithm returned dummy data that would require human examination to assert that the data is not what the attacker is looking for.

Example:

I encrypt the plain text (say, an account number) '123456789' with the password 'pass'.

Attacker attempts to brute force the encryption and tries the password 'a'.

The result is '987654321'.

Now, how is the attacker to know that this is not the value I encrypted, and that the password I used was 'a'? Additionally, even if the attacker guesses the password 'pass', how are they to know that '123456789' is the correct value?

This of course is a simple example and most people encrypt somewhat recognizable artifacts; human language text, files recognizable by headers, etc. So this idea could be expanded to not just scramble data upon output, but also to include a variety of generated 'dummy' artifacts (common file formats, samples of language text, etc) not necessarily included in the core algorithm (the dummy data could be user defined). The dummy data output on incorrect passwords could then possibly include valid JPEG files, WORD files, PNG files, and samples of valid text from a variety of languages.

The result would make the encrypted file very hard to brute force without either a huge amount of computing and human power, or specific knowledge of what is encrypted.

Are there any algorithms out there that work like this? Are there any flaws in the idea itself?

Yes, this is possible (conditionally). It sounds like you want Format Preserving Encryption. FPE works by encrypting from an arbitrary domain $X$ onto $X$. Consequentially, if plaintext $M \in X$ is encrypted to ciphertext $C \in X$, any decryption of $C$ - even with the wrong key - will yield a decrypted message inside of $X$. Thus an attacker doesn't know anything from a decrypted ciphertext if he only knows the original format of the valid plaintexts. All decrypted ciphertexts look like valid plaintexts to him.

For example, your domain might be "all ASCII strings of length 7", or "a NULL-terminated string of numbers with length less than 10", or some credit-card number format. All plaintexts, ciphertexts, and wrong-key decrypted ciphertexts will be in that domain. From your example, you might have a domain of 9 ASCII numeral digits.

(In case it's not obvious: The way an attack typically works is that the attackers are decrypting a ciphertext onto a plaintext message space $Y$, but they know something about the original plaintext that limits the potential domain to some set $Z$ strictly contained within $Y$ (that is, $Z \subset Y$). On a typical cipher we encrypt $\{0,1\}^n \rightarrow \{0,1\}^m$ (one binary string to another), but it's rare that all plaintexts could actually be any binary value, generally they are only a strict subset of the input domain. So we assume the attacker knows which plaintext formats are valid, and they just check decrypted plaintexts against this smaller domain. FPE addresses that issue by only allowing encryption and decryption from and to domains that are valid plaintexts. The attacker will never be able to look at a decrypted value and conclude that it is an invalid plaintext. Eg, if they are decrypting a credit-card number, they have an idea of what a valid decrypted CC will look like, but with an FPE algorithm all decrypted messages will look like a valid CC.)

Note that this won't mitigate the problem if the attacker knows some part of the original plaintext that does not apply to all valid plaintexts. FPE mitigates attacks where the attacker just knows the original message space for all valid messges, but it's possible they know something about the specific message on hand that doesn't apply to other messages. (For example, they may know that the 3rd digit is an 8 for the plaintext in question, but not necessarily an 8 for all plaintexts.) In this case they would have a smaller domain to check decrypted messages against and their original attack will still help them to some extent.

An FPE algorithm can be implemented from an existing block cipher. There are different schemes for turning a block cipher into an FPE, depending on your domain size and such. Some of the constructions are relatively simple given the block cipher and a function that decides whether a raw block cipher output is inside of the desired domain. The Wikipedia page linked to above contains descriptions of some.

As for your example: I think that it's rare to see FPE applied to very large domains, like image files. It's usually only applied to small domains, things like credit-card numbers in databases. I don't think I've seen it used in a case where the domain was larger than a couple block cipher blocks. (But whether you can use FPE efficiently on very large domains is a different question.)


Ed25519 and hierarchical deterministic wallet I'm building a solution based on the stellar codebase and using the Ed25519 curve for the signatures. One of the features I've been adding to the system is a support for hierarchical deterministic wallets according to BIP32. For that use case I've removed the clearing of the lowest 3 bits and setting the 254 bit for derived keys still having this features for regularly generated keys.

This allowed me to implement the HD part, but exposed the signature made by a derived key to the timing and the small-subgroup attacks. The derived keys are used as a single/couple time signers and does not participate in any DH communication.

This brings me to the question whether such schema can be considered secure?

Small-subgroup attacks are not relevant to Ed25519: You never reveal $[n]P$ for attacker-controlled $P$ where $n$ is your secret scalar.  Clearing and setting high bits of the secret scalar to put the highest set bit in a fixed position is not relevant to Ed25519: It is important only for easy implementations of the Montgomery ladder in $x$-restricted scalar multiplication, which Ed25519 does not use.

The only reason to use the same secret scalar clamping as X25519 is to allow the use of the same secret key material and software both for X25519 and Ed25519, e.g. in XEdDSA, and generally for compatibility with existing software.

Of course, you can only clamp the original scalars, not the derived scalar, since standard clamping is not a homomorphism of the scalar ring $\mathbb Z/h\ell\mathbb Z$, where $\ell$ is the large prime order of the standard base point and $h$ is the small cofactor: if your master secret scalar is $s \in \mathbb Z/h\ell\mathbb Z$, and you have random function $H\colon \{0,1\}^T \to \mathbb Z/h\ell\mathbb Z$ mapping tweaks to scalars, there is no way for the holder of the public key $[\operatorname{clamp}(s)]P$ to compute $[\operatorname{clamp}(s\cdot H(t))]P$, while they can compute $[\operatorname{clamp}(s)\cdot\operatorname{clamp}(H(t))]P$.

If you're not restricted to compatibility with existing software, but you still want to make sure low-order base points can't cause trouble, you can use a nonstandard clamping scheme suggested by Ian Goldberg, George Kandianakis, Isis Lovecruft, and Henry de Valence.  Let $\alpha$ solve the CRT system
\begin{align*}
  \alpha &\equiv 1 \pmod \ell, \\
  \alpha &\equiv 0 \pmod h.
\end{align*}
Then for any scalar $s$, the action of $\alpha s$ on a point in the order-$\ell$ subgroup generated by the standard base point is the same as the action of $s$ since $\alpha s \equiv s \pmod \ell$, but $\alpha s$ annihilates any $h$-torsion points since $\alpha s \equiv 0 \pmod h$.  Since multiplication by $\alpha$ is a homomorphism of $\mathbb Z/h\ell\mathbb Z$ and fixes the action of $\mathbb Z/h\ell\mathbb Z$ on the subgroup generated by the standard base point, it doesn't matter whether you do it to the original scalars, the derived scalars, or both.  This technique does not put put the highest set bit in a fixed position, however, so it requires more careful handling in a scalar multiplication ladder.


repeated use of HKDF-extract on the same PRK Regarding HKDF (RFC 5869) - HKDF has two steps, extract and expand.

Some answers on this site suggest that you can extract once, and then generate multiple keys from the resulting PRK by multiple invocations of HKDF-expand (with different info strings).

Other answers say this is not how HKDF should be used, and possibly not safe. However, using HKDF-expand to generate a longer key (say, 256 bits) and then splitting it would be ok. (See D.W.'s answer in Which risks are associated with deriving multiple keys from the same DH secret Z? for example).

When I originally read the RFC I got the impression that it is fine to generate multiple keys from the same PRK using different info strings, but re-reading it, I can't see this being substantiated anywhere, i.e., the RFC does not explicitly allow multiple HKDF-expands on the same PRK (and implicitly seems to not support it).

So:

can HKDF-expand be used multiple times on the same PRK/HKDF-extract result?
if not, is it safe to generate a longer key using expand and split it?

Taken directly from the RFC:

  The second stage "expands" the pseudorandom key to the desired
  length; the number and lengths of the output keys depend on the
  specific cryptographic algorithms for which the keys are needed.

The use of the plural here suggests (at least to me) that yes, it's ok to expand the same PRK several times with different contexts.  Can you provide any links (within SE or otherwise) that suggest otherwise?

Also from the RFC, regarding the 'info' parameter of the expand step:

  In particular, it may    prevent the derivation of the same keying
  material for different    contexts (when the same input key material
  (IKM) is used in such    different contexts).


Usage of parameter "b" of an elliptic curve over GF(p) I'm not fit with elliptic curves from a mathematicians point of view, so I hope, that this beginners-question is not too silly:

I use a library which permits certain operations on elliptic curves over $GF(p)$. I recogniced, that all elementary operations (point doubling - $2P$, adding - $P_1+P_2$ , exponentiation with a scalar number - $kP$  are not using the parameter $"b"$ of the underlying equation

$y^2=x^3+ax+b$

Only the check, whether a given Point is on the curve needs this parameter. This is understandable for me, because both sides of the equation above must be compared.

But why do the mentioned elementary operations NOT need b at all.

During writing this, I found from a white paper, that the mapping

$(x_1,y_1), (x_2, y_2) \rightarrow (x_3, y_3)$

indeed doesn't include $b$.

Is this just a mathematical coincidence or is there some deeper reason for this?

EDIT:

My personal explanation is, that, taken for granted that a given point (x,y) is part of a certain curve $(A, a, b, p)$, $b$ can (of course) be calculated from the defining equation and the knowledge of x,y,a, so additional specification of b would be redundant. Is this right? Then it would answer my question, and it was "silly" ;-)

Thanks

.

Adding two points $(x_1, y_1)$ and $(x_2, y_2)$ with $x_1 \neq x_2$ gives point $(x_3, y_3)$ with

$$x_3 = (\frac{y_2 - y_1}{x_2 -x_1})^2- x_1 - x_2$$

$$y_3 = (\frac{y_2 - y_1}{x_2 -x_1}) (x_1 - x_3) - y_1$$

The case $x_1 = x_2$ is either adding the inverse or point doubling.

Doubling point $(x_1, y_1)$ with $y_1 \neq 0$ gives point $(x_2, y_2)$ with

$$x_2 = (\frac{3 x_1 + a}{2 y_1})^2 - 2 x_1$$

$$y_2 = -(\frac{3 x_1 + a}{2 y_1}) (x_1 - x_2) - y_1$$

So addition does require neither $a$ nor $b$, whereas point doubling and exponentiation with a scalar number requires only $a$. Checking if both points belong to the same curve also only requires $a$.


Decoding an MD5 hash where I already know most of the string Let's say my friend has made an md5 hash of an email address and sent it to me. The email address will be something like 'jessica_XXXX@gmail.com', and I know it begins with 'jessica_' and ends with '@gmail.com'

Does software exist that would allow me to bruteforce the middle part, which is only four unknown characters?


What symmetric algo does TLS use? So my understanding of TLS is that it uses asymmetric cryptography such as DH to perform a key exchange, once this has occurred it then used an symmetric algorithm for the data exchange. (Obviously I am missing a lot of detail here and it may be slightly inaccurate but I think thats generally the high level idea?)
My question is once the key exchanged has taken place what symmetric algo is used? AES? Or is it implementation specific? Or developers preference???

My question is once the key exchanged has taken place what symmetric algo is used?

Well, that is negotiated between the client and the server (and that negotiation takes place along with the key exchange).
TLS 1.2 had a rather long list of symmetric algorithms that the client and server could choose from; in TLS 1.3, they trimmed it back significantly, currently the options are AES-GCM, ChaCha20/Poly1305 and AES-CCM.


Is there a bulletproof way to know a file has been successfully decrypted? I am wondering whether there is a bulletproof way to know if one is successful in decrypting a file.

As an example, say I encrypt a text file and protect it with a 3 letter password. I use brute force to decrypt it, but two different passwords lead to a file that contains English intelligible text. Is there a way for me to know which one is the original one? In other words, is there an infallible way to know I've entered the password correctly?

From the application designer's perspective: Yes, by using an authenticated cipher like AES-GCM or crypto_secretbox_xsalsa20poly1305, which you should do anyway.  See the scrypt tool for an example of an application that does just that: encrypts a single file using a key derived from a password using an authenticated cipher—specifically, the tool uses AES-CTR and HMAC-SHA256 in encrypt-then-MAC composition, but these days it is almost always simpler to reach for AES-GCM or crypto_secretbox_xsalsa20poly1305.

From the adversary's perspective: Can't say without more information about the plaintext in your particular case.

In most applications in practice, the plaintext has some identifiable pattern even if the application foolishly didn't use authenticated encryption.  For example, an HTML document will usually begin with <html> or <!DOCTYPE; an email will usually have a header and be limited to 7-bit US-ASCII.

In general, we consider a cipher to be secure for confidentiality (in the formal sense of IND-CPA) only if an adversary can't distinguish patterns in the plaintext given ciphertext even when the adversary can choose the pattern.  Of course, a 3-letter password admits a very short brute force attack, so we don't consider that to provide any meaningful security.

  I use brute force to decrypt it, but two different passwords lead to a file that contains English intelligible text. Is there a way for me to know which one is the original one?

Again from the adversary's perspective, let's suppose there's no authenticator to verify a decryption, and the pattern you're looking for is that the text is all 7-bit US-ASCII.  Actually you're probably looking for a pattern that is much sparser in the set of all bit strings, but this one is easy to quantify.

We can reasonably model each byte of a wrong decryption as independent uniform random, so there's a $1/2$ chance each byte in a wrong decryption is 7-bit US-ASCII independently, and if your file is $n$ bytes long, there's a $1/2^n$ chance that all bytes in a wrong decryption are 7-bit US-ASCII.

In cryptography we generally consider an event ‘not gonna happen’ when its probability is well below $1/2^{100}$.  If there are $2^t$ keys chosen uniformly at random (say, $2^{256}$ for AES-256 or Salsa20), all it takes is a bit more than $100 + t$ bytes in this model before you stop worrying about any false positives from wrong decryptions—that is, when the probability of a false positive from this pattern is at most the probability of a false positive from a cryptographic authenticator like Poly1305.

But if you do somehow find yourself confronted with two candidate plaintexts that both meet all your criteria, well, there's nothing in cryptography to help discriminate between them, and you'll have to use outside information to help you decide.

This model assumes that the key is substantially smaller than the message and the cryptosystem is not hopelessly broken by related-key attacks; for example, it breaks down when the key is a one-time pad, but it is a reasonable model for, say, AES-CTR or Salsa20.  Specifically, let $K$ be the event of guessing the key correctly, and let $A$ be the event that the ciphertext decrypts under the candidate key to US-ASCII.  The hypothesis is that that $P(A \mid K) = 1$ meaning that the true plaintext is known to be US-ASCII.  By Bayes' rule,

\begin{align*}
  P(K \mid A)
  &= P(K) \frac{P(A \mid K)}{P(A)} \\
  &= P(K)
     \frac{P(A \mid K)}
          {P(A \mid K) P(K) + P(A \mid \lnot K) P(\lnot K)} \\
  &= \frac{P(K)}{P(K) + P(A \mid \lnot K) (1 - P(K))} \\
  &= \frac{1}{1 + P(A \mid \lnot K) (1/P(K) - 1)}.
\end{align*}

The additional modeling assumption about the cipher is that $P(A \mid \lnot K) = 1/2^n$.  If we suppose the key is uniformly distributed among $2^t$ possibilities (e.g., $t = 256$ for Salsa20 or AES256-CTR) so that $P(K) = 1/2^t$, then this reduces to

\begin{equation*}
  P(K \mid A)
    = \frac{1}{1 + 2^{-n} (2^t - 1)}.
\end{equation*}

When $n < t$, meaning the key is underdetermined, this is about $2^n\!/2^t$.  For example, if you have a 100-byte text and a 256-bit key, $P(K \mid A) \approx 1/2^{156}$.  However, when $n > t$ so that $2^n \gg 2^t - 1$, this is about $1 - 2^{-n}$ and rapidly converges to 1 as $n$ increases and overdetermines the key with more bytes of plaintext that must match the pattern.


Merkle signature + PRNG? In the section 3 (page 44) of the book "Post Quantum Cryptography", it says:

  Then each one-time signature key must be generated twice, once for the MSS public key generation and once during the signing phase.

Also defined $\text{PRNG}$: $\text{Seed}_{\text{in}} \rightarrow (RAND, SEED_{\text{out}})$, where $\text{RAND}$ is a random number.

Finally, it describes an example of MSS + W-OTS. Here, $\text{SEEDOTS}_j$ is used to generate signature key $X_j = (x_{t-1},...,x_0)$ where $x_i$ are generated on $(x_i, \text{SEEDOTS}_j)=PRNG(\text{SEEDOTS}_j)$.

My question: How is possible generate  the same key for public key generation and during the signing phase, for each one-time signature key, if $x_i$ is random (by definition of $\text{PRNG}$)?

Probably it's possible because they are using a deterministic pseudorandom random number generator (PRNG) to generate these values, as a deterministic function of some seed, which is remembered by the holder of the private key.


Winternitz One-Time Signature I am reading the page 38 in this "Post Quantum Cryptography" book (Equations 8 and 9). My question is, why to compute the verification key $Y$, $f$ is applied $2^w-1$ times? Are there any security notions involved?

$w$ is a parameter that can be freely chosen, to maximize performance.   Each element of the signature encodes $w$ bits of the message to be signed, so the larger $w$ is, the fewer elements you need to include in the signature.

If you make $w$ large, then signatures can be shorter; however, the tradeoff is that key generation, signing, and verification run slower.  If you make $w$ small, then signatures are longer; however, key generation, signing, and verification run faster.  So this is a tradeoff between the size of the signatures vs the running time of the scheme.  You can choose $w$ to provide the best tradeoff for your application.  The scheme will be secure no matter what value of $w$ you choose.


Is a PBKDF2-derived master key easier cracked if very many Data Protection Keys are derived from it? I'm referring the NIST document about PBKDF2, NIST Special Publication 800-132, Recommendation for Password-Based Key Derivation,
Part 1: Storage Applications, Page 8 and 9, section 5.4 Using the Derived Master Key to Protect Data.

Here is Figure 3 from this document:

I am using the Option 1b: Generate Master Key (MK) first, and the get Data Protection Key(DPK) for file encryption.

I have 3 questions about this scheme:

If I have a lot (more than $2^{32}$) of files to be encrypted, each file is encrypted using newly generated DPK. Will it somehow cause the MK to be easily found? or easier to find?
The document does not specify which KDF to be used when generating DPK. Can I use back the PBKDF2 again?
Should I generate new random salt for each DPK? Or should I use something related (timestamp or file name) for the salt?

Reference: Secure Programming CookbookΤΜ for C and C++,
Page 142,
4.11 Algorithmically Generating Symmetric Keys from One Base Secret

Answering your three questions in order:

  "If I have a lot (more than $2^{32}$) of files to be encrypted, each file is encrypted using newly generated DPK. Will it somehow cause the MK to be easily found? or easier to find?"

It's not going to make it harder.  But no, as long as the KDF you're using lives up to its security claims, in practice it should not be feasible to construct the master key from the derived keys even if you have a lot of them.

If you want to be sure, check the standards and/or white papers defining your KDF and see if the security claims come with any restrictions like "assuming that at most $2^{64}$ bits of key material are derived from a single master key".

  "The document does not specify which KDF to be used when generating DPK. Can I use back the PBKDF2 again?"

In practice, yes, you could use PBKDF2 also for the second-stage KDF.  Since your input has already been key-stretched by the first application of PBKDF2, I'd suggest using an iteration count of 1 for the second stage to improve performance.  In fact, I'd recommend doing this whenever you want to derive more than one hash output block's worth of key material using PBKDF2, since it reduces the attacker's work advantage.

To conform with NIST SP 800-132, your second-stage KDF needs to be "approved".  Specifically, it needs to be (section 3.1):

  "Approved: FIPS-approved and/or NIST-recommended. An algorithm or technique that is 1) specified in a FIPS or NIST Recommendation; or 2) adopted in a FIPS or NIST Recommendation; or 3) specified in a list of NIST-approved security functions."

There are several NIST Special Publications describing key derivation functions.  SP 800-132 specifically references NIST SP 800-108, "Recommendation for Key Derivation Using Pseudorandom Functions", which specifies a set of approved methods for constructing a KDF from an approved pseudorandom function (HMAC or CMAC).  Then there's also NIST SP 800-135 rev. 1, "Recommendation for Existing Application-Specific Key Derivation Functions" and NIST SP 800-56C, "Recommendation for Key Derivation through Extraction-then-Expansion".  In particular, SP 800-56C specifically mentions HKDF (RFC 5869) as an instance of the general construction described therein, which I believe makes it approved, at least as long as it's instantiated with an approved hash function, such as SHA-2 or SHA-3.

As for PBKDF2, I'm not quite sure whether it should be counted as an "approved KDF" for this purpose or not.  Certainly it has been approved by NIST for password-based key derivation, and one could (and I certainly would) argue that key-based key derivation is merely a subset of that, but I'm not sure if that argument is actually explicitly supported by any official NIST publication.  In particular, I'm not sure if the use of PBKDF2 with an iteration count of 1 as a KBKDF is really sanctioned by any NIST publication.

In any case, HKDF isn't too different from PBKDF2 (they're both based on HMAC), and should be a simple and safe choice for a second-stage KDF.

  "Should I generate new random salt for each DPK? Or should I use something related (timestamp or file name) for the salt?"

The important requirement for the salt is that it should be globally unique.  A sufficiently long random string (at least 128 bits, preferably 256) is certainly one way to satisfy that requirement, but there are other options too.

For example, in the KDFs described in SP 800-108, the "salt" is, in effect, specified as the concatenation of two strings, Label and Context (separated by a null byte), defined as:

  "3) Label – A string that identifies the purpose for the derived keying material, which
  is encoded as a binary string. The encoding method for the Label is defined in a
  larger context, for example, in the protocol that uses a KDF.

  4) Context – A binary string containing the information related to the derived keying
  material. It may include identities of parties who are deriving and/or using the
  derived keying material and, optionally, a nonce known by the parties who derive
  the keys."

For your use case, the Label could include a number or file name identifying the DPK you want to derive, while Context could include a user identifier, and perhaps a fixed application identifier.

Similarly, HKDF takes both a "salt", used in the compression step, and an "info" string used in the expansion step, defined as:

  "salt: optional salt value (a non-secret random value); if not provided, it is set to a string of HashLen zeros."

and

  "info: optional context and application specific information (can be a zero-length string)"

The "salt" in the HKDF compression stage is basically the same as the salt for PBKDF2.  Indeed, HKDF allows omitting the compression stage entirely if the input is already a cryptographically strong key, such as the output of PBKDF2, so one could basically replace the compression stage of HKDF with PBKDF2.

The "info" string, however, is part of the second (expansion) stage, and can, among other things, be used to allow several different keys to be derived from the same compressed master key (PRK in the HKDF terminology).  For example, in your use case the "info" string could consist of a file number / name, a user ID and perhaps an application ID, plus whatever other information might be relevant.  The important part is that it should be globally unique for each DPK.


Is Argon2id safe from the discovered Argon2i issues? So far, as I understand it, two ways to reduce the complexity of Argon2i have been found, one of which was fixed in Argon2 1.3, and one of which is still unfixed but is not a practical problem given enough Argon2i passes.

What I have not seen properly explained anywhere, is whether these weaknesses effect Argon2id, or if the combination is still good - basically, is the weakness in Argon2i enough to undermine the benefits of using it as the first half-pass of Argon2id, or do the passes of Argon2d after basically "cover" it somehow?

My naive intuition is at worst you lose the side-channel resistance, but does this compromise the side-channel resistance?

The weakness I am thinking of that is still applicable to Argon2 1.3 is the one described in "Towards Practical Attacks on Argon2i and Balloon Hashing"

Related to, but not a duplicate of this one, because while the comments and answer there suggest that

argon2id 1.3 takes those known attacks into account, and
argon2id is different enough from argon2i that it is probably safe to assume attacks on the latter do not apply to the former,

it is not clear to me that this actually fully covers my question, and certainly when I was looking for duplicate questions, it was not obvious to me that a question about "which one to choose?" would even touch upon my question - certainly the question as titled points in a completely different direction.

Covers Argon2id the known attacks?
Although there is no research into this, I would say that Argon2id is probably not vulnerable to the attack shown by Alwen and Blocki. Maybe an attack on the first part (the Argon2i part) could be practically applicable, but the advantage for the attack quality would be ruined by the second part (the Argon2d part), because the second part is the more memory-hard one.
Is Argon2id still side-channel resistant?
Reasonably or at least halfway. If you successfully perform a cache-timing attack on the second part (the Argon2d part), you will receive certain patterns, but they only refer to equal outputs of the first part (the Argon2i part), not to passwords.

Both attacks are complex and it is not entirely clear whether they are feasible today.

As far as I know, cache-timing attacks have not yet been executed against password hashing methods in the wild (for example against Scrypt). However, it has been shown that this is basically possible and it is quite feasible that such attacks will be carried out in the future.
Schemes based on the "Bit Reversal Graph" like Argon2i and Catena-Dragonfly seemed to be the solution - they were just less memory-hard.

Although there were voices that suggested that, the authors of Argon2 did not originally include the possibility of combining Argon2i and Argon2d (a hybrid structure), presumably to avoid making the usage more complicated. Lyra2 and other schemes of the password hashing competition relied on the hybrid structure from the beginning, mainly as a compromise between resistance against cach-timing attacks and higher memory-hardness.

It was only after the end of the password hashing competition that it became apparent that methods that are resistant to cache timing attacks are more vulnerable in other ways.

The attack of Alwen and Blocki is based on several conditions such as no parallelism (p=0) and assumptions about (probably realistic) hardware available in the future. But still a weakness is shown, which could possibly be extended even further.
I don't know of any official statement about this, but I suppose that in view of the attacks on Argon2i, the authors of Argon2 are now tending to prefer the hybrid structure.

Password hashing is an area that is much less explored than, for example, block cipher. It is therefore possible that new cryptoanalyses will be published and further changes may be necessary.


Does a key exchange protocol with mutual authentication which does not provide forward secrecy can be proven secure in Bellare-Rogway model? Is forward secrecy a necessary security property for a AKE protocol to be proven secure in Bellare-Rogway model? Is freshness also a necessary security property for a  AKE protocol to be proven secure in Bellare-Rogway model? If not why A(k) MTI protocol with key confirmation can not be proven secure in the Bellare-Rogway model?

This depends on what you mean by the Bellare-Rogway model? Do you mean

BR93: the original AKE model by Bellare and Rogaway?
BR95: their follow-up AKE model which incorporates the three-party case (among other things)?
BPR00: their third AKE model (together with Pointcheval), which additionally deals with the case of password-based authentication?
Or any of the many derivative models which extends or updates the above models in various ways, but still are generally referred to as belonging to the family of "BR-like" models?

If the BR-model in your question is interpreted specifically as being about any of the first three models above, then the answer is:

BR93: forward-secrecy is not required. This is because the model does not give the adversary any means of obtaining long-term keys.
BR95: forward-secrecy is required. This is because BR95 provides a Corrupt-query which gives the adversary access to a user's internal state (including its long-term key).
BPR00: forward-secrecy is required. Again, in this model the adversary is provided with a query that allows it to obtain a user's long-term key.

However, if your question is more generally about the BR-model thought of as a family of models, all centered around some core modelling concepts, then the answer is: it depends. By this I mean that the BR-model can be modified to accommodate both forward secure and non-forward secure protocols. To model a forward secure protocol, include a Corrupt-query (or something similar), which allows the adversary to obtain long-term keys. To model a non-forward secure protocol, leave out this query (or at least restrict it for the Test-session).

Regarding your question about freshness, this is not really about the protocol per se, but rather a modeling artifact. I.e., by the queries and capabilities given to the adversary in the BR-model (whichever flavor you want), there will always be ways for the adversary to trivially break any protocol. This is independent of how secure the protocol actually is, because these trivial attacks are inherent to the model, and do not correspond to any real-life attacks. Thus, the concept of freshness is introduced to correct for these trivial attacks, by saying that the adversary is only "allowed" to do attacks which are not deemed trivial. I should note, however, that actually figuring out what the trivial attacks are, can sometimes be a bit tricky.


Is encrypting a single 128 bit block with AES ECB "safe" I want to encrypt a small piece of data that is less that 16 bytes in size (think SSN), and I'll be using a 256bit encryption key.  The typical suggestion is to never use ECB, but if there is just a single block being encrypted, is it a concern?

The reason I want to use ECB is because I want the encrypted value of the block to be consistent between encryptions for other reasons (so I can check if a value already exists by just comparing the uniqueness of the cipherText).

Updated: Also note that these encrypted values will be stored in a set, so there will not be data leakage by having multiple encrypted values of the same plainText available.

16 bytes is 128 bits, which matches the block size of AES-256, but not "256 bit block" in the (original) title. Hence the question is ambiguous: was it meant 16, or 32 bytes?

For 16 bytes: ECB reduces to single-block encryption, and yes ECB is safe, for a definition of safe that let one test identity of plaintexts by testing identity of the ciphertexts.

For 32 bytes (e.g. a US SSN encoded in UTF16 or perhaps ASN.1 or XML): no, ECB is unsafe. This extend to any standard block cipher mode of operation modified by fixing IV. Problem is, plaintexts that match in the first block, but not the second, will match in the first block of the ciphertext, but not the second, which leaks information (e.g. in the US SSN format, it allows to cluster plaintexts by identical area number if the block frontier happens to be on the right of that). You need a 256-bit block cipher, such as Rijndael (a superset of AES) instantiated with 256-bit block. There are ways to construct a 256-bit block cipher from AES-256, but I know none with both a sound security argument and either a short statement, or performance close to Rijndael.

Note: Public key encryption can not be used in the context where "encrypted value of the block (is) to be consistent between encryptions" and the plaintext is low-entropy (enumerable, or guessable). Here, there are few enough SSNs that they can all be enciphered by anyone (knowing the public key), and compared with the ciphertext, leaking the plaintext.

Update: it is now clear that the question is about 16 bytes. I wonder if some day, UTFx with x>8 will catch in the US.


Is it safe to send HMAC and plaintext in the same message? If a certain protocol sends $plaintext$ and its corresponding HMAC then is such a protocol prone to key extraction attacks ? Intuitively , HMAC is $ciphertext$ generated from $plaintext$, (although not an encryption of plaintext ), so the only secret being $key$. Will sending both of them together weaken the protocol ?

If a certain protocol sends plaintext and its corresponding HMAC then is such a protocol prone to key extraction attacks?

No, a HMAC uses a cryptographically secure, one-way hash underneath. That means that it should be impossible to find the input as long as the input cannot be brute forced. If you use a key of the right size (identical to the hash output size) and with enough entropy then the key cannot be found, even if the plaintext is available to an attacker.

  Intuitively , HMAC is ciphertext generated from plaintext, (although not an encryption of plaintext), so the only secret being key.

An authentication tag is not the same thing as ciphertext. But even with known plaintext & authentication tag (or ciphertext) the key should not be found.

Of course, an attacker should also not be able to create a new plaintext / authentication tag pair even if the attacker knows multiple other such pairs. Therefore HMAC also protect against e.g. length extension attacks, for which knowledge of the key is not required.

  Will sending both of them together weaken the protocol?

It is nowadays common to HMAC the ciphertext (encrypt-then-MAC), for instance to avoid padding oracle attacks on CBC mode encryption. So for the HMAC, the ciphertext is the plaintext in such a scheme. If knowing the plaintext / authentication tag is a vulnerability then many protocols are broken.

Commonly cryptographic schemes should even be secure if the attacker chooses the plaintext (CPA secure).


Why Elliptic Curves? What is the benefit of using elliptic curves over the standard finite field, when the cyclic subgroup we consider of the EC's  solution group is just isomorphic to some integer residue class of prime order? Is it because the group operation is more complex?

The answer is about the difficulty of discrete logarithm. The notion of isomorphism does not capture all that matters in cryptography; we also need to consider computing costs.

Suppose that we have an abelian group $\mathbb{G}$ with additive notation. Let $G$ be a conventional element of $\mathbb{G}$ of order $n$. The subgroup generated by $G$ is:
$$\langle G\rangle = \{ xG \ | \ 0\leq x\lt n \}$$
That subgroup is isomorphic to $\mathbb{Z}_n$ (the integers modulo $n$) and the isomorphism is easily computed in one direction, from $\mathbb{Z}_n$ to $\langle G\rangle$ with a double-and-add algorithm: from $x$, one can compute $xG$ with less than $2\log n$ group operations (see this in the case of elliptic curves, but it really applies to any group).

Discrete logarithm is about computing the inverse isomorphism, i.e. computing $x$ from $xG$. Generically, when the only operations that you can do on elements of $\mathbb{G}$ are applying the group law, and comparing two elements for equality, then the discrete logarithm cannot be computed with an average cost of less than $\sqrt{n}$ operations. We know several "generic" algorithms that offer that kind of performance, e.g. Pollard's rho algorithm. It can be proven that no faster algorithm exists, that would work on a generic group.

Of course, generic groups are an abstract concept. What we have in practice are groups on which we know how to compute the group law and compare two elements, and possibly have some extra information on the group structure that may or may not help in computing discrete logarithms.

Right now, when the group is a randomly chosen elliptic curve, then we have no idea how to compute the discrete logarithm faster than by applying a generic algorithm. Thus, a "256-bit curve" (sub-group order $n$ is a 256-bit prime) is enough to achieve a "security level of 128 bits" (i.e. unbreakable with existing and foreseeable technology). Note that there are some specific curves with a special structure for which we know faster discrete logarithm algorithms (e.g. supersingular curves).

However, when the group $\mathbb{G}$ consists in integers modulo $p$ for some prime $p$, with multiplication modulo $p$ as group law, then we do know faster (subexponential) discrete logarithm algorithms, in particular in the large family known as index calculus. To achieve a security level of 128 bits, one has to choose a modulus substantially larger (somewhere between 2500 and 3000 bits).

Since field operations tend to have a quadratic cost in the field size (at least with the kind of algorithms that are fastest in fields commonly used in cryptography), the speedup obtained by using an elliptic curve and a relatively small field more than compensates the overhead of elliptic curve operations. In practice, on today's computers and for comparable security levels, with decently optimized implementations, elliptic curves offer a 5x to 20x speedup. Which is why we use them. As an added bonus, the corresponding curve points can be encoded over fewer bits, so this also saves a bit of network bandwidth in some cases.


Executing encrypted code? I want a code 'black box' that receives data inputs, processes those inputs, then sends out the outputs.

I want the code to be encrypted, or somehow obfuscated.

Is there any known way to do achieve this outcome?

No, assuming your code is running in an environment completely controlled by an adversary (no TPM etc.). Note that if the instructions were encrypted in some way we assume an adversary could simply intercept them after they are decrypted.

Your best shot is to obfuscate the code making it cumbersome for someone else to grasp the logic behind it. This can never give you security in a cryptographic sense.


Stream Cipher Key Stream from Successive Hashes I'm currently studying crypto and wondered what would be wrong with the following process...
I want to encrypt a long message $M$ with a short symmetric key $K$ and a public nonce $X$.
The idea is to increase the length of $K$ with successive hashes
$$K' = H(X\mathbin\|K) \mathbin\| H(H(X\mathbin\|K)) \mathbin\| \cdots$$
until $length(K') = length(M)$.
Then encrypt with
$$M' = X \mathbin\| (M \oplus K').$$
I'm not suggesting that I would use that instead of using something like libsodium.
But I would like to have some intuition about stream ciphers with something that I can understand completely.
Is there anything fundamentally broken with this approach?
Is it possible to adjust this approach with minimal changes to make it not broken?

The Insecurity of Proposed Scheme
It is not as secure as it seems, in modern cryptography standards it is totally insecure. It is vulnerable to basic Known-Plaintext attacks (KPA) and in Modern Cryptography, we want a cipher secure against at least Chosen Plaintext Attack (CPA) or better Ind-CPA.
Now take the idea
$$K' = H(X\mathbin\|K) \mathbin\| H(H(X\mathbin\|K)) \mathbin\| \cdots.$$
If there is a known-plaintext block for the first output $H(X\mathbin\|K)$ then attackers can hash again and again (sometimes written as $H^s(X\mathbin\|K)$ ) to reveal the others without needing a key. So your design fails the next-bit test, i.e. the next bit of your keystream is predictable with 100%. The known block is not restricted to the first block, it can be anywhere except for the last block. All output keystream after the known block can be calculated. The previous blocks are secured with the pre-image resistance of the hash function.
The CTR mode with Hash
Instead, we used the CTR mode ( [1] as it is designed for PRF - Pseudo-Random Function - ( here we assume that the $H$ is a PRF). The CTR mode is CPA secure.
$$H(k,0) \mathbin\| H(k,1) \mathbin\|  \cdots \mathbin\| H(k,\ell)$$ where the $\ell$ is the number that your message size divided into output size $b$ of the $H$ i.e. $\ell = len(m) / b$
The CTR mode doesn't require a PRP (Pseudo-Random Permutation, not proven yet, however, like AES),  since it doesn't need the reverse of the encryption. For example, see the ChaCha20. Some restricted environment saves a lot of space for the implementation.
Transforming this scheme into OFB mode
The OFB mode is also CPA secure (the ECB is not). OFB produce the stream as $O_j = E_k(O_{j-1})$ with $O_0 = IV$. The encryption is performed as $C_j = P_j \oplus O_j$
As noted by SEJPM in the comments; Let define $H'(m)=H(m\|K)$ and produce the keystream similar to OFB.
$$K'=H'(X)\mathbin\| H'(H'(X))\mathbin\| \ldots$$ Note that in every step the key is added again. So the attacker needs the key to process from the known output stream. Assuming the used hash is a Random Oracle (RO) then this converts it into PRF then we can use the security arguments OFB.
Note that the hashes are candidates to Random Oracles.


What can be said about the order of short Weierstrass curves with $a=1$ and $b=0$? I am looking at a elliptic curves of the form $E:y^2=x^3+x$, i.e. short Weierstrass curves wtih $a=1$ and $b=0$, defined over a field $\mathbb{F}_p$ with $p$ being a safe prime. Somewhat interestingly, this is kind of an inverse Koblitz curve (where $a=0$ and $b\ne0$).
Because $b=0$, the case of $x=0$ will always be a valid point of order 2 at $(0, 0)$.

As far as I can tell, such a curve has a necessary cofactor $h=2\cdot2$, but I can't seem to find the reason for another point of order 2.
Are there other things that can be said about the curve's order?

The reason this is of interest is because older Windows product key systems used curves of this particular form.

The curve $E$ given by the equation $y^2 = x^3 + x$ is a Montgomery curve. Those are
are the form $By^2 = x^3 + Ax^2 + x$, so in this particular case we have $A=0$ and $B=1$.
The points of order $2$ have their $x$-coordinate as a root of $x^3 + x$. If $-1$ is a square over $\mathbf F_p$, then the points of order $2$ are $(0,0)$, $(\sqrt{-1},0)$ and $(-\sqrt{-1},0)$. Otherwise there is only $(0,0)$.
On those curves, the closest to a prime for the cardinality is $4\cdot\text{prime}$ for both the curve and its quadratic twist (such as the Goldilock curve), or $8\cdot\text{prime}$ and $4\cdot\text{prime}$ (such as Curve25519).


Is there something like a secure hashmap? TL;DR: Is there such a thing as a hashmap whose contents cannot be read unless you have the right encryption key, and where each encryption key only works for a specific key value pair?

More context:

Say you're building an offline first web application and want to save the client from having to do a bunch of round trips to the server to ask for data. Within such constraints you may decide to, say, provide a whole dump of the database when the client first loads the site, and then the client can query its own copy of the database without needing to talk to the server.

You wouldn't want sensitive data to be part of the database dump, so you're not going to include user emails and passwords in the dump. But here you run into a problem: part of the website relies on user data (perhaps a user wants to view another user's profile) and would then need to query the server.

Given that we want to avoid any additional requests from the client to the server beyond the initial request for the db dump, how could this be achieved? Let's assume you wouldn't include emails and passwords in the dump, but user data that is publicly available, such as user handles and full names.

In such a case, you could simply include user handles and full names in the db dump in plain text. But you don't want to do that because it would give away all users' names at once, as well as metadata such as how many users your site has, etc. If a user reads some other user's handle and name by browsing your site, that's one thing - but if he can read all users at once, that's a problem.

So I'm wondering if part of the dump that contains user data could be made of a sort of "secure hashmap". What I mean is that its contents are not readable unless you have the right key; and even then only those contents that correspond to the key can be read.

If there isn't, I would imagine its implementation to go something like the following:

It works like a regular hashmap, with the exception that all its keys are hashed, and its values are encrypted. That way, even though the consumer could iterate over all keys and values, he wouldn't be able to do anything with them. When a piece of privileged information that acts as a key into the hashmap is made available to the consumer - say, a user handle - the lookup mechanism could first hash the user handle, use the result as a key to the hashmap, and then the user handle would allow him to decrypt the corresponding value (e.g. the full name corresponding to that user handle). The producer creates the hashmap by hashing its keys and encrypting its values by partly using their keys.

So in short, if the producer has a hashmap that contains:

"foo" => "bar"

He then turns it into

"1234" => "6%!*3"

where "1234" is the result of hashing "foo", and "6%!*3" is the encryption of "bar" using "foo" as encryption key (or something along those lines, I'm afraid I don't know much about encryption - what I mean is that it should be possible to use the string "foo" to decrypt "6%!*3").

Am I trying to reinvent the wheel here? If not, is the implementation I'm proposing secure?

Edit: I just realized that doing it the way I proposed above would still divulge the number of entries in the hashmap. Ideally, that could be avoided, too.

where "1234" is the result of hashing "foo", and "6%!*3" is the encryption of "bar" using "foo" as encryption key (or something along those lines, I'm afraid I don't know much about encryption - what I mean is that it should be possible to use the string "foo" to decrypt "6%!*3").

So you want to encrypt the usernames, then use the username as an encryption key to the email address and other data?

This is doable and not difficult. If your usernames are unique, you can run the username through a PBKDF to generate a symmetric encryption key, then use it to encrypt the rest of the user's data. If they are non-unique, you need to concatenate the username with a salt first (a piece of non-secure data such as UserID).

My primary concern would rather be with whether the username can be used as a secret. If there is a public user profile, it can be trivially easy to obtain the complete list of usernames by querying the server for users with ?id=1, ?id=2, and so on. Many web applications, e.g. forums, outright offer a complete list of users.

Even if the username serves as a log-in only, and not for sharing anything, it's common practice to use the same username across multiple websites. Just trying each out of a few million usernames grabbed from various sites on the web, which don't make a secret out of them, could probably give one access to about half your entries. Large username dumps are publicly available.

It would be best to find something that is not publicly available to use as the encryption key. Unfortunately, mass dumps or email addresses are also readily available on the web.


Hardware Random Numbers - How to convert Voltage signal into binary? I have a physical unit, e.g. a resistor. I bias it with current and measure the voltage. Let us assume that the fluctuations ($\Delta V=V-<V>$) of this voltage signal are random. Now, $\Delta V$ contains floating numbers with some certain significant digits, say [1.243, 3.567, -3.987, ..., etc]. To test these random numbers (using something like DieHard test), I need to convert these values into binary, 0 or 1.

How do I do that? One way to do it is to set a limit, say 0, such that positive values are mapped to zeros and negative values are mapped to ones (or vice versa). Is there any better way to do it?

What you want to do depends on your objective.

If you only want to make a good RNG from the values you have, so that it passes a Diehard test (passing the test being the objective), that's fine and easy. You do not need to know, or care, about how the values are obtained; essentially, you can take whatever form the "floating numbers" reach you (be it characters coding numbers in decimal separated by newline character, words in whatever IEEE 754 format..) and feed that to a CSPRNG. Here is one of the simplest possible implementation: you decide a number $n$ of values to process (or a duration during which values will be processed), and hash whatever form the "floating numbers" representing these values reach you using SHA-256, giving a 256-bit $H$. You then produce random bits using HMAC-SHA-256, with key $H$, and input some counter initialized to zero and large enough to never repeat. This output will pass DieHard or any pre-existing RNG test (that works and is correctly interpreted). That's including if $n=0$ (illustrating that passing such test is not a good argument that a RNG is a good TRNG).

A very different objective is estimating how likely it is that a RNG made according to the above sound principle (feeding a CSPRNG with your source) gives the same output for $m$ uses (especially: on power-up of some device under some well-defined and attacker-controlled conditions), and how large $n$ should be to make this practically impossible. To do this accurately based on an analysis of a stream of the "floating numbers" (rather than on actual data gathered at numerous power-up), a good model of the physical setup and data processing chain leading to the "floating numbers" would be required.

But what you get with LabView from a modern digital scope (or worse, voltmeter) has gone through much undocumented preprocessing, so you can't do this. It remains a reasonable objective to give a lower bound on the actual entropy gathered. Update 2: A RNG test such as DieHard  is not intended for this, but here is something derived that should do: replace each pair of "floating number" by bit 1 if the first number is more than the other, or 0 otherwise. If the resulting sequence pass the DieHard test, then it is likely that each "floating number" has at least $1/2$ bit of entropy (thus feeding all the bits in $n=512$ consecutive representations of "floating number" will seed any sound CSPRNG with at least 256 bit of entropy). If not (that'll depend on the source), try again replacing each set of $k$ bits by the XOR of these bits, increasing $k$ until the test pass; then it is likely that each "floating number" has at least $1/2k$ bit of entropy, so that $n=512k$ will do.


Generate a per data shared secret vs per session I have read about SSL that they persist the shared-secret for the entire session. However, someone in stackoverflow suggested a way of generating a shared secret for each data to send and then send that shared-secret encrypted by client's public key with the intended message/data. The client would then have to decrypt the shared-secret first for that message using its private key then decrypt the message by the decrypted shared-secret.

The opposite is true for client to server connection.

My question is what advantages this has over the persistent shared-secret per session?

A session key is used to share a symmetric key over asymmetric encryption. The reason behind this is that symmetric encryption algorithms are faster than asymmetric encryption algorithms, this is also called a hybrid cryptosystem, since it combines symmetric and asymmetric encryption.

The session key is generated randomly at the start of a session and is only valid for one session (hence the name "session key"). The use of session keys provides a feature called forward secrecy. In short, forward secrecy gives assurances that session keys will not be compromised even if the private key of the server is compromised.

Creating a new session key per message would (kind of) violate the use of hybrid cryptosystems, since you'd have to use asymmetric encryption all the time and not just for the first exchange. If your messages are of course very large it would make some sense to use this scheme but this is rarely the case.

It's in genral perfectly fine to use session keys instead of "per-message-session-keys".

  My question is what advantages this has over the persistent shared-secret per session?

It would theoretically provide forward secrecy per message instead of per session and there are indeed new implementations of such cryptographic schemes of what you're describing, like Efficient Ratcheting, which apparently provides session-per-message and is also very performant.


Discrete log problem, when we have many examples Suppose I have many instances of the discrete log problem, all using the same unknown exponent.  Is this problem easier than the standard discrete log problem?

Oh, heck, I should be more precise.  Let $p$ be a large prime, chosen to be large enough that the discrete log problem modulo $p$ is (presumably) hard.  Everything from here on will be in the multiplicative group of integers modulo $p$.  Suppose we are given $a=(a_1,\dots,a_n)$ and $b=(b_1,\dots,b_n)$, where $b=a^k$, and we want to find $k$. In other words, $b_i = a_i^k$ for all $i$ (the same integer exponent for each of the $n$ instances), and we want to find the exponent $k$.

What is the hardness of finding $k$?  Is it significantly easier to find $k$, given these $n$ instances, than it would be given only one instance?  (say, is a greater than $n$-fold speedup available?)

$\newcommand{\Z}{\mathbb{Z}}$
I suspect it makes sense to focus in particular on three cases, depending upon how the $a$'s are chosen:

Random choice. In this variation, the $a_i$'s are uniformly and independently distributed on $(\Z/p\Z)^*$.
Non-adaptive adversarial choice. In this variation, the adversary chooses all of the $a_i$'s in advance, before seeing any of the $b_i$'s.
Adaptive adversarial choice. Finally, we can consider an adaptive variant, where the attacker chooses $a_1$, gets to see $b_1=a_1^k$, then the attacker can choose $a_2$, see $b_2=a_2^k$, and so on.

Does it help the adversary significantly to see $n>1$ pairs $(a_i,b_i)$?  Of course, when $n=1$ this just reduces to the standard discrete log problem.  When $n>1$, is this problem ever significantly easier than the basic discrete log problem?

In practice the view would be that no, it does not get any easier. Indeed many popular deployed schemes depend on it. For example the Trusted Authority in the Boneh-Franklin IBE scheme has a master secret s and issues private keys to users in the form s.ID_i, where ID_i is a point on an elliptic curve, and ID_i is related to the identity of the i-th user. It is a standard DL problem to find s from such a private key. Nevertheless the Boneh-Franklin scheme is assumed strong against a conspiracy of multiple users who can pool their secrets in an attempt to find the master secret s.


Does homomorphic encryption hide the algorithm itself? The question is rather simple, but finding resources and answers quite tricky. Homomorphic encryption should enable us to compute over encrypted data. What if the algorithm for computing should be kept in secret as well? Given we have a functioning homomorphic encryption in place, is the algorithm which is applied to the input data also secure?
Is it possible for an intruder to understand how the data is computed and learn about the algorithm, given the intruder has access to the program which does the computation?
Update
I tried to ask about circuit privacy or protection with this question. Luckily and unfortunately I learned about this term only by asking this question, which was misleading a bit.
So the question should have been: Does FHE offer circuit privacy?
With this term I found some papers which answer my question.

FHE does not offer circuit privacy by default, but can it can be upgraded to do so:

https://eprint.iacr.org/2016/164.pdf
https://eprint.iacr.org/2016/381.pdf

In brief, the extra cost for circuit privacy is actually very small (just a few noisy-dummy bootstraps at the end of your circuit)... in the honest-but-curious model ! For stronger variants of circuit privacy, you need to certify that the FHE public key is correctly generated; and FHE public key are already quite large, so I let you imagine how proving ZK statements about them would be.


The Goldreich-Goldwasser-Micali Construction with bad PRGS I understand that if we have a secure PRG then the Goldreich-Goldwasser-Micali construction gives us a secure PRF.

However, what I've not been able to find much material on is how will the GGM construction fairs when the PRG is less than perfect.

Suppose we used AES-128 in CTR mode as the PRG to generate 256-bits of output for use in this construction. I don't think anyone would argue whether this was secure or not. They might say it's horribly slow but let's ignore that for now.

What happens if we replace AES-128 in CTR mode with a bad PRG. One that has a bias that's significant? Let's say we had a bias in our PRG of  $ \epsilon = {1\over2^{16}}$. That would be a pretty terrible stream cipher and completely broken normally.

However, my intuition leads me to think the whole construction might even be secure with such a terrible PRG because we're only producing a stream double the key length. As such, the set of keys fed in to the next layer should still be pretty much uniform.

In fact, I'm tempted to claim that as long as there's no attack that can distinguish the PRG using only the first $2 \times k$ bits, the overall scheme is secure.

The argument goes like this:

The key at the top of the tree is seed to the prg. This is selected at random from the set of all possible keys.
We then feed this seed in to the prg. The prg can not be distinguished from random with the $2 \times k$ bits generated from it.
Thus the two cells below it can not be distinguished from random.
One of these cells then becomes the new key to the next layer down.
Given that this key could not be distinguished from random we replace it conceptually with a real random key.
The situation is now symmetric with step one, except we're now one step removed from the root of the tree.
We can now re-run steps 1-6 for each level in the tree and have a provably secure prf from a horribly bias prg.

That seems like it proves too much to me; it's an absurdly strong result.

Am I right or does the construction succumb in the presence of a wonky PRG in a way I haven't anticipated?

I know I'm answering my own question, but there's actually quite a nice worked example which completely refutes my question. I thought I'd share.

Suppose I use the GGM construction with the underlying PRG being RC4.

RC4 has a lot of problems, one of which is the fact that the second byte is basically twice as likely to be zero than it should be: $2\over 256$.

For longer key-streams, the biases settle down and the cipher can be used relatively safely. Google, for example, uses RC4 for in SSL.

However, the GGM really punishes RC4. Every stream that RC4 generates is short. An attacker can use this to distinguish the resulting PRF from random very easily. Here's how.

The attacker requests that you compute your PRF on values of his choice. He can craft those values so that the tree that is navigated in GGM always returns the left hand side of the expanded bit stream. These are the first bytes out of RC4.

He can then simply look at the second byte of the result of PRF(x) and count the number of times its zero. After a pretty trivial number of queries, he's clearly able to distinguish the PRF from a random function.

We're now in a position where the GGM has actually has poorer security than the underlying PRG! This nicely refutes my question.

The message is that a bias in the PRG should be assumed to render GGM insecure.


Integer factorization still hard with Hamming weight hypothesis? Consider the following problem:

Factorize a $n$-bit integer $c$ knowing that it is the product of two integers with known Hamming weight $h$.

Is there a way to prove that this is still hard? I have parameters $n=1024$ and $h=80$, but am willing to augment $h$ if this turns out to be easy. I think this problem is current-factorization-algorithms-related, since I did not find an easy way to describe the distribution of these type of numbers (my try considered quadratic expressions of dependent Bernoulli trials). So the question may be reformulated: Does this hypothesis helps any of the actual factorization algorithms?

I suspect that this might be vulnerable to a combinatorial factoring attack.

In this attack, we look at possible solutions to $pq = n \bmod 2^k$, and then extend $p$ and $q$ one bit to list the possible solutions to $pq = n \bmod 2^{k+1}$

Now, if we have no further information about $p$ and $q$, this turns out to be no more efficient than brute force search (as at each step, the number of possibilities doubles, and we have no way to distinguish likely versus unlikely possibilities).

However, in your scenario, we know that both $p$ and $q$ are strongly biased toward 0 bits, and so it would make sense to order our search to explore the possibilities with $p$ and $q$ being mostly 0 first.  The immediately obvious approach would be to keep a list of possible solutions to $pq = n \bmod 2^k$, ordered by hamming weight of $p$ and $q$ (and $k$ somehow); and explore the long solutions with low hamming weight first.

It would seem plausible that this might quickly find a solution if the hamming weight was sufficiently small.  How well would it work in practice (and how small is 'small')?  I suspect that's something that would need to be experimented with.


In end-to-end encryption, doesn't the server need to be trusted? Applications like WhatsApp use end to end encryption. WhatsApp says that only the users share a specific key and no third party can view the messages. But I do not understand how the two users agree on the shared key. It must have been transferred via WhatsApp servers. In that way, WhatsApp would know the shared key right? Please help me understand how keys are shared in end to end encryption.

End-to-end encryption over a channel with an eavesdropper, like the WhatsApp server, works by using a mathemagical spell called Diffie–Hellman key agreement.  What follows is not actually how WhatsApp works,* but explores some of the high-level ideas to concretely answer the question without getting lost in the full gory details of everything about the protocol, which defends against many more threats than what you asked about.

Alice and Bob agree on public parameters $p$ and $g$,† say $$p = 2^{2048} - 2^{1984} - 1 + 2^{64} (\lfloor2^{1918}\pi\rfloor + 124476)$$ and $g = 2$.  When Alice wants to have a conversation with Bob, she picks an integer $a$ with $0 \leq a < (p - 1)/2$ uniformly at random, computes the remainder after dividing $g^a$ by $p$,‡ written $g^a \bmod p$, and transmits $g^a \bmod p$ over the channel.  Bob does similarly: picks $b$ uniformly at random in the same range, computes $g^b \bmod p$, and transmits $g^b \bmod p$ over the channel.

By a remarkable feat of mathematics, when Alice receives $g^b \bmod p$, she can compute $(g^b \bmod p)^a \bmod p$, and it turns out to be the same as $g^{ab} \bmod p$.  Bob does the same: given $g^a \bmod p$, computes $(g^a \bmod p)^b \bmod p$, and obtains the same number as $g^{ab} \bmod p$.

Nobody has figured out the remarkable feat of mathematics that would allow someone who knows $g^a \bmod p$ and $g^b \bmod p$ but not $a$ or $b$ themselves to also compute $g^{ab} \bmod p$.

Thus can Alice and Bob share a secret, $g^{ab} \bmod p$, over a channel without revealing to an eavesdropper what the secret is.  They will then hash this into a short secret key, say the 256-bit $k = \operatorname{SHA3-256}(g^{ab} \bmod p)$, perhaps with SHA3-256, and proceed to use it for symmetric-key encryption such as AES-CTR.

But that's not all.  What if it's not just an eavesdropper, but our friend Mallory who, aside from having an annoyingly ungendered name, actively intercepts messages in transit?  Mallory could pretend to be Bob to Alice, and Alice to Bob, and do a pair of Diffie–Hellman key agreements, and establish shared secrets with Alice and Bob, and then eavesdrop on all the messages they exchange.  The WhatsApp server is in a position to do this.

To thwart this subterfuge of per-conversation shared secrets, Alice and Bob use long-term authentication in addition.  Alice generates a number $\alpha$ just like $a$, and puts $g^\alpha \pmod p$ in the telephone book, or shows it to Bob on her phone screen; Bob does likewise with $\beta$.  Thus they have a long-term shared secret $\kappa = \operatorname{SHA3-256}(g^{\alpha \beta} \pmod p)$.  Now when Alice wants to have a conversation with Bob, she does the per-conversation protocol—but instead of transmitting just $g^a \bmod p$, she transmits $(g^a \bmod p, \operatorname{KMAC256}_\kappa(g^a \bmod p))$.

When Bob receives a candidate message $(A, t)$, he first checks whether $t = \operatorname{KMAC256}_\kappa(A)$ before processing it.  If not, he drops the message on the floor and ignores it.  Only Alice and Bob can compute the function $\operatorname{KMAC256}_\kappa$, because only Alice and Bob know the secret $\kappa$.

Next, instead of just encrypting their actual conversation with $k = \operatorname{SHA3-256}(g^{ab} \bmod p)$ using AES-CTR, they encrypt and authenticate their conversation using AES-GCM.  The WhatsApp server can flip bits in messages encrypted using AES-CTR without either Alice or Bob being any the wiser even though only Alice and Bob know the secret key, but without knowing the secret key, the WhatsApp server cannot change anything in messages encrypted and authenticated using AES-GCM without Alice and Bob noticing.

What if Alice and Bob can't exchange $g^\alpha \bmod p$ and $g^\beta \bmod p$ on their phone screens because they've never actually met in person?  They have to consult the telephone book—which WhatsApp publishes.  When Alice consults WhatsApp for Bob's long-term public identity key $g^\beta \bmod p$, WhatsApp could spoof it and lie about it, and if Alice ever later checks Bob's phone screen she will detect the subterfuge because it won't match the key that the WhatsApp server handed out.

On the other hand, if WhatsApp does not spoof Bob's long-term public identity in the telephone book, then Alice will remember it in her personal address book.  If the WhatsApp server ever tries to impersonate Bob when Alice tries to start a conversation, Alice will detect that.  This model of authentication is sometimes called TOFU, or trust on first use.  You will also find it in the ssh protocol.

There's a catch: Sometimes Bob's identity key changes, like when he gets a new phone.  What should Alice do in that case?  In Signal, the app won't send any new messages on behalf of Alice; it will notify her that something is amiss and ask her what to do.  In WhatsApp, by default,§ the app will automatically retry with the Bob's new identity key, in an attempt to reduce usability hurdles for users who don't understand this, which led to an enormous kerfuffle about mainstream media reporting of the choice, which somehow dwarfed a much worse vulnerability in the app leaking the text of what you were typing if it looked like a URL.

In the end, since WhatsApp—part of Facebook—provides the software and doesn't let you scrutinize it, they certainly have the power to read and impersonate your messages, which they probably think very earnestly they won't ever abuse.  That's better than letting everyone on the internet route between Alice and Bob, like the stalker who is sitting a few tables down at the coffee shop on the same wifi network as Alice, which is why it was so harmful for the Guardian to report breathlessly in a back door in WhatsApp the way it did.

Even if your phone spoke TLS to the WhatsApp servers with a pinned certificate, it's still easier to engineer audit trails for malicious changes to the telephone book than it is to engineer audit trails for eavesdropping by the WhatsApp servers—whether by a technical attacker exploiting a software vulnerability, by a LOVEINT disgruntled employee, or by a court-ordered wiretap.

So, can third parties read your WhatsApp messages?  No, not likely, and it would take an active attack by WhatsApp itself—similar to the kind that Apple refused to do for the FBI—for them to read your messages.

* WhatsApp claims to use the Signal protocol (technical documentation).

† Technical details: $p$ is a safe prime, meaning it is a prime of the form $p = 2q + 1$ where $q$ is also prime.  $g$ is a quadratic residue modulo $p$, and thus has order $q$, meaning there are $q$ distinct possible remainders of $g^x$ when divied by $p$ for any integer $x$.  The powers of $g$ modulo $p$ form a subgroup of the multiplicative group of integers $(\mathbb Z/p\mathbb Z)^\times$.  None of this is important for you to understand how to share secrets over a public channel, but I provide the keywords for you to follow if you want to study further.

‡ Alice does not actually compute, e.g., 2^13805771959684693407656077397889219317288456747119690312451189306384849479687628613222950288427889322679415500741971589068616989911210949597114445259398229588157002772876797268276100622563299377498600497546320786879884333079126581727906347769889606788799518360227168951984468071470187490408276074397578464837282521956615118563389889631151319459158126320262667606793413409480951816493115818911703426164912115254095626026747790743791560327229116656590818054138360168383331595495242709153295834514181328053967320381842712608527965926684083141420258332671624779764031721576291538707703835661166957458717002972300906725181, and then divide the result by $p$; instead she uses a modular exponentiation algorithm so that it is possible to get an answer before the universe burns itself out.

§ Some of this is configurable: conscientious users who must use WhatsApp, like a journalist whose only contact with a source is WhatsApp, should study WhatsApp's privacy and security options.


The security effect caused by an MDS matrix in word-oriented designs Considering a design where the MixColumns operation of AES is replaced by a lighter MDS matrix where by the term lighter we mean the number of required XOR to implement an MDS matrix.

As you know the most relevant property of an MDS matrix in an
AES-like design beyond its branch number is the so-called related differential.

My question:  Is there any security escalation or degeneration due to
the differences of the bit-level representations of the MDS matrices?
(For more details please see  Remark section of [1]).

The current research aims to lighter MDS for implementation in constrained resource environment. The lighter MDS require less number of xors in the binary form (AES MDS). In term of security effect, this paper took the advantage of zero XOR-sum of more than two coefficients of each row of the MixColumns matrix to mound an  (theoritical) attack on AES up to 4.5-5 rounds.

to conclude this ,  zero XOR-sum of more than two coefficients of each row of the MDS matrix could be degradation to the security of the cipher , it is good to find MDS with no zero XOR-sum but this could a tradeoff for finding lighter MDS.


Problems with Matsui's Linear Cryptanalysis on round reduced DES I'm trying to understand the known plaintext attack that is briefly explained in the paper Linear Cryptanalysis Method for DES Cipher by Mitsuru Matsui. I've almost understood it (since I'm programming it and it's yielding good partial results) but there are some things I'm not understanding completely.
If I'm not mistaken, for the 4 round attack, Matsui uses a 3 round DES linear approximation, decrypts the final round and expresses that linear approximation using plaintext bits, ciphertext bits and the bits from the $F(C_R,K_4)$ being $C_R$ the right part of the ciphertext and $K_4$ the 4th subkey derived by the DES key schedule. This way, and since only one bit of $F(C_R,K_4)$ is used in the expression, only one S-Box affects it, so we can get those 6 bits using Algorithm 2. Furthermore we can get a 7th bit by the right part of the linear expression using Algorithm 2 too. Now we have 7 bits of the 56-bit key, and in order to get 7 more we do the same but instead of decrypting the last round we encrypt the first one, expressing the three remaining rounds with the same linear expression but this time using $F(P_R, K_1)$, and that gives us another 7 bits. The problems I'm having are:
1- If I haven't programmed it wrong, at least one bit of the key (after inversing the DES key schedule) is in both of the sets of 7 bits, so it gives us with only 13 (not 14) effective bits of the actual key. Where do I get the 14th bit Matsui says?
2- Even if I get 14 bits, how am I supposed to get the rest of the bits? In the paper he says that "It is easy to deduce the remaining key bits, and we omit the detail", but honestly I have no idea on how to do that beside the obvious way of bruteforcing the 42 bits, that I think it's completely unfeasible.
Any guidance would be welcome.

On 1: I have not seen the 14 bit claim disputed. Can you provide more details about how what you did corresponds to his paper and what goes wrong?
On 2: Since his attack complexity is larger than $O(2^{42})$ this brute force step is negligible, so acceptable. He actually improved his original attack to $O(2^{43})$ in a second paper.
Also $2^{42}$ encryptions is definitely doable even without special purpose hardware (see comment) these days. Even back then people railed against export restrictions which handicapped ciphers to 40 bits.


Groups for which DDH is easy but CDH is hard For prime p, is $\mathbb{Z}^{*}_{p}$ a group for which the Decision Diffie-Hellman problem is easy (because one can compute the Legendre symbol of ($g^{ab}$) while CDH is thought to be hard? Of course, computing the Legendre symbol won't always help differentiate right? But it'll work enough times to beat the DDH assumptions ("non-negligible probability"?)

Are there any more examples? For example with bilinear pairings on elliptic curves?

Many thanks.

Of course, computing the Legendre symbol won't always help differentiate right? But it'll work enough times to beat the DDH assumptions ("non-negligible probability"?)

Yes, if $g$ is an element with Legendre symbol -1, then a simple test of the symbols of $g^a, g^b, g^c$ will show that $ab \ne c$ half the time for random $a, b, c$.  That is certainly non-negligible, and is sufficient to invalidate any proof of a cryptosystem that assumes that DDH is hard.  However, depending on why you want the DDH problem to be easy, it might not be non-negligible enough.

  Are there any more examples?

If you need a group with a more reliable test, we can consider a group with a nontrivial bilinear pairing, in particular, one where $G$ and $e(G, G)$ have the same order.  In that case, we have a test that always gives the correct answer to DDH; $e( aG, bG ) = e( G, cG )$ will hold if and only if $ab = c$


Is a singular LUKS volume with different passwords that unlock different filesystems possible? So it's hard to make sense out of the title. Let me elaborate:

In LUKS, you can have multiple passwords that unlock the same volume (due to their "unified key setup" where they have a single master key). But I was wondering if you could have a single LUKS volume with, say, 2 passwords. The first password unlocks your secret data that you don't want your adversary to get. The second password unlocks pseudo-secret data (I.E. something like pornography, which would reasonably want to be hidden, but is not actually what you're trying to hide). This way, if your adversary found the 2nd password, then they'd think "Oh well this is embarrassing, but it's not what I'm looking for" and move on, being completely ignorant to the "shadow volume" of password #1 that really contains the secret data.

The only cryptographic protocol I've seen that exhibits this feature is steganography, specifically the program steghide. With steghide, you can splice secret data into a picture with one password, then also splice another, different piece of secret data into the same picture with a different password. Both pieces of data are accessible and not corrupted if you use the right passwords.

This is what I'm looking for. Is LUKS capable of doing this? If not, what is the closest thing that I could do to imitate this (aside from LUKS nuking, that's not what I'm looking for)?

No, LUKS does not support this. What you are looking for is plausible deniability, similar to what VeraCrypt supports. LUKS does not support this, with the reasoning explained in section 5.18 of the official cryptsetup FAQ. Their reasons for not supporting this boil down to the fact that it is difficult to use plausible deniability with hidden volumes correctly. For example, if you don't write to your dummy volume in a while and the timestamps show this, the deniability is broken.


What's the differences among Blind Computation, Secure Multi-Party Computation, Secure Circuit Evaluation and Homomorphic Encryption We know that Blind Computation,  Secure Multi-Party Computation, Secure Circuit Evaluation and Homomorphic Encryption all can process the encrypted data, but I am puzzled by them. What are their differences?

In short,

A cryptography scheme is a homomorphic encryption scheme if it is somehow equivalent to manipulate its plaintexts and its ciphertexts.

Secure multi-party computation and secure circuit evaluation are protocols to calculate functions in a distributed way without disclosing the data owned by each party and blind computation is any technique for transforming the data in a manner such that a third-party can calculate a specific function $f$ over these transformed data without knowing the value of $f$ when applied over the real data.

-- Verbose answer --

It is not right to say that

  all can process the encrypted data

In fact, the only one that must process encrypted data by definition is homomorphic encryption, because a scheme $\gamma$ is homomorphic for one operation $*$ if, considering $c_1 = E(m_1)$ and $c_2 = E(m_2)$, then $m_1 * m_2$ is equivalent to $c_1 * c_2$ (where equivalent means that $m_1 * m_2 = D(c_1 * c_2)$.

Secure Multi-Party is any protocol for doing distributed computations without revealing the data owned by each party.

For example, if I have $n$ numbers, you have $m$ numbers and we find out how to calculate the average of these $n + m$ numbers in such a way that we will get the result, but I will not know your numbers and you will not know mine, then we are doing Secure Multi-Party Computation. It doesn't require homomorphic encryption. But, homomorphic encryption is typically used because it makes things easier.

Blind computation (in this context) is a technique that aims to hide the input and the output values of a function, in such a way that this function can be calculated for one person and this person will not know the real values used as input and the real value of output. Note that in Secure Multi-Party Computation, unlike the blind computation, all the parties involved know the output value, and the function is typically calculated by all of them in some iterative process.

For example, if I have $n$ numbers $x_1, x_2, ..., x_n$ and I require you to calculate their average. Then, I generate random numbers $r_1, r_2, .., r_n$ and, instead of sending the real data to you, I send $x_1+r_1, x_2 + r_2, .., x_n + r_n$. Then, you will calculate an average $\mu'$ that is not the real answer and send it me. Finally, I just have to subtract the random numbers divided by $n$ to get the real $\mu$.

This example is too simple. Usually, the function to be computed is more complex and it's hard to figure out how to preprocess the data to hide them and come back to the result after the computation. So, again, homomorphic encryption is a good tool...


Linear Recurrence, keystreams, and periods I am trying to understand the following problem:

  Consider the following linear recurrence over $Z_2$ of degree four:

  $z_{i+4} = (z_{i+3} + z_{i+2} + z_{i+1} + z_{i}) \bmod 2$

  i >= 0. For each of the 16 possible initialization vectors
  ($z_0$,$z_1$,$z_1$,$z_4$) in ($Z_2)^4$, determine the period of the
  resulting keystream.

  What does it mean by the 16 possible initialization vectors? Are there just (0,0,0,0) (0,0,0,1) (0,0,1,0) (0,0,1,1) etc..?
  How do I use these initialization vectors in the formula it gives

Yes, all combinations of 0,1 of length 4. Interpret $(0,1,0,1)$ (as an example) as $z_0 = 0, z_1 = 1, z_2 = 0, z_3 = 1$. Then $z_4$ is given by the sum of these 4, so $z_4 = 0$ (as we work mod 2), so the sequence becomes $(0,1,0,1,0)$. Then $z_5 = z_4 + z_3 + z_2 + z_1 = 0$ mod 2, again, so we have $(0,1,0,1,0,0)$, etc. You go on till you find that the last 4 sequence elements are $(0,1,0,1)$ again, and then you know the period (you're back where you started): the number of steps (i.e. new sequence elements computed) taken to get there.

And this you do for all these 16 start inputs. You'll find $(0,0,0,0)$ as a start pretty boring...


Data-validating protocol I have to implement protocol of secure data transfer that can be described as

Alice selects data to send from finite set $m\in M$ (e.g. $M$ could be a column of values in database table)
Alice encrypts selected data with some symmetric(!) algorithm and sends it to Bob.
Bob decrypts data and get $m$
Bob verifies that $m\in M$. It's important to realize here that Bob have no need to authenticate Alice, he must only be sure that $m$ is belong to $M$. However, Bob have no direct access to $M$
If $m\in M$ then Bob sends $m$ via secure channel to Carol, else Bob ignore the $m$.

In other words, Bob serves as a gateway that provide secured communication and keeps Carol away from flooding of invalid messages.

Is there a protocol to achieve my goal? Please share any thoughts about it.

P.S. I don't want to use any TTP.

Carol generates a NIZK proof common reference string and a statistically binding commitment

to a formal description of $M$. $\:$ Carol sends both of those to both Alice and Bob, and additionally

sends the associated decommit string to Alice. $\;\;$ For each message $m$ in $M$, Alice calculates
the proof of $\:m\in M\:$ and encrypts it along with $m$ before sending the ciphertext to Bob.

After decrypting, Bob can then verify that $\:m\in M\:$ by verifying the NIZK proof.


How to generate a distributed private key? Shamir's Secret Sharing scheme is really interesting but the pain point is that the secret is generated by one trusted party, then the shares are distributed to other peoples.

Is there any scheme using distributed key generation in order to:

Generate a public key using multiple private keys

Generate a private key using a threshold of shared private keys

The private key is generated in a distributed way

I learned about DKG ( https://github.com/dfinity/dkg/blob/master/example.js )

Here's a paper that talks about a pre-commit DKG in detail https://eprint.iacr.org/2019/114.pdf.   It also includes some repudiation and decommitment features.

As a summary, each party does these steps:

roll a random number
publish the hash of (some dlp-hard-group-generator to the power of that random number)
after you get everyone's hashes, publish g to the power of that random number along with a signature, using g, proving ownership of that same random number
as long as everyone's hashes match up, compute the LagrangeSum(g) for the group
now you have a distributed M-Of-M key, and a public key corresponding to it, and a proof-of-secret key too.  any dishonest players result in the whole protocol failing
you can redistribute this key to M-Of-N players using VSSS.

A more broadly referenced solution is the ECDKG here:

https://pdfs.semanticscholar.org/3c52/35523be1d305de6dbf3433965c99d9fe4aea.pdf

Which relies on publishing and verifying commitments to polynomial coefficients, and secret communications between parties to ensure sharing was done correctly.   It is more robust to dishonest players, and ultimately works in 2 rounds for M of N instead of the 3 rounds (above).

IMO, the pre-commitment scheme is both easier to understand and easier to get right.


Why k-lists generalized birthday problem when $k=2$ is classical birthday problem? David Wagner in his article A Generalized Birthday Problem in CRYPTO 2002 says that in k-dimensional (also k-lists) generalization of birthday problem (GBP), when $k=2$ "this is just the extremely well-known birthday problem." Why is that so? As I understand it, in classical birthday problem we search for collisions in one list $L$, where $x_1$ and $x_2$ is supposed to be $\in L$), but, in k-lists GBP we have k number of lists, when $k=2$ it's $L_1, L_2$, we find $x_1 \in L_1$ and $x_2 \in L_2$ such that $x_1 \oplus x_2 = 0$.

So, how does k-lists GBP converges to classical birthday problem when $k=2$? Or I'm missing something?

They are essentially the same, certainly in terms of complexity. Any collision $x=y$ with $x\in L_x$ and $y\in L_y$ is a collision in a single list $L_x \cup L_y$ of size at most twice the size of the larger list.

Any collision in a single list is compatible with about half the partitions of that list into two equal sized halves. So an algorithm that finds a collision in the union randomly has found a collision in the two-list problem with probability $1/2.$

Moreover in the crypto context the lists contain (pseudo)random outputs of hashes or other crypto primitives.