Do very short values make a peppered hash less secure? Given many very short (or low-entropy) values – like 6-digit numbers – that are stored as hashes using a fixed secret pepper, e.g.:

value  | pepper               | hash = SHA265(value + pepper)
-------+----------------------+-----------------------------------------------------------------
100001 | e03c920babf6325ac56d | 75e3283fe3dbc8e1f86ac5ea7ac5325896a6036d5d2d73f355dca41b9dab4a42
100002 | e03c920babf6325ac56d | 20b50e24dc8a984905de5850e67167928f937f171a2e6cb9998c0a8131a11dda
100003 | e03c920babf6325ac56d | f555173d08ebd020b45a655cee159c2684ad98cd4901dc85ec047b565d3a4a05

... and assuming that an attacker knows that the values are 6-digit numbers and that the hashes were computed that way.

Could the attacker retrieve the values (or even the pepper) from the hashes? Do the short values make the hash more vulnerable / less secure?

The assumption seems to be that the adversary wants to confirm a guess of $\mathtt{value}$ given $\mathtt{hash}=\operatorname{SHA-256}(\mathtt{value}\mathbin\|\mathtt{pepper})$, for unknown random secret $\mathtt{pepper}$. This is an ad-hoc PRF of $\mathtt{value}$ with symmetric key $\mathtt{pepper}$.

No, the small size/entropy in $\mathtt{value}$ is not an issue. Neither is having a million of millions of $\mathtt{value}$ (or/and of leaked $\mathtt{hash}$ ). Without a successful and complete guess of $\mathtt{pepper}$, as far as we know, the adversary can't learn anything about $\mathtt{value}$ from its $\mathtt{hash}$ (beyond two $\mathtt{value}$ being identical with practical certainty when their $\mathtt{hash}$ is, something that additional random public salt would fix, see Maarten Bodewes's answer). Main theoretical weakness is the relatively small size of $\mathtt{pepper}$ (here 80-bit), which should be 128-bit or more by modern standards. Of course, there's the issue of keeping $\mathtt{pepper}$ secret, and other implementation issues (but the classic timing side channel of memcmp does not matter).

The best known generic attack is essentially brute force. For each guess of $\mathtt{value}$, it enumerates $\mathtt{pepper}$, computes $\operatorname{SHA-256}(\mathtt{value}\mathbin\|\mathtt{pepper})$, and compares to the given $\mathtt{hash}$ (or the full list of theses). If there are several guesses of $\mathtt{value}$ with different likelihood, it pays to try the guesses from most to least likely. If $\mathtt{value}$ was long (so that $\mathtt{value}\mathbin\|\mathtt{pepper}$ exceeds the 64-byte block size of the SHA-256 internals), it would pay to cache the intermediate values that do not vary with each $\mathtt{pepper}$.

Note: we'd have better academic security assurance if we used HMAC-SHA-256 rather than this ad-hoc PRF. See M. Bellare: New Proofs for NMAC and HMAC: Security without Collision-Resistance, in Journal or Cryptology, 2015, originally in proceedings of Crypto 2006.


how to calculate maximum data size of an RSA signature I am reading a content, and am not sure if I follow how they come up with the maximum data size which can be signed by an RSA key. The author states:

  "... if you are trying to sign a message using a 2048-bit RSA key whose public key size is 256 bytes, the maximum length is 256 bytes minus the encoding parameters, in this case 11 bytes. Therefore the maximum length of the data message that can be signed directly is 254 bytes ..."

I am not sure if I need to know a little more about RSA to know what the 11 bytes of encoding parameters are. My question(s) are:

How did he come up with the 254? 256 - 11 = 245
How did he get the maximum of 256 bytes?

See step 3, 4 & 5 of 9.2 EMSA-PKCS1-v1_5 that defines the PKCS#1 v1.5 padding mechanism for signature generation:

  If emLen < tLen + 11, output "intended encoded message length too
    short" and stop.
  Generate an octet string PS consisting of emLen - tLen - 3 octets
    with hexadecimal value 0xff.  The length of PS will be at least 8
    octets.
  Concatenate PS, the DER encoding T, and other padding to form the
    encoded message EM as

EM = 0x00 || 0x01 || PS || 0x00 || T

EM will have the same length as the modulus.

This means that T, the data that is padded and then used as input for modular exponentiation is modulus size - 11 bytes (if the modulus size in bits is a multiple of 8). So the data that can be "directly" signed is 11 bytes shorter than the modulus.

This is however half the story. PKCS#1 v1.5 uses signatures in combination with a hash mechanism. This is in step 1..2:

  Apply the hash function to the message M to produce a hash value
    H:

H = Hash(M).

  If the hash function outputs "message too long," output "message
    too long" and stop.
  Encode the algorithm ID for the hash function and the hash value
    into an ASN.1 value of type DigestInfo (see Appendix A.2.4) with
    the Distinguished Encoding Rules (DER), where the type DigestInfo
    has the syntax

  DigestInfo ::= SEQUENCE {
        digestAlgorithm AlgorithmIdentifier,
        digest OCTET STRING
    }

  The first field identifies the hash function and the second
    contains the hash value.  Let T be the DER encoding of the
    DigestInfo value (see the notes below) and let tLen be the length
    in octets of T.

So if you use the PKCS#1 v1.5 standard then T will always fit into the modulus as it just contains an (identified) hash value. The message size is than limited to the input size of the hash function, which is virtually unlimited.


Is there any Corelation between the SHA256 and SHA512 hash of the same data? Is there any Corelation between the SHA256 and SHA512 hash of the same data ?

No.

Knowing $h = \operatorname{SHA-256}(m)$ without $m$ doesn't help you to find $h' = \operatorname{SHA-512}(m)$, or vice versa, except insofar as you can use $h$ to test a guess $m^*$ for what $m$ might be, by checking $$h \stackrel?= \operatorname{SHA-256}(m^*).$$

The same goes for all of the SHA-2 functions {SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256}.  It also goes for the fixed-length SHA-3 functions {SHA3-224, SHA3-256, SHA3-384, SHA3-512}.

Note: The extendable-output SHA-3 functions SHAKE128 and SHAKE256 have the property that SHAKE128-$n$ and SHAKE128-$m$ share a common prefix—in other words, SHAKE128 and SHAKE256 produce infinite-length outputs for any input and you just use a finite prefix of the length you requested.  However, they are otherwise independent of the SHA-2 and fixed-length SHA-3 functions, and of the related SHA-3 constructions KMAC, TupleHash, and ParallelHash.

You can make your own family of independent functions in the privacy of your own living room by picking a fixed-length prefix $p$ in some set like {foo, bar, baz, qux, zot} and using, say, $m \mapsto \operatorname{SHAKE128}(p \mathbin\| m)$ or $m \mapsto \operatorname{SHA-512/256}(p \mathbin\| m)$; for each distinct $p$, this can be modeled as an independent uniform random function as in a random oracle, as long as you always use a prefix.*†

* Note that if you use $H_p\colon m \mapsto \operatorname{SHA-256}(p \mathbin\| m)$, you have the property that knowledge of $H_p(m)$ lets you compute $H_p(\operatorname{pad}(m) \mathbin\| m')$ for any suffix $m'$, which is quite improbable for a uniform random function.  This is called a length extension attack.  The SHA-3 functions dispense with this property, as do SHA-512/224 and SHA-512/256.

† Actually the set of prefixes need not be fixed-length—it is sufficient that it be prefix-free, meaning that if $p \ne p'$ are in the set of possible prefixes, then neither one is a prefix of the other.  For instance, length-encoded tags like 3 foo, 4 quux, 11 hello world would work too, as long as the length is encoded uniquely.


DPA Attack on HMAC SHA-256 I have read the paper Differential Power Analysis of HMAC SHA-2
in the Hamming Weight Model and I want to understand the DPA Attack. In section 3.2.1 Path 1 (page 4) there is written:

  The  last  remaining parts H$^{(0)}$ and C$^{(0)}$ can be recovered by making substitutions in Alg. 1:  in Step 7 of round 1, where
  H$^{(0)}$ is the only unknown variable, and similarly in Step 8 of round 1 where C$^{(0)}$ is the only unknown variable.

The substitution for $H^{(0)}$ is clear to me:

$T_1^{(1)} = \delta^{(0)} \boxplus W_1$ (1)
$T_1^{(1)} = H^{(0)} \boxplus \sum_1(E^{(0)}) \boxplus Ch(E^{(0)},F^{(0)},G^{(0)}) \boxplus K_1 \boxplus W_1$ (2)
(1) = (2):
$\delta^{(0)} \boxplus W_1 = H^{(0)} \boxplus \sum_1(E_0) \boxplus Ch(E^{(0)},F^{(0)},G^{(0)}) \boxplus K_1 \boxplus W_1$
$\delta^{(0)} = H^{(0)} \boxplus \sum_1(E^{(0)}) \boxplus Ch(E^{(0)},F^{(0)},G^{(0)}) \boxplus K_1$
$H^{(0)} = \delta^{(0)} \boxminus \sum_1(E^{(0)}) \boxminus Ch(E^{(0)},F^{(0)},G^{(0)}) \boxminus K_1$

But for $C^{(0)}$ I don't know how to start and my other problem is that I don't know how to substitute in the function Maj?

I will keep the same notations as in the paper mentioned above.

First, your substitution for $H^{(0)}$ is correct but you could stop to
\begin{align*}
T_1^{(1)} = H^{(0)}\boxplus \Sigma_1(E^{(0)}) \boxplus Ch(E^{(0)}, F^{(0)}, G^{(0)}) \boxplus K_1 \boxplus W_1
\end{align*}
since all values except $H^{(0)}$ are known from previous DPAs.

Regarding $C^{(0)}$, it is a little less straightforward. We have
\begin{align*}
T_2^{(1)} &= \Sigma_0(A^{(0)}) \boxplus Maj(A^{(0)}, B^{(0)}, C^{(0)})\\
&= \Sigma_0(A^{(0)}) \boxplus \big[(A^{(0)} \wedge B^{(0)}) \oplus (A^{(0)} \wedge C^{(0)}) \oplus(B^{(0)} \wedge C^{(0)})\big]
\end{align*}
which results in
\begin{align*}
\big[T_2^{(1)} \boxminus \Sigma_0(A^{(0)})\big] \oplus (A^{(0)} \wedge B^{(0)})&=  (A^{(0)} \wedge C^{(0)}) \oplus(B^{(0)} \wedge C^{(0)}) \,.
\end{align*}
Unfortunately, as bitwise AND operator is not invertible, we don't get $C^{(0)}$ directly. Still, $C^{(0)}$ is the only unknown variable making a bruteforce attack on this 32-bit variable easy in practice.


Regular and Efficient doubling in $GF(2^n)$ A naive approach to compute a multiplication $a \cdot b$ in a Galois field of the form $GF(2^n)$ is the russian peasant algorithm. However, it does not run in constant time and therefore is not safe against timing attack.

Does there exist optimization techniques to implement $2 \cdot a$ for $a \in GF(2^n)$  in a regular way ?

If we consider $GF(2^4)$ defined by the polynomial $X^4 + X + 1$ (represented by 0x13 in hexadecimal), the most efficient solution I found is to compute $2 \cdot a$ as described below (in C code)

 (a<<1) ^ (0x20 - ((a & 0x8) >> 3)) & 0x13

Can we do better in terms of efficiency without precomputations?


Is it right that the Bomba can halt, but give you a different settings other than the one Germans really used for encryption using an Enigma? Considering different groundsettings for these messages:

AWE RDE

AFR AFG

HIU HKQ (where similar letters were known as (1,4) ,(2,5) females etc.

I think the cipher clerk rotated the rotors based on the groundsettings with an offset of the 3 for the 2nd enigma in a pair. While that might produce the same letter in each enigma in a pair whether Bomba gives an accurate result of rotor order and ring settings. In other words can bomba still halt but give you different settings other than the one Germans used.

Not sure I follow your question and example.
For a start, the Bombe did not look for the correct key settings, it excluded impossible/wrong key settings. Since it exclude wrong setting then when it stops it might be a good stop or a false stop. They did calculate the number of stops they expected in a complete run (don't remember exact but <10) and later that calculation prove to be correct.

The groundsettings you show seems to be related to the repeated key that was used in the beginning. For that they used Zygalski/Jeffrey sheets to find wheels and key settings, that has nothing to do with the Bombe.


Naor Pinkas OT - senders security; reduction to DDH This question concerns the security of the sender in the Naor Pinkas OT. The protocol can be found here.

We can reduce the security to the DDH assumption. How exactly is this done? Can someone construct an adversary that shows this reduction?

To simplify the question. Working with the simulation based definitions the real and simulated views leave us with the job of showing $(g^a, g^b, g^c, g^{a\cdot b})$ and $(g^a, g^b, g^{a\cdot b}, g^c)$ are indistinguishable.

Let us assume that $D$ can distinguish these two distributions (can distinguish with probability that is non negligible).

That is,
$$|\mathsf{Pr}[(D (g^a, g^b, g^c, g^{a\cdot b}) = 1] - \mathsf{Pr}[(D (g^a, g^b, g^{a\cdot b}, g^c)) = 1]|$$ is non negligible.

What adversary can be constructed that breaks the DDH assumption? That is we must construct $A(D)$ (it takes in $D$, as an input) such that
$$|\mathsf{Pr}[(A(D) (g^a, g^b, g^{a\cdot b}) = 1] - \mathsf{Pr}[(A(D) (g^a, g^b, g^c) = 1]|$$ is non negligible.

Thanks

Hint

Due to DDH we have that $(g^a, g^b, g^{a\cdot b}, g^c)$ and $(g^a, g^b, g^{c'}, g^c)$ are indistinguishable (where $c'$ is uniformly random and independent of $c$).
By the same reason, $(g^a, g^b, g^c, g^{a\cdot b})$ and $(g^a, g^b, g^{c}, g^{c'})$ are indistinguishable.

Can you see how to put things together?


Prove that you have $K$ bytes of memory Alice has bought a brand new hard disk, $K$ (with $K \sim 10^{12}$) bytes in size. She is very happy about her purchase, and tells Bob about it. Bob claims he also bought a $K$ bytes hard disk. Alice doesn't really trust Bob on this, so she asks him to prove his claim:

Alice sends Bob an $O(\ln(K))$ sized problem she has generated.
The problem can only be solved if one has $K$ bytes of memory.
Bob sends back an $O(\ln(K))$ sized solution.
Alice verifies the solution.

In particular, there can be two distinct cases:

Alice verifies the solution without having to carry out the same operations as Bob (in this case, she doesn't even need to have a $K$-bytes hard disk herself)
Alice computes the same solution as Bob on her side, using her own hard disk.

What problem could we use? It is perfectly okay if the nature of the communication between Alice and Bob changes a bit (for example requiring more than a two-way communication is okay), but the communication should never grow in size to something like $\Theta(K)$.

Solutions I tried

(Feel free to skip this section if you don't need inspiration!)

Using $\Theta(K)$ communication, Alice could obviously generate $K$ random bytes, send them to Bob and ask him to compute the hash of some subset of them that she will send only after sending the whole payload. (We need the hash of a subset of the data otherwise Bob can compute the hash on the go as he receives the bytes). But this solution is obviously discarded because it requires too much communication.
Alice sends a seed, Bob generates random numbers with the seed to fill the $K$ bytes, then he sorts the bytes and computes the hash. However, an $O(K^2)$ (in time) solution exists that will allow Bob to compute the hash by extracting the first, second, third... item by repeatedly re-generating the random numbers. So this doesn't actually prove that Bob has a $K$-bytes hard disk.
Alice sends a seed, Bob generates random numbers with the seed to fill the $K$ bytes, then a shuffling procedure is put in place to randomly take small blocks and hash them together, or XOR them, or anything in that fashion, so that after a few iterations each byte depends on every other and it is impossible to compute a partial solution on the go. Alice then asks the hash of a subset of the total result (or even the total hash). This could work, but it has the issue of producing an huge amount of random I/O on the disk, which could actually damage a real-life, non-SSD hard disk.
Bob generates a sequence of proofs of work (as in bitcoin mining). Bob then generates a Merkle tree on the sequence and sends the root to Alice. Alice asks for $N$ random proofs of work, and Bob sends back the whole navigation on the Merkle tree from the root to the leaf, Alice verifies everything. However, Bob could just save the first $L$ layers of the Merkle tree, and re-compute on the go all the leafs under the last node memorized. If he stores $10^9$ values, for example, he will just have to recompute $10^3$ leafs, which is feasible on the go.

There has been a huge amount of work on related questions in the past years. As Thomas Prest mention, this problem was considered for memory-hard function, which provably (in some idealized models) require some amount of space to be evaluated.

However, MHF alone are only the weakest primitive of this kind; many primitives have been designed that enhance MHFs with other desirable properties, such as efficient verification. What you are looking for is probably best captured by proofs of transient space, where you provably use a given amount of space during a computation, so that the proof can be verified in a time and space considerably smaller (polylogarithmic) than the space used by the prover.

I recommend going through the introduction of this article, which does address your problem and furthermore points to many interesting references if you want to dig the subject a bit. Most constructions use graphs with specific combinatorials properties (such as expander graphs and depth-robust graphs), which imply lower bounds on the hardness of playing a certain game (the pebbling game) on the graph. These lower bounds then translate into bounds on the memory usage in the random oracle model.


In the SHA hash algorithm, why is the message always padded? In the SHA hash algorithm the message is always padded, even if initially the correct length without padding; the padding is of the form "1" followed by the necessary number of 0s.

Why is it necessary that the message always be padded?

Well, the entire point of a cryptographical hash function is that no one can practically devise two messages that hash to the same value.

Now, the SHA family of hashes use the Merkle–Damgård construction; that is, they have an iterated hash function, and each invocation of the hash function takes as input a fixed block size (either 512 or 1024 bits in the case of the SHA family).

However, we're interested in hashing messages that don't happen to be an exact multiple of 512 or 1024 bits in length.  So, what we do is define a padding function that takes a message, and converts it into a form that's a multiple of the block size in length; we then run the hash compression function on this padded message.

Now, there are a couple of requirements on this padding function; one of the most critical that if we had two different messages, then they must still be different after padding; if not, then the hash compression functions will work identically, and so those two messages would hash to the same value.

That really is the answer to your question (a); if our padding function didn't modify (pad) messages that happened to be the correct length, then that would immediately lead to a collision.  For example, if we take any message $M$ that's not a multiple of the block size, we could compute $Pad(M)$.  Now, $Pad(M)$ will be a multiple of the block size, and so we'd know that $Hash(M) = Hash(Pad(M))$.

As for the answer to your question (b), well, if our padding function was simply adding zero bits until the padded message was of the correct length, well, that would lead to a collision of the form $Hash(M) = Hash(M || 0)$ (assuming postpending the 0 doesn't cause us to cross a block boundary).  On the other hand, the SHA padding function isn't just appending 0 and 1 bits; it also involves adding a bitlength of the entire message at the very end.  If the question is "why do they add a 100...000 pattern and add a message length', well, I rather suspect that's a belt-and-suspenders approach.  Either would be sufficient in itself (as either would prevent two messages from padding into a common value); both are cheap, and so the designers decided to do both.


Why is Rijndael key length restricted? Why is Rijndael restricted to key length in $\lbrace 128, 160, 192, 224, 256\rbrace$ bits (and not larger)? The algorithm looks to me like it would support an arbitrary-sized key (multiple of $32$).

The rounds operate without the key. Between rounds, the state is XORed with as many key bytes as are needed according to the block size. The key generation process is dependent on the number of rounds, which is dependent on key size, so growing a key triggers a process that uses the key data.

I heard Dr. Eric Cole mention something about this like 10 years ago when first I took one of his classes which covered a "101" into to crypto. We were talking about how AES is replacing DES (triple DES, whatever) and he told us about basically said that Rijndael has variable key lengths. He didn't say specifically, but I took him to mean arbitrary. If I recall corrected he said that because of this feature we'd be using it for a long long time to come. He also talked about all the fun he had attending the NIST AES contests, but now I'm off topic. Does anyone actually know?

The key schedule uses constants that differ between the key sizes. For arbitrary sized keys you would have to define an algorithm for deriving them. Each key size also uses a different number of rounds, for which you would have to do the same.

Also, what's the point? 256-bit keys are enough for all eternity. Using a longer keylength variant would likely just introduce a false sense of security.

If AES gets broken, it is IMO unlikely that such an attack would break a 256-bit key variant without also breaking an e.g. 512-bit variant with an equal number of rounds. The main exception would be if there was something wrong with the key schedule for one, like the weaknesses in the 256-bit variant, but in that case a less studied longer key variant would be even more of a risk.


Using ECDH for authentication I've found this method for using ECDH for asymmetric encryption.

Is there a similar method for using ECDH (rather than the more usual ECDSA, let's say my hardware can do ECDH but not ECDSA) to accomplish authentication?

You van use DH over elliptic curve or over Zp for authentication. If the authenticating party has a fixed DH key and published in advance the public part $g^a$ (or multiplication for ECDH).
When we want to authenticate we can create a mutual DH key $g^{ab}$ and then the authenticator can prove knowledge of this in many ways.
encrypt a challenge with this as key would be a simple way. Could equally decrypt a challenge, or hash a challenge with the key prepended.
Or something fancier like socialist millionaire which gives zero knowledge proof both sides have the same key.
And if both sides have the other side public dh key it supplies authentication of both sides.


Proof that pseudo-random generated key is semantically secure Let $G: \{0,1\}^s \rightarrow \{0,1\}^r$ where $r > s \;$  be a secure pseudo-random generator.

Let $\xi = (E,D)$ a semantically secure cipher whose key space is $\{0,1\}^r$

Let $\xi' = (E',D')$ a cipher whose key space is $\{0,1\}^s$ and such that:

$E'(k, m) = E(G(k), m)$
$D'(k,\;c)\; = D(G(k),\;c)$

How can I prove that $\xi'$ is semantically secure?

I guess that I should use the fact that a semantically secure cipher uses a random key, so using a pseudo-random key would add just a negligible advantage for the adversary to guess the key, so the sum of the semantically secure negligible advantage and the pseudo-random key negligible advantage would also be negligible, but I'm not sure how to build a proof.

In order to answer that, let's remember the definition of a secure PRG:

Let $G: k \to \{0, 1\}^n$ be a PRG. $G$ is said to be a secure PRG if and only if $G(k)$ is indistinguishable from $r$, where $r$ is a truly random string from $\{0, 1\}^n$

By indistinguishable we mean that no statistical test can differentiate $G(k)$, where $k$ is chosen at random from the set $K$, from a truly random string $r$, $r \in \{0, 1\}^n$.

That said is easy to see that, if $G$ is a secure PRG no adversary can distinguish, with non-negligible advantage, the ciphertexts generated from $E$ and $E'$. So your idea of proof is correct.

Most of the times this should be enough to prove it... But bellow I present a proof using an Attack Game and an Statistical Test

To help with the actual proof one can define the problem as:

  If G is a secure PRG, then $\xi'$ is semantically secure.

Then, we can use the contrapositive to prove it:

  If $\xi'$ is not semantically secure, then G is not a secure PRG.

To prove that, given an adversary $A$ that can break the semantic security from $\xi'$, we need to be able to build an adversary $B$ using $A$ that can distinguish $G(k)$ from $r$, again, where $r$ is a truly random string from $\{0, 1\}^n$.

So, the way we would do this is by using $B$ at the same time as the challenger of $A$ and as the statistical test to distinguish $G(k)$ from $r$.

$A$ would provide $B$ two messages $m_0$ and $m_1$;
Then $B$ would get from his challenger an string $s$ that can either be $G(k)$ or $r$;
Then $B$ encrypts $m_0$ using $E$ and the string $s$ as key (essentially, he is using $E'$ when $s = G(k)$ and $E$ when $s = r$).
Finally, $B$ sends the encryption $c$ to $A$ that answers $1$ if he thinks $c$ comes from the encryption of $m_1$, and $0$ otherwise.
$B$ outputs to his challenger whatever is the answer of $A$

Note that if $B$ answer his challenger with $0$, then $s = G(k)$; If he answers $1$, then $s = r$.

Given that $A$ can break the semantic security of $\xi'$ he would output $0$ (guess correctly) whenever $s = G(k)$, and as we can see, $B$ would also be right by answering that $s$ is in fact $G(k)$.

This would break the definition of a secure PRG, thus proving that $G$ is not secure. $\square$

Just for a matter of completude:

What you are asking for is also the idea of turning the OTP practical, where the idea is to use a pseudo-random key instead of a truly random key, so we can use small seeds to generate much larger keys.

I should also note that a cipher who uses a PRG to generate its key can't be called a perfectly secure cipher. That's why the definition of security is stretched so the security property depends on the specific generator. That's where the semantic security definition comes on.


Only allow specific types of data to be transmitted via an end-to-end encryption service I have a service that allows multiple parties to share domain-specific textual data. This data is also end-to-end encrypted. How can I be sure the sharing parties don't send non-domain-specific data, considering I receive it encrypted?

For example, assuming I require a specific algorithm to be used for the encryption, is there either:

a zero-knowledge proof that would verify that the original data matches a given regular expression

or

a homomorphic identity operation that, applied to valid domain-specific encrypted data, would result in no change to the data, but applied to anything else, would result in undecryptable garbage

One (very generalized) solution would be to use a general ZKP solution like libsnark.

In libsnark (and other tools like it), you would write a function that accepts both public and private inputs, and outputs a proof that the inputs satisfy the logic of the function. This proof can then be verified, at a much lower cost than it took to generate it.

E.g., you might have:

public_inputs = { encrypted_string, regex, length }
private_inputs = { plaintext_string }

function(public_inputs, private_inputs)
  s = encrypt(plaintext_string)
  check1 = (encrypted_string == s)
  check2 = (length(plaintext_string) == length)
  check3 = string_fits_regex(plaintext_string, regex
  return (check1 and check2 and check3)

Libsnark gives you one algorithm for "prove" and one for "verify".

The sender would then call "prove", which would generate the proof, and then send the proof along with the encrypted string.

Then you (or the receiver), could call "verify" with the same public inputs and it would say "yes" or "no".

There's a lot more details, check the references at the end of that repo's README page. Here's a good illustration from a (somewhat related) blog post.

I bet there are other, even better (less computationally intensive) solutions as well.


Characteristics of an isogeny between super-singular elliptic curves I believe I've read this before, but I can't find it despite hours of searching on Google.
I've know the common definition of isogeny in elliptic curves, as $\phi:E_1 \rightarrow E_2$ a nonconstant morphism of curves satisfying $\phi(0)= 0$, however somewhere else I read a really lovely intuitive explanation that basically stated that if a curve $E_1$ is isogenic with curve $E_2$, then, not only will points, such as $p_1$, $q_1$ map to $p_2$, $q_2$ but moreover, the mapping of the point $E_1(p_1+q_1)$ to $E_2$, will result in the same point on $E_2$ as when the points $E_1(p_1)$ & $E_1(q_1)$ are first mapped to $E_2$ and then added on the $E_2$ curve.
I hope this makes sense, am I confusing this or does anyone have a resource that shows this detail?

Given two elliptic curves $E_1$ and $E_2$, an isogeny from $E_1$ to $E_2$ is an algebraic map $\phi$ (it is basically defined from rational functions) that sends the neutral element from $E_1$ to the neutral element of $E_2$.
As stated in Theorem 4.8 in page 71 of The Arithmetic of Elliptic Curves by J.H. Silverman:

Let $$ \phi : E_1 \longrightarrow E_2 $$ be an isogeny. Then $$ \phi(P+Q) = \phi(P) + \phi(Q)\quad \text{for all } P, Q \in E_1.$$

In other words, the isogeny is a group homomorphism (the group law of the curve $E_1$ is preserved after the transfer to the curve $E_2$).
The proof involves the divisor class groups of the curves, using the fact that the isogeny induces a group homomorphism between them.


What aspect of elliptic curve encryption paradigms makes them especially susceptible to quantum based attack algorithms? This was a statement made during a talk at today's DFN-CERT conference but unfortunately it wasn't explained further. Can anyone shed light on why elliptic curves are susceptible to quantum based attacks ?

The elliptic curve discrete logarithm—like integer factorization and the classic finite field discrete logarithm—is an instance of the abelian hidden subgroup problem.

Any abelian (commutative) instance of the hidden subgroup problem can be efficiently solved in quantum computers with (variants of) the Shor algorithm; therefore all of the above problems would be rendered weak if large enough quantum computers were actually built. Here is a concrete polynomial-time quantum attack  for the elliptic curve discrete logarithm. See also this question.


Euler's Totient function for semiprime numbers I have noticed, during the period I spent studying RSA, that Euler's Totient function can be calculated in another way than $ϕ(N) =(p-1).(q-1)$

Let me explain myself by pointing to a brief example:

$p = 131$

$q = 11953$

$N= p*q = 1565843$

The totient defines the quantity of positive integers less or equal than $N$ coprime with $N$. So we calculate it:

$ϕ(N) = (p-1)(q-1) = 1553760$

But I have realized that this way can also be obtained:

How many multiples of p are under N? q multiples of p

How many multiples of q are under N? p multiples of q

These previous statements show the quantity of integers NOT coprime with $N$ that are less or equal to $N$. It's just the opposite of the Euler's Totient.

So the equation is the following:

$ϕ(N) = N - p - q + 1$

In the example:

$ϕ(N) = 1565843 - 131 - 11953 + 1$

$ϕ(N) = 1553760$

I suppose that this method is well documented over there. I just want to know if this is a good praxis for using in an implementation (for example).

Thanks for your time!

You can get the 2nd equation from the first with some simple algebra.

$$(p-1)(q-1)$$
$$pq-p-q+1$$
$$n-p-q+1$$

I'm not really sure what you are asking though. Are you asking if computing the second is faster than the first?

I suppose you could argue that you have to do the $pq$ multiplication anyways, so why not reuse it. If that is your argument, then doing the calculation with the 2nd equation you gave for $\varphi$, then you get the multiplication for free and only have to do 2 subtractions and an addition. Using the first equation, you have to do two subtractions (although only a minus 1) and one multiplication. Multiplication is much more expensive, so the 2nd equation would be more efficient.


Can I use PGP to sign a message without providing cryptographic non-repudation? The difference between a digital signature and a MAC is non-repudiation. A message with a digital signature proves that only the sender could have signed the message, whereas a message with a MAC proves that either the sender or the recipient could have signed the message.

Can an OpenPGP implementation, such as GPG, be used to sign a message without providing non-repudiation?

Please note that I am referring to non-repudiation in the cryptographic sense, not in the legal sense.

Yes, there's an indirect way to perform what's asked with PGP and variants.

Draw a an asymmetric public/private key (of a type that can sign), protected by a passphrase. Publish the passphrase-protected private key. Discard the public key (it's in the private key anyway). Use the passphrase as you would use a symmetric key: share it by trusted means between sender and receiver (perhaps together with the passphrase-protected private key). Generate, transmit and verify a detached signature (sig file) of a file to integrity-protect as you would do for a MAC of the file.


Applying Chinese RemainderTheorem and Paillier Homomorphic encryption I'm trying to optimize the decryption process for Paillier Homomorphic Encryption (PHE) using the Chinese Remainder Theorem (CRT). However, I want to check if there's a different way of applying CRT to PHE apart from the traditional approach and still get the same result or a faster result since there's a simpler variant for the PHE as stated here in Wikipedia.

Recall that,

=(^   ^2 ).   ,   = ^.^   ^2,   =()=(−1)(−1)

=[((^ ^2 ))]^(−1) ,   =()^(−1)   = [(−1)(−1)]^(−1)

                    =(^   ^2 ).

                =(^((−1)(−1))   ^2 ). [[(−1)(−1)]^(−1)   ]

                    =  [(^((−1))   ^2 ).(−1)^(−1)  ]

                    =  [(^((−1))   ^2 ).(−1)^(−1)  ]

Let = (−1)^(−1)         and       = (−1)^(−1)

                    =  [(^((−1))   ^2 )]

                    =  [(^((−1))   ^2 )]

 = CRT(, )

 =  [(^(−1)   ^2 )   ]  +  [(^(−1)   ^2 )   ]

  = (^   ^2 ).

Implementing the above steps in python gave me an inconsistent decryption result.

Is this proof correct, and if not, can anyone please explain as to why it's not correct and how to make it correct?

A working method for CRT-aided decryption in Pailler goes:

Evaluate $x=c^\lambda\bmod n^2$ by the Chinese Remainder theorem, that is

$x_p\gets c^\lambda\bmod p^2$
$x_q\gets c^\lambda\bmod q^2$
$x\gets\left(q^{-2}(x_p-x_q)\bmod p^2\right)q^2+x_q$

Then evaluate $m\displaystyle\gets\left\lfloor\frac{x-1}n\right\rfloor\,\mu\bmod n$.

The savings are by a factor of at most 2, rather than at most 4 for RSA, because the exponent $\lambda$ remains the same size, when its $d_p$ and $d_q$ have their size halved in RSA.

The question's method is broken where it goes from the following line to the next:

$\begin{align}
m&=L\left(c^{(p-1)(q-1)}\bmod n^2\right)\cdot\left((p-1)(q-1)^{−1}\bmod n\right)\bmod n\\
m_p&=L_p\Big(\left(c^{p-1}\bmod p^2\right)\cdot\big((p-1)^{−1}\bmod p\big)\Big)\bmod p
\end{align}$

Problems are:

Function $L_p$ is not stated. I work under the assumption that $L_p$ is to $p$ what $L$ is to $n$, that is $L_p(x)\displaystyle=\left\lfloor\frac{x-1}p\right\rfloor$. Also I assume $m_p=m\bmod p$.
The term $(q-1)^{-1}$ of the first equation mysteriously vanishes from the second.
Something on the tune of $L(x)\equiv L_p(x)\bmod p$ seems to be assumed  without justification.
The term $(p-1)^{-1}\bmod p$ (which BTW is always $p-1$) has mysteriously entered the input of $L_p$ when $(p-1)^{-1}$ was at the output of $L$.

Numerical experiments disprove the second equation (under the assumptions made in 1). If there is a way to repair it, I want to know!


Arbitrary length to multiple of block size I would like to apply CTR mode on a arbitrary length which isn't multiple of block size. Is this possible without applying padding.

In case we apply padding - how does the decryption algorithm know this padding!?

In CTR mode, Enc is done as

CT = Enc(k,PT) = Enc(k,ctr) xor PT

The decryption is similar to encryption except you XOR Cipertext(CT) instead of Plaintext(PT).

PT = Dec(k,CT) = Enc(k,ctr) xor CT

So there is no need for plaintext to be multiple of block length and no need of padding because the PT or CT never become the input of the block cipher. Its the counter which is encrypted to generate a random stream and then Xored with plaintext or ciphertext. You can use the required length of generated bit-stream and discard the remaining.

More Details and picture Credit of CTR MODE


When are hash functions considered insecure? I'd like to know when a hash function is considered insecure. Clearly, if it is easy to invert then it's not secure at all. Apart from that, let's say I've found a bunch of inputs $x_1, x_2, .. ,x_n$ s.t their hashes are equal. Would this mean my hash function is insecure even though $n$ is much smaller than my input space?

In general, when is a hash function considered insecure?

The security level of a cryptographic hash function has been defined using the following properties:

Pre-image resistance

Given a hash value $h$ it should be difficult to find any message $m$ such that $h = hash(m)$. This concept is related to that of one-way function. Functions that lack this property are vulnerable to preimage attacks.

Second pre-image resistance

Given an input $m_1$ it should be difficult to find different input $m_2$ such that $hash(m_1) = hash(m_2)$. Functions that lack this property are vulnerable to second-preimage attacks.

Collision resistance

It should be difficult to find two different messages $m_1$ and $m_2$ such that $hash(m_1) = hash(m_2)$. Such a pair is called a cryptographic hash collision. This property is sometimes referred to as strong collision resistance. It requires a hash value at least twice as long as that required for preimage-resistance; otherwise collisions may be found by a birthday attack.
More details are in here.


Security proof of schnorr identification scheme I have studied the Schnorr identification scheme, and I came across the security proof.
My question is regarding the following:
$$\begin{align}
\text{Pr}\left[\text{DLog}_{\mathcal{A}',\mathcal{G}}\left(n\right)=1\right]
&=
\text{Pr}_{\omega,r_1,r_2}\left[
  V\left(\omega,r_1\right)\wedge
  V\left(\omega,r_2\right)\wedge
  r_1\neq r_2
\right]
\\ &\geq
\text{Pr}_{\omega,r_1,r_2}\left[
  V\left(\omega,r_1\right)\wedge
  V\left(\omega,r_2\right)
\right]-
\text{Pr}_{\omega,r_1,r_2}\left[r_1=r_2\right]
\\ &=
\sum\nolimits_{\omega}{
  \text{Pr}\left[\omega\right]\cdot
  \left(\delta_\omega\right)^2}-
  1/q
\\
&\geq
\left(\sum\nolimits_{\omega}{
  \text{Pr}\left[\omega\right]\cdot
  \delta_\omega}\right
)^2
-1/q
\\
&=
\delta\left(n\right)^2-1/q
\end{align}$$
With $\delta_\omega \stackrel{def}{=} \text{Pr}_r\left[V\left(\omega,r\right)=1\right]$ being the probability that the adversary will succeed in the identification experiment given that we use $\omega$ (random choices) and $r$ (the challenge).
When we move from the 2nd row to the 3rd, we assume that the event that the adversary correctly responds to the challenge $r_1$ is independent of the event that the adversary correctly responds to the challenge $r_2$.
But, we have no knowledge on how $\mathcal{A}$ is acting - so how can we assume these events are independent?

I believe this is the 'Rewinding Lemma' part of Schoor identification security proof, and very well explained in the Boneh and Shoup book "A Graduate Course in Applied Cryptography", pgs 727-728.
An important aspect here is that we have to consider another adversary B, who emulates (grab a digital compiled version of A) and plays/interacts with A. (we can think of B as whoever wants to break the scheme, and presupposes the existence of A):

first, B plays the role of the verifier, and expect A (playing the prover role) send w;
B send r1, and wait for the A's answer;
B rewinds A, so that A’s internal state is exactly the same as it was at the end of step 1;
B sends a random and independent r2; waits for the A answer.

So B may be ignorant about how A works, but s/he is who sets A independent challenges/answers, and takes advantage of it.


Signing with RSA-SHA256 algorithm using EC keys Is it practical to sign a data using RSA-SHA256 algorithm with EC keys?
I used a small NodeJS script and crypto module (uses openSSL internally) to test this and I could successfully sign the data and verify the signature.
Pseudo-code:

Sign( data, EC-Key-p256, 'RSA-SHA256')
Verify( data, signature,public-key, 'RSA-SHA256')

Have used openSSL to create EC keys (p256v1) and used it for my testing.
Could you please help me understand whether this is a standard practice?

tl;dr  - RSA keys and ECDSA keys are not compatible and cannot be used in one anothers signature algorithms

In RSA you have the following:

A public key $(e, N)$ where $e$ and $N$ are integers.
A private key $d$ where $d$ is an integer and $ed \equiv 1 \bmod \phi(N)$, $\phi$ being Euler's totient function.

In ECDSA you have:

A public key $Q$ which is a point on an elliptic curve e.g. $Q = (q_x, q_y)$.
A private key $d$ which is an integer such that $dG = Q$, where $G$ is the base point of the elliptic curve.

Given those facts the question you pose doesn't make sense. Indeed an RSA private key and an ECDSA private key seem similar in that they are both integers, but in RSA $d$ needs to also have a corresponding $N$, which is usually left out since it is a public value (if you want to be pedantic the private key is really $(d, N)$ in RSA).

So say I generate an ECDSA private key $d$ and want to sign a message $m$ with it via RSA-SHA256. RSA-SHA256 would look something like $signature = \mathrm{sha256}(m)^d \bmod{N}$ (actually you would want to apply padding after the hash and before the exponentiation but that's not really important here).

But if only $d$ is generated, as one would do for an ECDSA private key, how does one perform the $\bmod{N}$ operation? You can't because $d$ by itself is an incomplete RSA private key, you also need the $N$ corresponding to the public key.

Let's say you do generate some $N$ after the fact so that you can perform signing. Verification would run into the same problem of keys not being compatible. RSA-256 signature verification for message $m$ and signature $s$ looks something like $\mathrm{sha256}(m) =^? s^e \bmod N$ where $(e, N)$ is the RSA public key. But if one does not have $(e, N)$ and is provided only a point $Q = (q_x, q_y)$ that lies on an elliptic curve, how does one then verify the signature? One of course can't.

SEJPM is probably correct in his comments that the library you're using sees that the signature algorithm doesn't match the key and chooses the correct signature algorithm for signing. If the library isn't raising a warning and quietly acting as though all parameters are valid I would consider switching libraries.


Does having multiple hash iterations of the same message weaken your original message security? Take a hash function H() to be something like SHA-256 and message m. If you are given H(m) and H(H(m)), can you use this info to help derive m?

Also interested in knowing how you analyze this problem to come up with your answer.

A hash function is a hash function: a deterministic, public function with no secret parameter. Everybody can compute SHA-256, and they all get the same results when applied on the same inputs.

Therefore, if you give H(m) to the attacker (who tries to recover m: a preimage attack), giving him H(H(m)) too does not grant him any extra actual help -- because he already has it: given H(m), he can compute H(H(m)) himself (and H(H(H(m))) and so on).

In the question above, the attacker is shown x = H(m) (for an unknown message m) and challenged to find a message m' such that H(m') = x. Another, distinct but interesting setup, is the following: suppose that the attacker is shown y = H(H(m)) for some unknown message m, and is challenged to find m'' such that H(H(m'')) = y. This raises two questions:

Is this new challenge (finding a preimage for double-hash, not for the simple hash) harder, easier, or equivalent to the original preimage attack ?
Does showing H(m) in addition to H(H(m)) (but still challenging the attacker with finding a preimage for the double-hash, not for the simple hash) help him ?

We suppose that the hash function is "perfect", i.e. acts as a random oracle. For a perfect hash function, the best attack for preimages is luck, i.e. trying different inputs until a match is obtained. If the hash outputs data in a set of size N, then luck works with an average cost of N invocations of the hash function. For a 256-bit perfect hash function, N = 2256.

Now for the double-hash: if H() acts as a random oracle, then so does H(H()), albeit with a slightly reduced output set. Indeed, the outer hash works over the 256-bit output of the inner hash; H, as a random oracle which offers 256-bit outputs, is expected to produce, for all possible 256-bit inputs, about (1-(1/e))N distinct outputs (to say things otherwise: if H produced all possible 256-bit outputs when applied over all possible 256-bit inputs, then H would be a permutation over the set of 256-bit values, which would be very surprising and is not expected from a random oracle). Therefore, the double-hash produces outputs in a set of size about 0.632*N, and that's also the cost of the generic preimage attack on the double-hash. BUT remember that this cost is expressed in the number of invocations of the attacked function. Invoking the double-hash means computing H twice. So we are talking about 1.264*N invocations of H. This yields our answer to my first question: finding a preimage for the double-hash is about 26.4% harder than finding a preimage for the simple hash.

So this also answers my second question: does knowing H(m) helps the attacker finding a preimage for the double-hash ? Indeed it does, because he can then search for a preimage for the simple hash, in cost N instead of 1.264*N, and any solution will also be a solution for the double-hash.

Generalized result

Let H(n) be the n-hash (n nested invocations of the hash function). Let Cn be the challenge of finding a preimage for H(n) (attacker is given x = H(n)(m) for an unknown m, and his goal is to find an input m' such that H(n)(m) = x). Then the following holds:

The cost of solving Cn rises when n increases: though the output space of H(n) reduces with bigger n values, the individual cost of each invocation of H(n) increases and more than cancels the gains obtained through the space reduction. (This result holds until n becomes close to the square root of N, at which point things become more complex to analyze.)
When the attacker tries to solve Cn, giving him additional values H(k)(m) for values k > n does not help him, because he could have trivially computed them himself (H(n+1)(m) = H(H(n)(m)), and so on). If obtaining these extra values was a good idea, then he would do it right away.
When the attacker tries to solve Cn, giving him an additional value H(k)(m) for a value k < n indeed helps him, because it allows him to solve Cn by solving the comparatively simpler Ck.

Of course, we are speaking only theory here; with hash functions offering an output of more than 100 bits, the involved costs are way too high to be envisioned. In practice, preimages on simple hash or double-hash are unfeasible -- unless the hash function is not "perfect" and we can exploit a structural weakness of that specific hash function, at which point anything goes.


XOR LFSR and all zero state I read this in a description of Linear Shift Feedback Registers

Note that the allzero state must be excluded. If an LFSR assumes this state, it will get “stuck” in it, i.e., it will never be able to leave it again".

I can understand why an all zero state means that if the LFSR comes to an all zero state, it gets stuck in the state. However, how does one prevent it from getting to an all zero state? Can an LFSR never get into an all zero state unless it's initialized to an all-zero state? If it cannot, is there any proof for this?

how does one prevent a LFSR from getting to an all zero state?

One method is to not initialize the LFSR to the all-zero state, and use a feedback polynomial with a constant term (the $1$ in the polynomial).
 [image credit]
Proof that it works for a LFSR in Fibonnaci form, as illustrated with polynomial $x^{16}+x^5+x^3+x^2+1$ in the above picture, by induction: if the current state of an $n$-bit LFSR is non-zero, and there is a constant term (the $1$ in the polynomial, equivalently a XOR tap on the rightmost bit), then the next state is non zero, by considering the two cases:

If any of the $n-1$ left bits is non-zero, then this bit is carried to the next state, which thus is non-zero.
Otherwise, the $n-1$ left bits are zero and the rightmost bit is one. This bit enters the XOR, and all other bits entering the XOR are zero, hence the next left bit is a one, hence the next state is non-zero.

For LFSRs in Galois form, we can invoke the equivalence with the Fibonnaci form, or make a direct proof, as follows. If the LFSR's feedback polynomial is $P(x)$ and it's state $S(x)$, the next state is defined to be $\big(x\cdot S(x)\big)\bmod P(x)$. Since the degree of $S(x)$ is at most one less than the degree of $P$, the next state can be all-zero only if one of the following holds

$x\cdot S(x)=0$, implying that $S(x)=0$
$x\cdot S(x)=P(x)$, which can't be if $P(x)$ has a constant term.

Note: The condition "feedback polynomial has a constant term" is so common in practice that it is sometime part of the definition of LFSRs. When it holds, it can be shown that Fibonnaci and Galois forms of LFSRs with the same polynomial (perhaps within reflection, depending on convention for Fibonnaci) are equivalent, in the sense that the sequence produced by one for a given initial state is the same as the sequence produced by the other for a (different) initial state. There is no other common form or kind of binary LFSRs.

Some hardware constructions want to recover from a fault (invalid setting, "upset" such as a power glitch or a cosmic ray) and have special circuitry to leave the all-zero state if it gets entered. That can be a NAND gate on all the state bits forcing a one to enter the LFSR. Or a counter clocked with the LFSR, reset when the LFSR output is a one, with the counter's high-order bit forcing a one to enter the LFSR.


Does AAD make GCM encryption more secure? Does additional authenticated data (AAD) make AES GCM encryption more secure? What if we drop AAD in AES-GCM 256? If we drop it, how will it make the encryption less secure?

In general the AAD itself is not required or won't change the security of the GCM mode of operation itself.

It may however directly influence the security of the protocol in which GCM is deployed. For instance, you may have specific configurable parameters outside the ciphertext itself.

These parameters may very well include:

version number of the protocol
message specific nonces
addresses of recipient(s)

If you don't include these in the AAD or ciphertext then those parameters won't be validated by verification of the authentication tag. This means that attackers can simply change them. For instance, an attacker may try and switch to a previous, less secure protocol number.

You don't need to include the GCM nonce (the IV) itself in the AAD by the way; the nonce is already included in the calculation of the authentication tag.

Obviously if you allow the parameters to directly influence the GCM mode of operation itself then validating the authentication tag may be too late; you're better off to verify or set them beforehand for maximum security.


Decrypting the password from SHA-512 hash value I am currently studying AES algorithm and writing a Code using Python.
I am trying to add 'Salt' into the user input password,

Here is what I am doing,

import hashlib
import os
password = "Sufiyan Ghori"
salt = os.urandom(32) # 32bytes * 8 = 256bits
# Adding the Password into the first 128bits of SALT
# So that the password could be encrypted
Encoded_Password = password.encode('utf-8') + salt[:16]
# Output will be, Password + Salt

I've added comments above for better understanding.

If the 32-byte salt is equal to

b'\x937{\xa0\x9bo\x9f\x8b1\xbf\xa9\xc9\x01\x86\xa1\xd9\xc7\x00+\x81\t\x0f\\\xdc\
x9a\xe5\x84r\xce$EJ'

then Password + Salt[:16] would be

b'Sufiyan Ghori\x937{\xa0\x9bo\x9f\x8b1\xbf\xa9\xc9\x01\x86\xa1\xd9'

If I then create its digest using sha512,

sha512 = hashlib.sha512( Encoded_Password ).digest()

the output will be

b"\xe8\x02\xcc\xa9\x1a\xd3\x1b\x80\x1f{\xd2\xa6E7\x9d\x87\xcf\x17\xb1\xb4\x07\xb
1\xfe\xf2\x9a\xa5\xcc\xe7\x92\xc0\x81\xed\xf8HPu\xe2'\xfc\x0b\xc1\xa6\xc8\xd0N5a
\xc1;\xf7\xbc\xe3\xafN\xcaN\xdfqhc&A#%"

How am I supposed to recover the original password — which is Sufiyan Ghori — from this fixed-length hash value now?

You cannot recover the password from the hash. That's not something that password hashes are designed for — quite the opposite: with a proper password hash, the only way to recover the password given the hash is to make a guess and verify it — and the better the hashing scheme, the more costly verifying guesses is.

Passwords are used for authentication: a client attempts to prove its authenticity to a verifier by proving that it knows the password. The client knows the password and does not need to recalculate it. The verifier knows the password's hash; the client tells the verifier what it claims the password is, and the verifier computes the hash of the candidate password and compares it with the reference hash. The verifier does not need to compute the password. This works because computing the hash of the password is deterministic (the calculation always gives the same result).

A password hash needs three ingredients:

Hash: a one-way function (or a good enough approximation — a function for which nobody knows how to compute inverses), so that the password cannot be recovered from the hash except with a lucky guess.
Salt: a unique value that makes the hash computation unique, so that adversaries wishing to break passwords cannot make computations that are useful to break many passwords at once.
Slowness: so that brute force attempts by an adversary who knows the hash (make a guess, compute its hash, compare it against the known hash) take an impractically long time even for practical, low-entropy passwords.

See How to securely hash passwords? for a more detailed explanation.

Your password hashing scheme has two of the three ingredients: hash and salt. Keep in mind that the salt must be saved with the hash value so that the same hash computation can be made when a client submits a candidate password. You're missing slowness, which can be achieved by making many iterations of the hash function. There are better ways of achieving slowness which also make it harder to design specialized hardware dedicated to fast password computations; again, see How to securely hash passwords? for more details.


If two hosts are using a transparent IP level authentication and encryption, is their communication subject to both MITM or replay attacks? Encryption process for any outgoing packet to the specified "remote IP":

-original payload P is encrypted (the bytes after the IP header) using RC4 with the preestablished key KEY to obtain encrypted payload C=RC4(P, KEY)

-The encrypted payload C is concatenated with the 16 byte output of MD5(C|KEY), and the IP header is adjusted accordingly (increasing the packet total length, re-calculate the checksum) so that the outgoing packet will have payload C | MD5(C|KEY) and destination "remote IP"

Decryption process for any incoming packet from specified "remote IP":

-Check the packet payload for the MD5 authentication with the same given "key"
Specifically, divide the received packet payload (those bytes after the IP header) as two parts C, A where A is the last 16 bytes of the packet payload and C is the rest.

-If MD5(C|KEY) == A, decrypt C using RC4 to obtain
P=RC4(C, KEY), change the payload of the incoming packet from C|A to P, and adjust the IP header accordingly (decrease the packet total length, re-calculate the checksum) so that the incoming packet will be restored to its original form without keyed md5 authentication before sent to the receiving process

1) Are replay attacks possible?
Yes. For example, if Alice wants to tell Bob "Pay Eve \$100", then P = "Pay Eve $100"
C = RC4(P, KEY)
Packet = IP(C | MD5(C|KEY) )
By capturing and replaying Packet, Eve can make Bob pay her \$100 over and over again.

2) Are Man-In-The-Middle attacks possible?
More specifically, "Is there a possibility to intercept messages and impersonate at-least one of the parties? Is it possible for the attacker to put himself between the sender and receiver by breaking the encryption?"

This question is more complicated. In short, it depends.

If the attacker gets hold of plaintext / ciphertext pairs for the RC4 (either through encryption oracle or decryption oracle), he simply takes P xor C to find the keystream. RC4 key reconstruction attacks can be used to find the MD5 key. The attacker may then act as a full MITM, intercepting and viewing messages and optionally modifying them before passing them on.

I am also uncomfortable with that MAC construction, so I'll get back to you on that one.


Do I need different encryption and decryption algorithms for each key? Is a different encryption and decryption algorithm used for every secret key, or can I use the same encryption and decryption algorithm for different keys?

You can use the same ones (which is good, because otherwise you'd run out of them pretty fast). In fact, when a cipher allows you to choose a key, that's basically the same as giving you a new pair of encryption/decryption algorithms for every key.

Usually, when designing a system that uses symmetric encryption, a small set of ciphers are used. For example, the popular NaCl library only uses Salsa20+Poly1305 and AES-GCM.


Parallel Composition of ($\epsilon, \delta$) differential privacy I know that if there are $n$ functions $M_1, M_2, \cdots, M_n$ computed on disjoint subsets of the private database whose privacy guarantees are $\epsilon_1, \cdots ,\epsilon_n$ differential privacy, respectively, then any function $g$ of them: $g(M_1, \dots,M_n)$ is $$(\max_i \epsilon_i)$$differentially private.

This is known as the Parallel Composition Theorem.

My question is: does this Parellel Composition Theorem extend to $(\epsilon, \delta)$ differential privacy? In other words, is the following statement true?:

If there are $n$ functions $M_1, M_2, \cdots, M_n$ computed on disjoint subsets of the private database whose privacy guarantees are $(\epsilon_1, \delta_1), \cdots ,(\epsilon_n, \delta_n)$ differential privacy, respectively, then any function $g$ of them: $g(M_1, \dots,M_n)$ is $$(\max_i \epsilon_i, \max_i \delta_i)$$differentially private.

If this statement is NOT true, then what bounds are there are on the privacy of the composition function $g$.

Your conjecture seems correct. If the sets are disjoint then the mapping $\bar{M} = (M_1,\dots,M_n)$ is $(\max(\epsilon_i),\max(\delta_i))$-DP. Note that for every database $D$ and any $x$, $\bar{M}(D)$ differs from $\bar{M}(D\setminus {x})$ in only one coordinate by the disjoint assumption, w.l.o.g., they differ in the $j$'th coordinate. Therefore, the difference between the density functions of $\bar{M}(D)$ and $\bar{M}(D\setminus {x})$ is the same as the difference between $M_j(D)$ and $M_j(D\setminus {x})$.


What could be the problem with this TLS 1.2 Client Finished Message approach? Can someone make sure I'm creating my Client finished message properly as I've been working at this for days and keep getting a Bad record MAC error and I have no idea what I'm doing wrong.

First step is creating the 12 bytes of verify data. This is created using the PRF with the master secret, the label "client finished", and the sha256 digest of all the previous handshake messages. (The cipher suite is TLS_RSA_WITH_AES_256_CBC_SHA256).
The 12 bytes are then placed in the finished handshake record with a handshake type field and 3byte length field.
These 16 bytes are then passed through the sha256 HMAC, which has as input:

the sequence number (for a finished message this is number 3 as the previous 3  messages were the client hello, the client key exchange, and the change cipher spec)
the type - 0x14
the version - 0x0303
the length -16
the 16 bytes of 'plain text data'

This produces 32 bytes of hash which are tagged onto the 16 bytes of data, creating 48 bytes before padding (49 if you include the padding length field). And so we add 15 bytes of padding with value 0x0F. This takes the total length to 64 bytes (a multiple of the block size 16).
The 64 bytes are then encrypted with using the IV and the client write key.
The 64 bytes, preceded by the 16 byte IV are sent to the server - 80 bytes in total.

What am I doing wrong?

EDIT

Thanks for the pointers guys! Don't know why I hadn't thought of debugging another implementation to find where I was going wrong. Turns out the library I was using for calculating my SHA256 HMAC (I was using Nettle) was a bit buggy. I imported another library and managed to get it all working!

The sequence_number resets at CCS, so for Finished it's zero (for 8 bytes). Also record type for handshake is 0x16,
and to be clear the record length is 2 bytes, in this case 00 10, and "the IV" should be random for each record.
As a mnemonic, the RHUL group's Lucky Thirteen attack uses the fact that the HMAC pseudoheader is 13 bytes.

That said I agree with @Maarten's comment: debug against another implementation. Especially an open source one like OpenSSL/LibreSSL/BoringSSL or GnuTLS or Java.


Simplified Lagrange interpolation formula inside Shamir's secret sharing scheme I originally posted this question in the math stackexchange, but I then thought that it might be more appropriate in this section. I am currently studying Shamir's secret sharing scheme, which uses Lagrange's interpolation formula to reconstruct a key $K$ from a certain number of shares. In Shamir's scheme, during key reconstruction, there is no need to reconstruct the entire polynomial $a(x)$ since we only need the value $a(0)$, the secret. Therefore, we can use a simplification in the formula by substituting $x=0$ in the original Lagrange formula, which then becomes this:

$$K = \sum_{j=1}^t (y_j \prod_{1 \leq k \leq t} \frac {x_k} {x_k - x_j}) \pmod p$$

where $y_j$ are the shares owned by the participants. If we now define

$$b_j = \prod_{1 \leq k \leq t} \frac {x_k} {x_k - x_j} \pmod p$$

we can then reconstruct the key $K$ with this formula:

$$K = \sum_{j=1}^t b_jy_j \pmod p$$

And during the calculation of $b_j$ is where I hit a wall: in the book that I am using to study this (Cryptography Theory and Practice, by Stinson and Paterson), there is an example of how to compute $b_j$. We are given the following values:

$x_1=1, x_2=2, x_3=3, x_4=4, x_5=5$

And we want to get the value of $b$ for $x_1$, $x_3$ and $x_5$. The book shows this example for $b_1$:

\begin{align}
b_1 &= \frac{x_3 x_5}{(x_3 - x_1)(x_5-x_1)} & & \pmod{17} \\
&= 3 * 5 * (2)^{-1} * (4)^{-1} & & \pmod{17}\\
&= 3 * 5 * 9 * 13 & & \pmod{17} \\
&= 4 & & \pmod{17}
\end{align}

How did we get from $(2)^{-1}$ and $(4)^{-1}$ to $9$ and $13$ respectively?

All these calculations are done $\bmod{17}$.

$2^{-1}$ means here the number, $x$, that satisfies the equation $2x = 1 \pmod{17}$. (Note that this is the same definition that we use for the reals). When you're working $\bmod{17}$ (or any prime number, in fact), every number except 0 has an inverse.

To calculate inverses efficiently, you should use the extended Euclidean algorithm. But with a small number like 17, it might be worthwhile to just construct a multiplication table to get practice with modular arithmetic.


Difference between Rijndael 128 / 256 blocksize implementations? (and impact of block size in general) Can anyone shed some light onto the advantages/disadvantages of using Rijndael with 256-bit block size, as opposed to the 128-bit (AES) implementation? (please note: I'm not referring to key-size here).

These are standard implementations in Mcrypt.  I'm vaguely aware that a larger block size can help to mitigate some kinds of attacks... is that true?  Which ones?  Could a larger block size also introduce weaknesses?  I'm just curious to know why the 128-bit version become the standard, and whether there's any good reason to use the 256-bit version.

I'm just curious to know why the 128-bit version become the standard[.]

That question is easy to respond. In the section Minimum Acceptability Requirements of Request for Candidate Algorithm Nominations for the AES, it says:

  The candidate algorithm shall be capable of supporting key-block combinations with sizes of 128-128, 192-128, and 256-128 bits. A submitted algorithm may support other key-block sizes and combinations, and such features will be taken into consideration during analysis and evaluation.

So, while supporting different block sizes is considered a desirable property, AES's block size was already decided before the competition even started, i.e., it has nothing to do with the Rijndael algorithm itself.

  I'm vaguely aware that a larger block size can help to mitigate some kinds of attacks... is that true? Which ones?

For some attacks, yes.

Some block modes of operation (e.g., CBC) require that the same ciphertext will never get generated twice. If $$E(C_1 \oplus P_1) = E(C_2 \oplus P_2)$$ ($P_i$ denotes a plaintext block, $C_i$ the previous ciphertext and $E$ the encryption function), since $E$ is bijective, $$C_1 \oplus P_1 = C_2 \oplus P_2,$$ and, therefore, $$P_2 = (C_1 \oplus C_2) \oplus P_1.$$

Since $(C_1 \oplus C_2)$ is known by design, if you know $P_1$ as well, you can derive $P_2$ (see: code book attack).

With a block size of $n$ bits, collisions become likely after roughly $2^\frac n2$ blocks of plaintext (see: birthday problem). This was a problem of DES (with a block size of 64 bits, $2^{32}$ blocks are only 32 GiB of plaintext). A block size of 128 bits ($2^{64}$ blocks are 256 EiB of plaintext) should be enough for the foreseeable future.

The same concern applies to other block modes of operation (e.g., CTR) as well, although it is not as easy to launch a successful attack. After roughly $2^\frac n2$ blocks, collisions should start to occur. However in CTR mode, $E(nonce+counter)$ won't produce any collisions in the first $2^n$ blocks. Therefore, the stream will become distinguishable from a random stream at a given point (see distinguishing attack).

  Could a larger block size also introduce weaknesses?

In general, yes.

Despite its simplicity, the cipher XTEA remains unbroken. However, its extension Block TEA (XTEA is Block TEA with a block size of 64 bits), is vulnerable to differential cryptanalysis (see: A Cryptanalysis of the Tiny Encryption Algorithm).

  I'm just curious [...] whether there's any good reason to use the 256-bit version.

Categorically no!

In AES proposal: Rijndael, the authors say:

  For Rijndael versions with a higher block length, the number of rounds is raised by one for
  every additional 32 bits in the block length, for the following reasons:

  For a block length above 128 bits, it takes 3 rounds to realise[sic] full diffusion, i.e., the diffusion power of a round, relative to the block length, diminishes with the block length.
  The larger block length causes the range of possible patterns that can be applied at the input/output of a sequence of rounds to increase. This added flexibility may allow to extend attacks by one or more rounds.

Furthermore, the authors recommend a number of round ($Nr$) of $$Nr = max(Nk, Nb) + 6,$$ where $Nk$ is the key size and $Nb$ the block size (both in 32-bit blocks).

This means that Rijndael-128-256 will be slower than Rijndael-128-128 (AES-128), and that Rijndael-256-256 may have a lower security margin that Rijndael-256-128.

Bottom line

Rijndael N-256 hasn't received nearly as much attention as AES, so it might have some undiscovered weaknesses.

In contrast, AES is considered secure, despite being subject to probably more cryptanalysis than any other cipher.

The 128-bit block size isn't a problem. If it ain't broken, don't fix it!


Is DES slow in hardware or only in software? I have been reading that DES is slow.  Is it only slow in software or slow overall?  Also, as far as Triple DES being slow is concerned, is double AES with two 128 bit keys slower than single AES with a 256 bit key?

DES is slow in software because it was designed back in the early 70's even before the 8086 processor existed, and uses several bit oriented operations that are just not implemented efficiently in a processor with a word oriented instruction set.

Its intended product was ASIC hardware designs, in which DES runs quickly. DES hardware processors are quite common on older network cards intended for use in servers and workstations (I still have LAN card with wire speed TDES hardware). DES was already considered obsolete by the time the technology would have trickled down into consumer grade hardware.

DES becomes even slower when we compare it from a security standpoint against AES. DES in software is probably half the speed of AES, and it is also half the key space. Therefore TDES is used to increase the key space, but now it is 1/6th the speed of AES. AES is also better designed to resist attacks other than brute force.

Double AES with two 128 bit keys requires about 1.5X the processing of AES with a 256-bit key, and at least from a brute force perspective is not as secure. The reason TDES is used instead of double DES is because it requires 3 operations in order to double the key space.


Is there an adaptive version of LWE assumption with respect to some potentially non-uniform secret distribution? There is a version of LWE assumption as follow.

Assume that there is a positive number $n$, an integer $q = q(n) \geq 2$, an error distribution $\chi = \chi_{n}$, a vector $\mathrm{\mathbf{s}} \gets \mathbb{Z}_{q}^{n}$ and for every efficient algorithm $\mathcal{A}$,
$$\Pr \left[ A \gets \mathbb{Z}_{q}^{m \times n}, \mathrm{\mathbf{e}} \gets \chi^m,~  \mathrm{\mathbf{b}} \gets A \cdot \mathrm{\mathbf{s}} + \mathrm{\mathbf{e}}: \mathcal{A}(A, \mathrm{\mathbf{b}}) = s \right] \leq \mathrm{nelg}(n)$$

Q1: Why does it say $m = O(n \log q)$ in some schemes? I do not find some notes about the range of $m$. I think $m = \mathrm{poly}(n \log q)$ is OK.

Q2: Is there an adaptive version? Is it still hard to solve?

For example, Let oracle $\mathcal{O}_{\mathrm{\mathbf{s}}}$ satisfy that  $\mathcal{O}_{\mathrm{\mathbf{s}}}(\mathrm{\mathbf{a}}) = (\mathrm{\mathbf{a}},  \langle \mathrm{\mathbf{a}}, \mathrm{\mathbf{s}} \rangle + e)$, where $e \gets \chi$.
And for every efficient algorithm $\mathcal{A}$,
$$\Pr \left[ \mathcal{A}^{\mathcal{O}_{\mathrm{\mathbf{s}}}}(1^n) = s \right] \leq \mathrm{nelg}(n)$$
The algorithm $\mathcal{A}$ is allowed to ask the access of $\mathcal{O}_{\mathrm{\mathbf{s}}}$ for at most $m$ times.

Q3: If there are $l$ secret vectors and $S = [\mathrm{\mathbf{s}}_{1}, \mathrm{\mathbf{s}}_{2}, \ldots, \mathrm{\mathbf{s}}_{l}]$.
Is there a version of LWE with respect to some potentially non-uniform secret distribution? (e.g., $S$ belongs to the general linear group $GL_{n}(q)$ or the orthogonal group $S \in O_{n}(q)$)

It means that for every efficient algorithm $\mathcal{A}$,
$$\Pr \left[ \mathcal{A}^{
\mathcal{O}_{\mathrm{\mathbf{s}}_{1}},
\mathcal{O}_{\mathrm{\mathbf{s}}_{2}},
\ldots,
\mathcal{O}_{\mathrm{\mathbf{s}}_{l}}
} (1^{nl}) = S \right] \leq \mathrm{nelg}(nl)$$

For Q1, $m = O(n\log q)$ is the size required for the leftover hash lemma to kick in and $Ax$ to be statistically close to uniform (I believe). See questions like this one.

For Q2, the answer is yes. The hardness of LWE is essentially independent of the dimension $m$, as you can generate new LWE samples from a fixed collection of samples with only a mild loss in the error term. See proposition 2.1 of Regev's survey (and the "other implications" discussion after the proof).


CBC-Mode Infinite Garble Extension A variation of the CBC mode is the Inﬁnite Garble Extension.

I can neither find a block diagram of it, nor the formulas for encryption and decryption. I would really like to learn more about it but there is not much online information available which helps.

What is the main difference between "normal" CBC and the CBC Inﬁnite Garble Extension if I decrypt blocks ?

The infinite garble extension makes sure that if a ciphertext block is changed that this block and each block after it doesn't decrypt correctly. The way that additional plaintext is affected when the ciphertext is changed is called error propagation. Error propagation over large parts of the plaintext is mainly interesting if you want to combine it with some MDC: Manipulation Detection Code. Then the MDC can be used to verify integrity of the plaintext.

Nowadays we simply encrypt-and-authenticate using CBC + MAC or an authenticated cipher. Error propagation is of little use if you're already verified the ciphertext for integrity and authenticity. Hence you won't find too many mentions of these (computationally intensive) modes of operation; they are mainly used for niche problems where using an authentication tag isn't the right solution.

With most other modes there is a limited amount of error propagation. With CBC and CBF only the same plaintext block and the next plaintext block will not be the original plaintext. With CTR mode only the modified bits are affected; there is no error propagation.

There is also Bi-IGE which does the same, but in two directions: every plaintext block will be changed even if just one bit of ciphertext is changed. So each bit of plaintext is flipped with a 50% possibility (and at least 1 bit with 100% certainty, but that's inconsequential).

More information can be found in my question and the resulting answer about MDC / IGE.


Preventing attack in RSA modified version I have the following modified version of RSA apparently proposed by Shamir. To check the original version of RSA check the first scheme in this other question.

  The modified version goes as follows: que take $p$ a prime number of
  $s$ bits and $q$ a random number not necesseraily prime of size $ts$
  where $t \simeq 10$ and take $n = pq$. The public key and the
  encryption function are as in RSA shown in the link.

We can show that the decryption problem is equivalent to find the factor $p$ of $n$. Namely, to show that decrypting would imply finding factor $p$ we do at follows:

Choose a message $p < m < 2p$ and write $m = u + p$ then $m = m^{ed} \, mod \, p = (p+u) \, mod \, p = u$ so that $p = m-u$.

Here we used the fact that decrypting with $m^{ed} \, mod \, p$ is good enough (is injective if we choose $gcd(e,p-1) = 1$.

My question

In the previous the deduction we actually chose a convenient message to show that solving decryption problem implies factoring $n$ but in reality we won't get a chosen message $m$ but  random ones so that even if we know how to decrypt we might not be able to find out $p$. How is this deduction valid then?
The notes I'm following propose a way to thwart this attack.

  One can add some redundancy in the message before encryption, and
  check the redundancy after decryption before disclosing the result.

I don't see very well how this strategy would work. Can you give an example?

Tldr: Your notes are nonsense.

First, normal RSA: There are some big, random, secret (pseudo)-primes p and q, and a nonsecret N with N=p*q. RSA is secure (well, other than the known problems) because an attacker can't extract p and q from N (factorization).

Your version of RSA does not require that q is prime, just big and random. If the random number happens to be a prime, everything is ok.
If, on the other hand, it is something like 2^1024 or anything else with lots of small prime factors, it's trivial to factorize N => broken. In real RSA, the requirement for primes is important.

  We can show that the decryption problem is equivalent to find the
  factor p of n.

Yes, like in normal RSA. If p is found, q=N/p, broken.
But again, if I can factorize N easily, there's no challenge.
Let's take the 2^n - example from above: I do N=N/2 until I have a prime number (or any uneven number), and that's p. ... Other numbers than 2^n are not much harder.

  In the previous the deduction we actually chose a convenient message
  to show that solving decryption problem implies factoring n but in
  reality we won't get a chosen message m but random ones

The content of the message m does not matter at all. Factoring N => broken, that's all.

  One can add some redundancy in the message before encryption, and
  check the redundancy after decryption before disclosing the result.

That's something to detect tampering (ie. the attacker changes the encrypted data to something else, without knowing the plain content), but it does not prevent factorization.


Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$? A recent eprint paper claims to bound $\lambda_1(\Lambda^\perp(\mathbf{A}))$ for $\mathbf{A}\in\mathbb{Z}^{n\times m}$, a uniformly random matrix, by $O(1)$, specifically by $4$. This has applications to solving $\mathsf{SIS}_{n,m,q,4}$ in $\mathsf{P}$.

I'm no expert in this area, but it seems to me this contradicts the common thought that $\lambda_1(\Lambda^\perp(\mathbf{A})) = \Omega(\sqrt{n\log q})$ (see, for example, section 2.4.2 of this paper).

As getting into the details of the recent paper is likely off topic for this forum, I'm interested instead in another question --- what concrete/experimental evidence has been collected for the asymptotics of $\lambda_1(\Lambda^\perp(\mathbf{A}))$? Looking into data such as this would be an easy way to gain intuition for whether we're in an $O(1)$ regime or $\Omega(\sqrt{n\log q})$ one, and I had assumed that someone had papers along these lines, but don't actually recall seeing any of it myself.

The first inequality at the bottom of page 3 of the paper is false. For example, Conway and Thompson proved the existence of "self-dual" $n$-dimensional lattices $L$ (i.e., $L^* = L$) where $\lambda_1(L) = \lambda_1(L^*) = \Omega(\sqrt{n})$, hence $\eta_{2^{-n}}(L) = O(1)$ but $\tilde{bl}(L) \geq \lambda_1(L) = \Omega(\sqrt{n})$.

The statement and proof of Conway and Thompson's result can be found as Theorem 9.5 in https://www.springer.com/us/book/9783642883323 .


What do these notations mean in the definition of Perfect Secrecy, if we read those in English? If m: message, M: message space, k: key, K: keyspace, c: cipher, C: cipher space and $E_k$: encryption function, such that
$E_k(m) = c,\ m,m^* \in M,\ k\in K,\ c\in C.$

Then, what do the following notations actually mean in plain English?

What does it mean by $C=c$? If it means "If $C$ takes the value of $c$", to my understanding it is meaningless. Why would $C$ take the value of $c$? $c$ is a part of the whole message $C$. The same is true for $M$ and $m$.

Imagine the following three scenarios. In each, you intercept an encrypted message and you know from context:

the message is a randomly chosen key in $\{0,1\}^n$ for some other cryptosystem
the message is either "It's a boy!_" or "It's a girl!", both are equally likely
the message is a vote from someone in a referendum; it's either "yes" or "no_", and the probability of it being "yes" (based on your knowledge of that person's preferences) is around 9/10.

Each of these scenarios describes a different context and prior knowledge you may have about the message (formally: a probability distribution on messages). An encryption scheme that's any good won't reveal anything more about the encrypted message than you already know in any of these scenarios. Even in the last case where you can make a pretty good guess at the message without breaking any encryption, the ciphertext shouldn't tell you anything more than you already know.

The last line of that definition translates to "what you know about $m$ after seeing $c$ is the same as what you would know about $m$ without seeing $c$" (for any kind of knowledge about $m$ that you may have).


Trouble understanding range proof of Greg Maxwell's Confidential Transaction i've some trouble understanding the base of the range proof presented at
https://elementsproject.org/elements/confidential-transactions/investigation.html

I've understand the base of the Pedersen Commitment but I lost when he speak about commitment to zero:

  A pedersen commitment can be proven to be a commitment to a zero by just signing a hash of the commitment with the commitment as the public key. Using the public key in the signature is required to prevent setting the signature to arbitrary values and solving for the commitment. The private key used for the signature is just the blinding factor.

Why to prove a zero commitment it make an hash of the commitment? Does he intend this ( if we call $C$ the commitment)?

$Hash(C)H + C$

But if I know the Publik key $P=kG$ cannot simply check if $C= P$ because we have that $C= kG + 0H$?

Thanks!

not sure if I understand your problem.
But the zero commitment means that you know some k that makes k*G= your commitment C.

If you sign something with C as the public key, it also means that you know k.

so,
if you can sign with C = zero commitment with C.

Hope it answers your question.


What does the Double Ratchet algorithm need the Root Key for? One of the basic ideas of the Double Ratchet algorithm is that it performs DH exchanges in-band using a clever “half-DH” trick.

For some reason, instead of directly deriving the Chain Key from the DH exchange, it adds another layer: the Root Key. The Root Key is stored by both parties and is updated on every “half-DH” using the DH result and the previous Root Key. In the same way a new Chain Key is derived from the DH result and the previous Root Key.

Why is this Root Key needed? What would go wrong if we used solely DH to derive Chain Keys?

I went through the original description of the algorithm and a number of papers that study the security of Signal and WhatsApp implementations, but no one mentions Root Keys.

The only plausible explanation I found is in this blogpost. Basically it says that if we are so unlucky that the attacker is capable of breaking DH, deriving the Chain Key from DH is completely insecure. The fact that the Root Key is also mixed in means that the attacker will have to intercept and break every single prior “half-DH”-exchange. That makes perfect sense, but is that the only benefit?

Introduction of Root key is a critical element in ensuring Break-in recovery. Below is my dig at explaining its necessity -

Why is DH ratchet used:
For argument's sake, if an attacker was able to compromise a given message key, he/she would be able to compute future chain keys and message keys if only Symmetric-key ratchet were used. DH ratchet is hence introduced to prevent this and ensure Break-in recovery.

Now to answer your question:

In DH ratchet, each party generates a new DH key pair and forwards the public key component over to the other party.

Let us go by the assumption that an attacker was able to compromise the chain key at a given point when party A is sending a new DH public key to the party B. Provided that the attacker has the ability to intercept the channel, it would be trivial for him to replace A's DH public key with self generated public DH key and forward the message over to B. In doing so, the attacker can conveniently remain to be an MITM between A and B even with the DH ratchet, unless ---- the DH ratchet were to use an additional secret known only to A and B to derive the chain keys. No points for guessing what the secret is - root key.

Recall that the Root key was bootstrapped at the beginning of establishing the communication between A and B. Since this initialization used pure DH mechanism using Identity keys, there is really no way the attacker could have compromised the root key.

Continuing the narrative - So, when B makes use of attacker introduced public DH key in combination with the root key, B generates a "receiving chain key" and sends along a new public DH key. Our attacker who is intercepting the channel, now attempts to replace B's public DH key with a new self-generated DH public key and sends to A.

The attacker's intention being to to build the corresponding chains to match up to A's sending chain and B' receiving chain to successfully establish a working MITM.

But due to the introduction of 'root key' (or an updated version of it) in the DH ratchet, the attacker will not be able to generate corresponding chain that can quite match up to B's sending chain. The same holds true on the other side with A's receiving chain.

Hence, at this point when B sends a message encrypted using 'message key' derived from B's "sending chain key", the attacker  would not be able to make sense of it. Note also that, at this point A and B would have to re-establish trust because the message keys/chain keys don't match up at either ends.

This way, an attacker's window of interception after a chance compromise of a 'message key' is limited until the next opportunistic 'DH ratchet' cycle.

Note that the root key also gets updated with each DH ratchet but there is no way the attacker can influence the root key or glean its contents.


Ciphertext size of RSA, ELGamal, and EICES encryption I have to make a choice based on the minimum stored data, so I would like to know which encryption protocol is better in terms of the size of the resulting ciphertext for very short plaintexts (8 to 40 bytes)? RSA? ElGamal? EICES?

A compressed point - which makes up the ephemeral public key for ECIES - only takes the key size, possibly prefixed by an indicator byte with value 02 or 03 (which is required by some libraries).

So for e.g. BrainpoolP256R1 you'd get 32 bytes, and maybe one more for the byte indicating that it is a compressed point. That is enough to derive a data encryption key. As the public point is already ephemeral there is no need for an IV. After key agreement you would just require the ciphertext bytes - which for CTR is identical to the plaintext message size.

So that would come down to a ciphertext size of 32 + 8..40, or 40 to 72 bytes (not including the indicator byte), while still giving you 128 bits of security (and no protection against quantum computers of sufficient size, of course). That's way less than the 256 bytes required for RSA, while RSA would be less secure on top.


Cardholder to Merchant SET Protocol I have some doubts regarding the SET protocol. Let say the Alice payment information runs through a sha-1 hash function which is a one-way algorithm, irreversible to create a message digest. How do bob verify that the message is really from alice since he can't see the content of the message which bob shouldn't see in the first place?

Based on my understanding, it has something to do with public digital signature and comparing it with the message digest but I don't get it. Can anyone explain the concept to me in layman terms.

In SET, Bob the merchant doesnt need to know message is from Alice the cardholder. Bob needs to get paid for the order received. So Bob proceeds on response from Acquirer (running a SET payment gateway) telling him this particular cardholder (whatever the name) has sufficient funds in his account. This would likely mean funds were reserved, according to policy of issuing bank.

Yes, a "dual signature" was introduced in SET, meaning message to be signed is actually just two hashes, one is the order and the other is payment information. Merchant is supposed to receive the order and the hash of payment information, unless gateway would open more details.


Can I reduce the MAC size in TLS? The MAC size is reduced to 80 bits in truncated_hmac extension , which says "forging of MAC values cannot be done off-line: in TLS, a single failed MAC guess will cause the immediate termination of the TLS session."

Question 1 (main question):
So can I reduce MAC size to something even smaller, say 32 bits?

Question 2:
The truncated_hmac extension does not effect AEAD. Can I reduce the tag's size in AEAD, e.g. GCM or CHACHA-POLY?

You cannot change the hash size without altering TLS:

From: Appendix C.  Cipher Suite Definitions

MAC       Algorithm    mac_length  mac_key_length
--------  -----------  ----------  --------------
NULL      N/A              0             0
MD5       HMAC-MD5        16            16
SHA       HMAC-SHA1       20            20
SHA256    HMAC-SHA256     32            32

So although the mac_length is part of the SecurityParameters structure, the sizes are still predetermined. The implementation on the other side may not support truncated MAC values.

For the AEAD/GCM cipher the size of the tag is determined in RFC 5116 "Authenticated encryption" (normative reference):

  An authentication tag with a length of 16 octets (128
     bits) is used.

RFC 5116 is a rather strict (too strict in my opinion) as it assumes that the authentication tag is part of the ciphertext. It doesn't allow alterations to the size of the authentication tag either.

You are of course free to alter the specification for your own purposes. In that case the question however simply: what size of authentication tag should I use for ciphertext of "2^14 bytes or less" - as $2^{14}$ is the maximum size of a (data) fragment for TLS 1.2. In that case it depends on the MAC construction used.

For GCM the minimum is 64 bit, but a higher tag size would be preferred. For the HMAC variants you might go lower, but you should only do so for small, infrequent messages. This in turn means you must make sure that an attacker cannot trigger you to use more / larger messages.


RSA vs Elliptic Curves I am currently reading about how more efficient and ''light'' is ECC compairing to RSA as far as key generation is concerned. My question is simple, why does RSA continue to be used today (ex.SSL) while the ECC can be used instead, which has advantages over RSA?

Now, you highlighted key generation - no one really cares about key generation time (unless you are generating ephemeral keys, that is, a fresh key pair for each connection - we generally don't).  Instead, we might generate a fresh key pair maybe once a day or once a month (usually far less frequently), and so we don't care whether it takes perhaps a second (RSA) or submillisecond (ECC).

Now, while the key performance delta between RSA and ECC is the most extreme, ECC still outperforms RSA in most other measures, just not by as wide of a margin.  You can still ask "why do people still use RSA in spite of those other metrics by which ECC is better":

Inertia (we've been using RSA for decades, why should we switch?); this lends itself to trust.  And, this is not a spurious concern - we generally like to use crypto which has been published a long time ago, and vetted by a number of crypanalysts - the more, the better, and it's really hard to think of something more vetted than RSA.
RSA is easier to understand; it's not difficult for someone with a little bit of mathematical background to get the basics.  In contrast, to understand ECC, you need to dig into more number theory than most people have encountered.  This ease of understanding also lends itself into trust.
Backwards compatibility; there are a number of people running older browsers that just don't understand ECC certificates; if you're a server and all you have are ECC certificates, you've just disqualified those people from talking to you.  Now, you could have both an RSA certificate and an ECC certificate (TLS 1.2 and on allows you to select the certificate based on client capability); however if you have an RSA cert, why do you need a second cert?
Performance (which sounds like it contradicts what you read - it really doesn't).  For TLS, clients generally don't care about the performance of RSA vs ECC - they usually make a handful of connections per second, and either is fine for that.  For servers (which may need to make thousands of connections per second), they often have crypto accelerators.  And, at least in my limited experience, RSA crypto accelerators are rather more common than ECC ones, and RSA with a crypto accelerator does go faster than ECC in software.
Intellectual property; not that long ago, there was a company (Certicom) which claimed to have patent rights over most of ECC, and threatened lawsuits against companies which used ECC without paying them (and did file in at least one case).  Now, that was several years ago, and people are not concerned about them now.  However it did delay things, at least for those companies large enough to be concerned about Certicom suing them...


Can a SHA3 engine be used to construct a Keccak implementation? I am working on a cSHAKE-128 & cSHAKE-256 implementation that takes advantage of a number of hardware accelerators I have at my disposal, specifically for SHA-3 256/384/512 and SHAKE 128/256.
cSHAKE 128 is defined as follows:
1. If N = "" and S = "":
return SHAKE128(X, L);
2. Else:
return KECCAK[256](bytepad(encode_string(N) || encode_string(S), 168) || X || 00, L).

If condition 1 is met, the solution is trivial, since I do have a SHAKE128 engine available.
However, in the case of condition 2, I don't have a Keccak engine readily available. I'm wondering if SHA3 can be used as primitive to construct Keccak 256.
I have read that SHA3 is directly derived from Keccak (was a result of a contest which Keccak won), but I've also read they're not exactly the same. This very useful on-line hasher does not produce the same hash values for SHA3 256 and Keccak 256.

Let first look at  $$\operatorname{KECCAK}[c] (N || suffix, d) \label{1}\tag{1}$$ It calls
$$\operatorname{KECCAK}[c] (N, d) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], pad10*1, 1600 – c] (N, d).$$

$c$ is the capacity
$d$ is the output size
1600 is the base $b$
$pad10*1$ is the multi rate padding.
24 is the number of rounds $n_r$
The sponge in short is the framework for specifying functions on binary data with arbitrary output length.

Let assume that we have a black box SHA3 implementation of any mode

$\operatorname{SHA3-224}(M) = \operatorname{KECCAK}[448] (M || 01, 224)$
$\operatorname{SHA3-256}(M) = \operatorname{KECCAK}[512] (M || 01, 256)$
$\operatorname{SHA3-384}(M) = \operatorname{KECCAK}[768] (M || 01, 384)$
$\operatorname{SHA3-512}(M) = \operatorname{KECCAK}[1024] (M || 01, 512)$

and black box SHAKEx implementations

$\operatorname{SHAKE128}(M, d) = \operatorname{RawSHAKE128}(M || 11, d)$

$\operatorname{SHAKE256}(M, d) = \operatorname{RawSHAKE256}(M || 11, d)$
where

$\operatorname{RawSHAKE128}(J, d) = \operatorname{KECCAK}[256] (J || 11, d)$
$\operatorname{RawSHAKE256}(J, d) = \operatorname{KECCAK}[512] (J || 11, d)$

Now you want to use the above as black box implementation for cSHAKE
 cSHAKE128(X, L, N, S):
 1. If N = "" and S = "":
    return SHAKE128(X, L);
 2. Else:
     return KECCAK[256](bytepad(encode_string(N) || encode_string(S), 168) || X || 00, L).

The if part is not a problem, since it directly uses the SHAKE128.
The else part is the problematic part. One can externally implement bytepad(encode_string(N) || encode_string(S), 168) and concatenate it with X. The domain separation padding 00 is the real issue. If the block box doesn't allow this as input, then there is no way to this.

If the library somehow extendible one may use the \ref{1} to generate all of the above, otherwise no.
The cSHAKE is the base for KMAC, TupleHash, and ParallelHash. If you are going to need those, you may need to implement yourself.


Exactly two of the four roots must be greater than N/2 Theorem: Let $y$ be a quadratic residue in $\mathbb{Z}_N$* where $N=pq$.

There are exactly four integers $x_1, x_2, x_3, x_4$ where $0 < x_1 < x_2 < \frac{N}{2} < x_3 < x_4 < N$ such that $y = x_i^2 \pmod{N}$ for $i=1,2,3,4$.

The above theorem simply states that exactly two of the four roots must be greater than $\frac{N}{2}$.

Most papers will say that this result is well known, without providing any detailed proof. How can we prove that $0 < x_1 < x_2 < \frac{N}{2} < x_3 < x_4 < N$?

Each root $r$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ has a ``conjugate'' root $-r \equiv n - r$ since trivially $(-r)^2 \equiv r^2 \pmod{n}$.

If there are exactly four roots (each prime factor generally brings in two roots, well, one root and its conjugate, and they generate the roots modulo $n$ via by CRT - see gammatester's answer below for more details) we have exactly two pairs of conjugate roots. In each pair exactly one root will be greater than $n/2$.

By simple arithmetic, one can see that $r < n/2 \iff n-r > n/2$.  Thus, assuming that $n$ is odd (which rules out the possibility that $r = n/2$), it follows that exactly one of each conjugate pair of roots is grater than $n/2$.


Why would anyone use an elliptic curve with a cofactor > 1? In cryptography, an elliptic curve is a group based on a finite field $GF(p^k)$; this group has $n$ elements on it, and we work on a prime-sized subgroup of size $q$.  We denote the value $h = n/q$ as the cofactor of the curve.

My question is: why would we ever want to consider using a curve which has a cofactor $h>1$?  Or, in other words, why would we consider using an elliptic curve that had a composite number of points?  After all, the discrete log problem can be solved in $O(\sqrt{n / h})$ time; if we were to select a curve with $h>1$, we are deliberately making this problem easier.

Now, if $h$ is small, we're not making it much easier; if (for example) $p^k \ge 2^{256}$ and $h \le 4$, this would still appear to be an intractible problem.  On the other hand, I don't know if we want to make the attacker's job any easier than necessary, unless we gain some other benefit from it (perhaps making some other attack harder, or gaining some computational efficiency).

So, is there any benefit for using a curve with a cofactor > 1?

Montgomery and twisted Edwards curves have even order, but the group law can be implemented using fewer multiplications than Weierstrass models.  So that is why these curves are popular and we have to live with cofactors $> 1$.

There are other reasons to prefer to use prime-order elliptic curves (e.g., small subgroup attacks).  So you are right that in an ideal world one would used prime order curves.  But sometimes it is worth the trouble to use a more efficient curve model.