Is the following symmetric design secure? Assume:

$O$ be a reversible random permutation oracle on a finite set and $O^{-1}$ the inverse permutation (pretty much equivalent to a random permutation: What is the difference between a bijective random oracle and a random permutation?). Here, the attacker can call both $O$ and $O^{-1}$ on any input
$M$ be a fixed-length message to encrypt
$R$ some fixed-length random data. A new $R$ is generated every time you want to send a message
$K$ the secret key ($|K|=|M|+|R|$)
$C$ the encrypted message
$||$ the concatenation operator

Design:

Encryption:

Generate $R$
Apply $O$ to $M||R$
Xor the result with $K$
Send the output $C=O(M||R)\oplus K$. $R$ is not sent.

Decryption:

Xor $C$ with $K$
Apply $O^{-1}$ on the result
Remove $R$ (easy since $R$ has a fixed length)
Enjoy $M=MSB_{|M|}[O^{-1}(K\oplus C)]$

As long as $R$ is long enough, is this design secure? Why?

I think that any attack that requires more than $2^{|R|}$ queries of the Oracle should be viewed as infeasible.

Given:

The attacker can call PRP() and the inverse function prp() on any message of his choosing.
PRP is a pseudorandom permutation indistinguishable to the attacker from a random permutation.
Assuming R and K are "sufficiently large", perfectly random, and never leaked to the attacker -- in particular, during a chosen-ciphertext attack, the decryptor only gives the message M to the attacker, never leaking the value of R.

passive attacks

It appears at first glance that this construction is secure against a polynomial-time Eve, a passive eavesdropper, even under both a chosen-plaintext attack and chosen-ciphertext attack,
in the sense that the attacker can't decode any other encrypted messages
(other than the ones you allow him to decode during the chosen-ciphertext attack).

                    K
                    |
M||R----->[PRP]--->(+)---->C

active attacks

Because there is no message authentication code, an active attacker can conduct a replay attack.

If the "message" part is allowed to be short -- for example, 2 bytes long,
an attacker who can trick the system into encoding all possible 2 byte messages,
or decoding a few hundred thousand random values,
can make a collection of ciphertexts that he knows corresponds to each possible 2 byte message.
Because there is no message authentication code,
an active attacker can inject any such such message of his choosing -- "Ya", "No", "Hm", etc.

attacks on weakened variants

Alas, weakening any of the assumptions makes this almost trivial to break.

leaked R:

If R is ever leaked to a single known plaintext/ciphertext pair,
then the key can be recovered from that single message pair, allowing the attacker to decode all other messages encrypted with that key.

Key = PRP( R || plaintext ) xor ciphertext.

weak random-number generator

If the random number generator is "weak" for a single known plaintext/ciphertext message,
so it is known that the random number R for that message is one of N possibilities
(for example, if all but b bits of the number R are known,
so it is known that the random number for that message is one of 2^b = N possibilities),
and N is small enough for the attacker to try out all N possibilities,
then the attacker can narrow the key down to one of N possible keys.
With a single other known plaintext/ciphertext message, or a few more known ciphertext messages that decode to something that the attacker can recognize as plain text --
even if those other ciphertexts was built using a strongly-random number --
the attacker can narrow the possibilities down even further,
probably recovering the key.

weak PRP

If the function O() is statistically flawed,
the attacker may be able to recover the key.

For example, if the function O( R || M ) is truly awful and always returns ( R || Y),
where Y = R xor M,
then with enough ciphertext messages that were encrypted with some fixed key,
ciphertext-only techniques can be used to recover the re-used key
(see
How does one attack a two-time pad (i.e. one time pad with key reuse)?
).

other ideas

This construction reminds me of one round of a
Feistel cipher.
Perhaps a few more rounds would make it less fragile to weaknesses in the PRP and the random-number generator?

                K
                |
M||R---[PRP]---(+)--->[PRP]---->C

the Even-Mansour scheme:

        K              K
        |              |
M||R---(+)-->[PRP]--->(+)---->C

EDIT:

Rough draft of a proof

Let us imagine that Olivia implements the
random oracle
by sitting in a big isolated room with lots of filing cabinets.
Every time a piece of paper with a new red number comes in the red slot,
Olivia flips some coins to come up with a new black number.
(If that black number is the same as a black number already in her archives,
Olivia forgets that number and starts over, flipping all the coins again --
this is necessary to make this a random permutation,
rather than a random function.
).
Olivia writes down the results of the coin-flips in black ink twice --
once on a blank piece of paper that she shoves out the black slot,
and again on the incoming piece of paper next to the incoming red number,
which she then files.

When a piece of paper comes in with a previously-seen red number,
Olivia looks up that number in her files,
copies the corresponding black number to a blank piece of paper that she shoves out the black slot.

When a black number comes in the red slot, Olivia handles it similarly, writing with red ink and shoving a corresponding red number out the red slot.

Every time the the attacker feeds a red number directly to Olivia and gets the corresponding black number, if R is large and random enough, he's almost certainly getting the values of freshly-flipped coins -- practically the definition of useless information.

Every time the attacker feeds a black number directly to Olivia and gets the corresponding red number, if R is large enough, he's almost certainly getting the values of freshly-rolled dice -- practically the definition of useless information.

Every time the attacker tricks the system into encrypting some chosen-plaintext,
the system generates a fresh new random number R, Olivia flips her coins,
and the output ciphertext is the key encrypted by Olivia's new one-time coin-flips.
(Assuming R is large enough that Olivia actually does flip her coins again,
rather than re-use some previous number, the one-time-pad security proof
indicates that the attacker won't learn anything about the system key from that ciphertext).

Every time the attacker tricks the system into decrypting some chosen-ciphertext
that is different from any ciphertext generated in normal operation,
the "ciphertext" is run through the key,
again Olivia flips her coins,
and assuming the system throws away the many bits of "R" and only gives the decoded plaintext to the attacker,
the attacker only receives the values of freshly-flipped coins -- practically the definition of useless information.

user8911 pointed out a presentation about Even-Mansour:

Orr Dunkelman, Nathan Keller, and Adi Shamir.
"Minimalism in Cryptography: The Even-Mansour Scheme Revisited".
2012.

which is apparently a summary of thier paper,

Orr Dunkelman, Nathan Keller, and Adi Shamir.
"Minimalism in Cryptography: The Even-Mansour Scheme Revisited".

They prove that certain attacks require a certain number of operations.
It appears that all their proofs and attacks can be adapted to the randomized cipher machine proposed by udfrg2.
So any desired security level can be attained by fixing the message width |M| and the random width |R| wide enough.

As you may have already guessed, all these attacks rely on some kind of birthday attack --
after enough data runs through the system,
eventually the attacker gets lucky and Olivia re-uses some number rather than generating fresh coinflips.


AES vs RSA - Which is stronger given two scenarios? Let's say we have some plaintext.
Let's say that we encrypt this plaintext with a random 32 byte key using AES-256.
Let's say that we also encrypt this plaintext with an RSA 2048 public key.

If only the cipher text was known, which of these would be harder to identify the plaintext from?

My thoughts are that it would be the RSA ciphertext since the assumption is that the attacker has no access to either the public key or the private key, just the ciphertext. This is because the attacker has nothing to base any assumptions on and would still have to figure out what the private key is.

It is also assumed that an attacker doesn't know anything about the secret key used as input to the AES algorithm.

Now lets assume that for either algorithm a mode of operation is used that sufficiently protects the ciphertext (say AES-CTR and RSA-OAEP). Then it comes down to analysing the security of the cipher itself given the key size.

Neither AES nor RSA has been broken in the sense that it is much less secure than the strength it was designed for. The key size is therefore easy: AES-256 has close to 256 bits of security while RSA only offers about 112 bits of security. In that respect AES-256 has RSA-2048 completely beat.

As for the algorithm, AES-256 is considered secure against analysis with quantum computers. RSA is definitely not, given a large enough quantum computer. The only disadvantage of AES is that there is no security proof of the algorithm itself. We suppose it is secure, but we're not certain. RSA probably has a slightly better mathematical problem behind it.

Operationally speaking: it is much more likely that AES is implemented / executed correctly rather than RSA.

All in all I'd strongly recommend AES given your question.

But in the end recommending one over the other is futile; an asymmetric cipher has different properties and should be used in different scenarios than a symmetric cipher.

Say for instance that the system that performs the encryption is not as secure as the system that does the decryption. In that case RSA is a much better fit than AES as RSA encryption only requires the public key to be present.

Distributing a public key is of course also a completely different fish than sharing an AES secret key. With a public key you can distribute freely as long as the receiver can trust the public key. With AES you need a secure channel in advance.


Question about a proof in Junod's paper about the Blum-Blum-Shub generator I am reading Junod's paper about the Blum-Blum-Shub generator. There is one thing I just do not understand about his proof of Lemma 4. On page 17  he writes:

We conclude that $x=-x_0$ and from Lemma 1 we know that $x \ne x_0$
(So far I understand.)
, so they must have different parities (Why is this the case?), $n$ beeing odd, which is a contradiction.

Could you please explain that to me?

If $x_0$ is odd, then $-x_0 = n - x_0$ must be even (and versa-visa).


Why are logic gates assigned integers when checking QAP in zkSNARK algo? I am trying to understand how zkSNARKs work. Going through this article by Vitalik, in the section on 'Checking the QAP' he says " If the resulting polynomial, evaluated at every x coordinate that we used above to represent a logic gate, is equal to zero, then that means that all of the checks pass;" -
Can somebody help me understand why logic gates correspond to numbers 1,2,3,4?

Assigning "coordinates" (integers) to arithmetic gates is a way of combining multiple verification equations into a single one by Lagrange interpolation, and then testing that single equation at a random point. Choosing that point at random effectively results in random weights for original equations in the combination. This point could be compared to challenge of Schnorr protocol. For the statement cited, resulting polynomial is representing all the gates in the circuit.


Trivial Broadcast Encryption Scheme for video conferencing how well does it handle users joining or leaving a call? Consider the trivial Broadcast Encryption Scheme for video conferencing, where each user shares a long-lived key with the broadcaster, and the session key used to encrypt a multicast message (or stream) is sent to each participant encrypted under their long-lived key.

How well does it handle users joining or leaving a call?

For participants joining the call, the broadcaster would have to send the session key encrypted with their and joining user's long lived shared key. Which is simple enough.

When a user leaves the call, if the session key is unchanged, they can still decrypt the stream. The only secure option is change the session key and rebroadcast encrypted copies of it to all remaining participants. This ensures that when a user leaves, they can't continue to listen in.

Less obviously, when a user enters, if the key is not changed, the key they are sent decrypts data from before they joined.

The best solution is to rekey anytime the set of authorized users changes.


Why the definition in $\epsilon$-differential privacy is multiplicative rather than additive？ According to its mathematical definition, a random algorithm $M: D\rightarrow R$ satisfies $\epsilon$-differential privacy if the adjacent datasets $x, y \in D$ where $D$ is a whole dataset and datasets $x$ and $y$ differs by only one record, and any set of $S \in Range(M)$,
$Pr(M(x) \in S) \leq Pr(M(y) \in S) * e^{\epsilon}$.

The additive one is shown in this question: Differential privacy definition.

Dr. Dwork explains the advantage of using the multiplicative definition over the additive one in the Microsoft Research Lecture 2 (at about 2'50''). In short, with this multiplicative definition, it could be ruled out the possibility that an individual's record would be randomly selected and published.
However, I struggle to understand her meaning. I would appreciate any help in understanding this definition!

In short, with this multiplicative definition, it could be ruled out the possibility that an individual's record would be randomly selected and published.

Consider a malicious algorithm $M^*$ that picks a random individual's record from the input database (of size $n$) and outputs it. Note that this $M^*$ should not be considered secure for a good differential privacy definition because it compromises the privacy of a random individual.

However, the additive differential privacy definition regards $M^*$ as a secure algorithm for $\epsilon=1/n$. To see this, consider two input databases $X,Y$ (both of size $n$) differ with a single element $d$ (where $d\in X$ but $d\not\in Y$). Then, it's not hard to see $\Pr[M^*(X)\in S]\leq\Pr[M^*(Y)\in S]+1/n$ holds for any subset $S\subseteq R$, i.e., $M^*$ satisfies the additive $1/n$-differential privacy.

The above issue is fixed by the standard multiplicative definition. Note that for $S=\{d\}$, there is no $\epsilon$ such that $\Pr[M^*(X)\in S]\leq\Pr[M^*(Y)\in S]\cdot e^\epsilon$ because $\Pr[M^*(X)=d]=1/n>0$ and $\Pr[M^*(Y)=d]=0$. That is, $M^*$ does not satisfy the standard $\epsilon$-differential privacy.


How strong can multiple encryption be? Suppose I encrypted a homophonic substitution cipher at the level of syllables, trigrams, digraphs, and individual letter with a Vigenere cipher using the keyword cryptography. I would then encrypt the resulting complex ciphertext with an ADFGVX cipher in addition to using a code. How strong can a multiple-encryption be?

If the ciphers are different, with independent keys, you can say that it is at least as strong as the first cipher. If the ciphers commute, like with stream ciphers, you can even say that it is at least as strong as the strongest. See Cascade Ciphers: The Importance of Being First.

That's really all you can say in general.

In practice, the combinations you suggest are not cryptographically secure. You would need at least one secure cipher in the mix to have reason to believe it would be. (Though that's not strictly required in theory: a particular combination of insecure ciphers could be secure.)


Retrieving ElGamal message with negative exponent value Although the ElGamal scheme states that the message $M$ must be $1 \le M \le p-1$ in this paper: A Secure and Optimally Efficient
Multi-Authority Election Scheme they propose a method where the message can be $-l \le M \le l$ where $|\ l\ | \lt p/2$. This is stated in page 9.

The idea behind the paper is that for 2-way voting system the available options are encoded as $m_0=1,\ m_1=-1$ and when doing additive ElGamal the result could possibly be $g^{-4}$ or any negative exponent.

I know that for computing the message in the final stage of ElGamal we execute a loop for each possible value of $M$ but in this case, although this is what the paper proposes as well, I don't see how it is done.

In order to retrieve the message $M$ from the Discrete Log provided by the final step of ElGamal, knowing that $-l \le M \le l \text{ where } |\ l\ | \lt \lfloor p/2\rfloor$ works the same way as if $1 \le M \le p - 1$ that is, testing for all exponents.
For negative values of $l$ we use modular division, e.g. $$5^{-3} \equiv 125^{-1} \equiv 6^{-1} \equiv 6\bmod7$$ and we find the inverse with Ext-GCD algorithm

It is important to note that $|\ l\ | \lt p/2$ where $p/2$ is rounded down e.g. for $l=5$ then $p \ge 13$. The reason for this is that the number of encoded values for $-l \le M \le l$ is $2\ l + 1$ due to the existence of the value $0$ and the defined cyclic group must have order greater than that.


Precomputation attacks on RSA Are precomputation attacks - such as outlined in RFC 3610 chapter 5 - possible on RSA PKCS#1 v1.5 signature generation? If yes, are such attacks taken into account when calculating the cryptographic key strength of RSA? Do they have the same impact on the security strength of RSA as on block ciphers (i.e. halving the cryptographic strength of the block cipher)?

I presume this kind of attack - if applicable - is thwarted by the PSS padding scheme?

No, these sorts of attacks are not of any use against RSA -- they are much harder to perform than other existing attacks (and in particular, attacks that factor an RSA modulus).

Here is how this precomputation attack works; you assume that someone generating the keys will always MAC (or sign) a specific message:

$$S_i = MAC_{K_i}( FixedMessage )$$

And so you treat this as a fixed function of key $K_i$ to tag $S_i$.

The legitimate key generator creates a long series of keys $K_1, K_2, ..., K_a$, and corresponding tags $S_1, S_2, ..., S_a$

The attacker generates a long series of random keys $K'_1, K'_2, ..., K'_b$, and corresponding tags $S'_1, S'_2, ..., S'_b$

Now, let us call the key space of the MAC in question $n$ bits.  If $a \times b \approx 2^n$, then there is a decent chance that one of the keys $K'_j$ will happen to be the same as one of the legitimate keys $K_i$, and this will be detectable because $S_i = S'_j$; this can be detected by (say) a rainbow table lookup.  Because of this, the attacker learns $K_i$.

With $n = 128$, e.g. AES-CMAC with 128 bit keys, this is just on the border of plausibility; if the legitimate generator creates $2^{50}$ keys (which is a huge, but not inherently implausible number), then the attacker would need to generate about $2^{78}$ keys; a huge but not inherently implausible number (and will perhaps be a bit more likely after a few more years of Moore's Law).

All that said, let us take a look at this attack in terms of RSA.  With RSA, we have much larger keys.  Currently, any key much smaller than 1k can be factored, so let us take a look at how this would apply to a set of 1k RSA keys.  An RSA modulus is a product of two primes; there are a bit over $2^{500}$ 512 bit primes, and so there are approximately $2^{1000}$ RSA modulii that are 1024 bits long.

Now, if we assume that our legitimate generator creates $2^{50}$ keys, that means that we'd need to create about $2^{950}$ keys to have a decent chance of creating a collision -- that amount of work is completely and utterly implausble.  In addition, if we were able to assemble anywhere close to that amount of computational power, factoring a 1k RSA key would be trivial.  Hence, factoring one of the RSA modulii would be far easier than the collision method.

So, why does the collision method have such a hard time with RSA?  Well, RSA keys need to be as big as they are to address attack methods that use the inherent mathematical structure within RSA.  This collision method ignores this mathematical structure, and by ignoring this structure, doesn't work nearly as well.


Times of nested algorithms in proofs of security Proofs of security may be constructed such that an adversary $A$ is used to construct an adversary $A'$.
The reduction/algorithm which uses $A$ has to perform a number of computations in order to simulate the environnement of $A$ (t.i.t.s to intercept/answer to queries from $A$).

I've noticed that we evaluate the time $t'$ taken by $A'$ such that $t'=t+n \cdot t_c$ where $t$ is the time taken by $A$, $n$ is the number of computations made by the reduction and $t_c$ the time to perform one computation.

I don't understand why we generally conclude that $t \ge t' - n \cdot t_c$. I don't understand why we remove the quantity $n \cdot t_c$. It seems to me that $A$ and $A'$ terminate at virtually the same time ($A'$ uses the output from $A$ almost immediately).

An example: Assume that a computation needs $1$ unit of time. An algorithm $A'$ uses $A$ as follows:

$A$ makes a query (the elapsed time for $A$ and $A'$ is $1$)
$A'$ makes a computation and responds to $A$ (the overall elapsed time for $A$ and $A'$ is 2)
$A$ makes a query (the overall elapsed time for $A$ and $A'$ is $3$)
$A'$ makes a computation and responds to $A$ (the overall elapsed time for $A$ and $A'$ is 4)
etc ...
when $A$ terminates and gives the result to $A'$, we assume there is not need for more computations. It seems that $A$ and $A'$ terminate at the same time.

We see in this example that it's strange for $A$ to remove the time of computations (unless these computations are considered as "free").

The equation $t'=t+n\cdot t_c$ is an estimation to put an upper limit on $t'$. It might be possible that an attacker $A'$ can use a different, more efficient algorithm. But since the attack will work with using $A$, there exists an attacker $A'$ with at most $t'$. This means it's actually not an equation, but an inequality $t' \leq t + n \cdot t_c$. And then the next step is just a standard transformation to get $t'  - n \cdot t_c \leq t$.

Edit:
Actually, this assumes that $A'$ only has to run $A$ once. There are also reductions which run $A$ multiple times. If you are only looking for asymptotical complexity, it doesn't change much, tho. Running a polynomial time algorithm polynomial many times is still polynomial overall.

Edit2:
Concerning your example, there are a couple of misunderstandings of of the these times. First, in a reduction we use $A$ mostly as a blackbox. We can observe the queries (e.g. if we assume an oracle for that, which can be accessed by both $A$ and $A'$). But we make no assumptions about these times. Saying that $A'$ takes 1 unit of time for a calculation and $A$ needing 1 unit of time for a query (and possibly some internal computations)  is an assumption about their correlation we should not make.

And then there is the question what we actually use from the attacker $A$. Usually we do not only use their queries, but their results. And that happens at the time $A$ is finished, which is $t$. Then $A'$ can do its final transformation of results or do some more complex computations, which is not necessarily instant (e.g. solving a large linear system or doing $k$ exponentiations, etc.). If you assume this to be instant, then $t=t'$ for exactly this attack. But that doesn't mean that this is the fastest attack (if you assume $A'$ to be the "best" attacker, $t'$ might be lower), or if those computations are not instant, then $t'$ might be greater.


Finding the private key in Diffie Hellman Lets say there are 2 parties X and Y. They have agreed on prime number P and generator g. X uses the secret key K.
After the key exchange they calculated the common secret key g^4.

What are the 2 possible values for the secret key of Y?

That the parties have agreed on a DH secret means the following:
$$g^4=(g^K)^Y=g^{KY}\pmod P$$
Now we can just look at the exponents:
$$4=KY\pmod{P-1}$$
Which may or may not have the unique solution for $Y$:
$$Y=4\cdot K^{-1}\pmod{P-1}$$

That is if $\gcd(K,P-1)>1$ and we know that $K^{-1}$ must exist, then it will have multiple possible values. The precise values depend on $P$ and $K$.


Can a deck of cards be used as a practical source of cryptographic randomness? This is not a duplicate of Entropy measurement from shuffled cards, as this concerns use of cards as a cryptographic entropy source, rather than calculating entropy from some number of cards.

The Solitaire cipher from Cryptonomicon makes use of a deck of cards to encipher messages. However, it is considered insecure, and is likely impractical for actual cryptographic uses.

However, a deck of cards does have a large amount of entropy, and unlike electronically generated randomness, the randomness of a properly shuffled deck is nearly infalliable*. The entropy of a deck of cards is $\log_2(52!)$, or 225.58 bits, which approaches the Landauer limit and is well beyond anything we will ever be able to brute force. On the other hand, the order of a deck of cards is not a stream of bits, and is not easy to quickly process with a computer (a specialized deck reader and shuffler machine will be needed.)

My question is: How can random bits be extracted from a shuffled deck of cards?   Does this have any practical value at all?

So far, I've come up with the following procedure:

  -OCR the deck, producing a string like JH3CAS0D... to represent "Jack of Hearts, 3 of Clubs, Ace of Spades, 10 of Diamonds... and so on".

  -Take the SHA-512 hash of this string. For the sake of the example, I came up with:
  bfda311f6e9f6ad06825c9dc07fbbffb98ff86556a8e6fd7ac835b58f0c5eee04155db4e63f748a6c2b0b7c15e558b0e6c7e8222760283869904a2e485ef2d04

  -Take the SHA-512 hash of the last 256 bits of the first hash, and append that to the first hash.

  -Repeat step 3 as many times as needed to create an infinite stream.

*Barring cases such as improper shuffling or shuffling a default/stacked/known deck only once.

You're asking about a composition of two things:

Choosing a key—or perhaps passphrase—uniformly among $52!$ possibilities by shuffling a deck.  Although the key is not a uniform random bit string, it is uniform random in another space.
Expanding the key $k$ into a large effectively uniform random pad by computing $x_0 = \operatorname{SHA512}(k)$, $x_1 = \operatorname{SHA512}(\operatorname{trunc}(x_0))$, $x_2 = \operatorname{SHA512}(\operatorname{trunc}(x_1))$, etc., and returning $x_0 \mathbin\| x_1 \mathbin\| x_2 \mathbin\| \cdots$.

In the random process of part (1), if you do a good job shuffling then it's a reasonable way to choose a key from a weird space.

But in the deterministic procedure of part (2), it's trivially breakable—i.e., the procedure is not a good pseudorandom generator—because given $x_0$, or any $x_i$, I can perfectly predict the entire remainder of the output.

However, there's other possibilities:

$\operatorname{SHA512}(k \mathbin\| 0) \mathbin\| \operatorname{SHA512}(k \mathbin\| 1) \mathbin\| \operatorname{SHA512}(k \mathbin\| 2) \mathbin\| \cdots$, where the numbers $0, 1, 2, \dots$ are uniquely encoded in fixed width.
$\operatorname{AES}_{k'}(0) \mathbin\| \operatorname{AES}_{k'}(1) \mathbin\| \operatorname{AES}_{k'}(2) \mathbin\| \cdots$, where $k' = \operatorname{SHA512}(k)$.
In general, you could feed a hash $H(k)$ of $k$ to any pseudorandom generator $G$ to get an arbitrarily long effectively uniform random pad, where $H$ is a random oracle or reasonable to model as such like SHA512.  $G$ can be AES in CTR mode, or can be a Keccak duplex, or anything else that has PRG security.

For practical use, the standard way to do things is:

Use a random process—like shuffling a deck of cards and transcribing the order—to arrive at a secret string; the process need not have uniform distribution as long as it has high min-entropy.
Use a standard key derivation function—like HKDF-SHA256—to convert the maybe-nonuniform but high-min-entropy secret string input, together with an optional salt that is unique per user, into a family of effectively uniform keys, labeled by their purpose so that you can use the same secret string input for multiple cryptosystems.
Use standard cryptosystems—like X25519, AES-GCM, HMAC-SHA256—with the resulting keys confident that they are effectively uniformly distributed, in accordance with the security contracts of the cryptosystems.


Why public key has two parts in my secure messaging client similar to signal I am working on a Golang code similar to Signal protocol. I need to modify it. I am confused on tripartite Diffie-Hellman handshake part of code, i.e. why public key has two separate parts as compared to private key which has only one part in bytes as shown below. I can more info if needed. Thanks.

The answer to this question is simple. In simple words, in elliptic curve cryptography, the public key is calculated by multiplying the private key value $s$ with the base point $G$, which results a point on the elliptic curve point: $W = s \cdot G$. This point consists of has two values on the x-axis and one on y-axis if the curve is considered to be within a 2D coordinate system.

Here is a link which gives a good idea of it: ECC with Diffie-Hellman.


Does the Blowfish cipher work with OFB mode? I'm trying to implement the Blowfish cipher in Output Feedback mode.

OFB mode has two operations, XOR and the block cipher.  XOR inputs two blocks of the same length and outputs one block of the same length.  Blowfish inputs two blocks of the same length and outputs two blocks of the same length.

How can XOR and Blowfish be used together if they have different outputs?

Does the Blowfish cipher work with OFB mode?

Blowfish inputs two blocks of the same length and outputs two blocks of the same length.

That is where you are running into an issue. Blowfish inputs a single 64-bit block and outputs a single 64-bit block, just like the picture shows. All the standard 64-bit compatible block cipher modes are compatible with Blowfish.


Secret Sharing and Multiplication Triples I do not understand the multiplication technique using triples and secret shares of the inputs. Could somebody explain me where I'm wrong?
It works like this:
The inputs are secret shared in XOR shares.

Alice holds $[x]_a$ and $[y]_a$ and a share of a multiplication triple $[a]_a,[b]_a,[c]_a$ s.t. $a \cdot b = c$.
Bob holds the other shares.

Now multiplication is supposed to work as follows:

Both parties do the following:
$$[d] = [x] \oplus [a]$$

$$[e] = [y] \oplus [b]$$

Both parties reveal their shares of $[d]$ and $[e]$ to each other.
Then both calculate
$$ [z] = [c] \oplus e[x] \oplus d[y] \oplus ed $$

To reveal the result of their computation one party sends the other party its secret shares.

My questions:

How is reconustruction working? If I XOR the two shares of $z$, the last bit ($... \oplus ed$) cancels out.
I have seen this trick in many lecture notes and in all of them they analyze the correctness for showing that $xy = c \oplus ex \oplus dy \oplus ed$, but I don't see how this directly relates to the shares.

If you understand that $xy = c \oplus ex \oplus dy \oplus ed$ I am not sure what else is there to understand?

I wonder if you have understood how the $[x]$ notation works? $[x]$ means that $x$ is XOR shared between between Alice and Bob (I.e., Alice has $x_A$ and Bob has $x_B$, so that $x = x_A \oplus x_B$). When we write $[e] = [x]\oplus[a]$ this that Alice and Bob computes an XOR secret sharing of the value $e = x \oplus a$. Simlarly, if we write [f] = e[x], this means Alice and Bob compute an XOR sharing of $f = ex$. So by extension if $xy = c \oplus ex \oplus dy \oplus ed$ then $[z]$ means we have computed an XOR sharing of $z = xy$.


AES alternate equation for the S-Box affine transformation The Wikipedia article for the AES S-Box gives an alternate equation for the affine part of the S-Box transformation:

$$b_{out} = (b_{in} \times 31_d) \operatorname{mod} 257_d \oplus 99_d$$

It is not very clear in the article, but it turns out from the paper (as cited in the article) that the multiplication is to be carried out over a finite-field with polynomial $257 = 100000001_b$ for the modular reduction.

How could such an identity have been derived, since the AES specification makes no mention of the use of this other finite-field polynomial $100000001_b$? Is there any more information about where it comes from?

That alternate form, I think, makes things even more confusing than the standard form.

Since the matrix involved is circulant, the affine part of the AES S-box can be represented as
$$
b_o = b_i \oplus (b_i \lll 1) \oplus (b_i \lll 2) \oplus (b_i \lll 3) \oplus (b_i \lll 4) \oplus 99\,,
$$
where $\oplus$ is xor and $\lll$ is bit left rotation. So far so good. But mathematically, it is awkward to describe rotation as "moving bits".

So instead, we can treat a byte as a polynomial with coefficients modulo 2, that is, $\mathbb{F}_{2}[x]$, and a byte is $x^7\cdot c_7 + \ldots + x \cdot c_1 + c_0$, where the $c_i$ coefficients are the bits of the byte. What happens when we multiply by $x$? This is simply a left shift operation:
$$
x(x^7\cdot c_7 + \ldots + x \cdot c_1 + c_0) = x^8\cdot c_7 + \ldots + x^2 \cdot c_1 + x\cdot c_0 + 0\,.
$$
Now, if we reduce this polynomial by $x^8 + 1$, which means that we replace $x^8$ by $1$ wherever available, we get
$$
1\cdot c_7 + \ldots + x^2 \cdot c_1 + x\cdot c_0 + 0 = x^7 \cdot c_6 + \ldots + x^2 \cdot c_1 + x\cdot c_0 + c_7 \,,
$$
which is precisely a rotation left by $1$. You can verify that the same principle works for any rotation value: multiplying by $x^k$ and reducing by $x^8 + 1$ rotates the polynomial by $k$ positions.

Therefore, we can understand the affine transformation of the AES S-box as a multiplication in the ring $\mathbb{F}_{2}[x]/(x^8 + 1)$:
$$
b_o = b_i \cdot (1 + x + x^2 + x^3 + x^4) + 99 \in \mathbb{F}_{2}[x]/(x^8 + 1)\,.
$$
In other words, this modulus only exists to describe bit rotation cleanly, in an algebraic way.

Converted to decimal, this becomes $b_o = b_i \cdot 31 \bmod 257 \oplus 99 $, but that form, to me, loses all its descriptive value.


DDH Assumption Not Holding Reading about the Decisional Diffie-Hellman on Wikipedia, I came across this section:

  Importantly, the DDH assumption does not hold in the multiplicative group $\mathbb{Z}^*_p$, where $p$ is prime. This is because given $g^a$ and $g^b$, one can efficiently compute the [Legendre symbol] of $g^{ab}$, giving a successful method to distinguish $g^{ab}$ from a random group element

I read through the related questions to this and I still don't understand how this assumption is false if $g$ is a generator of $\mathbb{Z}^*_p$  and not of $\mathbb{G}_q$? Can we even show the probability would be greater than 0.5?

Here's the issue; the size of the multiplicative group is $p-1$; if $p>2$, then $p-1$ is even.

What this means is that we can divide the group into two equal sized halves, the "even" elements (which happen to be the values $x$ which have a solution to the equation $y^2 \equiv x \bmod p$, known as quadratic residues), and the "odd" elements (which happen to be the values for which the equation has no such solution, known as quadratic nonresidues).  Computing the Legendre symbol is an efficient way of determining which half a particular element falls into.

Here's why this is important: $g^{ab}$ will be a quadratic nonresidue if (and only if) both $g^a$ and $g^b$ are quadratic nonresidues.  Hence, given $g^a$, $g^b$ and a group element $h$, an attacker can determine the Legendre symbol on all three values, and see which half $g^{ab}$ would be expected to fall in; if it falls in one half, and $h$ is in the other, the attacker knows that $h \ne g^{ab}$ (and for a random group element $h$, this is expected to happen half the time).

We typically get around this by redefining the group; we limit ourselves to the subgroup of quadratic residues (and so $h$ isn't allowed to be a random group element, they're allowed only to be in the "even" half); hence this trick doesn't work.  This does mean that $g$ cannot generate the entire group (as we cannot allow it to generate the "odd" elements), however we can find an element that generates the entire "even" subgroup (in fact, if we select $p$ to be a safe prime, that is, $(p-1)/2$ is also prime, then any element in the even subgroup, other than 1, will generate the entire even subgroup).


Why can't I use ECB with some obfuscation for transient RAM? I understand that ECB does not hide data patterns well. But my understanding is that it cannot be broken to "know" the underlying message. If that was the case, why can't ECB be used with some obfuscation technique like say XORing with the address? I am talking about data stored in DRAM modules - and assume it is not an image data that gives away the information just by its pattern (as is explained in the Wiki page for block ciphers).

If let's say it is some software code and I obfuscate the AES output by XORing the AES output with the address - or some combination of the address, does it still make the data in the DRAM insecure?

The concept of encrypting blocks independently but based on the address is sound. It's commonly used in disk encryption.

In the simplest case you could use a tweakable blockcipher in an ECB like mode using the block index as tweak.

But let's say you want to use an existing block cipher, like AES. In that case you want to turn that block cipher into a tweakable block cipher. There are standard modes for doing this, in particular XTS. But they're more complex than your suggestion, applying a non trivial transformation both before and after encrypting with the block cipher. These transformations are keyed and necessary to eliminate patterns in the plaintext.

Simply xor-ing the address into the plaintext, like you suggest is not secure. If an attacker observes two identical ciphertext blocks, they learn that the xor of the corresponding plaintext blocks is equal to the xor of the address. Since they know the xor of the addresses, they learn the xor of the plaintext. In practice this could occur if two consecutive blocks of plaintext differ only by a single bit.


Algorithm design to verify an assertion on encrypted values I'm trying to design some kind of protocol but I'm stuck, need some help please..

Given
$ (a,b,c)\in \mathbb{N}^+$ with $ a + b = c $

I need to send an asymmetric encrypted version of a,b and c though a third-party that must verify that $ a + b = c $ but this third-party can't have access to those numbers, only their encrypted values.

I would appreciate a lot some suggestions.

There are two natural solutions to your problem.

The first one would be to rely on an additively homomorphic encryption scheme. In such a scheme, given encryptions of two numbers $a$ and $b$, anyone can, given only the public key, homomorphically compute an encryption of their sum, $a+b$ (usually modulo some value $M$, which can be set large enough so that no overflow occurs, given bounds on the values $a,b$).

If the values $(a,b)$ are small enough, this can be instantiated using the ElGamal encryption scheme, with messages in the exponent (decryption then requires computing a discrete log). If the inputs might be large, a good alternative is to use the Paillier encryption scheme, which does not have this small input requirement.

With such a cryptosystem, the protocol you want is straightforward: simply send only encryptions of $a$ and $b$ to the third party, and let him compute the encryption of $a+b=c$ by himself - that way, he is automatically convinced that the third ciphertext indeed encrypts $a+b$.

If you cannot really choose which encryption scheme you want to use, or want to rely on a different encryption scheme for other reasons, an alternative to the above is to use zero-knowledge proofs. After sending the three ciphertexts to the third party, you can perform with this party a zero-knowledge proof that the third ciphertext encrypts the sum of the first two ciphertexts - this will not leak any information about the content of the ciphertexts, appart from the fact that the statement is true. Zero-knowledge proofs for such linear statements are known for most standard public-key encryption scheme (they can in theory be designed for arbitrary encryption schemes, even e.g. AES, but would be a quite inefficient for encryption schemes without algebraic structures), using e.g. standard Sigma-protocols (which you can make non-interactive in the random oracle model if you don't want to require interactions with the third party).


How to prove a function is negligible? My question essentially concerns how to prove if a function is negligible. As a matter of fact, though this question might seem very basic, it seems that most of the "proofs" of negligible concern comparing the the function with another negligible function and then asserting its status via laws of negligible functions.

What I am insisting on is a direct mathematical proof of proving how functions can be proven as negligible without comparison with any other function.

As stated by Dan Boneh:

  Different communities define these (negligible and non-negligible) differently

For practitioners they are basically a scalar $\varepsilon$, where, for example:

$1/2^{30}$ is considered non-negligible because an event with this probability will probably happen after $2^{32}$ bits (1 gigabyte) of data
$1/2^{80}$ is considered negligible because an event with this probability will not likely happen over the life of the key.

On the other hand, in theory, $\varepsilon$ is considered a function $\mathbb{N} \to \mathbb{R}$.

Saying that a function is non-negligible means that the function is bigger than some polynomial infinitely often:

$\exists d: \varepsilon(\lambda) \geqslant 1/\lambda^d$

Saying that a function is negligible means that the function is smaller than all polynomials:

$\forall d, \lambda \geqslant \lambda_d: \varepsilon(\lambda) \leqslant 1/\lambda^d$

where $\lambda_d$ is some integer depending on $d$ and, in both cases, $\lambda$ is an integer.

That said we can see that $\varepsilon(\lambda) = 2^{-\lambda} = 1/2^\lambda$ is negligible, because for any constant $d$ there is a sufficient large $\lambda$ so $\varepsilon(\lambda) \leqslant 1/\lambda^d$.

We can also verify the other example from the link e-sushi provided: $\varepsilon(\lambda) = 2^{-100} = 1/2^{100}$ is non-negligible because if we set $d = 1000$ this function is clearly bigger than $1/\lambda^d$

$\square$

Note: Most of the answer is based on Dan Boneh's explanation about this subject on his coursera course
Note 2: This is also a nice answer on the subject


How to use Libsodium encryption (in PHP) in the most secure possible way? In a PHP project in which fool-proof encryption is fundamental, I'm using the Libsodium library.

Hope you guys can shine some light on the following questions.

For all of the following functions, it looks like the length of the encrypted message is directly proportional to the length of the unencrypted message:

sodium_crypto_secretbox
sodium_crypto_box
sodium_crypto_box_seal

It looks like no padding is used by default, correct ?
This means that if within my setup I use different types of messages which each have a different length, an attacker can easily derive what kind of message it's about (without however knowing the content of the message), right ?

To mitigate this risk, I want to implement padding and I am looking for some advise on how to do this.

Is appending a random length random content (using random_bytes) message to the unencrypted message a good idea ? Does it make a difference whether I append it to the end of the message, at the beginning of the message or somewhere in the middle (or a combination of all) ?
Are there more efficient ways to do this ?
If part(s) of the unencrypted messages are known, is it possible for an attacker to crack the encryption ? Or does it somehow becomes easier to do so ?

Example: if each encrypted message contains data delimited by for example "," or if each message starts/ends with a certain string or contains a certain string somewhere in the message, does this make attacks easier ?
I mean, even when using padding an attacker might still know for sure part of the message's content.

I previously asked a question about how safe the encryption is (How safe are Libsodium Crypto Boxes?). Someone replied that 2^128 tries would be required to crack it. Does the amount of tries decrease if part of the message is known ? If yes by how much does it decrease ?
What if someone knows the entire unencrypted message (for example the receiver) ? How easy/hard would it be for him to crack the senders' secret key ?
What about signed messages in Libsodium ? I know that signing does not encrypt the message but only appends a signature to it. How easy/hard is it to crack a SK based on a signature ? Could the receiver of a signed message potentially create a valid signature for a message not created by the sender ?
I read that nonces can be public without a problem. Nonetheless, does the fact that an attacker is in the possession of the nonce of a message decrease the cracking difficulty ?
Is it a good idea to change keypairs periodically to increase security ? Or doesn't this make sense ?
Does multi layer encryption make sense ? For example putting a crypto box inside another crypto box (with different keypairs off course). Or is this a bad idea ?
What about timing attacks ? I read that the time needed to decrypt/encrypt a message might give some clues about the SK. If Bob wants to crack Alices' SK, can he do so by analyzing how long it takes him to decrypt her message ? Or does it at least decrease the difficulty to do so ? If yes by how much ?

No need to implement padding, as it's already available. See the second example of the libsodium-PHP module.
Partially-known plaintext has no implication on security, especially in counter mode where the encryption of a block is independent from the previous blocks.
Creating a valid signature requires the secret key. Ed25519 has a 2^128 security target. The best attacks known actually cost more than 2^140 bit operations on average, and degrade quadratically in success probability as the number of bit operations drops.
Nonces can be public. Keeping them private doesn't significantly change the security level. However, nonces should never be used with different messages and the same key. See this page for a discussion on libsodium and nonces.
Yes. This doesn't make the cipher stronger, but mitigates the implications of a leaked secret key. If you are encrypting very large data streams, the secretstream API will automatically rotate the keys for you.
Salsa20 already has a huge key space. A salsa20-in-salsa20 cascade would have no benefits, and would be twice a slow.
Libsodium does its best to avoid side channels. Leaks are more likely to happen in the PHP code.


Difference between Zero Knowledge Proofs and Multi Party Computation I am struggling with understanding the difference between the two. From what I am putting together, they have different adversarial models, MPC adds the condition of collusion between parties i.e. election voting.

I would appreciate if it anyone could provide both a simple and expanded explanation for this.

A zero knowledge proof allows the prover to prove a statement to someone else, without giving any bit of information. Consider the following "game":
Bob tells Alice he knows how to open a door, and Bob does not want to tell her how. Say this door is in the middle of a tunnel, that has two entries. So people can enter it, open the door in the middle of it, and exit on the other way.
Now, Bob enters the tunnel from some side, say left, and Alice didn't see him. Then Alice yells: "Bob, can you get out from the right side of the tunnel, please?". If bob knows the secret, opens the door and exits on the other side, otherwise he got lucky and exits from where he entered. What is the probability for bob to fool Alice the first time? 50%, right? Because is Alice that chooses from where he must exit, once he is inside the tunnel. Think Alice and Bob repeat this protocol many, many times, say 200. The probability for Bob for exiting always from the side asked by Alice, without him knowing the secret, is 1/2^200. This is just an example, but in reality, making a proof be zero knowledge is very difficult.

For more details on it, see also the answer here

Unfortunately, regarding the MPC I don't know very much, so let's hope someone else can help you.


Is it possible to find the key for AES ECB if I have a list of plaintext and corresponding ciphertext? Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.

Can I recover that key?

If, how big does the list of plaintext and matching ciphertext have to be to be able to find it in a feasable amount of time (say in 1 or 2 hours)?

Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.
Can I recover that key?

No.  This is what is referred to as a known plaintext attack, and secure block ciphers are designed to prevent exactly this kind of attack.  This answer on the Mathematics Stack Exchange goes into more detail about the notion of IND-CPA ("indistinguishability") which AES is conjectured to meet and how that implies that a known plaintext attack is impossible.


How can I do a brute force (ciphertext only) attack on an CBC-encrypted message? Given a CBC ciphertext and IV, how can I find the encryption key?

We are limited with an 8 chars key, each char in the range of [a..h], so I can generate every possible key (these are only $8^8 = 2^{24}$ (about 4 million) different possible keys).

How would I go about finding the correct one though?

If (you suspect that) the (plaintext of the) encrypted data is ASCII text, you can check if the high bit of each decrypted byte is zero.  As long as you have more than 24 bytes of data to check, the odds of that happening by chance are pretty low (given that you have a 24-bit keyspace).

UTF-8 text is also pretty easy to detect, since all bytes that do have the high bit set can only occur in a very distinctive pattern.

More generally, if you decrypt something with the wrong key, the output will look random, and thus all bytes (and all sequences of n bytes) will appear on average about equally often.  If you get output that deviates significantly from this (where significance can be measured e.g. using Pearson's χ2 test), it will most likely be the correct plaintext.

For small amounts of data, it may be useful to apply this test not only to the full bytes but also to their highest and/or two (and maybe even three) highest bits.  This will detect byte values that cluster together (as e.g. letters and numbers do in ASCII), even if there are not enough bytes in the data to get many exact repeats.  You can also try looking at the differences between two successive byte values (modulo 256) to detect correlations.  All these (and many other variations of them) should be uniformly distributed for random data, whereas many of them will show distinct deviations from uniformity for most kinds of non-random data.


MAC where key is provided afterwards I was just wondering if there is a MAC scheme where the key provided after part of the message has been hashed. I was just looking at TLS 1.3 and a comment of Thomas Pornin where the messages needed to be stored before they were hashed with the session key. But I wonder if it isn't easier to first hash the messages and then provide the key.

Of course the hash algorithm would have to be established, but the ciphersuite is established after the Server Hello message. In that case it could be benificial to something similar to $\operatorname{HMAC}_{K_{mac}}(\operatorname{H}(M_1 | M_2 | M_3))$ (where M is a handshake message), but preferably with a single primitive.

Is there a reason that the key is put in first within HMAC / or SHA-3 / KMAC? Are there reasons that the key cannot be put in last? Or are there schemes that already do this?

If you have a secure MAC algorithm $M$ and a collision-resistant hash function $H$, then you can define another secure MAC algorithm $M'$ such that $M'(x) = M(H(x))$. Historically, though, HMAC was defined as a construction that provides reasonable security as a MAC even for an underlying hash function which is a bit flaky in that respect (in that case, Merkle-Damgård functions like SHA-1, that suffer from the so-called length extension attack, which illustrates the subtleties of MAC-building out of hash functions).

(For reference, my comment in the TLS-1.3 mailing-list is about the need to buffer incoming data until the MAC can be verified; this is unrelated to the moment the key is injected in the MAC process.)


Attribute-based encryption for cloud storage I'm trying to understand attribute-based encryption schemes. Almost all articles describe that they are designed for cloud storage, but as I understand, almost all computing (encryption & decryption) is performed client-side and not in the cloud.

In this regard, I have a question: How are these schemes related to cloud storage?

It is related to Cloud storage in the sense that you don't have to trust the server you put your data on.
Usually, the access control is done via authentication. This requires the server to be trusted.
However in the case of Cloud storage, you don't know anything about the server hosting the data, so being able to do access control with the encryption scheme is great.


Shared secret beginning with 0h? I'm designing a system where my hardware piece uses an ATECC608A to calculate an ECDH shared  secret in order to exchange data with a HSM in the cloud.

For some unknown reason, whenever the first nibble of the shared secret generated by the device is zero, the correspondent shared secret generated by the HSM is shifted 4 bits.

ATECC output :  0D E8 A2 9D 8F .....
HSM output   :  DE 8A 29 D8 FE .....

The HSM never generates a shared secret starting with 0, while the ATECC generates it at a rate statistically compatible with 1:16.

My questions are:

Is it mathematically possible to generate a shared secret starting with 0x0n using ECDH? (My guess is "yes")
Is there any rule or convention  stating that a shared secret should be shifted so that the first nibble shall never be 0?
Since I'm not the guy working on the HSM side, and don't know anything about it. Is it possible that there is some sort of configuration flag enabling or disabling the generation of shared secrets starting with nibble 0?

I don't believe there is a bug in such a widely used device, nor that at least two different software packages running on the HSM (as the HSM guy told me) are also wrong.

Added information: the generated shared secret is 32 bytes long.

Any ideas?

Thank you very much for any help.

1 - Is it mathematically possible to generate a shared secret starting with 0x0n using ECDH? (My guess is "yes")

Yes; the shared secret is the $x$ coordinate; approximately half of the values between 0 and $p-1$ (where $p$ is the prime that the elliptic curve is defined over) are possible; there's no reason to believe that the values with a top nybble of 0 are all impossible.

  2 - Is there any rule or convention stating that a shared secret should be shifted so that the first nibble shall never be 0?

I've never heard of one.


Any standards for canonical ordering of HMAC or additional data in AEAD ciphers? According to RFC 5116...  If the AD input is constructed out of multiple data elements, then it is essential that it be unambiguously parseable into its constituent elements, without the use of any unauthenticated data in the parsing process.  (In mathematical terms, the AD input must be an injective function of the data elements.)  If an application constructs its AD input in such a way that there are two distinct sets of data elements that result in the same AD value, then an attacker could cause a receiver to accept a bogus set by substituting one set for the other. The requirement that the AD be uniquely parseable ensures that this attack is not possible.  This requirement is trivially met if the AD is composed of fixed-width elements.  If the AD contains a variable-length string, for example, this requirement can be met by also including the length of the string in the AD.

I’m using an AEAD to confirm integrity on a message and occasionally decrypt a payload if it exists, but my issue should apply to any arbitrary data in CRC to HMAC. How do you take arbitrary data and unambiguously order it

Imagine I have some serialization (example JSON) that can have 1-100 fields I’ll assemble into data to be get a MAC (my AD in AEAD). The receiving end has no idea which ones are coming, and the ordering of decode is not guaranteed.

It seems my options are to order the object data in some predetermined way like apple’s value is placed into a byte array  before bannana’s value is. But then there is an issue of types, in my system apples will only ever be 0-12 so one byte works great, but bananas can get to 65000, so two bytes, carrots need a 32bit, and I  am owe dates so I need signed there. Or I have the option of using the serialized container without parsing it at all but there are other problems with that.

Without getting too over the top in examples, I see the issue even if I gave everything a 64bit space and put its length in front, I quickly end up with a confining system - or I end up with a schema that needs to be shared on both sides.

So are there any standards or even formally recommended practices for this?

Imagine I have some serialization (example JSON) that can have 1-100 fields I’ll assemble into data to be get a MAC (my AD in AEAD). The receiving end has no idea which ones are coming, and the ordering of decode is not guaranteed.

If the receiving end really has no idea which fields are coming as you say, then the only way it can possibly determine the authentic AD for a message has to be from information that's transmitted alongside that message.  There's a bit of a subtle point here: the AD for a message in practice can be either (or a mix of):

Unencrypted data that is stored or transmitted along with the encrypted data proper.  Often people will call this a "header."  In this case the receiving end knows the AD because it's right there next to the ciphertext so to speak.
An encoding of information that isn't stored or transmitted along with the ciphertexts, but which the sender and receiver can correctly infer from the context in which each message occurs. For example, if messages are part of some protocol where the participants' interaction is governed by some state machine, an encoding of the current mutually known state can be used as AD.

If your statement that "the receiving end has no idea which [fields] are coming" is true, then, it sounds like you're in a pure example of #1—you have to send the JSON-encoded AD along with the ciphertext for the recipient to know it at all.  In that case the JSON text sounds like it would serve you just fine as AD or an element thereof, as the JSON encoder call that produced that text embodies some injective function of the data elements into a textual representation that can then be uniquely parsed.

JSON-encoded data however can be problematic for case #2 (implicit AD), because although JSON is uniquely parsable, there is more than one textual encoding for any given datum, e.g., whether you use optional whitespace or not, and ordering of named fields as you remark. The problem is that even if both ends mutually know the correct set of key/value mappings, they might encode it to different textual AD strings that would then fail the authenticity checks.  In that case either the two ends would have to agree on how to do the JSON encoding in an identical manner, or use some other encoding that's not prone to this problem. Encoding the fields alphabetically by field name as suggested is one possible tool for this, indeed.


7-Zip Encryption: Practical Effect of Lacking Salt A previous discussion on Cryptography StackExchange leads me to understand that 7-Zip does not use salt to derive an encryption key from password to use its AES-256 encryption; that this is a potentially severe shortcoming; and that its impact is to make it relatively easy to crack multiple .7z files.
My question is, what does this mean in practice? Possible inferences or points of confusion:
(1) Virtually all other notable AES-256 file encryption tools (e.g., AES Crypt, Gpg4win, Cryptomator) do use salt; therefore they are significantly more secure than 7-Zip.
(2) The absence of salt doesn't have any practical effect on brute force password cracking methods, else Elcomsoft would not say that .7z is still harder to crack than RAR5.
(3) The absence of salt is a severe shortcoming only where the cracker seeks access to multiple .7z files. But why would that make a difference? If all those files use the same password, then yes, brute forcing one will open them all. If they use different passwords, the absence of salt would presumably make no difference.
(4) The absence of salt in 7-Zip is moot if I use some other AES-256 tool with salt to create a .7z file.

The absence of salt is a severe shortcoming only where the cracker seeks access to multiple 7z files. But why would that make a difference?

If there is a password verification method and there is no salt, then password search can be batched. Calculate one hash and test for all targets. If you consider that the 7Zip uses SHA-256 with $2^{19}$ iteration this is a huge reduction in the attacking timing.
The batching is usually performed by building a rainbow table in advance for the small size of passwords including the known passwords. This highly reduces the attack time if the target passwords are on the table.
If the attacker has only one file, then this doesn't matter; instead of building the table, just search. For further usages building the table is preferable.
It seems that 7zip doesn't use a password verification method. One has to decrypt and unzip the file. If during this process there is a format error the process will stop. This severely affects the performance of batching. Still, the attacker can generate the hash of the password and test for all targets this is faster than one by one for each file.
In any case use passwords with good strength like passwords generated from dicewire or Bip-39. If you have a password that has strength > 128 then you are safe against the attacker even the batch.
Note that there is no detailed information about the experiment made with Elcomsoft. Does it a single password or multiple password search. It seems a single search. The article is not well written in this sense.
The less number of password tries is due to the number of iterations.

The absence of salt in 7-Zip is moot if I use some other AES-256 tool with salt to create a 7z file.

Lack of Salt is not a real problem for a power user. Just generate a salt and carry it with the 7zip file. During the key generation prepend the salt to yo your password.
For normal users, the salt must be used against the batch attackers.


What is the probability of attacking SHA1 used in RSA signature with small exponent? There is RSA signature check which has following properties:

RSA modulus N which is 2048-bit
RSA public exponent equal 41 (0x29)
Genuine Signature uses EMSA-PKCS1-v1_5 padding of SHA1 hash, however the verifier only compares 20 least significant bytes which are the SHA1 hash. In order to trick verifier, forged signature needs to contain SHA1 of message on the 20 least significant bytes. All other bytes are ignored.

Due to broken check, there exists around $2^{48}$ (because $(2^{48})^{41}$ is smaller than modulus) SHA1 signatures that can have signature forged using algorithm described in Mathematics.

If I try $2^{32}$ different hashes (by trying all numbers in the last 4 bytes of the hashed message), what is the probability that I will encounter one of these $2^{48}$ easy-to-forge hashes?

Is there any other attack type that might be used for such broken signature check?

Adversary has 6 genuine signed messages (message and signature; message not chosen by attacker) and is not able to obtain more.

This is not an answer; rather, I attempt to improve the method outlined in the question.

Problem statement (slightly simplified): it is given an RSA public key $(N,e)$ with $2^{n-1}<N<2^n$, $n=2048$, $e=41$, a hash function $H=\operatorname{SHA-1}$ with output of $w=160$ bits. It is asked an $(m,s)$ with $0\le s<N$ and $H(m)=(s^e\bmod N)\bmod2^w$.

Note: for simplicity, I ignore the six given (message, signature) pairs and that the $(m,s)$ to exhibit must not be among them. These $(m_i,s_i)$ are such that $0\le s_i<N$ and $(s_i^e\bmod N)=H(m_i)+c$ with known $c=2^{n-15}-2^{8+v+w}+2^w b$, $v=120$, $2^{v-8}\le b<2^v$, $b=\mathtt{0x3021300906052b0e03021a05000414}$ (that's by definition of EMSA-PKCS1-v1_5).

As noted in the question, for any given $m$ with $H(m)$ odd, if there exists an odd $s$ such that $(m,s)$ is a solution to our problem and $0\le s<\Big\lceil\sqrt[e]N\Big\rceil$, then we can efficiently find that $s$ by computing $h=H(m)$ and solving for $w$-bit $s$ the equation $s^e\equiv h\bmod 2^w$; we keep $s$ as solution if $s<\Big\lceil\sqrt[e]N\Big\rceil$.

If we try this for a random $m$, each attempt costs an average of two hashes to find $H(m)$ odd, finding one solution to the equation $s^e\equiv h\bmod 2^w$, and succeeds with probability about $\epsilon=\sqrt[e]N/2^{w+1}\approx2^{(n-1/2)/e-1-w}$; that's slightly under $2^{-111}$ and as is, this strategy is doomed.

Notice that for any given $m$, if there exists $r\ge0$ with $r+H(m)$ odd and odd $s$ such that $(m,s)$ is a solution to our problem and $\Big\lceil\sqrt[e]{r N}\Big\rceil\le s<\Big\lceil\sqrt[e]{(r+1)N}\Big\rceil$, then we can find that $s$ by computing $h=H(m)$, and solving for $r$ of appropriate parity and $w$-bit $s$ the equation $s^e\equiv(h+r N)\bmod 2^w$; we keep $s$ as solution if $\Big\lceil\sqrt[e]{r N}\Big\rceil\le s<\Big\lceil\sqrt[e]{(r+1)N}\Big\rceil$.

If we just enumerate small incremental $r$ of the appropriate parity, compute $h'=h+r N\bmod 2^w$, and solve for $w$-bit $s$ the equation $s^e\equiv h'\bmod 2^w$, then for each $r$ we have probability about $\epsilon_r=\left(\sqrt[e]{(r+1)N}-\sqrt[e]{r N}\right)/2^{w+1}$ that $s$  turns out to be in the correct range; that is, $\epsilon_r=\begin{cases}
\epsilon=\sqrt[e]N/2^{w+1}&\text{ if }r=0\\\left(\sqrt[e]{1+1/r}-1\right)\;\epsilon&\text{ if }r>0\end{cases}$
This is an improvement if the cost of solving $s^e\equiv h'\bmod 2^w$ is much lower that the cost of a hash (or if our messages $m$ are heavily constrained). In particular, if $h=H(m)$ turns out to be even, we formerly abandoned that $m$, and now have probability about $\epsilon_1\approx\epsilon/59$ that the solution $s$ to $s^e\equiv(h+N)\bmod 2^w$ is acceptable.

Also, when solving $s^e\equiv(h+r N)\bmod 2^w$, if we compute $s$ bit by bit starting from the low-order bits, we can abandon as soon as we have enough bits that it is certain that $s$ is not in the appropriate range.

Perhaps a simultaneous search of $(r,s)$ is feasible; I'll be thinking about it. As the saying (attributed to the NSA) goes: attacks only get better; they never get worse.


Is it possible to create a 128-bit UUID from a weak entropy source? I am looking at a seemingly popular piece of JavaScript code to generate a UUID which is supposed to be a 128-bit number:
function uuidv4() {
  return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
    var r = Math.random() * 16 | 0, v = c == 'x' ? r : (r & 0x3 | 0x8);
    return v.toString(16);
  });
}

This uses the browser's Math.random(). To dissect this further, it seems to be mostly replacing each x character in the string with a separate call to the Math.random API to create a hex digit (4 bits) e.g.:
function getRandomHexChar() {
    let randomChar = Math.random();       // 0.6429364007765519
    randomChar = randomChar * 16;         // 10.28698241242483
    randomChar = randomChar | 0;          // 10
    randomChar = randomChar.toString(16); // a

    return randomChar;
}

For our application I assume we absolutely need the UUID to be unique or probably bad things could happen if it is repeated. However the thing I would like to know is if it needs to use a cryptographically secure PRNG to guarantee it to be unique?
Apparently Math.random once returned random numbers limited to $2^{32}$. It is a bit better in Chrome, Firefox and Safari now though, they are able to return numbers limited to $2^{128}$ (but it now uses xorshift128+ algorithm which is not cryptographically secure). Also this is certainly not 'all' browsers so maybe it's safe to estimate Math.random only gives $2^{32}$ bits of entropy.
So I guess my question really boils down to this: With repeated calls to Math.random (i.e. a non-cryptographically secure 128 bit RNG or with perhaps $2^{32}$ bits of entropy) like this e.g. getRandomHexChar() + getRandomHexChar() + ... to concatenate 4 bits of pseudo randomness at a time until you get a 128 bit number, will this really give a safe unique UUID of 128 bits? Or is the entropy in that resulting UUID much lower?

The entropy will never go higher than the amount you put in. So if you require 128 - 4 = 124 bits and you input 32 bits, you can rest assured that the amount left is at most 32 bits. It's really that simple. And in that case, there is a high likelihood of collisions due to the birthday bound.
Now generally you will likely not find dupes during regular use, but an adversary may simply try and see if a collision can be made. In that case all bets are off, because in the end the RNG is simply not cryptographically secure.
I'd also be concerned about the entropy source. If it is 32 bits taken from the system clock then it is really not entropy at all, to name just one common option.

Try and avoid generating UID's at the client side entirely.
If this is really something you require then there is subtle crypto now for JavaScript in browsers, use that cryptographically secure random number generator instead. Beware of dragons though: "There is no minimum degree of entropy mandated by the Web Cryptography specification." ... this might especially be an issue on non-standard / embedded browsers.


Creating single-cycle permutations There was this one time I came up with a small permutation that had a block size of 16 bits. This was small enough to compute every mapping. I then iterated the mapping starting with zero to see how many iterations it would take to return to zero. The number was less than half of $2^{16}$.

For whatever reason, let's say a person needs a pseudorandom permutation that has only one cycle. Perhaps they need to make a single-cycle S-box or they want to use the permutation to create a non-linear tweak to the plaintext input of a block cipher (each block's tweak is the result of successive iterations instead of increments of one). First thing that comes to my mind is a full-period LCG, but when I tried this for making an S-box ($f(x) = (37 \cdot x + 11) \mbox{ mod } 256$), the results seemed rather orderly. This wouldn't matter for a tweak for plaintext blocks, but it seems desirable to simply not have that property of orderliness. So, what are some way of generating/constructing single-cycle permutations?

The obvious way to construct such a pseudorandom single-cycle permutation is to take a pseudorandom permutation $P$ (which need not be single-cycle), a simple fixed single-cycle permutation $Inc$ (e.g. just increment the value by 1), and construct:

$$S = P^{-1} \ \circ Inc \ \circ P $$

That is, to evaluate $S(x)$, you first apply the permutation $P$ to $x$, then the permutation $Inc$, and then the permutation $P^{-1}$, which is the inverse of the permutation $P$.

Things that should be obvious:

$S$ is a single cycle permutation
Every single cycle permutation can be expressed this way with an appropriate choice of $P$
(Less obvious) if $P$ is selected uniformly over all permutations, then $S$ is selected uniformly over all single-cycle permutations.


How to design a secure data container? I want to design a secure data container that can be used to transfer encrypted data over a public network that can defeat common attacks. Data is already encrypted before entering this container so that is out of scope. The container need to store some detail about the cipher used so that it can be properly decrypted when arrived at the other end.

My basic idea is to use chunks of data, with headers seperated from actual data, containing:

CHNK chunk: chunk list chunk, always the first chunk.
DATA chunk: encrypted data, as is or optionally compressed (after encryption).
SIGN chunk: Signature of the data chunk, either a digital signature or a MAC.
INIT chunk: (Optional) IV of the cipher used, optionally encrypted with the asymmetric algorithm used.
ISGN chunk: (Optional) Signature of (possibly encrypted) IV.
SKEY chunk: (Optional) Encrypted session key, if the main algorithm is asymmetrical.
KSGN chunk: (Optional) Signature of encrypted session key.
INFO chunk: (Optional) Comments that is not encrypted or verified.

File structure: (Using C structure notation, all multi-byte numbers is stored in network byte order)

struct chunk_s
{
    uint8_t  magic[4]; // Chunk FourCC header.
    uint32_t flags;    // Chunk flags, including information of the algorithm.
    uint64_t offset;   // Offset of the chunk from head of file.
    uint64_t size;     // Size of the chunk.
}

EDIT:

To resolve some issues raised in comments, I will say again that the signature chunks can be either a signature or a MAC, also you can apply both a signature and a MAC by using two (or more, if different algorithms are used) SIGN, KSGN, ISGN,HSGNorSSGN` chunks carrying different flags. Algorithm is identified by the flags field.

HSGN chunk: signature of header/chunk list.
RSGN chunk: "signature of randomness", essentially a chunk of nonce that is counted when calculating SSGN chunk
SSGN chunk: signature of all other types of signature chunks concatenated together in the exact order as found in the chunk list. Usually the last chunk.

You should encrypt the data using a well-vetted standard, like TLS (for data in motion) or GPG (for data at rest).  Designing your own is more likely to lead to sadness.  The format of the data that you protect in this way is up to you and can be broken down into structs and chunks and headers etc. to your heart's delight.


Is the Java function AES/CBC/PKCS5Padding vulnerable to padding oracle? I have an application that stores data on the devices. Currently AES/CBC/PKCS5Padding from javax.crypto.Cipher(see reference) is used to encrypt the stored data.

The padding isn't verified manually. Does that make the process vulnerable to Padding Oracle attacks?

Would the process benefit from using AES/GCM?

The problem with CBC mode is the padding. When there is a padding error, the server must respond a message back to you so that you can send the message back again or encrypt the message from the beginning.
The padding oracle attack is solely based on this idea. The attacker changes the byte and looks at the response of the server to execute the attack.
As we can see the attacker needs an oracle to execute the padding oracle attack. Data on-rest or encrypted databases has no oracle. Therefore they are not vulnerable to padding oracle attacks.

CBC mode has no integrity and authentication and removed from TLS 1.3.
AES-GCM which is in TLS 1.3 has an authenticated encryption scheme which provides both integrity and authentication. In the internal GCM mode uses CTR mode for encryption that requires no padding. Therefore padding oracle is not applicable.
So in short, in GCM mode you will have

Integrity
Authentication, and
No padding which is vulnerable to padding oracles.

Since you are going to use AES/GCM your next issue will be the IV. Instead of random IV, you can use incremental IV so that you can mitigate IV Reuse catastrophe. For more information on IV recommendations see section 8 of NIST-800-38D
In Java, you can use AES/GCM/NoPadding from  javax.crypto.Cipher package.


Finding IV for forgery of AES CBC-MAC with non-fixed IV As CBC mode might do several rounds, how it could be possible to find another IV for forgery attack?
This is an example from my course:
Assume you receive a pair with the plaintext $P_1$ and its MAC using an original $IV_1$. If you want to change $P_1$ to another plaintext $P_2$, how to find the $IV_2$?
As said in explanation, the process could be:
$MAC = E(P_1 \oplus IV_1)$
$MAC = E(P_2 \oplus IV_2)$
so,
$IV_2 = P_1\oplus IV_1 \oplus  P_2$
Why it is possible?
I test it with cryptool2 but it doesn't work...

This is a demonstration of MAC forgery. This is not the CBC-MAC where the IV is always set to zero and there is also, ECBC-MAC as encrypt the last block which doesn't need the length of the message beforehand to be secure.
Given a MAC, its plaintext $P_1$, and the $IV_1$ on this simple CBC-MAC
$$MAC_1 = E(P_1\oplus IV_1)$$
We want to forge a signature based on this;
$$MAC_2 = E(P_2\oplus IV_2)$$
and we want a forgery without even knowing the key. Since the IV is not fixed, we can play around with it.
Set an IV so that the resulting X-or with the plaintext will be equal to the giving message and its IV. The plaintext will be different, however, the MAC value will be the same; a forgery!
Take $P_2$ be the target message to be forged into the signature.
Take
$$IV_2 = \underbrace{P_1\oplus IV_1}_{\text{cancel part}} \oplus \underbrace{P_2}_{\text{target message}}$$
check  $$P_2 \oplus IV_2 = P_2 \oplus P_1\oplus IV_1 \oplus P_2$$
simplify
$$P_2 \oplus IV_2 = P_1\oplus IV_1 $$
and, this is a forgery since we have a different message and IV that it's x-or equal to the given MAC. This can happen since the attacker can choose the IV. To mitigate take the IV fixed as in the CBC-MAC.

As CBC mode might do several rounds, how it could be possible to find another IV for forgery attack?

The above example was for messages of one block. For multiple blocks, just set the first block as above, and keep the remaining blocks are the same. This will be multiple block messages forgery on this signature scheme.


What operation does $\|$ denote in ANSI X9.63 KDF? Can someone tell me in laymens terms what this is?

$$K_i = \mathrm{Hash}(Z \| \mathit{Counter} \| [\mathit{SharedInfo}])$$

What do the double pipes represent?

It means concatenation. Z, Counter, and SharedInfo are three bitstrings which are to be concatenated before hashing. The [ ] around SharedInfo means it may be absent in which case you would use an empty string instead. (Since concatenating an empty string to the end yields the same result as not concatenating anything.)


Intuition for Schnorr Blind Signatures I was studying the Blind schnorr signatures in this paper (PDF) which says that the signer sends a commitment

$$r=g^{k}\bmod p$$

which the user blinds with 2 random elements $a,b$ to get

$$r'=r\cdot g^{-a}\cdot y^{-b}\bmod p$$

what is the intuition behind this blinding step?

Why can't we use the normal Schnorr signature with Fiat-Shamir heuristic  with the user supplying $e=H(m,r)$ to generate the challenge on his message?

Schnorr signature is a pair challenge-response $(e, s)$ with challenge computed as a hash of message $m$ and initial commitment $r$; signature is verified by re-creating that commitment with challenge and response only.

For blind Schnorr signature, one keeps verification equation while randomizing both challenge and response with $\beta, \alpha$ respectively, see page 368. Hash is calculated by receiver of the signature; signer computes his response having blinded challenge $e = H(m, r') + \beta$ only, without $\beta$ and $r'$ to enforce blindness property. That is, having an $(e, r)$ pair verified, signer can not recognize it as any of his signatures sent to receivers.

In case receiver would send $e = H(m, r)$ unblinded to signer, or let signer calculate the hash himself, signer would recognize the receiver later.

The only missing part is how to calculate $r'$ such that verification equation would hold for $(e, r)$ after blinding. Best be done yourself as a homework.

Blind signatures are here to avoid recognition. That is, to have no algorithm that, having a signature and a database (records of signatures issued), would output who this signature was produced for. To achieve this, two challenge-response pairs were introduced, and the user is actually generating $e = H(m, r)$ himself. Connection between that pairs is user secret. Having it open, blindness property would be lost.


Is the one-time pad still perfectly secret if all-zero keys are excluded? I'm trying to solve this question related to one-time pads and perfect secrecy:

My solution is: I assumed that the current message space is  $M = \left\{ 0,1 \right\}^l$ and the new keyspace after removing $0^l$ from the set is $K = \left\{ 0,1 \right\}^l - 0^l$. Since clearly $|K| < |M|$, the new scheme is not perfectly secret.

Is my solution correct?

Yes your solution is correct; the flawed OTP scheme is no longer perfectly secret if there are fewer keys than messages.

Once you remove the all zero key the property
$$
\mathbb{P}[M=m|C=c]=\mathbb{P}[M=m],\qquad \forall m,\forall c,\quad(1)
$$
required for perfect secrecy will no longer necessarily


Is it Ok in practice to rely only on the first 64 bits of a scrypt hash in this scenario? I’m in a situation where I need to perform authentication against a large set of exactly 8 bytes longs passwords (with however full choice of encoding from the user and even custom encoding support): more exactly 15,000,000,000 passwords corresponding to the same numbers of unsorted hash which should be used on a public custom blockchain (with however no lookup services).
Due to the public nature of the process, the plan is to only keep the first 8 bytes of each scrypt hash without salt (yes salting is not used) in order to reduce storage. So hash sizes would have the same length as passwords.
If a single collision is found against only one of those passwords it’s game over (since there’s no randomnization generation in the process each inputs will always match a specific hash).
Result
The sets of passwords are changed every 2 years so there would be no benefit from finding a collision on no longer valid data.
Additionally, it’s a modified version of scrypt designed to take way more times longer than the original. The results still give the same hashing characteristics than original scrypt but with differents hashs than plain scrypt given the same data. The algorithms itself has been audited by a third party professional as being sound both on paper and rust implementation.
This also gives the benefit of being both initially gpu and asic resistant (an implementation could still be designed but the money required would outweigh the reward/damage obtained in this scenario).
Question
This situation sounds risky, but I think the probability is still low for being secure in practice. Though I recognize I’ve no idea on what would be the lookup time on a such large table built from the valid hash lists.
So from a pure performance standpoint, is it correct to assume no collisions can be found using cpu (including those without any support for simd instructions) only methods on a reasonable timespan in practice?
The reference generic implementation used performs a Hash every 5 seconds on a Skylake cpu (and it was optimized with code coverage but is not simd outside using the 128 bits Builtin type). An attacker would have to cope with such low speed if he/she want to brute force (it’s also possible to create a naïve and far slower implementation).

No, you cannot assume that no collisions can be found if there is a chance of $1 \over 2^{32}$ per try. That's too high a risk for almost any kind of cryptographic scheme, especially if parallel attacks are possible. This is true by definition for scrypt as you can simply try multiple passwords at the same time. That kind of parallelization cannot be avoided even if you modify scrypt.


How OR gates are garbled in recent optimizations techniques like free XOR, Half Gates? I am a research student and I have been studying garbled circuits, specifically its optimization techniques. However, in every research paper i have encountered, the researchers have only shown how to garble an AND gate and XOR gates. The circuits do contain OR (or don't they?), my question is how an OR gate will be garbled in Half gates and Free XOR techniques scenario? Any help in this regard would be highly appreciated.

Usually, only AND gates and XOR gates are considered in garbled circuit schemes, because they form a complete basis for boolean circuit - id est, any boolean circuit can be written only with XOR gates and AND gates. In particular, you can implement an OR gate with a single AND gate and only XOR gates, using the fact that $a \text{ OR } b = \text{not }((\text{not } a) \text{ AND } (\text{not } b))$, and $\text{not } x = 1 \text{ XOR } x$. Therefore, with the latest scheme which garbles AND gates with two ciphertexts, and where XOR gates are for free, garbling an OR gate uses only two ciphertexts, exactly as an AND gate.


Merkle tree (dm-verity) with SHA-256 vs. SHA-1 Is there any knowledge or research on the use of different hash functions within a Merkle tree? My use case is file integrity protection. I am thinking about using different hash functions due to performance restrictions:

Linux device mapper verity target allows you to select different hash functions. I originally aimed at SHA-256, however SHA-1 is measurably faster and I would like to know if its insecurity is still there, when used in a Merkle tree. (Btw: root hash is protected by RSA signature) Assuming a storage device with 2GB of data and 4Kb blocks, verity creates a merkle tree with 3 tree levels between data and and the root hash. I understand that a single SHA-1 is unsecure for the integrity of a file, but what about the approach of having a hash per 4Kb of a file. If an attacker changes one block only, the input data for intermediate hashes change only at 20 bytes (32 byte for SHA-256) while the remaining 4064 (4076) byte are identical. So does this make finding a collision really harder or is this a misinterpretation? This partial change in data propagates up to the root of the tree.

Ok, changing only one data block with a collision in the corresponding hash breaks the hash tree, as the collision at the bottom yield to the same hash tree. This is easier with SHA-1, isn't it?

What about changes in a block without a collision where collision at the intermediate nodes must lead to the same root hash value. Is this harder?

What hash would you suggest for such a use case? There is no recommendation with Linux kernel implementation of dm-verity. Is SHA-1 too weak?

SHA-1 is measurably faster and I would like to know if its insecurity is still there, when used in a Merkle tree.

Yes, the insecurity is still there. Any collision in the underlying hash function can be used to produce a collision in the root of the Merkle tree.  A quick example:

Suppose our SHA-1 Merkle tree has two leaf nodes, $a$ and $b$, and that we know a SHA-1 collision such that $\text{SHA-1}(m_1) = \text{SHA-1}(m_2)$ but $m_1 \neq m_2$.  The root hash of the Merkle tree will be $h = \text{SHA-1}(\text{SHA-1}(a) \| \text{SHA-1}(b))$.

We can create two different trees with the same root hash by setting $a$ to $m_1$ in one tree, and $a$ to $m_2$ in the other (and keep $b$ the same for both trees).  These trees will have the same root hash: $\text{SHA-1}(\text{SHA-1}(m_1) \| \text{SHA-1}(b)) = \text{SHA-1}(\text{SHA-1}(m_2) \| \text{SHA-1}(b))$, because $\text{SHA-1}(m_1) = \text{SHA-1}(m_2)$.  In other words, an attacker can swap out a block in the bottom of the tree without the root node "noticing".

The use of a Merkle tree will not protect against problems in the underlying hash function's collision resistance.  I wouldn't recommend using SHA-1 if security is an important consideration here.

Normally, I would recommend using BLAKE2.  It (well, its predecessor) was a finalist in the SHA-3 competition (i.e. it's secure), and it's faster than both SHA-1 and MD5.  Unfortunately, I don't know if it's available in dm-verity.


Is there an "additive" proof-of-work? I'm trying to find a proof-of-work algorithm with the following properties:

If A(1) is a proof of work with Difficulty(A(1))=n (requires n basic operations on average), then one can find a proof of work A(2)=F(A(1)) with Difficulty(A(2))=Difficulty(A(1))+n by performing approximately n operations.
The size of A(i) is be bounded by the logarithm of Difficulty(A(i)) (the accumulated difficulty).

One way to achieve this is to choose a problem which allows approximating the solution that also has a fast method to find out the approximation error. Then performing the proof of work consist of refining the best previous solution.

For example, approximating the real square root of 2 may satisfy property 1, but it does not satisfy property 2. In some finite groups finding a non-trivial root is hard, and the proof is bounded in size, but property 1 is not satisfied.

I was also thinking that maybe a variant of Very smooth hash may work, or a group-theoretic hash function, buy I haven't figure out how.

The idea is that if such function is used for PoW of a block-chain, then comparing the difficulty of two competing chains is reduced to comparing the difficulties of two blocks.

There is a solution in Bitcoin involving using Merkle trees of previous blocks and SPV proofs, but I'm looking for a proof whose size is strictly bounded.

Your property of what I would call "improvable" is actually considered undesirable for PoWs. It would allow a prover to make continuous progress
toward a solution that satisfies the difficulty threshold. Which would
mean that a prover that's twice as fast as another, has more than double
the chance to win the race, which is considered unfair. Being twice as fast should just double your expected wins.

So in fact a PoW should be what is known as "progress free",
which would seem to require not having your property.


Why doesn't SSH use TLS? Most cryptographically protected protocols use TLS these days. This applies to mail protocols, HTTP and many others. The newly designed QUIC has also adopted TLS as its cryptography layer.

However, SSH is different: it has its own cryptography layer.

Why does SSH have a non-TLS cryptography layer? Are there any benefits for SSH to have its own cryptography layer?

About the only difference between SSH and other protocols is that SSH frequently sends messages having just one keystroke. Is the SSH cryptography layer more optimal in the case of extremely short messages?

Related although not the same: How does TLS differ from SSH from a strictly cryptographic perspective?

I think the certificate verification mechanism of SSH (automatically learning) could be supported with TLS. You just wouldn't have a root CA; you would accept each certificate separately and remember the acceptance.

SSH not using TLS is mostly historical; see for instance this answer (on security.SE). In practice, one could perfectly define a sort-of SSH that would use TLS for the data transport part; but, of course, it would not be compatible with existing SSH servers and clients. From a pure cryptographic point of view, SSH actually has some shortcomings with its encrypt-and-MAC encryption, and encrypted "length" field; this does not lead to really exploitable vulnerabilities due to the specific usage of SSH (attackers don't get to trigger thousands of new silent connections with partially chosen data, contrary to TLS, where such things can be done thanks to the magic of JavaScript), and recent AEAD integration mostly fixes them anyway.


Is there a client-side program to cryptography a HTML page and decode if correct password is writen? I want to know if there is an easy way to do this:

create a complete HTML page
cryptography the text content (image is not important)
ask user some password
check the password with a cryptographed password if(hash(userPassword)==hasedPassword)) return true;
if the password is correct it will decode it and show the content.

All this in user-side, not server-side. Because this I will use javascript.

Is there any good implementation?

If you put the text content of the webpage encrypted into HTML5 local storage, IndexedDB or embedded as a hex/base64 string in the web page, then you you could try something like TripleSec which would take your password, run a PBKDF and decrypt the content.

Or you can use one of the many JavaScript libraries CryptoJS, SJCL etc and do it yourself manually.

You should run the code as a local .html file on the filesystem or in a browser extension. Don't make the mistake of running the JavaScript code served up from the server because your security would only be as strong as the HTTP/HTTPS connection and vulnerable to MITM. Even HTTPS is not secure against some attackers.


Can $d$ and $e$ be the same number in RSA? I'm reading about RSA and I have doubts:

1) To choose $e$, this value have to be between $1$ and $\phi=(p-1)(q-1)$, with $\gcd(\phi, e) = 1$, right?

2) In my example, $p = 139$ and $q = 491$. So $n = 68249$ and $\phi = 67620$. Assuming my point 1 is correct, $e$ can be $67619$. But $d$ can be $67619$ too, because $67619^2 \equiv 1 \mod 67620$.

Is this reasoning incorrect?

1) To choose $e$, this value have to be between $1$ and $\phi=(p-1)(q-1)$, with $\gcd(\phi, e) = 1$, right?

No; $e$ can be any value that's relatively prime to both $p-1$ and $q-1$ (or equivalently, relatively prime to $\operatorname{lcm}(p-1, q-1)$).  There may be little point in choosing an $e$ larger than $n$; however there's no specific reason it wouldn't work.

  2) [Paraphrased] What if I pick an $e$ with $e^2 = 1 \bmod (p-1)(q-1)$; and set $d = e$.  Would it work?

Well, yes, it would work, in the sense that the protocol will encrypt and decrypt messages just fine.  It wouldn't work in the sense that it wouldn't be secure (even if you used more realistic sizes of $p$ and $q$).


Choose Argon2i or Argon2id for secure password hashing on a website? I make a website with authentication. I have studied a lot of answers to these questions, but I still don't understand what is better and safer to use for a website: Argon2i or Argon2id?
I know which attacks they protect against, but unfortunately I don't know which ones are dangerous for the website.
The only thing I realized is that Argon2d is not suitable for me, since It is used mainly for cryptosystems.

Also, although this is not entirely relevant to this question, when I
chose the hashing algorithm from bcrypt, scrypt, pbkdf2 and Argon2, I
chose it. Did I make the right choice?

Thank you all in advance for your answers!

It depends. If you use weak parameters, then no matter what algorithm you choose the brute-forcing can be done relatively easy.
Think against what risks do you want to protect passwords. Argon2d gives some possibility of side-channel attacks. This is relatively complex and expensive approach. I'd suggest you to estimate the risk that somebody will pay a lot of money to implement side-channel attack. If you are implementing an application where passwords protect banking transactions of millions of USD, then the risk may be higher. If you are implementing an application focused on cooking receipts or traveling recommendations, then may be nobody will be willing to pay a lot of money for a side-channel attack. Then Argon2d may be a perfect choice for you.
I would suggest following (it is a matter of taste): Take Argon2id, it combines advantages and disadvantages of both Argon2d and Argon2i. It combines advantages of both. Pay better more attention to the proper selection of tuning parameters.


Figure 2 in the Verifiable Computation - Pinocchio I am reading the Pinocchio paper (verifiable computation): http://research.microsoft.com/pubs/180286/pinocchio.pdf

The paper is rather hard for me. For the Figure 2, I guess $v_1(x)$ should be $(r_6-r_5)^{-1}*(x-r_5)$, and the rest can be found similarly.
Is this right? If yes, then how do we determine $r_5$ and $r_6$ when we generate the keys (evaluation and verification). Since we will have to calculate $v_k(s)$ etc.

Thanks for help me to understand it!

Yes, this is correct. The $r_i$ are arbitrary elements of the base field, their values are unimportant as long as they are all distinct.


Poor man's SSL - is this method as safe as SSL/TLS? I need to send data between two applications. I've got requirement that says that data should be transmitted using secure protocol such as SSL/TLS. Data is sent using TCP sockets and I don't have built in SSL/TLS support. However, I'm able to encrypt content using AES and I'm also able to exchange small amount of data using https. I'm thinking of exchanging the key for symmetric encryption using https and then encrypt the data with AES before sending it over the network.

I'm in full control of both parties that exchange information. The keys are exchanged using SSL and I know that both parties are able to use AES. I guess there is no way anyone could decrypt the data without knowing the key. I agree that someone would be able to interrupt the transmission but it will be only noise since he would have to know the key to encrypt data with it.

Is this solution safe? Can it be compared to using SSL/TLS in terms of security? Is there some obvious security hole that I'm missing? Do you see any flaws in terms of security of the message (by it I mean that someone who is unauthorized sends his data as part of transmission or reads data from my transmission)?

TLS not only provides privacy, but also authentication:

You can be sure you know who you speak to (at least the client knows if the server was using a certificate). (You provide this by the "HTTPS key exchange" you are doing at the start.)
You can be sure that you speak to the same entity at the other side throughout the whole live of your connection (even if you don't know who this is, e.g. as a server with non-authenticated client).
You can be sure that you get exactly what the other side sent, not something modified by someone between both sides.

AES (or any other block cipher) in a streaming mode (like CBC, CFB, OFB, CTR, ...) doesn't provide this guarantee. Because of this, there are various attacks at these modes which also endanger your privacy.

So make sure you are either

using a mode of operation which also includes authentication (look for "AEAD") or
using a normal privacy mode together with an external MAC (like HMAC) - and transfer the MAC key together with the encryption key during your key exchange).