Does impersonating an SRP server give you enough information for an off-line dictionary attack? In a comment to an answer I wrote to another question, CodesInChaos wrote that:

"Problem with SRP is that an attacker who impersonates a server learns the password hash, enabling offline search."

and further that:

"If the server successfully impersonates a legitimate server [...] they learn the public key of the client. Knowing the public key allows a password guessing attack, which is only partially mitigated by using a good password hash."

This initially surprised me, since I'd somehow assumed that SRP was designed to avoid this kind of attack scenarios.  However, upon a closer review of the SRP design specifications, it does seem to me that this attack does work, and in fact seems unavoidable given the SRP design.
The point is that, to complete the authentication process, the client and the server must prove to each other that their keys match.  In SRP, the client is the first to send its proof (and the SRP design spec insists on this; I'm not sure what attack would be enabled if this were not done, but I assume there must be one, or the spec wouldn't be so explicit about it).  But this proof value must be something both the client and the (legitimate) server can compute, and thus it must be entirely determined by:

values chosen by the client and sent to the server during the authentication process,
values chosen by the server and sent to the client during the authentication process, and
the password and/or the verifier (which itself is determined by the password).

Thus, having received the client's proof, an attacker spoofing the server can now try to guess different passwords, keeping the other values the same, and see which password yields the same proof.
A technical detail to note here is that, in earlier phases of the SRP authentication process, the server is supposed to provide the client with the salt $s$ and public ephemeral value $B = kv + g^b$, which depends on the verifier $v$.
The first is not actually an issue for an impostor, since not only does SRP assume that the client won't verify the salt supplied by the server, but even if it does, obtaining the correct salt from the real server requires no authentication.  The second looks like it could be an issue, but as far as I can tell, it actually isn't: since the server never needs to (and indeed must not) divulge either $b$ or $g^b$ to the client, the impostor is can just pick any $B$ value they want without the client having any way to verify it.

Now, so far, everything looks clear.  But what's confusing me is the section "Computation of $B$" from the original SRP-3 paper (Wu, 1998), which, in explaining why $B$ is not computed simply as $B = g^b$, first describes what looks like exactly the attack outlined above and then goes on to say:

"Since this attack comes from an impostor who does not know $v$ (anyone who does know $v$ can already perform a dictionary attack), one way to thwart it is to force the host to commit to its value of $v$ in Step 4. [...]
"Modular addition appears to be the simplest operation that leaks no information about $v$ while at the same time enabling SRP to resist a dictionary attack by a fake host."

What I don't see is how including $v$ in the computation of $B$ would actually "force the host to commit to its value of $v$", since there's no way the client can actually verify that $B$ was computed in the specified manner.  Or maybe there is, and I'm just missing something?
So is the argument given by Wu in that section just complete nonsense, or is there actually something to it?  And if there isn't, is there any reason why the verifier $v$ should be included in the calculation of $B$ in SRP?  And, most of all, is SRP actually resistant to dictionary attacks by fake hosts, as the 1998 paper seems to claim, or isn't it?

Suppose the server did not include $v$ in the computation of $B$. In such case the following events have happened:

The server has sent a salt value $s$ to the client. We might assume it is authentic (because it is easy for the fake server to get it from the real server). The client re-calculates its long term private key $x$ such that $v = g^x$.
The client has generated a fresh random ephemeral key pair $A = g^a$ and sent $A$ to the server.
The server generates a random $u$ and a random $B$ and sends them to the client. The server might, or might not, know the value $b' = log_g(B)$.
The client calculates $S = (B-g^x)^{a+xu}$ and sends a proof of $S$ to the server.

Let's assume the fake server aborts the protocol at this point and attempts to mount an offline dictionary attack on the client password, in order to find the $x$ value.

Now, the problem is that the server is supposed to calculate $S = (Av^u)^b$, but that would require, for each guess at $x$, finding a value $b$ such that $g^b = B - g^x$. The "SRP assumption", if there is one, is that this is as hard the discrete log problem.

Conversely, should the fake server instead try to simulate the client calculation of $S$, it would require also guessing the ephemeral client private key $a$.

Is there any way around this? Yes, there is, but it requires that the server sends $B = 0$ and the client doesn't check for this. If $B = 0$, then we might infer that $b = x + (p - 1)/2$ (where $p$ is the prime field modulus). In such case $B = g^x + g^xg^{(p-1)/2} = g^x + g^x(-1)$, provided that $g$ is a generator of $\mathbb Z^*_p$. The offline calculation of the fake server, in such case, collapses to $S = (Ag^{ux})^{x + (p - 1)/2}$. This has only one unknown.

Edit:
It might be noted, with regard to the "SRP assumption", when e.g. $g = 2$ there are couple of special cases when the assumption is false. For instance, for arbitrary values $z$, ${2}^{z+1} = {2}^z + {2}^z$ and ${2}^z = {2}^{z+1} + 2^{z+(p-1)/2} \pmod p$.

As far as I can tell, all this means, is that if the server sends $B = 2v$ or $B = p-v$, it means that the server already knows both $v$ and $x$ and has selected $b = x$ or $b = x + (p-1)/2 + 1$ respectively. Hence, the server commits to $v$, but fails to hide it, or, alternatively, the server actually commits to $x$.


How much entropy do I need to add to passwords if they are NOT used in conjunction with logins I'm building a system to authenticate users to a website via a single use login token. This token can either be included in links OR typed in directly by the user as a code. Because of that second requirement I'm interested in the token being as short as possible in order to improve user experience.

There are plenty of guidelines regarding "regular" password strength, i.e. for a password to be used in conjunction with a login handle (email, username...). But in my case I believe the entropy needs to be higher since an attacker would essentially be targeting all users in the system at once when doing a brute force attack: if they guess any of the currently valid tokens they'll get into that random user's account.

So the solution needs to take into account how many valid tokens exist in the system.

So, if I can have up to $v$ valid tokens at any point in time in the system, how much more entropy do my tokens need to have? Do I just need to add $log_2(v)$ bits of entropy or is there something else to take into account? How can we prove that?

PS: I'm focusing here on the additional entropy required compared to "regular" password systems as a way to focus the discussion, as there are various measures that can be put in place to reduce required entropy (rate limiting, token expiration policies etc.) that could be applied, but this is not my question :)

Summarizing the question:

  I can have up to $v$ valid tokens at any point in time in the system, how much more entropy do my tokens need to have compared to "regular" password systems?

In addition to regular password entropy, $\log_2(v)$ bit extra is enough if the number of online attempts $a$ that an attacker can make is unchanged. That amount of additional entropy is necessary if you want no increase in the probability $\epsilon$ that $a$ online attempts succeed to find a working token, compared to the probability of logging into any account assuming the list of accounts is large and known to the attacker¹. Less extra entropy may be needed to maintain the probability that an adversary logs into a particular account², but how much depends on the distribution of passwords assumed in calculating password entropy.

Caution: Except when the system (rather than users) assign uniformly random password values, password entropy has almost nothing to do with the base-2 logarithm of the number of possible passwords. It varies widely with the restrictions put by the system on the choice of password, and with how dearly users care for the security of the data protected by the password. Also, that a certain password entropy is used is no proof that it is enough! And, the hypothesis of constant $a$ might not apply³.

Therefore, you can and should compute directly (without reference to a password-based system) how much entropy is needed in a token: that's $\log_2(v)+\log_2(1/\epsilon)+\log_2(a)$ bit⁴. The simplest and best is that the token is this many bits chosen independently and uniformly at random. That's assuming no information leak beyond correct/incorrect token, like getting an answer faster when the beginning of a token is correct, as notoriously occurs for comparisons using memcmp.

One may choose $\log_2(1/\epsilon)=20$ (slightly less that one chance in a million) and $a$ the number of possible attempts in a day given countermeasures³ to limit this in the server, or the sheer server capacity or link bandwidth absent such countermeasure. The estimation of $a$ should account for the possibility of concurrent attacks ($a$ is independent of network lag).

¹ Making the best attack strategy to test all accounts for the most likely password (or the few most likely ones starting from the most likely).

² Making the best attack strategy to test the account targeted for passwords approximately in decreasing order of likelihood.

³ Countermeasures to lower $a$ are easier with passwords and small user lists (or user lists assumed not to leak), because we can limit the number of login attempts per day/hour/minute and per user, something that might be impossible in the token context. Limiting the total number of attempts per second for the whole server opens to Denial of Service attacks, and limiting per attacker based on IP address is both difficult and uncertain: attackers may use multiple IP addresses using botnets, generate IPv6 addresses on the fly, or maybe spoof IP addresses if acting deep enough in the network infrastructure.

⁴ Proof for that formula: there are $k$ possible tokens, and $v$ of them are assigned uniformly at random and independently (except for being distinct). Attackers make $a$ attempts to log in by submitting a token, different at each time which maximizes their chances. Each attempt has the same probability $1/k$ to hit a particular token irrespective of the index of the attempt (for the same reason that the order in picking straws is immaterial to the probability one has to pick the shortest straw). Since these $a$ events are exclusive, the probability to hit any particular token in $a$ attempts is $a/k$. By the union bound, the probability $\epsilon$ to hit at least one of the $v$ tokens is at most $v$ times larger, that is $\epsilon\le v\,a/k$, and close to that for the low $\epsilon$ that we want in practice. Thus we want $k\ge v\,a/\epsilon$, and that only errs slightly, always on the safe side. Taking the base-2 logarithm, that gives $\log_2 k\ge\log_2(v)+\log_2(1/\epsilon)+\log_2(a)$.


How to calculate an IV when I have a shared private key? I'm working with a server/client system that has securely negotiated a private key. I need to encrypt/decrypt messages passing in both directions which are typically between 100 bytes to 100 KB. I'm working with AES-128 bit, but I cannot really understand how the private key is to be used with the encryption algorithm.

  "You should ALWAYS use unique IV's every time you encrypt, and they should be random. "

Based on the previous point, how can I calculate a 'unique' IV on the server and client, when all I have is the secure Key on both sides? Or is it fine to calculate a random IV and  send the IV on the wire? Wouldn't this open up a security hole?

Data: Small sized messages, often with repeating data.
Key: I've got a secure key on both sides.
IV: No idea how to calculate this. Key-derivation? Salted hash? PRNG?

Well, to start off with, IVs have different security properties than keys.  With keys (as you are well aware), you need to hide them from anyone in the middle; if someone did learn your keys, then he could read all your traffic.

IVs are not like this; instead, we don't mind if someone in the middle learns what the IV is; as long as he doesn't know the key, he still can't do anything with the encrypted traffic.  Because of this, one common practice is to have the encryptor select the IV, and then include it along in the encrypted message (generally immediately before the ciphertext).  This eliminates half your problem (how does the decryptor know which IV to use; he gets it out of the message); the attacker can see the IV as well, but (as above) we don't care about that.

So, the question comes down to "how does the encryptor select the IV"?  Well, the answer to depend comes down somewhat as to the mode you're using; the requirements for IVs differ depending on whether you're using CBC or CTR mode.

For CBC mode, the statement you list is mostly accurate (although I would write it as "You SHOULD use unique IV's everytime you encrypt, and they MUST be unpredictable"; there are known attacks against predictable IVs; I don't know if they apply to your scenario, but it's generally safer if we don't have to worry about them at all).  There are several ways do to this; a cryptographically secure PRNG (with good seeding) works.  Another thing that I've seen is you take a counter (say 0 for the first message, 1 for the second, etc), encrypt that (in ECB mode) with the same key you'll be encrypting the message in, and use that ciphertext as the IV.  This works because the ECB encryption of a counter is unpredictable to anyone who doesn't know the key.  Of course, if both ends of a bidirectional channel use this method, they need to either use different keys or make sure that their counter values won't overlap (e.g. one end could use only even values and the other only odd ones).
For CTR mode, the statement is less accurate; it would be more properly "You MUST always use unique IV's every time you encrypt; predictability is not a concern".   Because of this, it is common to use a counter as the IV; we get uniqueness (counters obviously never repeat within the lifetime of the key), and while it is predictable, we don't care about that here.  Now, there is one note: the uniqueness requirement doesn't just apply to the IV's, it also applies to the values you present to the block cipher.  Because of this, one common approach for CTR mode is to take the 16 byte AES plaintext block, and divide that up into (say) a 12 byte IV field and a 4 byte message index field; during the encryption of a single message, the IV field is always the IV value we are using to encrypt/decrypt the message, and the message index field increments for every block we encrypt; say, 0 for the first block, 1 for the second, etc.

Lastly, while you haven't specifically asked about this, I believe a heads-up is required; usually, when we encrypt a message, we generally need to use an integrity check as well (to make sure that the message received was the message sent); even if you don't particularly care about message integrity, there are several clever ways for an attacker to find things about about the encryption by modifying the cipher text, and seeing how the receiver reacts.  The short answer is that you should include some integrity transform (be it HMAC, CMAC, or replace the entire encryption operation with a primitive that does both privacy and integrity, say, GCM or OCB).  However, to fully discuss this requires more space than I should take up in the answer to a different question.


Why isn't f(G) uniform in ECDSA? In ECDSA, $f(G)=r$, where $r$ is the $x$-coordinate of group element $G$. My question is, how to prove this $f$ is not uniform? In other words, how to prove that, given a random element $G$ with different x-coordinates on an elliptic curve, $r=f(G)$ is not uniform over $\mathbb{Z}_q$? I would like to stress that here we see the group elements that share the same x-coordinate as the same ones.
I know in the paper ''On the Provable Security of (EC)DSA Signatures'', the author has talked about this. But I could not understand what they mean("On elliptic curves, for only about every second $x$-value a corresponding curve point exists; this is responsible for a
huge bias of the $x \bmod q$ function"?). Can anybody give a more clear explanation?

Hasse's bound tells that the order $n$ of [that is, number of elements in] an Elliptic Curve group is about the same as the order $p$ of the underlying field [note: $x$ and $y$ coordinates are elements of the field, points $(x,y)$ are elements of the group].
For every $x$ in the field with $(x,y)$ in the group, there is exactly one other point in the group with the same $x$: $(x,-y)$.
Therefore, about one value of $x$ in the field out of two is such that there exist $y$ in the field with $(x,y)$ [and $(x,-y)$] in the group. Like, if you have $n$ nuts and $p$ persons, with $n\approx p$, and you give two nuts to each person, then only about half the persons get a nut.
Therefore, $f$ as defined in the question is not uniform in the field, for it only reaches about half of the field elements.


ECDSA: What is the purpose of adding a hash of the used certificate to the signed data? I recently started looking into security mechanisms used for Car2Car communication according to DSRC/WAVE and ETSI.

What I found so far is that each packet is signed using ECDSA mechanism.
Also each packet either contains the certificate that is used for signing or some hash value identifying that certificate.
This certificate contains the public key that can be used to verify the signature.

What puzzles me is the way the signature is created.
I am aware that not the whole message is used for signing, but only a hash value.
But the way this hash is created, looks a bit strange to me:

Hash ( Hash ( Data ) || Hash ( SignerInfo ) )

where Data is the message or part of the message to be signed and SignerInfo refers to the certificate in use (or to an empty string in some cases).

Why is this second part required?

Hashing the message as well as hashing the certificate does not include any secret credential as both are transmitted within the message.

Given the public key from the certificate I can validate that the related private key was used for signing.

While the length of the 2 hash values isn't very large, it still means that I have to run a second round of hashing which is probably not done "just for fun".

Which benefit do we gain from this extra step?

It is probably a countermeasure to multi-user attacks.

In the classic (single-user) attack scenario the attacker wins if she manages to create a valid signature under a given public key, without knowing the private key. (note that a it is not request to obtain the private key, but just one valid signature)

In the multi-user scenario, instead, there are multiple public/private key pairs. And the attacker wins if she's able to create one valid signature under just one of the given public keys (the attacker can choice the target one).

The multi-user attack is believed to be easier than the single-user attack.
The high level idea is that the attacker's computation can be reused against any of the allowed public key, thus increasing its efficiency.

A common countermeasure, introduced in ed25519, is to create a stronger bond between the signer and the signature by including in the hash computation the signer's public key.
What you describe in the car2car scenario looks similar to that countermeasure as the forger needs to create hashes of the messages which include the signer's identity. This most likely remove the multi-user advantage compared to single-user.

Bernstein showed that adding the signer's key in the ed25519 hash computation protected against multi-user attacks.
Klitz et al. later showed a reduction from the multi-user to the single-user. Bernstein, however, disagrees with the paper conclusions.

To summarize, IMHO, adding the signer to the hash is very efficient and seems to provide a generic solution to concerns about multi-user attacks, while the reduction between multi-user and single-user for signatures is still unclear.


Hardness of problem related to bilinear pairings Let $e: \mathbb G_1 \times \mathbb G_1 \rightarrow \mathbb G_T$ be an efficient bilinear pairing. Note that the pairing is symmetric (i.e., Type 1).

The problem is, given $g \in \mathbb G_1$ and $e(g,g)^a \in \mathbb G_T$, for an unknown $a$,  to compute $X_1, X_2 \in \mathbb G_1$ such that $e(X_1,X_2) = e(g,g)^a$

Is this a hard problem? My feeling is that it is not and there should be an easy way to solve it.

Update 1: I have found a related problem that it is said to be hard:

  The Pairing Pre-Image Problem (PPIP) in $\mathbb G_1, \mathbb G_T$
  such that $\mathbb G_1 = <g>, |\mathbb G_1| = |\mathbb G_T | = p$ with
  pairing $e : \mathbb G_1 \times \mathbb G_1 \rightarrow \mathbb G_T$
  is defined as follows: On input a tuple $(g, Z) \in \mathbb G_1 \times$
  $\mathbb G_T$, output $X \in \mathbb G_1$ such that $e(X, g) = Z$.

According to this paper:
 CDH in $\mathbb G_1 \leq$ PPIP $\leq$ DL $\in \mathbb G_T$

The problem I am asking is not harder than PPIP since I could use PPIP to solve my problem : simply run the PPIP solver on $(g,Z)$, take output $X$, and return $X_1 = X, X_2 = g$. That is, PPIP is my problem but requiring that $X_2=g$.

Still, I think that there should be an easy way to solve my problem. Any ideas?

Update 2: Thanks to the comment from @DrLecter, now I know that the original problem I stated was exactly the Generalized Pairing Inversion (GPI) problem, which seems to be hard. That makes me reformulate the question to my real problem (see this question).

What you present is a generalized version of the so called fixed-argument pairing inversion (FAPI) problem. The FAPI problem is given an element $z\in G_T$ and an element $h\in G$ to compute $f\in G$ such that $e(h,f)=z$.

Note, that FAPI is implied by the computational Diffie Hellman problem: Given $(g,g^a,g^b)\in G^3$, call the FAPI oracle with $z\gets e(g^a,g^b)$ and $h\gets g$ and clearly we have that $f=g^{ab}$ which is a solution to the CDHP in $G$.

The generalized (GPI) version is that when given $z\in G_T$ to compute $h,f\in G$ such that $e(h,f)=z$. Obviously, GPI implies FAPI.

Pairing inversion is AFAIK generally believed to be hard. You may study this paper or this blog post for more details.


Paillier cryptosystem, small integers and range of values First, this a different take on my previous question: Pailler encryption of small integers to 32-bit integers

I have to encode small integers (range 0-50) using the Paillier cryptosystem. Those values will be encountered many times (100,000) in my dataset.

Version 1

I encode each of this 51 numbers with different r and therefore I get 51 different ciphertexts. The advantage of this method is that each time any ciphertexts are multiplied, e.g., MOD(c(1)*c(2),n2) I always get the same product.

The attacker knows that the range is small (<100) but looking at the 51 different ciphertext values, he can now guess that the range is 0-50 (0 is necessarily the smallest value). Does this make possible for him to actually get the plain texts from the ciphertexts?

Version 2

For each time one of these numbers are encountered in my dataset, I use different r. Therefore I now have 100,000*51 ciphertexts. Now it is impossible for the attacker to actually get the plain texts from the ciphertexts. But the problem is that each time any ciphertexts are multiplied MOD(c(1)*c(2),n2) I do not always get the same product [the plain texts 1 and 2 are encoded multiple times with different ciphertexts], although those different products will always decrypt to the same sum of plain texts.

Obviously, version 2 is more secure. But I would rather use version 1 for its simplicity and easier processing. Does the limited range of the values, makes cracking the Paillier cryptosystem easier?

Version 3

Let's put an intermediate version. For each value in [0,50] I use up to 10 (or more) different random values of r per value. Meaning that for plain text 0, I will get up to 10 ciphertexts. Overall, 51 plain texts => 510 ciphertexts. This should somehow limit the problems of version 1, without blowing up entirely.

With version 1, you are essentially using an additively homomorphic substitution cipher. I understand that the database is quite large, but the number of different values small. This (typically) means that statistical analysis can be used to derive a lot of information, especially if the attacker has some auxiliary information which is often the case. This is a very bad idea.

Version 3 is like version 1, but it's a bit harder to do the statistics. The problem is that the database is so big, that this may also be easy. Of course, it's very hard for me to judge how easy it is to do statistics without knowing the application and without knowing what auxiliary information is available.

Having said the above, your actual question is whether it helps the attacker to actually decrypt (say, with no auxiliary information whatsoever). The answer is no. In order to see why this is the case, consider a game whereby the attacker either receives encryptions of 0 to 50, or 51 encryptions of 0. It is easy to see that the adversary can guess which is the case with probability only negligibly greater than 1/2 (e.g., this is the multiple encryption experiment). Now, an adversary in this game can emulate the database assuming it has encryptions of 0 to 50 and can see what the adversary for the database can learn. If it can learn something, then it must be that the encryption adversary received encryptions of 0 to 50 (since encryptions of zeroes only reveals nothing).

In any case, please do not interpret the above as "approval" for version 1. I think that it's a VERY BAD idea, and strongly advocate for version 2.


Hardness of LPN problem with small secret The Learning Parity with Noise (LPN) assumption states that, for a fixed secret $s$ chosen uniformly from $\{0,1\}^n$, then the distribution that outputs $(a,a\cdot s+e)$, where $a$ is uniform in $\{0,1\}^n$ and $e$ is sampled according to a Bernoulli distribution $\mathsf{Ber}_\tau$ (with parameter $\tau\in[0,1/2]$), is pseudorandom.

My question is: Does the LPN assumption holds even if $s$ is chosen according to the same distribution as the error, that is, $\mathsf{Ber}_\tau^n$?

In other words, given $s$ from $\mathsf{Ber}^n_\tau$, is the distribution $(a,a\cdot s+e)$ pseudorandom?

There is a simple trick (known in the LWE literature as the Hermite normal form of the problem) that takes an existing LPN problem and transforms it into a problem in which the secret has the same Bernoulli distribution as the error. This trick is proved in Lemma 2 of Applebaum et al. for a more general case, or on the (Ring-)LPN attacks of Kirchner (Section 4.3.2) or Bernstein and Lange (Section 3).

The idea is that you start with a number of $n$ samples $(\mathbf{a}_i, c_i)$, where $c_i = \mathbf{a}_i \cdot \mathbf{s}$. Suppose, now, that some subset of the $\mathbf{a}_i$ vectors is linearly independent (you do not need much more than $n$ randomly-sampled $\mathbf{a}_i$ for this to be the case), and let them form the matrix $M = \{ \mathbf{a}_{i_1}, \dots, \mathbf{a}_{i_k}\}$. Then we have $$\mathbf{c} = M^T\mathbf{s} + \mathbf{e},$$ where $\mathbf{c} = \{ c_{i_1}, \dots, c_{i_k}\}$ and $\mathbf{e} = \{ e_{i_1}, \dots, e_{i_k}\}$ are the corresponding vectors to the chosen $\mathbf{a}_i$. But we also have $$\mathbf{s} = {M^T}^{-1}(\mathbf{c} + \mathbf{e}).$$

Now that we have this matrix $M$, query the LPN oracle with a new sample $\mathbf{u}$, receiving $(\mathbf{u}, v = \mathbf{s}\cdot \mathbf{u} + e)$. But you can convert this into a  second oracle that returns $(M^{-1}\mathbf{u}, \mathbf{c}\cdot M^{-1}\mathbf{u} + v)$.
Obviously, $M(M^{-1}\mathbf{u}) = \mathbf{u}$. Further,
$$
\begin{align}
\phantom{=}  &\mathbf{e}\cdot M^{-1}\mathbf{u} + e \\
= &(M^T\mathbf{s} + \mathbf{c})\cdot(M^{-1}\mathbf{u}) + e  \\
= &M^T\cdot\mathbf{s}\cdot M^{-1}\mathbf{u} + \mathbf{c}\cdot  M^{-1}\mathbf{u} + e \\
= &\mathbf{s}\cdot M M^{-1}\cdot u + \mathbf{c}\cdot M^{-1}\mathbf{u} + e \\
= &\mathbf{c} \cdot M^{-1}\mathbf{u} + v.
\end{align}
$$ So this is now an instance of LPN with Bernoulli-distributed secret $\mathbf{e}$, from which you can extract the original secret as $\mathbf{s} = {M^T}^{-1}(\mathbf{c} + \mathbf{e})$.

In other words, given some algorithm that solves LPN with a Bernoulli-distributed secret, you can also solve regular LPN with the same error distribution.


Is hashing data with dynamic keys still worth effort? some years ago it took long time to "decrypt" hashes because they took slow cpu to brute force. Nowadays they use graphic cards for stuff like this and can do this most time in less than 20 Minutes without problems.

So: Even if they don't take that long to decrypt hashes, would it still be worth time in developing, debugging and troubleshooting(, ...) or would they still take only minutes to crack a hash when using dynamic keys (never the same two) ...

Is there any kind of formula to calculate how much time they'd need like there is with normal hashes?

Your question is about breaking password hashing schemes (PHSs).

The usual way to break password hashes is by brute-forcing the input until you find a match between the resulting hash and the obtained hash.

Now there're some counter-measures to harden the schemes against various attacks that would allow you to break many passwords very fast, because most passwords are weak.

So let's build some formula to estimate the time you need to break a collection of given hashes $(h_1,h_2,...,h_n)$.

The first thing you do is think about how many values are actually possible for the passwords. Are they restricted to lower-case only? Do they actually use numbers? How long are they? This is expressed in the metric $NumberOfPossibilities$ which can usually be approximated by the size of the dictionary you use times the permutations you try. If you assume clever users you can computer $NumberOfPossibilities=NumberOfPossibleChars^{NumberOfChars}$.

Now we have to consider how much time do you need to actually try any of those passwords. Because if we'd consider 0-time we could instantly brute-force all passwords (which would be boring). This metric is called $TimePerTry$ and good programs use functions that require you to spend 100ms and more per try using PHSs like PBKDF2, scrypt, bcrypt or Argon2.

As you've expicilitly asked for different salt and pepper for each password you also need to consider each password by itself as they all have different salts. This is captured by $NumberOfPasswords$.

Finally you also asked for pepper, which is a value that is assumed to be need to be guessed by the attacker (and sometimes also by the defender). The amount of possible values for the pepper is captured by $NumberOfPossiblePeppers$.

This finally gives you the above mentioned formula $$NumberOfPossibilities \times TimePerTry \times NumberOfPasswords \times NumberOfPossiblePeppers = OverallTime$$ to calculate the overall time to break the scheme. The needed memory requirements (of own interest) and the parallelization can be calculated / inserted in a similar manner as the other values and I'll leave this as an exercise.


One Time Pads and "Bit Flip" Attacks One Time Pads and Vulnerability to "Bit-Flip" Attacks:

I've seen it in this group, and apparently there are a (small) number of voices on the 'net opining that those relying on OTP are essentially "amateurs" (or otherwise oblivious) to the possibility of "bit-flip" being a fatal flaw in OTP and they should NOT be used. Given my own professional experience using One Time Pads, I found these claims astonishing and was interested in learning if there was chink in the OTP armor rendering it an insecure system to protect data secrecy.

"Bit Flip" in the context of these claims being that the OTP message can be tampered with in transit- that there's no validation the recipient has received exactly the message that was originally sent. But even tampering doesn't imply that the attacker can read the text they tampered with sans a key. So as far as I can see at this point, the secrets still remain protected.

Further, in order to tamper with the contents of the OTP encrypted message would imply that the attacker knew exactly "when", "where", "how" and most importantly "who" the message was being transmitted to.  Those decrying One Time Pads as an insecure, flawed system are thin on details how an attacker would obtain this key these key pieces of data.

Such a claim is bold and it contravenes accepted wisdom that OTP encrypted messages are secure & unbreakable- if the system is operated correctly of course.  Am I missing something here?

accepted wisdom that OTP encrypted messages are secure & unbreakable

OTP encrypted messages are secure & unbreakable assuming the pad is secret, uniformly random, and not reused... and the message does not otherwise leak! The last point is where the "Bit Flip" attack comes to play.

Imagine the message is conventionally a digit send in ASCII, and parsed as such by the receiver after decryption; and that the context tells the adversary that a particular message is 1 or 2, that is the bitstring 00110001 or 00110010. With the OTP (or a stream cipher), the adversary can flip the 5th bit of ciphertext, and know that changes the plaintext to 00111001 or 00111010, that is the character 9 or :. Now if the adversary can sense whether the receiving system accepts the result as a digit, or rejects it, the confidentiality is lost!

More generally, when users of cryptography need encryption for confidentialitty, they tend to additionally need assurance of integrity and origin. The OTP only gives confidentiality, and as illustrated not unconditionally in some quite practical cases.

However, assurance of integrity can be obtained with an information-theoretic substitude to a MAC, or universal hash, such as Carter-Wegman; and when the OTP is shared among only two parties that gives assurance of origin. That consumes some of the OTP, but manageably so. And it can help mitigate the above attack (an altered message will be rejected before it is tested that it is decimal).

There remains two reasons making the OTP impractical:

It is easy for an adversary to mount a denial of service attack that de-synchronize sender and receiver (that can be solved to a degree, but is not trivial)
The random pad must be sent in advance by secure means, and kept secret on both sides.


What is a purpose of reducing lattice basis? This may be too broad question but it is not. I have been studying lattices for few months now, more specifically I studied:

Lattice problems ($SVP$, $CVP$ and etc.)
Lattice cryptography in post quantum computers
Worst-case hardness in Lattice cryptography
Public key encryption using Lattice
Lattice reduction algorithms (LLL and its running time)

However, I could not figure out the relationship with reducing a lattice basis and lattice problems. Essentially, why we should reduce a lattice basis? I know the goal of reducing lattice basis is to get short and nearly orthogonal basis vectors, but why? what is the bigger picture?
To be fair, during past few months of reading papers, I found only few only sentences (here, and there):

Reduced bases allow to solve the following important lattice problems (SVP, CVP), either exactly or approximately

It would be greatly appreciated if I could get a direction or hint or something to help me figure out the concept.

Lattice Reductions in Lattice Crypto

Well to start off, lattice reductions are of interest in the context of lattice crypto because, as already stated in other answers, they allow us to find short vectors in a lattice, which relates to SVP (finding the shortest vector in a lattice).

We care about solving SVP because it is believed that there may be a security reduction from Ring Learning With Errors (RLWE) to SVP. So if we can solve SVP (via some technique e.g. lattice reduction) we may be able to break schemes based on RLWE e.g. these homomorphic encryption and key exchange schemes.

It should be noted that reduction techniques such as LLL do not allow us to solve SVP efficiently for lattices in a high dimension and as such they are not effective for breaking these schemes.

Lattice Reductions in Number Theoretic Crypto

But there's also an application to "classical" number theoretic crypto. I'll explain one (of several) possible applications. Suppose we want to attack (EC)DSA where nonces are generated with biased bits. It turns out we can use a lattice reduction to recover the private signing key.

If we can get enough message/signature pairs that all used nonces with the same bias then we can actually write a system of equations (with each equation corresponding to a message/signature pair) that can be interpreted as a lattice (just like how you can might use an augmented matrix in linear algebra to represent a system of equations).

We can then actually perform a lattice reduction (e.g. LLL) on this system of equations. If we have sufficient message/signature pairs then with high probability one of the entries in the reduced basis will be the private signing key. The details of this attack can be found in this paper.

For more information on lattice reductions in this context I'd encourage you to look at the paper Lattice Reduction: a Toolbox for the
Cryptanalyst.


Using NIST SP 800 - 90Ar1 Test Vectors for HMAC_DRBG with Reseeding and AdditionalInput I'm trying to test my HMAC-DRBG implementation, but I do not understand how the AdditionalInput paramter should be used. From one test case (pr-false):

[SHA-256]
[PredictionResistance = False]
[EntropyInputLen = 256]
[NonceLen = 128]
[PersonalizationStringLen = 0]
[AdditionalInputLen = 256]
[ReturnedBitsLen = 1024]

COUNT = 0
EntropyInput = 05ac9fc4c62a02e3f90840da5616218c6de5743d66b8e0fbf833759c5928b53d
Nonce = 2b89a17904922ed8f017a63044848545
PersonalizationString =
EntropyInputReseed = 2791126b8b52ee1fd9392a0a13e0083bed4186dc649b739607ac70ec8dcecf9b
AdditionalInputReseed = 43bac13bae715092cf7eb280a2e10a962faf7233c41412f69bc74a35a584e54c
AdditionalInput = 3f2fed4b68d506ecefa21f3f5bb907beb0f17dbc30f6ffbba5e5861408c53a1e
AdditionalInput = 529030df50f410985fde068df82b935ec23d839cb4b269414c0ede6cffea5b68
ReturnedBits = 02ddff5173da2fcffa10215b030d660d61179e61ecc22609b1151a75f1cbcbb4363c3a89299b4b63aca5e581e73c860491010aa35de3337cc6c09ebec8c91a6287586f3a74d9694b462d2720ea2e11bbd02af33adefb4a16e6b370fa0effd57d607547bdcfbb7831f54de7073ad2a7da987a0016a82fa958779a168674b56524

So I would basically instantiate my DRBG with EntropyInput and Nonce.

HmacDrbg drbg = new HmacDrbg(new DrbgParameter(macFactory,
                entropyInput,
                nonce,
                new byte[0]));

Then before generating output, I would reseed the DRBG with EntropyInputReseed and AdditionalInputReseed

drbg.requestReseed(entropyInputReseed,additionalInputReseed);

But what should I do with the other 2 AdditionalInput inputs? The spec seems to only specify the reseed mechanic that takes AdditionalInput?

The other two AdditionalInput are to be used with the Generate function.

Page 47 of the spec describes it.

Step 2 of the algorithm performs:

 If additional_input ≠ Null then (Key, V) = HMAC_DRBG_Update (additional_input, Key, V)

Now, you might wonder why there are two strings AdditionalInput. Well, as described in the test spec there are two calls to the generate function for each test vector, so you have two additional inputs.
Note that only the second output of the generate is printed in the test vector.


Generating unbiased numbers with a biased six sided die? Eve takes a fair six-sided die and adds some heavy paint to the side of the die with the 6 on it. This results in a biased die that rolls a 6 with probability 2/7, and each other number (1-5) with probability 1/7.

If Alice learns that the die is loaded in this way, only has this die, and must generate 20 fair/unbiased random numbers between 1 and 6, what procedure can I propose that she can use to generate these fair numbers with this unfair die and computing how many times (exact or on expectation) Alice will have to roll the tampered die to conduct this procedure.

Each biased die result has >2.52 bits of Shannon entropy. Each unbiased die result has <2.59. So 21 biased rolls have more entropy than 20 unbiased ones.

Alice can concatenate 21 biased results into $r$ and use $r_i = H(s||r||i) \bmod 6$ as the unbiased results, where $H$ is a hash function like SHA-256 and $s$ is a unique salt she decides just before rolling.

(If Alice wants to cheat, she must use >$2^{52}$ work to find an $s$ with biased outputs. If this is insufficient, roll more dice or decide $s$ in a way that does not allow this.)


What's the likelihood of a collision if I use a hash to detect data change? I have a set of data that I want to sync, and instead of sending an entire set of data, I wanted to use a hash.

It is basically a list of GUIDs with either "true" or "false".

eaa54efe-2b10-4d3b-b9c2-30d2bcca7e06 : true
94297d72-573a-4e6c-a45e-37a390750b64 : false
36d1acbd-b2dc-4a90-a7be-fb65b63639a5 : true

I plan to generate a hash of the entire list so that I can send much fewer data to sync than the entire data set.

Should I ever be concerned that a specific change of true/false will happen to randomly result in a collision and become "undetected" or is that really not going to happen?

I don't really understand the math and proofs behind the hashes, but I also understand that good hashes are supposed to be designed against trivial collision.

Note: the main goal is just data comparison.  There is no encryption of the data because they're useless data without the meaning behind the GUIDs.  This is, literally, live data I just posted.

When syncing two data set over the internet one can basically two choices;

send all the data and compare: This is slow but complete.
send the hash of the data: This is very fast but there is a tiny-tiny-tiny change of a collision is almost zero. If you are that lucky, you probably become reach or hit by an asteroid. This is very common on Linux's CD/DVD image downloads.

In your case, you want to just send a hash of one huge list. If you fear that the almost zero ( $2/2^{256}$ for a 256-bit bash function) is bothering you, you can decrease the change below almost zero by taking another hash function to have two hashes, though not necessary.

and, yes, Cryptographical hash functions are designed to have collision resistance, however, over the time one might find better attacks than generic collision attack like SHA-1 and it has already removed from the standard. This attack, actually, searching for different inputs, where the data structure enables, to find a collision. And the generic collision attack is $2^{80}$ on SHA-1, that is low in today's standards if you consider that Bitcoin miners reached $\approx 2^{92}$ SHA-256 hashes per year in 06 Agust 2019. Reaching $2^{128}$ way beyond classical computing.

Stick to a good hash function, SHA-256, SHA-512, SHA3, Blake2.


Can someone steal the key between 2 clients which are using Symmetric Encryption? Can someone which is not authorized be able to listen between the conversation of 2 clients and catch the key? Because if I understood correctly one client needs to send the key through a channel so the another client could decrypt the data... So yeah that's my question; Can someone not authorized in that time frame catch the key and then start decrypting any data that passes through that channel?

In this answer I shall assume that the two relevant parties already share a strong symmetric key (ie not a password), which may have been established by e.g. using appropriate key agreement techniques (such as those used by TLS which may use asymmetric cryptography) or by e.g. physical, secure courier transport.

No, an attacker cannot learn the key or anything about the messages except their lengths if an appropriate (set of) encryption mechanism is used. In these protocols, the symmetric key is usually used to derive encryption and authentication keys and these are used to encrypt and authenticate messages between the parties. Man-in-the-middle attacks are then thwarted by the security of the symmetric-key encryption schemes as well as by the fact that the other party is authenticated by knowledge of the relevant symmetric key.

Additionally, sometimes the symmetric key is combined with the result of a run of the Diffie-Hellman protocol to gain extra security properties such as that when the symmetric key is leaked in the future, no past sessions can be decrypted.

One example set of protocols, that achieves these security properties given a shared symmetric key is the PSK ciphersuites from TLS.


DES Weak Keys - Double Encryption I know there are 4 known weak keys, their value and that double encryption using one of the weak keys should give back the plain text.

I implemented this in OpenSSL. I have a plain text $m$ in a file plain.txt and compute $y = DES_k(m)$ where $k$ is a weak key. Then I compute $y' = DES_k(y)$. Instead of getting $m$ I get only a portion of it and the rest is part of $y$.

Why is this happening?

If you don't get the expected result, then you are doing it wrong; most probably, use wrong mode of operation and/or wrong padding. You can get the expected result with openssl as

openssl enc -e -des-ecb -in plain.txt -out cipher1.txt -nopad -K 0101010101010101 -iv 0
openssl enc -e -des-ecb -in cipher1.txt -out cipher2.txt -nopad -K 0101010101010101 -iv 0

plain.txt file size should be multiple of 8 (8 bytes is DES block size), and plain.txt and cipher2.txt files should be identical.


Security Implications of Fixed & Opposite Fixed Points of Sbox Fixed point means when Sbox Input is equal to Sbox Output whereas Opposite Fixed Point means when Sbox Input is complement of Sbox Output. How does Fixed and Opposite Fixed Point affect the strength/ security of Sbox?


Would reuse of the symmetric key in a hybrid cryptosystem between files be inherently insecure? This question stems from a UX problem where I want to allow the user to input their PIN only one single time when they open up an mobile app. Here are some properties of the application to provide some context.

The user is on a mobile device with a bluetooth smart card reader
The data stored on the device is PII-data and national regulations (Sweden) state that the data must only be accessible via secure 2-factor auth
I'm planning to use a hybrid cryptosystem for the sensitive data
The symmetrical key will be decrypted with the smart card
I want to store the information for offline use so an embedded web browser for an online webapp does not cut it.
There will be multiple files that requires encryption, media for example will all be individual files.

Given these prerequisites I plan to have one symmetrical key defined for each unique user per app install.

This means any data synced to that app install for a single user will use the same symmetric key. This way I want to decrypt all files related to one user with the same symmetrical key. I consider it something similar to an OAuth2 token (but without the renewal part right now).

Please help me assess if there are any security flaws with this model!

Reusing the symmetric key in a hybrid cryptosystem may or may not be safe depending on the cryptosystem. To give a simple example, suppose a system was designed to use a single-use symmetric encryption key with a cipher in CTR mode, and it is now extended in such a way that the symmetric key is now reused for several messages but still shared with the same party. (If the protocol changes to share the symmetric key with a different party each time, that obviously affects security.) If the cryptosystem uses a random initial counter value, the same key could be used more than once without affecting security. If the cryptosystem uses the initial counter value 0, that's perfectly fine with a single-use key but catastrophic if the key is reused.

Having data which is encrypted with a long-term key which is unlocked at the beginning of a session is perfectly standard. Full-disk encryption does this, for example — typically the same key is used to encrypt all the successive versions of all the blocks of the encrypted device.

The basic idea of storing a symmetric key in a smartcard and having the card deliver it to the computer (a phone in your case) when the user enters a PIN is sound. The computer should keep the key only in RAM, and your application should wipe the key after a delay. How long a delay is a compromise between UX and security and depends on the nature of the data; you have to balance user convenience with the risk of the device being stolen.

There may or may not be value in encrypting each file with a different key. Having the card do the whole encryption and decryption is probably out of the question for both performance and UX reasons (the card would have to be present during all file accesses). But having the card release only one per-file key at a time may or may not make sense. You do need per-file keys if there is ever a reason why access to different files should be subject to different rules (e.g. you might want different timeouts on different files' keys). Per-file keys also offer better protection against a limited-time compromise (e.g. a rogue app that can extract the key from your app's memory but not inject code into your app). You can have per-file keys in two ways: either there's a single master key which the card releases upon request, and the computer does the key derivations; or the master key never leaves the card and the computer asks the card to derive each file's key when that file is accessed.

Whatever algorithm you pick, make sure to use it properly, in particular with a random IV for each file (stored at the beginning of the file). Note that if a file changes, the new version of the file must use a new random IV if it's encrypted with the same key.

You should use authenticated encryption (e.g. GCM), to prevent active attacks where a rogue app on the computer tries to decrypt bad data. Note that this means that a file must be decrypted (+authenticated) as a whole; you may need to split large files. Note also that authenticating a file only proves that it's some valid version of the file; it could be an old version, or it could be valid content of a different file unless you authenticate the relationship between a file's name and its content.

As a final note, modern major mobile platforms include protected environments that can store encrypted files with some protection against third-party applications and some form of user authentication (PIN or fingerprint) required for access (keychain on iPhone/iPad, keymaster on high-end Android phones and tablets). This satisfies the requirement of two-factor authentication. While it doesn't offer as a good a protection against attacks against the key at rest, it offers a better protection over what is a significant threat here, which is a rogue app on the device exploiting an OS bug to extract the key while it's in use. With the smartcard approach, the key is in your app's memory; with a keychain/keymaster approach, the key remains inside a protected environment, although the decrypted data would be visible to the rogue app anyway.


X25519 - why openssl shows 253 bits? When using ECDHE with Curve25519 with openssl:

Server Temp Key: X25519, 253 bits

I thought when we use X25519, it use 256 bit key.  Why openssl shows the server temp key as 253 bits?

The order of the base point of Curve25519 is the a 253-bit integer $2^{252}+ 27742317777372353535851937790883648493$. Choosing as private key a random positive integer less than said order is a common choice in cryptosystems based on the difficulty of the Discrete Logarithm in some group. That might be why private keys are said to be 253-bit.

However, per comment: the set of Curve25519 secret keys is defined as those 32-byte bytestrings which, when converted to integer (per little-endian convention on top of the byte level), form a 255-bit integer $n\in2^{254}+8\{0,1,2,3,\dots,2^{251}-1\}$. That bytestring is 256 bits, among which 251 are variable, and 5 are set to predefined values (the 3 low-order bits and 2 high-order bits: these are zero, except the second-highest order bit). Nothing reasonably adds up to 253.

Note: that's not to be confused with the security level, believed to be comparable to 128-bit symmetric cryptography (best attack cost $2^{140}$ bit operations).

References:

Daniel J. Bernstein, Curve25519: new Diffie-Hellman speed record, in proceedings of PKC 2006
Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang: High-speed high-security signatures, in proceedings of CHES 2011 and JoCE 2012.


Which functions can be used as Pseudo Random functions? Can block Ciphers be used for this purpose with our own encryption function? Since the cloud security algorithm I am trying to implement says that for a PRF, any secure encryption algorithm or a keyed hash function can be used. The security parameter I have chosen is 15 bits while AES and SHA use a large key size than this. So which block cipher and encyption function should I use for a PRF?

I would recommend against using ONLY 15-bits as a key for your encryption algorithm. A key size that small can be broken via brute force by any standard machine. There's a reason that AES (where the key can be 128 bits, 192 bits, or 256 bits) or SHA-256 are so widely used. The extended key lengths of those algorithms add security against brute force attacks from adversaries.


Is a hashing algorithm considered broken if a collision happens under $2^{n/2}$? If for example we would find a hash collision for SHA256 with $h(x) = h(x')$ for $x \ne x'$ and $x, \space x' < 128$ bit (meaning both $x$ and $x'$ are smaller than 128 bit), would SHA256 be considered broken?

Is it then always possible to create more collisions in a feasible time or could this hash collision just be considered an "anomaly"?

If for example we would find a hash collision for SHA256 with $h(x) = h(x')$ …

Yes, pretty much.  Now, I'm not certain what you meant by "$x \land x' < 128$ bit" (total bit length is less than 128 bits, or they disagree in at most 128 bits???), however, it doesn't really matter; finding any collision would demonstrate that SHA256 isn't quite as collision resistant as we had thought.

  Is it then always possible to create more collisions in feasible time or could this hash collision just be considered an "anomaly"?

If $x, x'$ had the same length (or, more generally, used the same number of SHA-256 blocks when hashing), then it's easy to find more collisions; we would have $h(x || Pad_x || y) = h(x' || Pad_{x'} || y)$ for any string $y$ (where $Pad_x, Pad_{x'}$ is the padding that SHA-256 applies when hashing $x, x'$).


How to check that you got the right key when brute forcing an encryption? How do you know when you have the right key when brute-forcing? Let's say that they test the right key. They then have to check that the decrypted text makes sense.  To do so, they can test whether there is a word in the dictionary.

But then let's say that the message is encrypted with Enigma then with RSA encryption. They try to brute force the RSA encryption but how do they do to know that they got the right key, since the text itself is encrypted with Enigma and has no word contained in the dictionary ?

First, you do not break RSA through brute force. RSA is an asymmetric encryption algorithm, with a public/private key pair. The public key has a strong internal structure, and unravelling it yields access to the private key (basically, the main component of the public key is the modulus, which is a big composite integer, and the private key is equivalent to the knowledge of the prime factors of the modulus). This can be done a lot more efficiently than trying out possible private keys; in fact, trying prime factors one at a time is a method known as trial division, and is about the least efficient of all integer factorization methods.

The bottom-line is that the attacker perfectly knows when he has found the private key, and he does not need to see any encrypted text for that.

Now let's suppose that you are not talking about RSA encryption, but a symmetric encryption algorithm such as AES. In that case, your question makes more sense, because:

In a symmetric encryption algorithm, there is no public key to work with, so the attack must proceed from some intercepted ciphertexts.
In symmetric encryption algorithms (at least the "secure" ones), the best known attack method is, indeed, brute force. Brute force is the generic method that necessarily works (at least in theory -- in practice we use keys that are large enough to make it totally infeasible); an encryption algorithm is said to be secure if no better attack method is known.

Enigma uses as input and output sequences of latin letters -- the 26 letters from 'A' to 'Z'. Modern encryption systems work on bits and octets, i.e. "binary data". If you cascade AES with Enigma, then you need some conventional representations of letters into bits, e.g. ASCII. You would, for example, map each letter of the Enigma output into an 8-bit byte, to be used as input to AES. Since 26 is not a power of two, it is unavoidable that this mapping will have "holes": there necessarily are some sequences of bits that could be a valid AES input, but are not possible as an encoded Enigma output.

This thus yields a valid strategy for our attacker: for each possible AES key, decrypt the AES layer, and see if the result is a valid encoded Enigma output. If not, the AES key is wrong, and proceed with the next one. If you used ASCII encoding, then a 16-byte output from AES decryption is a valid Enigma output encoding only with probability 1 in 7803076729492126.75 (approximatively). This comes from the fact that there are 25616 possible sequences of 16 bytes, but only 2616 possible sequences of 16 uppercase letters. This is an awful lot of power of recognition of bad keys by the attacker. If the attacker has access to two encrypted blocks (32 bytes, corresponding to 32 characters of Enigma output), then he will be able to pinpoint the single AES key that "makes sense". In all of this, the attacker never has to even begin to consider how he will break through the Enigma.

Of course, the above is quite artificial. You may imagine cascading algorithms that live in the same world; e.g. two symmetric encryption algorithms that both work over bits.

Cascading algorithms is a method of construction of bigger encryption algorithms. It is not a very good one, though. For instance, suppose that you cascade AES with another block cipher such as Serpent; or maybe you use two AES instances with two keys chosen independently. The hope may be to thereby produce a synthetic block cipher that will have twice the key length. But it does not deliver all these promises: the double-encryption method falls prey to the Meet-in-the-Middle attack (not to be confused with the unrelated Man-in-the-Middle attack). This schema may be enlightening:

So, by cascading two algorithms, you double the operational cost, but you do not get your money worth in security increase. To really get extra security, you must go to triple-encryption. This is why Triple-DES is triple-DES, not double-DES: the latter would not be substantially stronger than simple-DES.

It still is much simpler not to use weak algorithms at all. If you cascade AES with anything else, then either the "anything else" is completely useless, because the AES is already strong enough to defeat brute force attacks; or you use the AES really poorly and that is what you should fix first.


Verify correct answer transparently The following problem needs to be solved:

Person A will be guessing the number that Person B has in mind.
Only Person B can confirm that the answer provided by Person A is correct.
Person A can not be sure if Person B is fair

Is there any cryptograhpic way to achieve something like this:

A third party will generate a random value X which both Person A and Person B are able to see in an encrypted form
Only once Person A has guessed value X, it should be possible for Person A and Person B to decrypt value X.

All ideas and suggestions are welcome on how to achieve this. Thank you!

All ideas and suggestions are welcome on how to achieve this.

It sounds like commitments should be one way to handle it.
A commitment scheme is a method where:

Someone (person B) can generate and publish a commitment to a secret value; someone else (person A) looking at the commitment learns nothing about the secret value (we say that this is the 'hiding' property of the commitment scheme.

Later, person B can open the commitment; they publish the secret value and a proof that the committed value corresponds to the secret value (which anyone can verify).  We insist that person B cannot generate a proof to any secret value other than the one in mind when they generated the commitment (we say that this is the 'binding' property of the commitment scheme.

In your case, person B will initially generate a commitment to the number he has in mind.  Then, when person A has published his guess, person B will open the commitment, and show whether person A's guess to the secret value was correct or not.
The simplest commitment scheme is a hash based commitment; to generate a commitment to the value X, person B would select a fixed size random value r and publish $\text{hash}( r || X )$ (where $\text{hash}$ is a collision resistant hash function, such as SHA256 or SHA3); to open the commitment, you would publish $r$ and $X$.  This is simple, however sometimes you need more from your commitment scheme (such as the ability to generate proofs about your commitments, for example, that the committed value is not the value that person A guessed (without revealing the correct value); if so, then Pedersen commitments make that a lot easier.  I don't know enough about what you need from a commitment scheme to advise you which way to go.


Product of Vigenère ciphers is not a Vigenère cipher with length of LCM I have always thought that using two Vigenère ciphers leads to another Vigenère cipher with key length of LCM (least common multiple) of the two previous Vigenère ciphers. But I have stumbled upon this problem:

  Let $\mathcal{V}_1,\mathcal{V}_2, \mathcal{V}_3$ be Vigenère ciphers with key length $l_1, l_2\in\mathbb{N}$ and LCM$(l_1,l_2)$. Prove that for some $l_1, l_2\in\mathbb{N}$ is not $\mathcal{V}_1\times\mathcal{V}_2\approx\mathcal{V}_3$.

I have tried with some lengths but it worked so that the product was Vigenère with length of LCM. Would you give me example of lengths for which it doesn't work?

I have tried with some lengths but it worked so that the product was Vigenère with length of LCM.

Actually, the statement really isn't "is encrypting with cipher $\mathcal{V}_1$ and the cipher $\mathcal{V}_2$ always equivalent to some cipher $\mathcal{V}_3$.

Instead, it's "are the set of transforms that you can express by first encrypting by some transform (I'll say key, even those the members in the set are technically transforms and not keys) in $\mathcal{V}_1$ and then by some key in $\mathcal{V}_2$ precisely the same as the set of transforms you can reach by encrypting by some key in $\mathcal{V}_3$."

Expressed that way, it should be obvious that, for some lengths $l_1, l_2, LCM(l_1, l_2)$ there are keys in $\mathcal{V}_3$ that cannot be reached by $\mathcal{V}_1$ followed by $\mathcal{V}_2$

To take a simple example, if $l_1 = 2$, $l_2 = 3$ and we're doing Vigenère in base 26.  In this case, the total number of transforms that can be expressed by $\mathcal{V}_1$ and $\mathcal{V}_2$ is at most $26^2 \times 26^3 = 26^5$ (and it's actually less than that).  However $\mathcal{V}_3$ contains $26^6$ transforms, hence there must be quite a number that are not reachable via $\mathcal{V}_1$ and $\mathcal{V}_2$


Does 3-DES take approximately the same time to encrypt 1B and 1KB? I am using 3-DES to encrypt some data in Java. I decided to run some tests and plot some graphics to decide how to optimally pack data for its encryption (see how encryption/decryption time behave depending on the length of the plain text), so I measured the time to encrypt one thousand Strings of incremental size (first one of length 1, second one of length 2, etc.) and then did the same the other way around (decrypt the first results).

I find that the decryption time increases with the size of the resulting plain text, although the time/character decreases as a rule. However, for encryption all the tests take approximately the same amount of time (it takes as long to encrypt a 2-character String than a 1000-character String, ~0.003 ms).

Is this something inherent to 3-DES, to how Java implements it or maybe I measured the time wrongly?

This is both a DES (or any block cipher) and a programming concern. It is not a problem, just something to be aware of.

The reason time/character decreases with larger plaintexts is that the initial overhead and memory management takes up the bulk of time with small inputs. With large inputs (megabytes+) the time/char will stabilize to a fairly consistent number. Memory management techniques and encryption mode of operation also effect overhead. Making a copy of the plaintext instead of reading its memory space directly into the block cipher state for example.

DES processes blocks of 64-bits, which is 8 bytes at a time. So your time per character between 0 and 8 will be the same, as it is processing a single block.

There is also the accuracy of the measurements, which in Java is probably not using a high precision event timer, and will therefore be extremely inaccurate in measuring events that take small fractions of a second to complete. Try using a hand stopwatch to measure something that takes 0.02s to complete for example, you will never get a consistent or even accurate measurement.

Because block ciphers are fairly quick in processing block inputs, you will need to process several megabytes of data in order to get a more accurate time/block. Try 8 million bytes to start. You will need to increment the data size to get to around 10s of processing time before you can get an accurate time/block.


How to derive two keys from one password What is the best way to generate two independent symmetric keys from one user-entered password or passphrase?
Would using both scrypt and pbkdf2 achieve this?

Yes, scrypt achieves this.  Scrypt has a variable-length output, so just generate as much output as you need.  For instance, you can ask it for 256 bits of output, then use the first 128 bits for one key and the second 128 bits for the other key.

While PBKDF2 also has a variable-length output, I do not recommend that you use it in the same way.  It has a subtle disadvantage/weakness which slightly reduces its available security if you ask it to generate more than one block of output.  Instead, I recommend that you use PBKDF2 like this:

Kt = PBKDF2(..., passphrase, salt, n, 128)
(K1, K2) = PBKDF2(..., Kt, salt, 1, 256)

In other words, use PBKDF2 with lots of iterations (choose $n$ to be large) to generate a 128-bit temporary key $Kt$; then use PBKDF2 a second time to stretch $Kt$ into 256 bits of pseudorandom output, and use that to form the keys.

What's wrong with just asking PBKDF2 to give you 256 bits of output?  It turns out that, due to a subtle issue, this may let an attacker get a 2x speedup.  Or, another way to think about: it forces legitimate users to do twice as much work as they ought to, which means you can't push the iteration count up quite as high as you should, so you get weaker security than you could have gotten.  The subtle issue is described at a high level in this Ars Technica article; a blog post has more technical details, as does an explanation from 1password.

Basically, the issue is that with PBKDF2, an attacker who wants to test a guess at your password can generate just the first 128 bits of the 256-bit output twice as fast as generating the whole thing, and the first 128 bits may be enough to verify whether the guess is correct.  Scrypt does not have this issue (when used with typical parameters), so with scrypt, you can just ask it for 256 bits and you'll be fine.

Don't try to use both.  There's no need to use both scrypt and PBKDF2; and if you do use both (scrypt to generate one key, PBKDF2 to generate the other), then you will have introduced the same subtle weakness described above, just in a slightly different guise.

Bottom line recommendation. If this sounds too complicated: just use scrypt, and ask scrypt for as much output as you need.  You can ignore all the rest.


Elliptic Curve Cryptography insecure when input does not lie on the curve? I am new to Elliptic Curve Cryptography and I was reading up on it online when I came across this link. It stated the following.

  Unfortunately, there is a gap between ECDLP difficulty and ECC security. None of these standards do a good job of ensuring ECC security. There are many attacks that break real-world ECC without solving ECDLP. The core problem is that if you implement the standard curves, chances are you're doing it wrong:

  Your implementation produces incorrect results for some rare curve points.
  Your implementation leaks secret data when the input isn't a curve point.
  Your implementation leaks secret data through branch timing.
  Your implementation leaks secret data through cache timing.

So, I was curious about the second point. How is it possible to leak secret data when the input isn't a curve point. I am assuming it means the base point(P) is not on the curve, but then how would P+P be calculated and how would it make the implementation insecure?

Suppose you publish a public key $P = [n]G$ for a secret scalar $n$, where $G$ is the standard base point.

If you are willing to tell me $H([n]Q)$ given $Q = (x, y)$ for any coordinates $x$ and $y$ of my choice, then I can send you a point $Q$ of (say) order 2 on some other curve whose arithmetic law happens to coincide with the curve you meant to use, and learn $H([n]Q) = H([n \bmod 2]Q)$.

How does this work?  Suppose you use the short Weierstrass form $y^2 = x^3 + a_4 x + a_6$.  Since the addition law doesn't involve the constants $a_4$ or $a_6$ at all, and the doubling law involve only $a_4$, it turns out that you will happily compute scalar multiplication of points on any curve with the same $a_4$, so all I need to do is find some $a'_6$ whose curve has low-order points.

When I get back the answer, it is either $H([0]Q) = H(\mathcal O)$ or $H([1]Q) = H(Q)$, so by examining which one you returned, I can learn $n \bmod 2$.  The same applies if I send a point of order 3, 4, 5, etc., and I can combine the results with the Chinese remainder theorem to interactively compute the discrete log $n$ of your public key $P = [n]G$ with your help.

Of course, if you expose the point $[n]Q$ instead of the hash $H([n]Q)$, then my task may be even easier!


Elliptic curve point multiplication — who is wrong? I am relatively new to ECC, but my understanding is that the result of a point multiplication must still be a point on the curve. I have implemented an ECC calculator in Python, to add and multiply points on any curve mod p.

My misunderstanding is about the curve defined $y^2=x^3+2x+2 \pmod{17}$, with $\# E=19$. As $19$ is prime, Lagrange's theorem implies that all points except the point at infinity are generator points for the cyclic group. Considering the generator point $p=(5,1)$, my program says the result of $891p$ is $(6,14)$, while other online calculators say the result is $(11,3)$, but this point is not even on the curve!. Nearly always, both my own and online programs agree on the resultant point, but occasionally, like in this example, they do not.

Any help on this issue is appreciated, as to who is correct?

The (very useful!) computer algebra system sage says the correct result is indeed $(6,14)$:

sage: E = EllipticCurve(Zmod(17), [2, 2])
sage: E
Elliptic Curve defined by y^2 = x^3 + 2*x + 2 over Ring of integers modulo 17
sage: P = E(5, 1)
sage: 891 * P
(6 : 14 : 1)

Those "online calculators" you used appear to be broken.


Use AES in CTR mode with pycrypto The doc of pycrypto gives an example of using AES in CTR mode:

>>> from Crypto.Cipher import AES
>>> from Crypto.Util import Counter
>>>
>>> pt = b''*1000000
>>> ctr = Counter.new(128)
>>> cipher = AES.new(b''*16, AES.MODE_CTR, counter=ctr)
>>> ct = cipher.encrypt(pt)

I think this isn't safe for encryption of multiple messages with the same key because the counter value defaults to 1. Would it be safe if I do:

iv = os.urandom(16)
ctr = Counter.new(128, initial_value=int.from_bytes(iv, 'big'))

Some articles recommend a timestamp-based nonce (e.g. 64-bit timestamp + 64-bit random value). I was wondering if it's OK to simply draw a 128-bit random value with urandom, and if this implementation is flawless.

Probably the best thing to do is to decide the maximum message size in bytes, then divide that size by 16 (the block size), call that $m_c$. The number of bytes required to encode $m_c$ is called $l_c$.

Create an IV of 16 bytes and randomize the first (leftmost) bytes, leaving at least $l_c$ bytes at zero. You then have a non-repeating counter of size $l_r$ bytes where $l_r = n - l_c$. That means that you can encrypt about $2^{l_r * 8 - 64}$ messages with the same key while still having a rather small chance of ever repeating the random nonce $r$ and thus the counter.

Time stamps are dangerous, an attacker can try and control the time, clocks can get out of sync, and there may be precision related issues. Time stamps are therefore commonly not used to create nonces - for encryption modes anyway. You don't want to use /dev/random either. Generally /dev/urandom is secure and at least it doesn't block.


How to adapt the equation of Gaussian mechanism noise based on number of executions I'm trying to build a differentially private machine learning model. I'm using the Gaussian mechanism to calculate the required noise amount based on pre-defined privacy budget value
The equation to find the noise amount is below
$\sigma = \sqrt{2ln(1.25/)} / \varepsilon $
I'm aware that when the model performs several epochs, say 15, I will need to use either the naive composition or the advanced composition theorem to calculate the new $\varepsilon'$
$$\varepsilon' = \sqrt{2k\log(1/\delta)}\varepsilon + k \varepsilon (e^\varepsilon-1)$$
1. I'm interested to know how to adapt the first equation and use it to compute the total amount of noise to be dded based on the number of executions (epochs)

The formula you mention to get $\sigma$ given $\delta$ and $\varepsilon$ is only correct for $\varepsilon<1$. It's also not tight.
If you use Gaussian noise on multiple statistics, each of sensitivity 1, and want to get the tightest possible privacy guarantees, then you should use the Analytic Gaussian Mechanism instead (Theorem 8), replacing $\Delta$ with the square root of the number of your statistics. It's tight and works for any value of $\varepsilon$ and $\delta$.
The only problem with that approach is that there's no formula giving $\sigma$ as a simple function of $\varepsilon$, $\delta$ and $\Delta$; so you have to do some binary search to find the best possible value (and be careful about how you do the floating-point calculations). Here is an example from our open-source differential privacy library.
Finally, if what you want to do is train a model in a DP way, I would suggest using existing tooling, like TensorFlow Privacy, rather than rolling your own.


How can I factorize a 350 bit (106 decimal digits) number in two prime factors? I have this large number:

1728098743723095094470726818328193358068864405124007684733613106475812450278961107574624070107782941006379

which is the multiplication of two unknown large prime numbers. I try to factorize it with the "Yafu" tool, but i get an error of "time exceeded.

How can I factorize it? How many time will it take?


Binary verification of application image before loading it into DRAM Working on a boot process where the application image has to be verified before loading it into DRAM.

We found 2 strategies;

RSA-1024, where the private key is secure in premises and the only public key is distributed with out boards. (Is it better if up-gradable to RSA-2048?)
AES-256 with CMAC, same key available both board and premise.

As they are symmetric and asymmetric, it is difficult to compare them directly. Like to understand, which is best suited for binary signature verification during boot process?

The obvious flaw of approach 2. is that you need the same key to sign and verify.
This means that whoever reverse-engineers one device and gets out the verification key can now sign their own application images which will be accepted as genuine by other devices.

The standard way of application signing is by using asymmetric algorithms (RSA-2048 is a minimum, or ECDSA-256). That way the device has only a public key (hopefully stored in a read-only memory so that it's not replaceable) and no one is able to sign application images even if devices get reverse engineered.


Clarification on the TLS verification process I am reading this article in my attempt to understand how the TLS verification and chain of trust works. In the piece I come across a section that I am not sure I understand.
In the simplified description of how the browser validates a certificate you have this:

The client, which is a browser for ease of explanation here, has two processes that it must complete to validate the signature. The first process is to take the signature on the bottom of the certificate and decrypt it with the CA's public key. This public key comes from the CA's intermediate certificate which should be delivered by the server during the connection at the start of the TLS handshake. This tells us that if the CA's public key can decrypt it, the CA's private key must have encrypted it. This means it definitely came from the CA in question because only they posses the private key. The second process is for the browser to calculate its own hash of the Pre-Certificate to compare to the hash stored in the signature and determine if they are identical

But not sure if this portion is correct:

The first process is to take the signature on the bottom of the certificate and decrypt it with the CA's public key. This public key comes from the CA's intermediate certificate which should be delivered by the server during the connection at the start of the TLS handshake.

Is the portion that says the public key is delivered by the server correct? I would have assumed that the browser uses the pre-installed public key of the CA in this step.
Is the article wrong? Or am I the one who has got things wrong?

The article is wrong, but not there. It's the previous sentence that's incorrect. "The first process is to take the signature on the bottom of the certificate and decrypt it with the CA's public key." Emphasis mine: signatures aren't encryption, decrypting them isn't what the client does, the client verifies the signature. This is unrelated to your question, but it's important not to confuse encryption/decryption with signing/verification, since doing so can lead to major security issues. Such confusion is only really possible with RSA, many other public-key systems don't have any real notion of encryption/decryption to begin with. Confusing basic terminology like this is good reason to stop reading any article about public key cryptography. Confusing signing and encryption is like confusing addition and division: vaguely related, sort of swapped (signing is closer to decryption in RSA though still different), and generally a sign that the article wasn't written by anyone competent.
To answer your question, the server sends a chain of certificates. Each certificate in the chain contains a public key, a name (a domain for the server, an organization name for a CA), some extra information, and a signature covering all that. The signature was created by the private key of the next certificate in the chain, and can be verified by that certificate's public key. At one end there's the certificate of the web site, which doesn't sign any further certificates, and at the other end there's a "root" certificate. This "root" is the only thing that gets preinstalled by the browser. The browser can verify that the named root in the chain has a pre-installed certificate. Then the browser can verify that the next certificate's signature was made by that root, etc down the chain. If all the signatures verify, the final website certificate can be trusted to belong to that domain's owner.
In practice those certificate chains can be short. Lots of CAs are trusted as roots for these chains. For example, this site has (at this time) a certificate for *.stackexchange.com which is signed by the Let's Encrypt R3 certificate (Let's Encrypt is a CA), which is in turn signed by the Internet Security Research Group ISRG Root X1 certificate (ISRG is the organization that runs the Let's Encrypt CA). Browsers trust ISRG Root X1 directly, and verify that it signed the Let's Encrypt R3 certificate. Then they verify that the Let's Encrypt R3 signed the certificate for *.stackexchange.com. Only 3 levels in the chain.


Is it possible to have identical public keys for different ciphers? Is it possible (and is there any research I can read) to have 2 key pairs for different ciphers, for example RSA 1024 and some yet to be released EC (or other asymmetric cipher) than uses 1024 bit keys, that have the same public key?

There's not really a good way to answer your question other than to explain the concepts involved. The answer can be any one of "yes", "no", or "it depends".

Asymmetric encryption algorithms use public keys that have some structure. For instance, RSA public keys are a tuple of $(n,e)$, where $e$ is the exponent, and $n=pq$ for some primes $p$, $q$ unknown to all but the holder of the private key. In modern systems, $n$ will typically be on the order of 2,048 or 4,096 bits. ECC keys, on the other hand, consist of a point $(x, y)$ on an agreed-upon elliptic curve. In typical ECC schemes, each of these points will be on the order of 192, 256, or 384 bits.

Semantically there will not be colliding keys between these algorithms, because the constituent components of these keys have different meanings. On the other hand, it's technically possible (but exceedingly unlikely in practice) to create, say, a 512-bit RSA key whose $(n, e)$ is also a point $(x,y)$ on an elliptic curve used in ECC. Or, whose bit representation of $n||e$ is equal to the bit representation of a point on an elliptic curve $x||y$.

On the other hand, if two different ECC elliptic curves intersect, you could have a point $(x,y)$ that lies at that that intersection and works for both curves. One could also hypothesize the existence of a future cryptosystem that uses public keys of the form $(n,e)$ as RSA does, but isn't RSA.

However, most cryptosystems that handle public/private keys encode the type of key and additional parameters into the public key file, so it's impossible in practice to ever have a public key that will work natively for two different types of cryptosystems.

TL;DR, it's plausible that one could find colliding keys between different ECC schemes. It's not totally inconceivable to find a colliding key between RSA/ECC by either bit representation or by actual colliding $(n,e)=(x,y)$. And it's not out of the question for some new cryptosystem to reuse keys from an existing cryptosystem verbatim. But in practice, no real world software is likely to be able to use an single public key file for more than one cryptosystem.


Why Elliptic curve cryptography are not popular in practice RSA and ElGamal can be implemented using the technique of Elliptic curves. I am confused on why the it seems that Elliptic curves are not so popular in cryptographic applications since they provide the same security with smaller key sizes?

It is true that elliptic curves allow the same security with smaller key sizes. However, the size is not the only important aspect. Familiarity of algorithm, ease of implementation, performance, how many independent implementations exist, etc. affect how widely algorithm is implemented.

For Elliptic Curves, like many other technologies one factor slowing down the adoption has been patents. EC2m was previously considered "patent mine field" and there are also some patents on ECP techniques.

Elliptic Curves are still fairly new, and for security levels usually deployed, it is very common that in practice performance of RSA, DSA or DH exceeds ECC of similar security strength.

For larger security levels (around 192-bit or 256-bit security strength, i.e. 384-bit - 521-bit ECC curves), the required DSA/DH primes or RSA modulus grow so large that ECC usually wins in performance.

So, in my experience the reasons for smaller adoption are: difference in complexity, smaller speed on usual key lengths, patent risks, and the fact that there are less implementations than of, say RSA.

I have seen Elliptic Curves getting some attention and deployments and it seems to be growing. The drivers for that (which help with ECC adoption) seem to NIST's transition to higher key lengths (see SP 800-131A) and NSA Suite B. There are very few applications where the difference in key length is significant differentiator.


Security of authenticated encryption modes GCM & CCM I have two questions for Clarification for AE mode choice criteria

GCM : it  appears to be actually the most popular and widely used AE mode of operation. however it is also well-known to be highly sensitive (more than other AE modes ?) to IV uniqueness requirement and completely fails if such requirement is not respected'. I personally in regard with planned target domain of application consider this as a weakness . So such weakness should not weight in the criteria for AE mode selection ? Remain GCM the one of most powerful AE mode despite this weakness ? Isn't EAX or OCB if no more patented a more efficient & secure choice ?
CCM : I understood via such mode review that it is based on MacThenEncrypt procedure (CBC-MAC then CTR ) . So why is  such mode always presented as candidate AE mode if only Encrypt-Then-Mac procedure seems actually recommended by cryptography experts ?

Regarding GCM mode and the uniqueness of the nonce, it should be noted that EAX mode and OCB mode also require unique nonces. One potential problem EAX mode has, which neither GCM or CCM have, is that it is hard to implement it in such way that you can guarantee that the probability of nonce collisions is zero; only that it is acceptably low. OCB mode has been revised a number of times due to attacks such as this one against one of the earliest versions of OCB mode.

Regarding the security of CCM mode, this paper provides a security proof that explains the use of a CTR-encrypted CBC-MAC, with the conjecture that it is stronger against birthday attacks, compared to an unencrypted CBC-MAC. Hence, as a consequence CBC-MAC-then-CTR-Encrypt is actually stronger than (naive) CTR-Encrypt-then-CBC-MAC. The security of EtA versus AtE is consequently a rather complex matter. Generally it is probably best to regard dedicated proofs for a specific mode, as trumping proofs for the generic compositions. The security properties of CCM are well understood, so I doubt many security experts rule against it just because it is not EtA. A better argument against CCM is that it requires two AES operations per block, while other AE modes only require one.


What is the impact of different modes on pseudo randomness of AES? AES in CBC-MAC mode is proven to be good PRF . But is there any study done on other modes ? how good is ECB mode as PRF ?

Yes, of course other modes have been studied.

See this paper for one study, and that paper for another study.

The bottom line is that CFB, OFB and CTR modes are also good PRFs (assuming you use random IVs).

As for ECB mode, it is a good PRF if you limit it to inputs of precisely one block (128 bits for AES); it is not a good PRF if you are allowed to submit larger inputs.


Should the field size in Shamir secret sharing scheme be larger than secret? I'm playing around with implementing Shamir's secret sharing scheme in Kotlin.
Here is implementation so far:
fun main(args: Array<String>) {

val a = 10.0.toBigDecimal()
val b = 10.0.toBigDecimal()
val c = 7.0.toBigDecimal() // secret
val field = 20.0.toBigDecimal()
 fun polynomial() : (BigDecimal) -> BigDecimal =
    { x : BigDecimal -> ((a * x.pow(2))+(b*x)+c).remainder(field)}

fun generateShares(one :BigDecimal, two : BigDecimal, three :BigDecimal): List<Pair<BigDecimal,BigDecimal>> {
    var shareSet = arrayOf(one,two,three)
    return shareSet.map { x ->  Pair(x, polynomial().invoke(x)) }
}

val shares = generateShares(1.0.toBigDecimal(), 2.0.toBigDecimal(), 3.0.toBigDecimal())

fun langraged(cord0 : Pair<BigDecimal,BigDecimal>,cord1 : Pair<BigDecimal,BigDecimal>,cord2 : Pair<BigDecimal,BigDecimal>) : (BigDecimal, BigDecimal) -> BigDecimal{
    val L0: (BigDecimal) -> BigDecimal = { x -> ((x - cord1.first)*(x - cord2.first)) / ((cord0.first - cord1.first)*(cord0.first - cord2.first))}
    val L1: (BigDecimal) -> BigDecimal = { x -> ((x - cord0.first)*(x - cord2.first)) / ((cord1.first - cord0.first)*(cord1.first - cord2.first))}
    val L2: (BigDecimal) -> BigDecimal = { x -> ((x - cord0.first)*(x - cord1.first)) / ((cord2.first - cord0.first)*(cord2.first - cord1.first))}

    return { x, field -> // This lambda is what I am asking about
        val resser = cord0.second * L0(x) + cord1.second * L1(x)  + cord2.second * L2(x)
        if (resser < 0.0.toBigDecimal()){
            (resser % field) + field}
        else {
            resser % field
        }
    }
}

val constructedPolynomial = langraged(shares[0], shares[1], shares[2])

val reConstructedSecret = constructedPolynomial(0.0.toBigDecimal(), field)

println("and we reconstruct f(0) as: " + reConstructedSecret)

}

So the gist of my question here is about the usage of my field size, that I use for modulo.
With this implementation, if I choose a field that is larger than my secret then I will only be able to reconstruct the part of the secret that is remainder after dividing by the field size.
In other words, In order to reconstruct my polynomial, when using a field I have to return
result % field

So for example, if my field is 50, and my secret 51, then my reconstructed secret is 1.
So, in order to use Shamir's scheme with  a field, is it necessary for the field to be larger than my secret? or is there some trick I can do to reconstruct it?

So the gist of my question here is about the usage of my field size, that I use for modulo.

Well, the first thing to notice is the definition of a 'field' (which is a term from mathematics); I don't feel like getting into a discussion of what a field is (look it up in Wikipedia if you're interested), however addition and multiplication modulo a composite (such as 50) is not a field, and Shamir Secret Sharing won't work there.
If you replace 50 with 53 (which is prime), then it would work.
In practice, we often use a extension field $GF(2^k)$ for $k$ perhaps 8 or 16 or 32; that makes things nicely line up in bytes, however the operations are not modulo the field size (the 'addition' operation is actually exclusive-or, and the multiplication operation is significantly different than what you're used to).  Of course, it's up to you if you want to look into that; you might want to learn the basics with a prime field (which is what you're using) first.
In any case, to address your question:

So, in order to use Shamir's scheme with a field, is it necessary for the field to be larger than my secret? or is there some trick I can do to reconstruct it?

Well, a single iteration of Shamir's secret sharing will always return a field element (that can be interpreted as a value between 0 and the field size minus one); hence if you need to share a secret that may be larger than the field size, we generally divide the secret into a number of smaller secrets, and share each subsecret independently.
For example, if you have a 16 byte secret, we may divide that into the 16 values of one byte each; for each byte value, we may generate a secret polynomial modulo 257 (a prime), and distribute shares for that.  When it comes time to reconstruct, we construct each of the byte values independently, and then concatenate them to form the original 16 byte secret.
Just a word of warning: you must generate an independent secret polynomial for each byte - reusing the same polynomial (except for the constant term) breaks the system.  On the other hand, you can use the same $x$ coordinate for each of the subsecrets when you give a share to someone.
Now, with $p=257$, each share will be somewhat larger than the original secret (because each secret share is a value between 0 and 256; that doesn't quite fit into a byte).  That's why using $GF(256)$ is popular; each secret share is a value between 0 and 255, and so everything fits nicely...


Speed up modular exponentation with fixed base and modulus Can someone explain, how $a^x \mod N$ can be speeded up, when $a$ and $N$ are known constants? How big is the gain and what resources are needed?

https://www.imperialviolet.org/2013/05/10/fastercurve25519.html

Just to mention: it can speed up SRP hashes bruteforce, which is calculated as  $v = g^x \mod N$ where $x = hash(username, salt, password)$

One obvious way is to precompute values $a^{k_1} \bmod N$, $a^{k_2} \bmod N$, ...,$a^{k_i} \bmod N$, and (depending on the value of $x$) multiply together the appropriate elements.

To take a simple example, if we precompute $a^1 \bmod N, a^2 \bmod N, a^4 \bmod N, ... a^{2^k} \bmod N$, and (based on the value of $x$ in binary, multiply the appropriate elements together); this gives a method which takes an average of $1/2 log_2 N$ multiplies, which is an obvious improvement over what you can do without any precomputation.

The paper gives a slightly more aggressive example (treating $x$ as a base 16 rather than a base 2 number).

However, you can do even better: see this paper for a survey of the various possibilities.

One note: if you are performing operations on an Elliptic Curve (that is, doing a point addition rather than a modular multiplication), then the operation of computing the inverse of an element is cheap; even though the cited paper doesn't cover that case, that can be used to reduce the number of operations even further.


Is error propagation desired in modes of operation I'm taking a very simple class on cryptography. The class is not mathematical is just the very basics. We learned about modes of operations recently (such as CBC and CTR), one of the things I learned was about error propagation. I just don't quiet understand if this is a desired effect or not. Sorry for such a simple question, but unfortunately my class doesn't have textbooks, it's just slides, and when I have questions is difficult to look for answers. Thank you.

It is neither desirable nor undesirable on its own.  Error propagation is not relevant to any modern cryptography.  The concept is a relic of an archaic school of crypto engineering that has been left to the junk heap of the previous century, but not all textbooks or instructors with job requirements to teach courses called Cryptography 101 have kept up with the state of the art.

What is relevant is authentication.  If there is any chance that an adversary might have the power to interfere with the channel between two peers—whether by intercepting packets on the wire or by compromising the server where messages or stored or what—then the peers should have a system for authenticating messages so that any changes an adversary makes have negligible chance of going undetected by the recipient.

If the peers already share a secret key that they could use with a block cipher, then, instead of picking a block cipher and a mode of operation as last century's school of engineering prescribes, they should pick an authenticated encryption scheme.  This is a gizmo that takes a key, a message sequence number, and an arbitrary bit string as a message, and turns it into a ciphertext which the recipient can use the same key to detect modifications in and, if unmodified, turn back into the message.

One example of an authenticated encryption scheme is NaCl/libsodium crypto_secretbox_xsalsa20poly1305.  Another example is AES256-GCM.  AES256-GCM happens to be built out of the block cipher AES-256, but this is an implementation detail—you should think of it as picking AES256-GCM as a unit, not picking AES and then a 256-bit key and then GCM as a mode of operation.  crypto_secretbox_xsalsa20poly1305 is not built out of a block cipher at all, and has some advantages over AES256-GCM—faster and safer in software, larger message sequence numbers so you can safely randomize them.


Equality checking using additive homomorphic encryption Given two ciphertexts $c_1 = enc(p_1)$ and $c_2= enc(p_2)$ using any additive homomorphic encryption scheme (or specifically Paillier).

Can we find out whether the underlying plaintexts $p_1,p_2$ are equal without decrypting $c_1,c_2$ i.e. homomorphically?

I'm not sure if I understand what you are asking, so I'll clarify what I am about to answer. We are given two ciphertexts and we want to know if they encrypt the same plaintext or if they encrypt different plaintexts, and we want to do this without revealing anything but this fact.

Then, using the additive homomorphism, it's possible to compute $c=enc(r\cdot (p_1-p_2))$. If $p_1=p_2$ then this is an encryption of 0; else it's an encryption of a random value.

Now, let's consider the setting where one party holds the private key and the other has $c_1,c_2$. Then, the 2nd party can compute the above as I showed and send it to the first party. The first party can then decrypt and see if it is 0 or not. There exist ways for the first party to prove this to the second party efficiently.

I hope that this answers the question.