Shamir secret sharing with no dealer Suppose we have a set of $N$ parties. I am looking for a scheme to generate shares of a random secret $s$ where any subset of the participants with size $k$ can recover the secret similar to Shamir's scheme. Additionally, no party outside of the group, such as a dealer, has access to $s$.

I think this can be done relatively simply with any additive secret sharing scheme (which Shamir's scheme is). The basic idea behind the scheme (to make a $(n, k)$ no-dealer secret sharing scheme) is:

Each party samples a uniformly random value $s_i\in\mathbb{F}_p$
Each party makes $n$ shares of this value (using an additive $(n, k)$ secret sharing scheme), which we will call $\{s_{i, j}\}$ for $j\in[n]$
For all $(i, j)\in[n]^2$, Party $i$ sends $s_{i, j}$ to party $j$.
For all $i\in[n]$, party $i$ sets $s_i' = \sum_{j\in[n]}s_{i, j}$
All parties are left with a sharing of $s' = \sum_{i \in[n]} s_i$

The idea for why this should be secure (up to the threshold $k$) is that there are really three things an adversary can do:

Choose $s_i$ non-uniformly (and among the $k-1$ parties, choose them dependent in some way)
Send out "incorrect" shares of their secret
Compute $s_i'$ incorrectly

The first two points can be seen to be equivalent, as sending out "incorrect" shares is the same as sending out correct shares of an incorrectly sampled secret.
If you know a group of honest parties will reconstruct the secret, these incorrectly sampled secrets will not be an issue (the sum $s' = \sum_{i\in[n]}s_i$ will be uniformly distributed as long as any $s_i$ is individually uniformly distributed, and all other secrets are independent of this value).
I don't know how tolerant the above will be to corruptions during the reconstruction process, but it doesn't seem like this is what you're asking about. I imagine it would be roughly as tolerant as the "base" additive secret sharing scheme is, but don't have a readily available argument (so will omit this, while mentioning that it's an interesting thing to think about).
This also has relatively high communication complexity ($O(n^2)$ in the sharing process --- it feels like $O(nk)$ might be possible, but I don't want to over-optimize it right now), and can only sample secrets on fields $\mathbb{F}_p$ for which Shamir's is secure (so you must take $p$ to be exponentially large, so it is wasteful in the size of communications (instead of just the number of messages) if you only need a "small" secret to be agreed upon), which seem like the major "downsides" of it to me.


Must a line hitting two points on the elliptic curve over a finite field hit another point by continuation? The Arstechnica article title as "A (relatively easy to understand) primer on elliptic curve cryptography" claims this;

In fact, you can still play the billiards game on this curve and dot points together. The equation for a line on the curve still has the same properties. Moreover, the dot operation can be efficiently computed. You can visualize the line between two points as a line that wraps around at the borders until it hits a point. It's like, in our bizarro billiards game, when a ball hits the edge of the board (the max) and then is magically transported to the opposite side of the table and continues on its path until reaching a point, kind of like the game

and provides an animation (It is a GIF see on the page, can't link here).
And I've made a similar test that achieved the same;

The simple curve is $E\colon y^2=x^3+4x+20$ over $\mathbb{F}_{29}$ and $P=(1,5), Q=(5,7)$ and $R = P+Q = (16,2)$ is drawn on the figure.
I've followed the same step, draw a line passing through $P$ and $Q$, and continue from the opposite edge when an edge is hit!
The green lines are the borders+1 of the possible elements, the blue lines have used for (visual) check the continuation.
Now enough experience;
If the claim on the Arstechnica is theoretically correct then what is the theory?

The question asks to prove the (true) fact that, in order to perform point addition $R\gets P+Q$ graphically on an Elliptic Curve over the field $\mathbb F_p$ of equation
$y^2\equiv x^3+a\,x+b\pmod p\tag{1}\label{fgr1}$
with $p$ suitably small (here $p=29$, $a=4$, $b=20$) and
$4\,a^3+27\,b^2\not\equiv0\pmod p\tag{2}\label{fgr2}$
we can (except in the special case¹ of $P$ and $Q$ equal or on the same vertical line) perform the geometric construction of $R$ per the figure

Draw on a (black) square grid of side $p$ the points of the curve (blue dots) other than the neutral².
Draw a red line that starts from $P$ parallel to and in the direction of $\overrightarrow{PQ}$.
As soon as the line hits a point of the curve other than $Q$, call it $R'$; then on the vertical (purple) line going thru $R'$, find another point of the curve and call it the result $R$ of $P+Q$.
If the red line hits a side, draw an horizontal or vertical (green) line from there to the opposite side; then from that intersection keep drawing the red line parallel to and in the direction of $\overrightarrow{PQ}$, and iterate to the above bullet.

After drawing the red line for a displacement of $d$ along the $x$ axis starting from $P$, and accounting for the wraparound on the sides, the pen drawing the red line has coordinates
$\begin{align}x&=(x_P+d)&\bmod p\tag{3}\label{fgr3}\\ y&=\left(y_P+d\,\frac{y_Q-y_P}{x_Q-x_P}\right)&\bmod p\tag{4}\label{fgr4}
\end{align}$
with the computations in $\mathbb R$. Justification: What's on the left of the $\bmod$ operator³ in $\eqref{fgr3}$ and $\eqref{fgr4}$ is the position of the pen having moven by $d$ along the $x$ axis if we did not wraparound on black edges. The $\bmod$ operators capture the effects of the wraparound.
The points on the red line with both coordinates an integer (including but not limited to any point of the curve) thus have a corresponding $d$ an integer, and verify
$(y-y_P)(x_Q-x_P)\equiv(x-x_P)(y_Q-y_P)\pmod p\tag{5}\label{fgr5}$
And any $(x,y)$ matching this equation would be on the red line if we kept drawing it indefinitely; $P$ would be reached when $d=p\,(x_Q-x_P)$ (or earlier).
It follows that our graphical search procedure for $R'$ hits a point of the curve (and thus terminates), and yields a point $R'$ which coordinates $(x,y)$ involves integers that verify $\eqref{fgr1}$ and $\eqref{fgr5}$. But we have not shown yet that $R$ obtained from $R'$ is the expected point (we have not ruled out that $R'=P$ or some other unwanted point of the curve).
An intuitive argument is that when we remove the $\bmod p$ from equations, and work in the field $\mathbb R$ instead of $\mathbb F_p$, $\eqref{fgr5}$ becomes the equation of the line going thru $P$ and $Q$ in the Euclidean plane (with coordinates in $\mathbb R$). Our graphical procedure that draws the red line and finds a third point on the curve that the line intersects is thus a mere translation⁴ in field $\mathbb F_p$ of the graphical construction of point addition on the curve with the same equation in the field $\mathbb R$, and must thus "work", in the sense of yielding a commutative group law on the set of curve points and neutral.

Alternatively, we can make an analytical proof that this graphical procedure terminates and yields the same $R$ as the usual formulas for point addition on the curve of equation $\eqref{fgr1}$ with $\eqref{fgr2}$, that is when $x_P\ne x_Q$
$$\begin{align}
\lambda&\gets(x_Q-x_P)^{-1}(y_Q-y_P)&\bmod p\tag{6}\label{fgr6}\\
x_R&\gets\lambda^2-x_P-x_Q&\bmod p\tag{7}\label{fgr7}\\
y_R&\gets\lambda(x_P-x_R)-y_R&\bmod p\tag{8}\label{fgr8}
\end{align}$$
Note: In this, all quantities are elements of $\mathbb F_p$, or equivalently integers in range $[0,p)$. In particular, $(x_Q-x_P)^{-1}$ is a modular inverse.
Proof sketch, which mostly⁴ parallels a possible demonstration of the point addition formulas for the same equation in the field $\mathbb R$:

We analytically show that $\eqref{fgr1}$ and $\eqref{fgr5}$ are verified by $(x,y)\gets(x_R,(-y_R)\bmod p)$ computed per $\eqref{fgr6}$, $\eqref{fgr7}$, $\eqref{fgr8}$.
The condition $\eqref{fgr2}$ allows to prove $x\ne X_P$ and $x\ne X_Q$.
Thus the point with these coordinates $(x,y)$ is on the red line drawn indefinitely, and neither $P$ nor $Q$.
When we eliminate $y$ from equations $\eqref{fgr1}$ and $\eqref{fgr5}$, we get a cubic equation in $x$ in the field $\mathbb F_p$. It thus has at most 3 distinct solutions. Two of these are $x_P$ and $x_Q$, and the third is the above $x$, neither $x_P$ nor $x_Q$.
Since our graphic procedure start from $P$ and skips $Q$, it must reach a point with that $x$ before reaching $P$ again.
Hence the $R'$ of our search procedure has the $x=x_R$ of $\eqref{fgr7}$
Points of the curve on the same vertical line share the same $x$, thus the same $y^2\bmod p$ per the curve's equation. It follows that the $R$ graphically constructed has the coordinates $(x_R,y_R)$ of $\eqref{fgr7}$, $\eqref{fgr8}$, Q.E.D.

¹ This special case subdivides into

$P\ne Q$, in which case $P+Q$ is the neutral².
$P=Q$. One graphical construction chooses two distinct points $S$ and $S'$ on the same vertical line, both distinct from $P$, and computes $(P+S)+(P+S')$. When $S$ can be chosen on the same horizontal line as $P$, that simplifies drawing the red line for $P+S$. I know no more direct graphical analog to the "tangent" technique used for a curve in the field $\mathbb R$.

² The neutral is an extra point of the curve, not on the figure, often noted $\infty$ or $0$, such that for any point $S$, $S+\infty=S=\infty+S$.
³ The $\bmod$ operator has a canonical extension from $\mathbb Z$ to $\mathbb R$: we can define $u\bmod m$ with $u\in\mathbb R$ and $m\in\mathbb R_+^*$ as $v\in \mathbb R_+$ with $v<m$ and $(u-v)/m\in\mathbb Z$.
⁴ The only operational difference is that for the Elliptic Curve in the field $\mathbb R$ we must draw the red line in both directions, when that's optional here because we're in a finite set and the line ultimately wraparounds back to $P$.


Significance of IV in Merkle-Damgård construction Is Merkle-Damgård essentially encrypting the IV with the given message? I may be wrong but this is how I understand Merkle-Damgård:

  There is a message of an arbitrary length, which is broken up into blocks before it can be encrypted; the blocks can be padded if necessary. Then a fixed IV is used and the first block of the message is run through a compression function using something like AES (possibly derived from a block cipher) with the IV. The output is then taken as the IV for the next round. In the end, the resulting output is the same size as the IV.

What is my error in understanding?

broken up into blocks before it can be (hashed)... Then a fixed IV is used...

In practice, you may not even know the entire message before beginning hashing. So this is incorrect. You divide into blocks as more of the message becomes available.

  before it can be encrypted

You are not encrypting. You are hashing.

  the blocks can be padded if necessary

Padding is always added, not only added if necessary.

  the first block of the message is run through a compression function using something like AES (possibly derived from a block cipher) with the IV

So this is sort of correct. We don't use AES, but the constructions are similar/derived from block cipher principles. The key requirement is that the compression function should be collision resistant. With a block-cipher, you typically need to be able to undo the encryption. This is not necessary for a hash function's compression function.

Specifically related to AES, another reason we don't just use AES is that is only has a 128 bit block size. This is insufficient for the types of hashes we see today, which have at least a 224 bit output (SHA-2). The internal state must be wider than 128 bits.

P.S., thanks to fgrieu for some additional points that I have added.


Is using Euler's Totient/phi in Tonelli-Shanks (used to recover EC coordinate) safe? I'm implementing an algorithm in order to recover the $y$ co-ordinate from $x$ in order to construct a co-ordinate pair that satisfies secp256k1's elliptic curve equation, which is:
 $y^2 = x^3 + 7 \bmod q$.

$q$ is a prime and $q \equiv 3\bmod 4$ (I've checked) so we should be able to use:

$y = (x^3 + 7 \bmod q)^{\frac{q+1}{4}}.$

However, the size is limited to 256 bits and so $\frac{q+1}{4}$, which I'm calculating by $(q+1) \times 4^{-1}$, will be taken modulo $256$. I'm scared of this making the overall result wrong, so I was thinking of using Euler's totient and taking $\frac{q+1}{4} \bmod (q-1)$, as $\phi(q) = q-1$ due to $q$ being prime.

Is this safe? I can't find it recommended anywhere and I feel like it would be a good optimisation if it was actually safe to use, and so would be noted somewhere?

As user94293 says, $q\equiv 3\bmod4 \implies q+1\equiv0\bmod 4$ hence $\frac{q+1}{4}$ is an integer. Clearly it is smaller than $q$ and larger than $0$, hence reducing it mod $q-1$ does not change anything. Hence in your circumstance everything is okay.

In a bit of a more broad context, determining whether something is "safe to use" depends on context. What can generally go wrong is that execution time of an algorithm is dependent on some secret data. An attacker will exploit this timing dependency to gain information about the secret, which is indeed a problem. So in this case you can ask yourself two more general questions:

What information could an attacker learn if you were to compute $$\left(x^3+7\right)^{\frac{q+1}{4}\bmod{q-1}}\bmod{q}$$ as opposed to
$$\left(x^3+7\right)^{\frac{q+1}{4}}\bmod{q}?$$
As long as you don't compute either one or the other depending on some secret, both are fine. Note that this includes that we could choose to compute a square root by doing
$$\left(x^3+7\right)^{\frac{q+1}{4}+1000(q-1)}\bmod{q},$$
but we won't because it is not efficient.
What data is actually being processed? I'm not aware of the details of the protocol you are working with, but in many cases $x$-coordinates of points are part of public data. In that case even if you do the exponentiation based on the value of $x$, an attacker can still not learn anything secret.

In short, it is important to remember that it is not important for an algorithm to be constant time, but to have run-time independent of secret data.


What is the difference between a bijective random oracle and a random permutation? Assume

$S$ be a finite set
$O$ be a random oracle from $S$ to $S$, such that $O$ is bijective
$f$ be a random permutation of $S$

Is there any difference between $O$ and $f$?

Does it makes any difference if $S$ is not finite?

At some level, there is no essential difference.  Certainly, there is no difference in the distribution on the random variable $O$ vs $f$.

However, there is a potential difference in how the terms are typically used.

If we say that $O$ is a random (bijective) oracle, then we are usually implicitly hinting that it is available to everyone: the legitimate parties, the attacker, everyone -- anyone can supply an $x$ and get back $O(x)$.
In contrast, if we say that $f$ is a random permutation, we have not yet made any commitment about whether it is made available as an oracle to everyone, or whether it is closely held.

Hopefully the set of parties who have access to $O$/$f$ should be made clear elsewhere (e.g., in the formalization of security), so there is no real danger of serious confusion, but this might serve as a hint to let readers know what to expect.


generate a hash and validate if subset of string belong to that hash I am trying to find if I can generate some encoded data from set of string and compare if the subset belong to that encoded data.
Say
encoded data : 11187bcb32536890a9cb307865b027af565cb2f74b7d498fa4def5c3fde53721 (sha256)
keyitem : item1
item1 sha256 code is : 5f3c4f8580d392e422e7c2f6802674ac27966c98d95c39696e4b2490168e5488

is there any way to check if item1 is part of this encoded data without deciphering it ?
I do not want to use base64_encoding. Looking for little bit robust way of doing this.

In case hash is shorter than strings that are hashed it is not possible.
Suppose there is such algorithm $isSubstring(x, h)$ that tells if a string $x$ is a substring of a string $S$ whose hash is $h$.
If hash is shorter than message, then there are at least 2 different strings $A$ and $B$ that both produce the same hash $H$:
$hash(A) = hash(B) = H$
Sinse $A$ is a substring of itself, it holds
$isSubstring(A, hash(A)) = isSubstring(A, H) = true$
Sinse $B$ is a substring of itself, it holds
$isSubstring(B, hash(B)) = isSubstring(B, H) = true$
Then:
$isSubstring(B, hash(A)) = isSubstring(B, H) = true$
This means, $B$ is substring of $A$.
Also:
$isSubstring(A, hash(B)) = isSubstring(A, H) = true$
This means, $A$ is substring of $B$.
Thus, $B$ is substring of $A$ and $A$ is substring of $B$. This is only possible if $A$ and $B$ are equal. But we choose $A$ and $B$ that are not equal. This means that the assumption that such function exists is wrong.


Logarithmic brute-force for stream-ciphers First of all, I want to make sure I understand stream ciphers correctly:
I put a plainchar (e.g. byte?) through the stream cipher and receive a cipherchar. Correct?

When I now have a pair of plaintext/ciphertext, I could then brute-force all secrets which map plainchar[0] to cipherchar[0]. For the next character, I only need to try those passwords which succeeded for the first one. This way the brute-force search space is reduced logarithmically.

Is this correct?

Update As @poncho pointed out correctly, the search space is not reduced logarithmically, but the expensive encryption operation which generates the ciphertext for the plaintext. This has to be done for every tried password which is every possible password for brute-force.

This way the brute-force search space is reduced logarithmically.

Well, no.

If there are $N$ possible keys, then you test $N$ keys on the first byte.  Then, you keep only those that succeed on the first byte, and test those on the second byte; that's approximately $N / 256^1$.  Then, you test those keys that succeed on both bytes, that's approximately $N / 256^2$ keys.

When you count the total number of keys you've tested (including those you tested multiple times), you come up with an expected:

$$N + N/256^1 + N/256^2 + N/256^3 + … = (256/255)N$$

And, $(256/255)N$ is not a "logarithmic reduction" over $N$...


How to derive a 4096 bit or 8192 bit RSA private key from a (BIP39) mnemonic seed? How to derive a 4096 bit or 8192 bit RSA private key from a (BIP39) mnemonic seed?

Any tool available for this?

As it was already pointed out in a comment by @corpsfini, you could use a PRNG to generate pseude-random numbers from the seed. Then you would check whether they are primes using some probabilistic primality test.

In spirit the same procedure is implemented in this github repo you might find useful.


How do we know a cryptographic primitive won't suddenly fail? It took more than a decade from when MD5 looked like it was going to break to the point when it was actually broken. That's more than a decade of warning. One might suspect that we were fortunate that we got all that time. Even so, it took a long time for the world to move away from MD5.

How can we be sure that when our cryptosystems are flawed, that we'll have enough warning time to change them?

How can we be sure that, say, ECC won't get broken overnight?

We don't.${}{}{}{}{}{}{}{}{}{}$

Moderator note: This answer exists for historical significance, but it does not meet the guidelines for answering questions, so please do not use it as evidence that you can post similar answers here. This answer and its comments are frozen and cannot be changed. More info: meta.


Signing an exchanged symmetric key that is asymmetrically encrypted Consider the following implementation:

  Bob wants to communicate long-term with his team over an unsecured channel. Bob and all members of the team generate individual public/private keypairs (ex. RSA) and store/share their public keys on an untrusted key server.

  Bob, being the first member of the team, also generates a long-term random symmetric key for the team that he and all team members will use to encrypt their communications. Bob encrypts the team's symmetric key with his public key and also the public key of all current members of the team and stores them on the same untrusted key server.

  When new members are added to the team, Bob (or any existing member of the team that can add new members) takes his own encrypted version of the team's symmetric key from the key server, decrypts it with his private key, then copies and re-encrypts it with the new member's public key, storing it back on the key server for the new member to use for future communications with the team.

The problem with this implementation is that the symmetric key can be forged by Eve, a bad actor with access to modify the key server. Since public keys are all available, Eve could take Bob's (or any and all members of the team) public key and encrypt a new symmetric key on the key server. Past communications would then fail to decrypt, however, if gone unnoticed by the team any future communications could be read by Eve. If the forgery occurred when the symmetric key was first stored, no member of the team would ever know that Eve has been reading their communications.

I think that we need some sort of signature on the symmetric key exchange, however, where would the key material for this signature come from? How could we produce a signature in a way that each member of the team could privately verify that their version of the team's symmetric key is authentic? Maybe some other way?

Update #1

One solution could be for Bob to compute a hash of the symmetric key whenever he first generates it, then sign the hash with his private key and store it on the key server. Whenever members retrieve their copy of the symmetric key from the key server, they could also obtain Bob's public key, verify the hash's signature and recompute the hash to verify the symmetric key.

However, the problem I see with this solution is that it seems Eve could still forge a new symmetric key, sign it with her private key, and replace Bob's public key with hers on the key server. This would allow her to impersonate Bob's signature while other team members verify and use the forged symmetric key.

Your scenario seems overly simplified but anyway:

Just have Bob sign the key that he uploads.

You're assuming that people know each other's public keys anyway. So everybody can verify that the key has been signed by Bob.

If you want to keep your one-to-one trust structure the people adding new team members could also sign the key again or just sign that they trust Bob.


What is the best encryption protocol to encrypt streaming video? I am building a SoC to capture and encrypt video at once. I would like to understand what encryption protocols are available to encrypt the video stream.

The video stream will be coming from a camera sensor, like a CCD. If necessary it can be pre-processed on the SoC into a particular format (for example to compress it) before being encrypted. It can also be encrypted from its RAW format if possible. The encryption protocol should have an efficient hardware implementation that can be implemented on SoC.

The goal of this embedded system is to achieve the highest possible security by reducing potential hardware or software attacks on the Soc that might expose the clear video stream to the attacker.

Note that this is a self contained chip, and the video data will not be sent over WiFi or network. It stays inside the chip.

I am building a SoC to capture and encrypt video at once. I would like to understand what encryption protocols are available to encrypt the video stream.

Building tiny SoC? Are you sure you're not using a SoC on a larger board like a pi? Do you have video compression acceleration?

  The video stream will be coming from a camera sensor, like a CCD. If necessary it can be pre-processed on the SoC into a particular format (for example to compress it) before being encrypted. It can also be encrypted from its RAW format if possible. The encryption protocol should have an efficient hardware implementation that can be implemented on SoC.

For performance, you'll want hardware AES. Although you could use AES-GCM, this will require GHASH in hardware for performance; instead you can ignore GHASH and use a parallel block cipher based MAC instead, such as PMAC.

  The goal of this embedded system is to achieve the highest possible security by reducing potential hardware or software attacks on the Soc that might expose the clear video stream to the attacker.

So far we have AES-PMAC; which makes a fine AEAD, although you ask for higher security so lets add nonce-misuse resistance. Accidental nonce-misuse may occur in many ways, including but not limited to: power faults, wrapping the counter, or incorrectly handling backup and recovery. I recommend you use AES-PMAC-SIV.

Encrypting raw uncompressed video does not leak anything assuming the raw size is constant. Encrypting compressed data can leak for instance the presence of motion in the video stream.

In either case, you should chop the video stream on segment borders such that no segment crosses multiple ciphertext messages. We now have an unbounded stream of variable-length messages to encrypt. You may use the OAE2 construction family to maximize nonce-misuse resistance. Use CHAIN to force sequential decryption, or STREAM to enable out-of-order decryption. The latter is ideal for video, as it enables seeking and does not rely on previous blocks (critical if you want to use the disk as a ring-buffer).

  Note that this is a self contained chip, and the video data will not be sent over WiFi or network. It stays inside the chip.

If the data never leaves the disk, why are you encrypting the video stream instead of using full disk encryption (LUKS, LUKS2)?

If you'd like to restrict the lifetime of the video stream you can rotate the keys and treat your storage device as a large ring-buffer. This way you never need to waste time zeroing out the disk, which doesn't work well because the HDD or SSD is making sectors inaccessible while managing hardware errors and wear leveling.

Keys should only exist in memory and/or on a HSM.

Miscreant is the only library I've seen to offer AES-PMAC-SIV and OAE2 so far.

Pseudocode in Rust:

let mut file = File::open("video-dump", append);
let mut segments = record_camera();

let key = random();
let mut stream = Stream::new(key, nonce);

for seg in segments {
    file.write_all(stream.encrypt(seg, authenticated associated data))?
}

Notice the safe and simple interface. You do not need to mess with any raw ciphers. However, you'll want a header per message with the length of the segment and a flag for the start of a new stream and a flag for the end of a stream (if it ends peacefully).


In a Feistel cipher structure, what exactly does the "round function $F$" do? In a Feistel cipher structure, what exactly does the "round function $F$" do to the right half of the data, before taking XOR of the output with the left half of the data?

What exactly does the "round function F" do

Pretty much anything it wants, with the proviso that it must be a deterministic function of the right hand data and the keying data; it cannot depend on the left hand data.

With that constraint, you get an easily invertible cipher structure, with the inverse function being essentially the same (except that you perform the various rounds in the opposite order; if you feed different subkeys into the various rounds, you invert that, and if you use different F functions for different rounds, you reverse the order of that as well).

Now, to get a secure and efficient cipher, well, that takes a bit more work...


Does an attacker gain an advantage if they have the initialisation vector? Does an attacker gain any advantage by knowing which initialisation vector was used for encryption?

No, they do not gain an advantage; part of the definition of IV is "information that is used to encrypt data which can be sent in the clear".

In fact, it is actually rather common to send the IV along with the encrypted message.  TLS version 1.1, IPsec, IKEv2 are all protocols that do that.

In CBC mode (which you didn't specifically ask about, but it is the most common), the argument that it can be sent in the clear is simple.   Here is CBC mode encryption:

As you can see, the IV is used as as input to encrypt the first block.  In exactly the same way, we use the first ciphertext block to encrypt the second block.  We send the first ciphertext block "in the clear", and hence the attacker can see it, and it does not cause a weakness.  Because we use the IV in exactly the same way, sending it in the clear also does not cause a weakness.  Now, there are some subtle points; the first ciphertext block is unpredictable to an attacker before he sees the message; it turns out that this is actually important, and so the IV must itself be unpredictable.

In Counter mode (the second most common case), the argument is different.  Here is counter mode encryption:

In this diagram, the IV is called the 'nonce'.  Now, the nonce is fed as input to the block cipher; since the block cipher is strong against known (actually, in this case, chosen) plaintext attacks, giving the attacker information about what the input to the block cipher is doesn't aid him.


Bruteforcing a symmetric cipher I don't understand how we could bruteforce a symmetric cipher.
Let's take AES with a key size of $128$ as an example. It means that there are $2^{128}$ possible keys, and as many ways to decrypt a ciphertext $c$. Given that there are so many different keys, it is theorically possible to decrypt $c$ into multiple plausible messages (e.g. message that read like english). So while we are bruteforcing $c$, if at some point we obtain a plausible message we can't tell for sure that we found the good key because there are plenty of other plausible messages that we haven't found yet.
It's not like with hash functions or asymmetric ciphers, where we have a way to make sure that we found the good antecedent/private key.
So I don't understand what they mean in this article: https://en.wikipedia.org/wiki/Key_size
For example:

For instance, Triple DES was designed to have a $168$ bit key, but an attack of complexity $2^{112}$ is now known (i.e. Triple DES now only has $112$ bits of security, and of the $168$ bits in the key the attack has rendered $56$ 'ineffective' towards security).

Even if Triple DES only had 50 bits of security, we would still be able to decrypt multiple plausible messages that are not the original message, let alone the case where the original message is gibberish and not necessarily natural language. I feel like the notion of "security level" is not the same for hash functions/asymmetric ciphers and symmetric ciphers. For both, it refers to the subset of the antecedent/key space that we know the good antecedent/key is in, but for the latter, we can never be sure that we have found the good secret key, and thus that we bruteforced successfully.
Could you explain it to me please? Thank you for your help.

You are forgetting that messages usually consist of many blocks and that many messages contain much more structure than just English text. For example an RSA private key will, when encoded, have a easy to distinguish header and will consist of many blocks of plaintext / ciphertext when encrypted with a block cipher. The same is true for Word documents, XML messages, images and many other formats.
Otherwise, it is a simple game of chance. At each block that decrypts correctly according to the available information, you get more confident that you've found the right message. However, you can choose a block for which you have the most information and only continue decrypting the next block once you've found a match. That way you can very quickly filter out wrong keys.
For instance, for English text you'll generally know at least one bit: the highest one bit of ASCII text is always zero, so that already makes 8 bits per block that you need to get right. Assume that you've got another 2 bits per byte / character simply by checking if the English text is consistent after that. Then you only need to advance to the next block once in $2^{8 \cdot 3} = 2^{24} = 16,777,216$. During the calculation of cryptographic strength, we can safely ignore that kind of detail. If the message is very small then such analysis will indeed fail, and you cannot tell if the key is correct or not. This is easy to show by looking at single bit encryption, e.g. using stream cipher mode such as CTR.
As indicated in the comments, generally we also assume that messages have integrity protection and provide message authentication, usually through authenticated cipher modes or explicit inclusion of a Message Authentication Code (MAC) / authentication tag. In that case, the correctness of the key can also be verified through that code. For most modes that add at least 64 bits to test (128 bits for most authenticated modes and 256 or more if HMAC is used).
Usually, for attacks, we assume that (part of) the message is known, i.e. known plaintext for a known-plaintext attack at the very minimum. Ciphers are expected to be even more secure than that: allowing the attacker to choose which messages get encrypted while leaking no information about the data (other then information about the message size). In other words, the ciphertext should be INDistinguishable from random under a Chosen Plaintext Attack, i.e. IND-CPA secure.


How can I generate reasonably short temporary unlock codes? I need a way to generate temporary unlock codes for an application to use when it can't go online to confirm that its activation subscription is still current.

The application needs to able go offline for 30 days without needing to re-authorize, and this would just be a fallback option for an extended network outage/etc.

My first thought was to just store a timestamp for how long to remain unlocked combined with an RSA signature that the application could use to confirm the unlock came from us and wasn't something the user just made up.

This appears to meet our security needs if we embed the public key in the application (if a cracker modified the binary they could just remove the check entirely instead of installing their own key).  For normal operation sending the data down as part of normal data transfers to/from the associated web application means that we could do this without any particular difficulty.

The problem I see is that since this needs to be usable if there's a network outage the unlock code needs to be short enough to send over a phone call or the equivalent.  An RSA signature with a secure key length fails there.

Use hash based cryptography.
First, define a one way function F. It takes as input a small (10-16 byte) string and uses a secure hash function (EG:SHA2) to produce another string of the same size.
We number each day from (Jan 1 2000) to (Jan 1 2100) with a number n (n=0 ... 36500)
Each day is assigned a code. If the user has the code for a particular day, they are allowed to use the software for all days leading up to and including that day. If we supply the code for day x we don't care if the user can find the code for day x-1 since the code for day x allows them to use the software on that day too. With that in mind, we do the following:
code(x)=f(code(x+1))
The codes form a chain. For each installation, you pick a random code for day 36500 then hash it repeatedly until you get the code for day 0. You then sign a message telling the application the day 0 code.
At that point, give out the code for a particular day to unlock the software up to that date.
Anyone can apply F to a code to get the code for the previous day. But they can't reverse F to get the code for the next day. Since you picked the code at the beginning of the chain you have all of them. This is the asymmetry that makes this system secure. Yes, asymetry ... this is public key cryptography.
To verify a code, the application applies F repeatedly until it reaches the day 0 code. If this does not happen within whatever the set length of the chain, the code isn't valid. Keep a counter during this process to get the code number. Enforcing this limit is not necessary for security it just times out the verification process if the user makes a mistake when entering the code.
Implementation
F can be truncated SHA2. The number of bits kept determines the security level. 80 bits is plenty.
You'd need a binary to text encoding to make this something humans can read and enter into your application.
My current machine can do ~1e6 SHA2 ops per second. That's 3000 years worth of unlock codes. Traversing the chain for generating codes on the server and verifying them on the client won't take much time.
Trusting the Clock
This relies on the application having access to the right time. Users can always change the system time so that's not something a license enforcement system can fix. If the application does something time sensitive (Like recording timestamped records) users might not want to run the software with the wrong time. I'd recommend keeping an internal saved time value which increases while the software is in use and can never run backwards. That's the best you can do. The user is always free to make a system image and restore from backup as many times as they like.
Some things you should already be doing.
I'm assuming you already have a per install ID saved somewhere. That's kind of a requirement for this. Each installed copy of the software has to have a unique ID, a code(0), and a stored signature of the (ID,code(0)) pair for this to work. This prevents the client from deploying lots of identical images of the same installation and using the same code for all of them. This is another thing that can't really be helped.
If you give the client software that gets installed on a machine and will run, the client can make a full system backup. As I mentioned before, they can restore from backup and turn back the clock as many times as they want. But they can also re-image another machine from that same backup. Handling both of these cases is a cat and mouse game of them trying to spoof the environment your application runs in and you trying to make sure they're not doing that.
Deriving an ID from hardware Is one simple option. This prevents the same license data from working on another machine ... but IDs can be spoofed. In this cat and mouse game you try to get legitimate unspoofed HW ids and the client tries to feed your application spoofed values. There isn't anything that can be done about this short of special hardware like TPMs.


Unsafe prime in DH key exchange How the use of unsafe prime in DH key exchange makes DH vulnerable to be broken?
can anyone explain to me what is safe prime, and what is the difference between safe and strong prime?
How the attacker can solve DL problem if safe prime hasn't been used even if the prime is large enough says >1024 bits

First some definitions:

A safe prime is a prime $p$ of the form $p = 2q + 1$ where $q$ is also prime. This is important as the Pohlig-Hellman algorithm runs faster as the largest factor of $p - 1$ becomes smaller. A safe prime is optimal in this sense as $p - 1 = 2q$ and $q$ is therefore the largest possible factor of $p - 1$.

Strong primes are defined here:
https://en.wikipedia.org/wiki/Strong_prime#Definition_in_cryptography

Notice that depending on your definition of "large prime factors" either all strong primes are safe, or they are distinct but similar class of primes.

The fastest algorithms for breaking Diffie-Hellman in the generic case of a group of order $p$ (i.e. those that also work in elliptic curve groups) are $\mathcal{O}(\sqrt{q})$ where $q$ is the largest prime factor of $p$. Hence it is important that $q$ be as large as possible. Ensuring $p$ is a safe prime is a good way of enforcing this.

In specific cases, when groups are represented as $\mathbb{Z}_{p}^{\ast}$, since the fastest algorithms (Index Calculus and Function Field Sieve) are sub-exponential and do not depend on the prime factors of $p$, it is less crucial in these settings.


Determine the RSA private key from public key I was told that you can determine the private key of an RSA encryption with the public key.

I thought the point of a public key was to avoid letting people find the private key, but anyway, they said I could find it by simply factoring the public key modulus? Were they joshing me or can it be done? If so, how would I do that (need to acquire $p,q$ somehow?)?

So with with example Public Key $( e, n ) = ( 13, 119 )$ or any other valid key you want to use...

I was told that you can determine the private key of an RSA encryption with the public key. Were they joshing me or can it be done?

Yes, it can be done. What you have not been told is that to factor a public key (usually hundreds of digits) to find the private key,  requires a time exponential in the length of the public key,
therefore even a supercomputer could take years, if not centuries. Factorization is believed to be a Hard Problem.
 On the other hand, if you already know the private key, you can get the plaintext in very few CPU's cicles.
This is the general principle underlying asymmetric cryptography:


Is there any reason to use RSA or DSA when we have ECC? I am having trouble coming up with a use case for RSA or DSA.  It appears that ECC is better in every way.

Is this true?

I am looking for cases where RSA/DSA is superior to ECC, not where it is used for historical reasons.

There are three use cases where RSA beats common ECC algorithms, such as ECDSA:

Signature with verification frequent or/and by low-power devices. The verification cost of $n$-bit RSA with usual public exponents is $O(n^2)$, but the verification cost of ECC-based signatures is $O(n^3)$ (using usual algorithms). Together with simpler math, that's why RSA can be way over 10 times faster for signature verification at usual security levels, even though it must use a larger $n$ for equivalent security level.
Similarly, encryption by low-power devices or/and with decryption comparatively rare.
Need to minimize the size overhead of adding a signature; using signature with message recovery, that can be 34 bytes for RSA (using SHA-256 hash, ISO 9796-2 mode 3 or the deprecated mode 1, for messages at least 222 bytes before signature at the 2048-bit security level), versus 64 bytes for ECDSA for comparable security.

RSA is thus a good choice (and indeed still the dominant one, I believe) for signing public-key certificates; beside inertia, in the internet domain that's mostly for reason 1 (certificates are verified often), but in the Smart Card and payment industry reason 3 adds up.

Additional arguments for RSA (vs ECC) are

RSA was first there / is the most time-proven, and became an industry standard.
Simplicity. RSA signature verification is much easier to code, and get right, than ECDSA signature verification.
RSA is now clearly patent-free.
Perhaps, slightly more quantum resilience; that is, at comparable level of resistance versus non-quantum attacks, RSA arguably would fall after ECC if it ever emerged quantum computers usable for cryptanalysis; see this other answer and section 5.4 of its source; note that Koblitz and Menezes are not making any strong statement, rather, their intro is (emphasis mine):

  We next examine some conjectures about the NSA’s motives in its PQC announcement (..)
  The NSA believes that RSA-3072 is much more quantum-resistant than ECC-256 and even ECC-384. (..)

Note: this answer does not touch use cases where ECC is preferable, or its virtues.


Learning to encrypt/encryption algorithms I am a beginning programmer interested in coding an application of my own to encrypt sensitive files of mine. For example: lists of passwords, bank accounts, Credit Card numbers etc.

I was wondering what would be the easiest encryption algorithms to learn from a purely theoretical point of view?

Concerning "As a new programmer...":

Probably you don't know this yet, but as a rule of thumb: Do not use your self-implemented crypto for anything unless you are really an expert in the field. This might seem counter-intuitive for the outside, but anything else has to be considered insecure.

The reason for this is that for most aspects of programming and computer science the average case is the most important one. It is not too important if there is a very unlikely flaw in a system since it probably won't happen anyway. But in crypto, the attacker will exploit this flaw to break the system on purpose. Therefore, not the average case is important, but the worst case. For example, you can find statements like "the probability of the attacker to guess right is no more than $\frac{1}{2^n}$" (worst case estimation).

The above statement is not entirely true, but it depends on the abstraction layer: If you utilize standard implementations of encryption, hash functions, key exchange, TLS, etc... you can use those primitives in a high level protocol and most likely you are "secure".

But if you start writing your own crypto primitives, you will probably overlook something. Even worse, if you start using your primitive in a larger context, there is not only a small problem in a single function... you make the entire system insecure. Security is like a chain, and it breaks with the weakest link, not the "average strength".

Back on topic:

You can implement encryption schemes for practice or to learn something, but I advise heavily against using this.

For practice, this depends largely on your experience as a programmer. For the very start, you might want to consider using historical ciphers like Caesar, Vigenere in order to get comfortable with the principles (they are not secure, tho). If you want to have something more useful, you can implement a stream cipher (XOR cipher with some kind of random number generator). Some public key cryptosystems can be easily implemented, too. For example ElGamal encryption, plain RSA, DSA, etc. ... just stay away of elliptic curve crypto, unless you understand what those actually are.

For usage you might want to learn how to import and use standard crypto libraries, for example, "Cryptlib", "Bouncy Castle", "OpenSSL", etc. E.G. this is a list of libraries.


Usefulness of Damgård–Jurik I am trying to understand what are the benefits of using Damgård–Jurik over Paillier. I understand that expansion factor decreases as s increases. But isn't it the case that this comes at the expense of security? If your goal is to reduce space overhead compared to Paillier then you might choose a smaller security parameter and a higher value for s. Or to put it otherwise for a fixed security parameter as s increases cipher-text size increases. So why not just use Paillier with a smaller security parameter?

With Damgård-Jurik, not only expansion factor is decreased: this scheme improves state of the art.

Reducing size of prime factors makes better chance of factoriation or maybe solving particular decision problem that Paillier scheme depends on.


X.509 strong authentication protocols Is there also a protocol definition in X.509? In "Handbook of Applied Cryptography" by A. Menezes there is a reference to X.509 strong authentication protocol, nevertheless, I could not find the definition of the actual protocol, i.e. which massages are passing between the partners, in the source quoted, i.e. ITU-T X.509. Can any one help with this?
Thanks

The strong authentication protocol referred to in the book is defined in the Annex N of "X.509 (10/16)" published by the ITU https://www.itu.int/rec/T-REC-X.509

Here is an excerpt of the standard for the two-way and strong three-way protocols:

  Annex N

  Considerations on strong authentication

  Strong authentication makes use of PKI as specified by this Specification, which
  provides the basic approach to authentication. However, many authentication procedures
  employing this approach are possible. In general, it is the business of a specific
  application to determine the appropriate procedures, so as to meet the security
  policy of the application.

  NOTE – This Specification does not specify the procedures in the detail required
  for implementation. However, additional standards could be envisaged that would do
  so, either in an application-specific or in a general-> purpose way.

  Two-way authentication, described in clause N.3, involves, in addition, a reply from
  B to A. It establishes, in addition, the following:

  that the authentication token generated in the reply actually was generated by
  B and was intended to be sent to A;
  the origin, integrity and timeliness of the authentication token sent in
  the reply;
  (optionally) the mutual confidentiality of part of the tokens.

  Three-way authentication, described in clause N.4, involves, in addition, a
  further transfer from A to B. It establishes the same properties as the two-way
  authentication, but does so without the need for association timestamp checking.


What Are the Risks of AES-GCM [Key, Nonce, Message] where Nonce = Message A group of bankers will store sensitive financial information on a server owned by a third party.  I represent the 3rd party server.

The financial information  will be stored as plain text on the server except that the customer's Account Numbers will be encrypted.  The banks do not want us to know their customers' account numbers.

My question is, how safe is it to use the Account Number as a nonce if it is also the message being encrypted when using AES-GCM?  So, how safe is it to encrypt as follows: AES-GCM[Key, Nonce = AccountNumber, Message = Account Number].

I know this is an example of deterministic encryption and it would be best to use GCM-SIV mode but I cannot find any libraries that implement this encryption that I can use with the .NET Framework.

On a side note, has anyone ever used Miscreant .NET?  As far as I know it has not received FIPS compliance.

Here is an example of the design:

Banker's Data:
Note, that the AccountNumber is a primary key and will not be repeated.  Therefore, nonce = message = AccountNumber will never be repeated.

PK*AccountNumber   Balance     Nonce
1                  $10,000     1
2                  $15,000     2
3                  $20,000     3

3rd Party Server
AccountNumber   Balance
A2B3C4          $10,000
T4K8S9          $15,000
L6D9S8          $20,000

If the Banker wants to query the 3rd party server for the balance of AccountNumber = 1, he will query the server for AES-GCM(Key,Nonce=1,Message=1)='A2B3C4'.  Since only the banker knows the Key and AccountNumber only he can know which record to query for.  This is in essence a zero-knowledge encryption scheme where only the Banker has any knowledge of the key, nonce or message.

I think this is a bad idea for a few reasons:

In GCM mode, if you encrypt two messages with the same nonce, then the messages' plaintexts may be retrievable from the ciphertexts. So if you have two different messages about the same customer that both use the customer id as the nonce, then your encryption may be broken.
When a user retrieves a ciphertext, how will they know the customer ID to use as the nonce? Usually the nonce is included with the ciphertext so that the user can use it with the key to decrypt the ciphertext, but if you do this, then the customer ID will be in plaintext.

Is there some reason that you don't want to use a random nonce as is normally done? If there isn't a specific reason to go off the standard path, then you should avoid doing so.


How does Euler's Theorem show that $(m^e)^d ≡ m \bmod n$ In this thread Henrick Hellström says that when $ed \equiv 1\ (mod\ \phi(n))$ then $(m^e)^d \equiv m\ (mod\ n)$. So I thought this is how Euler's theorem is related to RSA. But at least I thought that due to Euler's theorem the prerequisite for $(m^e)^d \equiv m\ (mod\ n)$ was $ed \equiv 1\ (mod\ \phi(n))$, until I read the comments of the answer and @poncho says that

  Minor nit: it's not true that e,d must meet (satisfy) the equation $ed \equiv 1\ (mod\ \phi(n))$. One counterexample is $n=133, e=5, d=11$. That has $ed \equiv 55\ (mod\ \phi(n)=108)$, however $(m^e)^d \equiv m\ (mod\ n)$ for all m. This is a minor point, however we should avoid telling beginners things which aren't true.

So $ed \equiv 1\ (mod\ \phi(n))$ doesn't need to be true in order for $(m^e)^d \equiv m\ (mod\ n)$ to work. At this point I am really confused about the relation between Euler's theorem and RSA, and why we need $gcd(e,d)=1$.

EDIT: Also this website says that $(m^e)^d \equiv m^{\phi(n)}\ (mod\ n)$. How could this be true? Wouldn't this imply that $ed =\phi(n)$?

I thought that Euler's theorem basically proved that, for $(m^e)^d \equiv m \pmod n$ to work, $ed \equiv 1 \pmod {\phi(n)}$ must be true

No; a direct application of Euler's theorem shows that if $ed \equiv 1 \pmod {\phi(n)}$ is true (and $\gcd(m,n)=1$, Euler's theorem needs that as well), then we always have $(m^e)^d \equiv m \pmod n$

However, it does not imply the converse (and in fact, the converse is not true).

A stronger statement would be (assuming $n = pq$ for distinct primes $p, q$) that if $ed \equiv 1 \pmod{ p - 1}$ and $ed \equiv 1 \pmod{ q - 1}$, then we have $(m^e)^d \equiv m \pmod n$ for all $m$.

And, in this case, the converse is true; if we have $(m^e)^d \equiv m \pmod n$ for all $m$, then we necessarily have $ed \equiv 1 \pmod{ p - 1}$ and $ed \equiv 1 \pmod{ q - 1}$.  In fact, if we have either $ed \not\equiv 1 \pmod{ p - 1}$ or $ed \not\equiv 1 \pmod{ q - 1}$, then we'll necessarily have $(m^e)^d \not\equiv m \pmod n$ for at least 1/3 of the possible $m$ values.

Another (perhaps more common) way of writing these two equivalences is to express it as $ed \equiv 1 \pmod{ \lambda(n) }$ for the function $\lambda(n) = \text{lcm}(p-1, q-1)$.

How does these stronger statements relate to your original relation?  Well, if we have $ed \equiv 1 \pmod{\phi(n)}$, then we necessarily have $ed \equiv 1 \pmod{\lambda(n)}$ (and hence RSA "works")


Are there any hand ciphers not obsoleted by computer cryptanalysis? Computerized cryptanalysis has obviously made formerly "secure" hand ciphers like Playfair, Four Square, and the Hill Cipher obsolete because they can be defeated in seconds. But is there a hand cipher where a modern computer attack does not have an advantage over a cryptanalysis done by hand? There are certainly tasks that are more quickly done by humans, rather than computers. I'm wondering if there is a hand cipher that takes advantage of this.

One time pad is definitely both easy to do and has perfect secrecy, but key management is a pain and can compromise security. Basically a Vigenère cipher with a key as long as the the message should be secure, because different keys can create ALL possible messages with equal probabilities.

Again, it's a one time pad, so no KPA, CPA, or CCA security. Actually I don't think any pen & paper cipher system has such security.


Using C_Sign to create a PKCS7 signature I am using the PKCS#11 function C_Sign to sign some data. The output I get is just a signature. How do I get it in PKCS#7 format - i.e. ASN1 with signature and certificate (for detached) or ASN1 with signature, certificate & unsigned string (for attached).

The PKCS#7 standard is a messaging standard which includes messaging formats for signed data, enveloped data or signed and enveloped data. The PKCS#11 api will produce a "raw" signature, which you will have to wrap in the PKCS#7 signed data formats. If you are using Java or .Net I would recommend looking at the Bouncycastle apis, which include full PKCS#7 wrapper classes. If you are using C / C++ you may have to look for an appropriate ASN.1 library.


Would dividing a random number by a constant "ruin" it? If I get a random number from a cryptographically secure random number generator then divide it by a number, say 2, is it still cryptographically secure?

It does not lower the security at all - at most, it changes the output space. If your output space is, say, the integers between $-100$ and $100$, then computing PRG$(s)/2$ for a random seed $s$ gives a value indistinguishable from a random value in the set $\{-50, -49.5, \cdots, 49.5,50\}$. Depending on which output space you consider and what you exactly mean by "dividing by 2", it can even remain a cryptographically strong PRG with the same output space: if your output space is, say, the field $\mathbb{F}_p$ with $p$ prime, then computing PRG$(s)$ and multiplying the output by $2^{-1} \bmod p$ gives a value indistinguishable from random in $\mathbb{F}_p$.

This follows immediatly from the security of the original PRG: since division by 2 is a reversible operation, any distinguishing attack on the new PRG trivially translates into a distinguishing attack against the original PRG.


The "Square Root" Solution of Oblivious RAM Simulation I am reading the paper Software Protection and Simulation on Oblivious RAMs by Oded Goldreich and Rafail Ostrovsky. And I wonder about the description of the "Square Root" solution of oblivious RAM simulation at page 20.

The algorithm seems simple: the aim is to 'simluate' the original RAM of size $m$ by an oblivious RAM of size $m+2\sqrt{m}$. So it uses the first $m+\sqrt{m}$ cells of the oblivious RAM to shuffle or to obscure,  and uses the last $\sqrt{m}$ cells as a cache (or shelter) in case of leaking information about access frequency.

However, the first step to use the shelter reads 'first, we scan through the entire shelter and check whether the contents of the virtual word $i$ is in one of the shelter's words. '

Here, we want to simulate an original RAM access at location $i$ (for fetching the virtual word $i$) by using the shelter, and then comes the question : since we haven't known what the contents of virtual word $i$ actually was yet, how do we check whether it has been in the shelter or not?

Presumably, the shelter could store a bunch of pairs $(a,v)$ where $v$ is the contents of the virtual word at address $a$.  Then, to scan through the shelter to see whether it has the value of the virtual word at address $i$, you'd just check whether the shelter contains any pair $(a,v)$ where $a=i$.

I don't know whether this is actually what Goldreich and Ostrovsky do, but it seems like one natural candidate scheme that could be used.


Semantic Security Active or Passive attacks? I'm reading A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack and here define Semantic Security ...

  Semantic security, dened by Goldwasser and Micali [14], captures the intu-
  ition that an adversary should not be able to obtain any partial information
  about a message given its encryption. However, this guarantee of secrecy is
  only valid when the adversary is completely passive,

but in the abstract of other paper Semantically Secure McEliece Public-Key Cryptosystems –Conversions for McEliece PKC say

  we propose slightly modiﬁed versions of McEliece PKC that can be proven, in the random oracle
  model, to be semantically secure against adaptive chosen-ciphertext attacks.

I'm confusing Why if semantic security is for passive attacks exists the term "secure against adaptive chosen-ciphertext attacks", when Adaptative Chosen ciphertext attack is a model to active attacks?

The initial notion of semantic security from Goldwasser and Micali has been shown to be euqivalent to what we call today indistinguishability under chosen plaintext attacks (IND-CPA). Yes, that's the only security against a passive adversary and actually the weakest reasonable security notion that we use today.
The authors of the second paper you link seem to use the term semantically secure in a slightly misleading way in the cited part of the paper. What they actually mean is a much stronger notion which is better known as indistinguishability under adaptively chosen-ciphertext attacks (IND-CCA2), which covers active adversaries.
However, this "wording" the authors are using seems to be used by various authors in the way that semantically secure against is seen to be equal to providing indistinguishability under. Also, it is common that when only saying semantically secure, then one means IND-CPA, i.e., a passive adversary. But if one says semantically secure against (adaptively) chosen message attacks, then (IND-CCA1) IND-CCA2 is meant, i.e., an active adversary.
If you read in some parts of the remainder of the second paper you cite from, you will find the correct use:

Under the assumption that this inverting problem is hard, we investigated, in the random oracle mode, how to convert this hard problem into the hard problem of breaking the indistinguishability of encryption with CCA2.


Convert message to polynomial NTRU How to make a message into a polynomial? I saw many answers to this question and yes, i know that here are some questions. But i did not get it. I think that i am making some mistakes. I took a word and just convert to binary-and here is my polynomial. I this that it is not correct, i am working with utf-8 (so example with ascii-7 not solution for me). I dont like to use a hybrid crypto ( with for example aes-think that these symmetric crypto are not secure), but i tried it-and i used a 128-bit key for aes and parameter N=503 for NTRU and this is not enough for me. Because i have key ( aes) for example 255 255 255 255 255 255 255 255 255 255 255 255 255 155 155 155 and i need these spaces- i am trying to create app for windows phone  encrypt sms, so it need for correcting decrypt. So i think that i am not right and need your help. Help me understand how to correct in my case make a message into a polynomial and may be give some ideas for encrypting sms.

What you are looking for is explicitly specified in the IEEE Standard 1363.1 [1], which covers NTRU. In particular, encoding a bit string into a polynomial is done in the following manner: Once you have processed the input message, you divide it into blocks of 3 bits, and transform each block in a pair of coefficients of a ternary polynomial according to a predefined table (described in 9.2.2.h of [1]):

{0, 0, 0} is converted to {0, 0}
{0, 0, 1} is converted to {0, 1}
{0, 1, 0} is converted to {0, –1}
{0, 1, 1} is converted to {1, 0}
{1, 0, 0} is converted to {1, 1}
{1, 0, 1} is converted to {1, –1}
{1, 1, 0} is converted to {–1, 0}
{1, 1, 1} is converted to {–1, 1}

Note that the input bit string needs some processing before transforming it into the polynomial (also described in section 9.2.2).

Also note that we assume the original message is a bit string, so it doesn't matter which was the codification of the original text string (ASCII, UTF-8 or whatever); that should be a problem of your application, not of the encryption algorithm.

References:

[1] IEEE Std 1363.1 - IEEE Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices. 2008.


Use Initializaiton Vector as Additional Authenticated Data Cipher is GCM-AES.  Is it acceptable/recommended to store the IV as AAD?  Any popular examples?

You don't need to put the IV in the AAD (Additional Authenticated Data) as already indicated in the comments.

The GCM proposal as adopted by NIST (PDF) clearly specifies this in paragraph 2.1 Inputs and Outputs:

  The IV is authenticated, and it is not necessary to include it in the AAD field.

The NIST document SP 800-38d (PDF) does not explicitly specify it, it does however contain some hints to this effect, for instance in Appendix B:

  The creation of an authentication tag by the authenticated encryption function provides the mechanism whereby assurance of the authenticity of the plaintext and AAD (and IV) can be obtained upon the execution of the authenticated decryption function.

Finally, to make this a bit more general, RFC 5116 : An Interface and Algorithms for Authenticated Encryption, 2.1: Authenticated Encryption specifies the following:

  The nonce is authenticated internally to the algorithm, and it is not
     necessary to include it in the AD input.  The nonce MAY be included
     in P or A if it is convenient to the application.

So it is acceptable to store the IV in the AAD, but I don't see any reason to recommend it.

If I'd see the IV included in the AAD during a review I'd probably see it as an indication that the designer didn't know what he/she was doing.


Splitting text before Format Preserving Encryption operation What is the effect on Format Preserving Encryption security if I reorder text before FPE encryption?

Take as an example Canadian postal codes (letter-digit-letter digit-letter-digit):

Parliment: K1A 0A6
Santa Claus: H0H 0H0
Easy to remember: A1B 2C3

Using the postal code as a base 36 number and applying FF1 (NIST 800-38g test vector AES128 key, no tweak) gives this ciphertext:

$$E_k(\mathtt{K1A0A6}_{36}) ==> U7F8BD_{36}$$

But the original format is not preserved (last character is not a number).

What is the difference effect on the security of encryption if I

Group digits and characters toghether prior to encryption
Reduce the base to 26 and 10 for letters and digits, respectively
Apply FF1 on the two sets
Re-order the ciphertext so format is preserved

Something like this:

\begin{gather}
E_k(\mathtt{KAA}_{26}) ==> FDE \\
E_k(\mathtt{106}_{10}) ==> 143 \\
\end{gather}

Would end up with FF1 encrypted postal code: F1D 4E3

I'd strictly perform FF1 on the entire postal code. That means converting the code to a number in the range $\big[0,26\cdot10\cdot26\cdot10\cdot26\cdot10\big)$ and then encrypting, decrypting and getting it back. This is relatively simple base conversion so it should be easily done using division and remainder math.

Obviously, otherwise you may leak repetition of parts of the input. For instance, if we encrypt the first and second part separately, you may also have Sneezy's postal code, $\mathtt{H0H\space1H0}$ in there ($\mathtt{H1H\space0H1}$ was already taken by the evil witch). Now you can see that $\mathtt{H0H}$ repeats, so anybody knowing Sneezy's code will also indicate the first part of Santa's code; not good.

With many known postal codes - many of which may already be known - this means that it will become easy to quickly guess all the postal codes. If one is relatively unique then it clearly indicates a rather sparsely populated part of the country.

Other schemes - like the one you are proposing - may have similar issues, it kind of depends on how the postal codes are generated. By converting the entire postal code to a number issues such as these can be avoided.


Wikipedia's double-and-add point multiplication algorithm for elliptical curves Here's the algorithm Wikipedia gives for double-and-add point multiplication:

   N ← P
   Q ← 0
   for i from 0 to m do
      if d[i] = 1 then
          Q ← point_add(Q, N)
      N ← point_double(N)
   return Q

$P$ is an $(x, y)$ coordinate and so it seems reasonable to assume that $0$ is a $(0, 0)$ coordinate but there's no guarantee that $(0, 0)$ will even be on the curve, which would thus skew the whole thing.

Indeed, it seems to me that $Q$ is probably better represented as $\infty$ due to the P + ∞ = P identity?

I suppose one could assume that $0$ and $\infty$ are the same thing, but that wouldn't work if $(0, 0)$ were an actual point on the curve.

P is an x, y coordinate and so it seems reasonable to assume that 0 is a 0, 0 coordinate

Actually, that's an incorrect assumption; by 0, they really mean the point at infinity (aka the neutral element aka the identity element).  That is, it is a point that doesn't actually correspond to a solution to the cubic equation, but instead is something that needs to be thrown in to make the curve a mathematical group.

As for how it is represented, well, that rather depends on the implementation; there might be implementations that represent it as (0, 0), but (as you point out), that might not work if $x=y=0$ is a valid solution to the equation.


Can you please explain weak keys of the following 2-round DES? 2-rounds DES (M-DES)

• $|M|=|P|=|K|=2^4$;

• S-boxes: $S_1 = [1 0]$ and $S_2 = [11]$;

• The initial and the final permutation are the identity permutation;

• The expansion function is the identity function;

• The key schedule function is defined as follows: For a key $K = (k_1k_2k_3k_4)$, the
round 1 key is $K_1 = (k_4k_1)$ and the round 2 key is $K_2 = (k_2k_3)$.

A key $K$ is called a weak key for the cipher $E$ if $E_{K_1}(E_{K_2}(x)) = x$ for all $x \in M$.

Please explain M-DES Weak Keys.

The definition of weak key in the question is a mixup with that of semi-weak key pair, or/and semi-weak key. Let's put these definitions straight.

We'll consider a block cipher $E$ over set $M$, with a key set $\mathcal K$.

The defining property of a weak key $K\in\mathcal K$ is: $\forall x\in M,\,E_K(E_K(x))=x$. In other words, encryption and decryption with $K$ are the same.

The defining property of a semi-weak key pair $(K_1,K_2)\in\mathcal K^2$ is: $\forall x\in M,\,E_{K_1}(E_{K_2}(x))=x$. In other words, encryption with one key in the pair is the same as decryption with the other.

The defining property of a semi-weak key $K\in\mathcal K$ is that there exists $K_2\in\mathcal K$ such that $(K,K_2)$ is a pair of semi-weak keys. In other words, the key occurs in a semi-weak key pair.

The M-DES block cipher in the question is a symmetric Feistel cipher with 4-bit message space $M$ and 4-bit key space $\mathcal K$; and a structure similar to that of DES, but simplified to caricature. In particular

The S-boxes have 1-bit input and 1-bit output (one is bit inversion, the other has constant output 1). Complete linearity follows: within polarity, any ciphertext bit is the XOR of whatever few plaintext and key bits influence it.
Expansion E is removed; and, beyond a mysterious and probably unrelated $|P|=2^4$, we are not told about a permutation P. Complete lack of diffusion between odd and even bits of the message space would follow that both are gone.

Reducing M-DES to equations, then applying the definition to find weak keys, is left as an exercise to the OP. A computer is not useful.


zero-knowledge proof of disjunctive statements (OR proofs) I know there are standard ways to prove disjunctive statements about discrete logs, e.g. OR proof. But are there similar approaches for other class of language? For example, how can one go about proving either $G_1$ or $G_2$ has a Hamiltonian path (without leaking which one)?

You can use the CDS94-technique for that. Suppose you have two zero-knowledge proof systems $\sigma_1$ and $\sigma_2$, both of which consist of three messages: a commitment $com$, a (public-coin) challenge $ch$, and a response $r$. And suppose you want to prove the OR of both claims, meaning that you can generate a valid proof for (wlog.) $\sigma_1$ for any challenge even after generating the commitment, but in order to generate a valid proof for $\sigma_2$ you must get the challenge first and compute the commitment from there. So you have essentially one degree of freedom in the choice of $(ch_1, ch_2)$, i.e., one is fixed beforehand but you want to hide which one. The clue is to get a new challenge $ch'$ from the verifier and guarantee that $(ch_1, ch_2, ch')$ satisfies a suitable relation, for instance sum-to-zero. So the proof system for $\sigma_1$-OR-$\sigma_2$ looks like this:

preprocessing by the prover: compute $com_2, ch_2, rsp_2$ for a random $ch_2$
prover sends commitment: $com_1, com_2$
verifier sends challenge: $ch'$
prover computes $ch_1 \leftarrow ch' - ch_2$ and uses this to complete $\sigma_1$
prover sends response: $(ch_1, rsp_1), (ch_2, rsp_2)$
verifier verifies that $(com_1, ch_1, rsp_1)$ is valid, that $(com_2, ch_2, rsp_2)$ is valid, and that $ch_1 + ch_2 + ch' = 0$

You can use $\sum_i ch_i = ch'$ for OR-proofs consisting of any number of claims. However, in some cases you want to prove more specific facts such as "$t$ out of these $n$ claims are true". In this case, you want to use Shamir's secret sharing and exchange the sum-to-zero relation for a polynomial of degree $n+1-t$: this guarantees that all $n-t$ degrees of freedom for choosing $ch_i$ must be used up by the false claims.
The CDS-94 technique applies to any zero-knowledge proof system that follows this three-pass public coin structure. Schnorr's protocol for proving discrete logarithm knowledge is just one particular case of that structure.
CDS94: Cramer, Ronald, Ivan Damgård, and Berry Schoenmakers. "Proofs of partial knowledge and simplified design of witness hiding protocols." CRYPTO 1994.


Is there any place where I can find test vectors for point addition and doubling of ECC? I want to extensively test my implementation of point addition and doubling. I have only one test vector with me. I need more values to test.

In the web, I could find test vectors only for key pair generation and  signature verification. So if anybody can refer me a link containing test vectors, it will be of great help!

Thankyou.

You can check Elliptic Curve Calculator.
It has point addition and scalar multiplication. For doubling, adding the same points(P+P) should do the work.


How much data can we encrypt using AES 256 before changing the key? Although this question has been answered in this link (After How Much Data Encryption (AES-256) we should change key?), I am not satisfied with the answers because the Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM)and GMAC has a different view on this. It says

Now 2^32 block ciphers, means 2^32 * 16 bytes of data, which is approximately 68 GBs. So do I need to change keys after 68 GBs?
I am confused because I am very new to the field and I would be very thankful for any help or suggestion in this regard.

AES-GCM is not the same thing as AES. AES-GCM uses a 96-bit IV, or transforms a non-96-bit IV into a 96-bit IV before use. The particular constraints of the RBG and Deterministic constructions mean that not all of those 96 bits are expected to change between invocations. An IV collision (two uses of the same IV with a given key) is catastrophic to GCM's security, and therefore must be avoided.
The "Birthday bound" of an n-bit value is $2^\frac{n}{2}$, so a 96-bit IV has a bound of only $2^\frac{96}{2}=2^{48}$ blocks. But both recommended IV constructions keep some bits of the IV fixed, resulting in the lowered block count recommendation. EG

this  Recommendation  suggests,  but  does  not  require,  that  the  leading  (i.e.,  leftmost) 32 bits of the IV hold the fixed field; and that the trailing (i.e., rightmost) 64 bits hold the invocation field

means that only 64 bits of the IV would vary, so $2^\frac{64}{2}=2^{32}$ blocks can be safely encrypted with those GCM settings. Other IV generation methods similarly tend to reduce the number of varying bits. Fixing some bits allows for multiple sources to encrypt data using the same key. If one bit is fixed, two devices can share a key. If two bits are fixed, 4 devices can. Etc. If no bits are fixed, then each device must have its own send and receive key for each other device. Since this part of the spec is about fixed, shared keys the storage requirements would quickly overwhelm small systems.


Secondary hash function utility, regarding data destruction? Given that hash functions are inherently irreversible, would they not then be useful in applications where it's desired to overwrite sensitive data? (i.e. Darik’s Boot and Nuke)

Specifically, why should hash functions not be used for data clearing?

Specifically, why should hash functions not be used for data clearing?

I take it you mean that we would overwrite the storage with output produced by feeding its sensitive contents to a hash function.  The problem then is that this output, being a function of the data you're overwriting, therefore provides information about that input.

In particular, it could be used to efficiently test hypotheses about the content of the overwritten data.  This is the same principle as password cracking; just like password hashes allow you to quickly test password guesses, the overwritten disk sectors' contents could perhaps be used to test whether the disk contained or not some specific data before being overwritten.

You may think that this sounds like a very unlikely attack, and you could well be right about that.  But why allow it in the first place?  Particularly when the alternative is simple enough: overwrite with random or pseudorandom data that has no correlation at all to the sensitive contents you're overwriting.


Taking half of a X bits hash key as secure as using a X/2 bit hash function? This question comes from a (nitpicking) comment by me in this SO question.

I said that using the half of the output from a 256 bit hash function is worse than using a 128 bit hash function. My reasoning is that the contract of the 256 bit function takes into account the full length output so you can find more collisions in the first half of the 256 bits output than you would in a 128 bit hash function.

As I saw here Is truncating a SHA512 hash to the first 160 bits as secure as using SHA1? that that could not be applied to SHA so I was wrong there but in a more broad scenario, does it provides the same security taking the half of the output from an X bit hash function than using a X/2 hash function?

It is unlikely that a secure X-bit hash function's X/2-bit truncation would not be X/2-bit secure.

For example, suppose you have a faster than $2^{128}$ second preimage attack on the 128-bit truncation of a 256-bit hash. Then you can run that attack $2^{128}$ times and expect to find a second preimage for some value of the full 256-bit hash, so that hash does not have 256-bit second preimage resistance (at least for some definitions of second preimage resistance).

However, the same argument does not apply to collision resistance: even if you can get a collision for the first half you need $2^{X/2}$ such pairs before you expect a collision in the second half. The birthday bound does not apply because you cannot compare different first-half collisions to each other.

(Collision resistance of the whole hash does put a bound on the multicollision resistance of the first half. If you had a $2^{X/4}$-collision in the first half, you would expect a collision among them in the second half.)

So theoretically it could be easy to find a collision for the first half, but no easier than brute force to find a collision for the whole. However, because real world hash functions use the same function to derive the whole hash value, any weakness affecting only the first half would be unlikely.

For Merkle-Damgård hashes in particular, a truncated hash means you actually have a wide-pipe construction, which has some advantages over an untruncated hash of the same length. So you would expect e.g. SHA-512/256 to be at least as strong, if not stronger than SHA-256.


Adversary for attack on one variant of ElGamal I came by the following question:

Consider the following variant of ElGamal encryption.  Let $p= 2q+ 1$,
let $G$ be the group of squares modulo $p$ so $G$ is a subgroup of
$Z_p^*$ of order $q$, and let $g$ be a generator of $G$.  The private
key is $(G, q, g, x)$ and the public key is $(G, q, g, h)$, where $h =
\> g^x$ and $x\in Z_q$ is chosen uniformly.  To encrypt a message $m ∈
\> Z_q$, choose a uniform $r∈Z_q$, compute $c_1=g^r$ mod $p$ and
$c2=h^r+m$ mod $p$, and let the ciphertext be $(c_1, c_2)$.  Is this
scheme CPA-secure? Prove your answer.

Here $G$ is set of all elements in $Z_p^*$ which are quadratic residue modulo $p$ and $Z_p^* \setminus G$ is set of non-quadratic residue elements
.I think attacker should choose two messages in way that encryption of one be in set quadratic residues modulo $p$ i.e $G$ and one be in non-quadratic residues set i.e. $Z_p^* \setminus G$   then use this property to distinguish challange ciphertext . For example, if the attacker choose $m_0 = 0$ encryption of $m_0$ will be in set quadratic residues modulo $p$ i.e. $G$.
How should attacker choose $m_1$ to be able to calculate advantage of adversary exactly? The attacker can choose $m_1$ uniformly and with good probability encryption of it will not be in set quadratic residue but then I can't calculate exact advantage of this attacker. I want a attacker that i could calculate exact advantage.
Also we know $|G| = |Z_p^* \setminus G | = q$  but we do not know the way elements of $G$ are distributed over $Z_p^*$.
Recall: it is easy to tell whether or not an element $g∈Z_p^∗$ is a quadratic residue(simply see if $g^q= 1$ mod p).

How should attacker choose $m_1$ to be able to calculate advantage of adversary exactly?

Well, for $p$ prime, then precisely $q$ of the values in $(1, p-1)$ will be Quadratic Residues and the precisely $q$ will not be; furthermore, there is one value ($0$) that resides outside the group (and hence is also an impossible value for $h^r$).  Hence, if he chooses $m_1$ uniformly from the range $(0, p-1)$ (and independently of the value $r$ the encryptor selects), then $h^r + m_1$ will be a random value uniformly from the range $(0, p-1)$, and hence will be either a quadratic nonresidue or 0 with probability $(q+1)/p > 0.5$.
You should be able to precisely compute the advantage from that.


Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$? Suppose that we are given $\mathbb{Z}_{N}$ and an element $x^u \in \mathbb{Z}_{N}$ with $u \in (0,l]$ where $l$ is the bit-size of $N$. Is it difficult to recover $x$ by knowing $u$ without knowing the factorization of $N$?

Yes, the problem of finding unknown random $x\in\mathbb Z_N$ given $N\in\mathbb N$, $u\in\mathbb N$ with $1<u\le\lceil\log_2N\rceil$, and $x^u$ computed in $\mathbb Z_N$, is believed hard unless the factorization of $N$ can be determined, which itself is believed hard for appropriately constructed RSA moduli $N$. Moreover, depending on $u$ and $N$, there might be several solutions with no way to tell the right one (if $u$ is odd and $N$ squarefree with no divisor up to $\lceil\log_2N\rceil$ then there is a single solution). Notice that I have excluded $u=1$ (which the question allows), for it makes finding $x$ trivial.

When $u$ is odd this is the RSA problem with small exponent, which is believed hard when the factorization of $N$ can't be determined (with the caveat that a usual definition of that problem asks that $N$ is squarefree and without small divisors).

When $u$ is $2$, this is the square root modulo unknown composite problem, which is demonstrably hard when the factorization of $N$ can't be determined.

Ability to consistently solve both that square root problem and the RSA problem implies ability to find a solution to the question's problem, by writing $u$ as $e\cdot2^s$ with odd $e$, solving the RSA problem for exponent $e$, and solving the square root problem $s$ times.

Addition: this answer is for version 5 of the question. As correctly noted in another answer for an earlier version of the question, knowing that $N$ is a square does not make the problem easier if the factorization of $N$ remains unknown.

Further addition following comments:

It is easy to find the inverse of any given element of $\mathbb Z_N$ when its exists, using the Extended Euclidian algorithm.
It is hard to exhibit $a\in\mathbb Z_N$ that has no inverse modulo $N$, other than $0$ or a multiple of an easily found factor of $N$ (argument: if such an $a$ was found, then $\gcd(a,N)$ would be a non-trivial divisor of $N$  contributing towards finding the full factorization of $N$).
If $\gcd(u,N)=1$ (which we'll assume hereafter), it is thus easy to find non-negative integers $v$ and $k$ with $u\cdot v=k\cdot N+1$, otherwise said with $v\equiv u^{-1}\pmod N$.
It does follow that $\forall x\in\mathbb Z_N$, $(x^u)^v=x^{k\cdot N+1}=(x^N)^k\cdot x$.
That does not seem to help finding $x$, because we have nothing telling us that $x^N=1$; on the contrary, $x^N=1$ seldom holds when $x\ne 1$; in particular $x^N=1$ holds only for $x=1$ when $N$ is prime, since in this case: $\forall x\in\mathbb Z_N$, $x^N=x$ by Fermat's little theorem.


Why are in asymmetric cryptography as many keys as people involved needed? The question: "10 friends wish to establish secure communications between themselves using asymmetric-key cryptography. How many keys need to be known by each user?" was posed by my teacher. He says 10 keys are needed. I say only 2 keys are needed. As long as they have copies of the same keypair (keypair=2 keys, a public and a private), they don't need more than two. Why in the WORLD would you need more than a public key and a private key?

Edit:

I have already seen a few questions of this type by googling. Turns out this kind of question never specifies that the people of the group must be able to talk individually to each other. Nevertheless, the student must always assume they want to talk individually and secretly. That makes no sense to me, but that's reality. Ie: In public key cryptography, how many keys are required for secure communication between n parties?

In other words, in criptography, when they say communication between N entities, it is not actually communication between N entities, it's more like N private communications between each of the N entities.

Actually you are both wrong, assuming that each user wants to authenticate themselves individually and / or establish private conversations between pairs. Unfortunately this is assumption is missing from the question. If everybody is using (EC)DH then they need a key pair each to setup communication by establishing a session key. That means 10 times 2 keys = 20 keys. However, quite often key and key pair are confused, so the professor is really talking about the latter, only counting the private keys / key pairs, making 10 the correct answer.

If you establish a "master" user that you trust, and no entity authentication is required then you are correct. You need just one private key pair known to all, initially distributed by the master setting up the group. Then you can e.g. encrypt a session key with the public key and only those that have the private key can decrypt. Arguably this is not a good example of asymmetric cryptography though: the private key is now a shared secret, something that is common for symmetric cryptography rather than asymmetric cryptography. The sharing of the private key is required in this scheme, otherwise an adversary can join by identifying as one of your friends.

Note that just having 10 key pairs is not enough to authenticate all the users and setup 1:1 communication. It is also required to trust the public keys. Authentication is about proving you have (access to) a private key that belongs to a public key known to belong to you by the other user.

Note that I've talked about (EC)DH rather than RSA in the first section. It is common to setup (multiple) session keys in transport protocols rather than encrypting directly with the public key and decrypt with the private key. Of course, this requires a set of temporary keys in addition to the asymmetric keys.

It is possible to perform encryption / signature generation with just 10 key pairs, so session keys are not necessary. However, that's really not following good cryptographic practice. So I decided simply not to count the symmetric session keys.


Forge CBC-MAC given the MAC of two messages and of their concatenation I found this question about CBC-MAC forging and want to make sure I understand it:

  Let a and be be two strings of block length one. Suppose the sender sends $(a, \text{CBC-MAC}(a)), (b, \text{CBC-MAC}(b)), (a||b, \text{CBC-MAC}(a||b))$. Find new messages / MAC pair which the attack can now forge from the messages / MACs given above.

I have:
$\text{CBC-MAC}(x) = t$ and
$\text{CBC-MAC}(y) = t'$,
then $\text{CBC-MAC}(x || y \oplus t) = t'$.
Then can I forge the permutation combination of the given pairs with that formula?
i.e. if $\text{CBC-MAC}(a) = x$ and $\text{CBC-MAC}(b) = y$, then $\text{CBC-MAC}(a || b \oplus x) = y$.

Yes, your understanding is correct.  With the CBC-MAC's of $(a), (b)$ and $(a||b)$ you can forge the following new messages:

$(a||b \oplus MAC(a)), \\
(b||a \oplus MAC(b)), \\
(b||b \oplus MAC(b)),\\
(a||a \oplus MAC(a)),\\
(a||b||a \oplus MAC(a||b)), \\
(a||b||b \oplus MAC(a||b)), \\
(a||b \oplus MAC(a)||a \oplus MAC(b))\\
(a||b \oplus MAC(a)||b \oplus MAC(b))\\$

...And so on and so forth until you get tired of pwning CBC-MAC with forgeries (assuming the recipient accepts messages longer than the one-to-two blocks we know from the question).


Why aren't zero-knowledge proofs used in practice for authentication? I read on Wikipedia that zero-knowledge proofs are not used for authentication in practice. Instead (I think) the server is entrusted with seeing a password in plaintext form, which it should then add a salt to and hash. But for a split moment, the server knows the secret. Why should I implicitly trust the server like this? It could go rogue and record my password in plaintext form. I could use that same password for other sensitive things. Aren't zero-knowledge proofs a necessity? Why aren't they used? Or are they used?

Update, an alternative: What about never reusing your password and instead generating different passwords from a master password and website name using only a program that runs on the client? It seems much simpler, because you never reveal the master password. That way, you don't need to trust the website nearly as much.

This clarifies my previous question.

Answering the question in your title (and not addressing your proposed alternative which I don't quite understand) there is a zero knowledge proof of password protocol "SRP" which is fast and effective.

SRP does not seem to have been given as wide publicity as it should get. Having implemented it, and being an advocate of its use, I don't really understand why everyone doesn't use it all the time. Some reasoning that I have seen for dismissing it are:

A belief that a server is either totally 'good', or totally 'bad', and that using HTTPS ensures you always talk to 'good' servers, which can be trusted with plaintext passwords. Real life just isn't like the movies; it is more complex. The Heartbleed debacle shows that an otherwise trustworthy site can be leaking bits of memory such that a plaintext password sent over HTTPS can be observed by 3rd parties. More common would be poor error handling in custom website code which would print out a plaintext password into a log file which can be read by an intruder who can only see the file system on the server. Large systems stream logs to a central local exactly to make it easier to look at errors in logs where many people can search for patterns.
A belief that the client is either fully secure, or totally compromised, such that an attacker can see nothing, else can record what is being typed. If an attacker can record what is being typed they can steal the password directly; SRP only protects against interception on the wire and the TLS protects the wire. In reality interception is much more routine than people realise even using well configured HTTPS. Large employers routinely decrypt and scan HTTPS to protect themselves from intellect property theft by their employees. Even if they are only doing this to protect their own digital property rights it increases the risk of bugs leaking plaintext passwords or else a rogue employee stealing passwords. Big laptop suppliers install things like superfish to decrypt customers HTTPS traffic to sell "smart ads" on pages. They might not be all bad people; but it increases the risks of bugs leaking passwords or else a rogue employee stealing them. There have also been examples of certs being compromised meaning that encrypted traffic can be snooped. All this means that it might often be the case that an attacker cannot directly record what the user typed at the keyboard; but can view anything passed over the network even when HTTPS is being used. SRP can protect against any such interception as it is a zero knowledge password proof.
A belief that SRP is an positioned as an alternative to HTTPS. SRP does not (out of the box) verify the server (upon registration) so you might be talking to a fake server. So in an "either-or comparison" of SRP and HTTPS (assuming none of the problems detailed above) then HTTPS is often judged superior. This is a false dichotomy as in practice real world HTTPS has many weaknesses which can be addressed by using SRP over HTTPS. Performing SRP over HTTPS gives you server verification which strengthens SRP. So people should always be using both together.
A lot of focus on two factor authentication as an enhancement to plaintext passwords. Companies who have identified that passwords are high risk tend to employ a second factor (say, a text to your phone). The site may still leak passwords, which users may be using on multiple sites, many of which don't use a second factor. If sites upgraded to use SRP and a second factor they would fully protect their users.

When it comes to implementing SRP there are a couple of inhibitors:

A historic lack of a pure JavaScript examples. An early authoritative demo used a Java applet. Recently after the Heartbleed debacle there has been a revival of SRP and there are now a few solid opensource JavaScript libraries and demos.
An extra round trip to login. With plaintext you send username and password in one post. With SRP you first send username to get the salt (and a challenge) and then generate the password proof to send to the server. Most web security frameworks assume that everything is sent in one round trip. This can be addressed by an AJAX call for the first round trip and posting the password proof as the password. More sites are now splitting username and password across two pages to implement ”social login”. Based on your email given at the first page they present a password page that targets the correct social login server. This two page pattern fits well with SRP and end users are becoming more familiar with it.

Having said all of that there is no good reason why every site doesn't now use SRP. So you are correct in being surprised that plaintext passwords are still in use.

Update: I still encounter quite aggressive push back about SRP from crypto experts who are arguing about TLS being sufficient. I am sure they are only hired by high security outfits that (in theory) would never make the mistakes listed above. The fact that they use their theoretical knowledge to shoot down a practical additional defence in depth strategy of both TLS and SRP is a surprise to me. I didn't become a fan of SRP for theoretical reasons. I became a fan after the online banking system I had just upgraded failed its penetration testing with perfectly configured TLS with the external tester managing to harvestest live passwords. As my grandfather told me ”In theory, both theory and practice are the same. In practice, they are not.” Passenger airlines use redundancy to keep people alive. Security practitioners should use defence in depth rather than a theoretical model of security.


RSA PKCS#1 v.15 Signature verification computational complexity explanation? I've been experimenting with MBEDTLS on an ARM-M4 (but this question is not platform-specific) and am confused/surprised regarding the computational complexity (execution time) of mbedtls_rsa_pkcs1_sign() versus mbedtls_rsa_pkcs1_verify(). Apparently the _sign is much more computationally complex than the _verify. I don't understand this and would expect the opposite to be true.

Observations:

mbedtls_rsa_pkcs1_decrypt() or  mbedtls_rsa_pkcs1_sign()    < 3 secs
mbedtls_rsa_pkcs1_encrypt() or  mbedtls_rsa_pkcs1_verify()  < 100 millisecs
(this is for RSA-2048 / SHA-256)

I would have assumed that the verify should be similar in complexity to the decrypt (because it requires decryption of the signature hash) and that the sign would be similar in complexity to encrypt (because it requires encryption of the hash). I understand that for the signature operations the Private and Public key use is reversed, but I'm not sure how/why that affects things.

Apparently the _sign is much more computationally complex than the _verify.

For RSA, this is typically the case.

For the signature verification operation, the computationally expensive part is the computation of $M^e \bmod N$ (for some $M$); where $e$ is a public value, which is typically fairly small (65537 is the most common value).

For the signature genearation operation, the computationally expensive part is the computation of $M^d \bmod N$ (for some $M$); where $d$ is a private value that's close to the size of $N$.

The computation of $M^x \bmod N$ takes time roughly proportional to the log of $x$; and so we're talking about of log2 of 16 (for signature verification) versus a log2 of 2048 (for signature generation), and so by this simple-minded analysis, we'd expect that verification be about a 100 times faster.

Now, during signature generation, an implementation can use the "Chinese Remainder Theorem" to cut this time by maybe a factor of 4 (this optimization cannot be used during the signature verification, as it requires knowledge of the factorization of $N$); this would reduce the expected ratio to about 25, which is roughly what you see.

For RSA, $d$ must be large (small values of $d$ are known to cause weaknesses); on the other hand, we don't mind if the attacker can guess $e$ (we'll publish it in the public key, hence he doesn't have to guess), and so there is no drawback in making is small.  Actually, an $e=3$ can actually be secure; however some people don't like it as it can be fragile if you don't get the padding right.


Semantic constraints and authentication In some cases (such as XML or JSON files), the bytes being encrypted have very specific semantic requirements, such that a random byte sequence will be rejected with very high probability.

In such circumstances, is it possible to do without an authentication tag, and reject forged messages at a subsequent stage?  This obviously requires that the cipher mode of operation meets certain requirements about non-malleability; to my knowledge XTS mode qualifies.

In some cases (such as XML or JSON files), the bytes being encrypted have very specific semantic requirements, such that a random byte sequence will be rejected with very high probability.

In the case of XML or JSON, I don't believe that's actually the case.

For example (example was the first JSON example I googled, simplified):

{
    "glossary": {
        "title": "example glossary",
        "GlossDiv": {
            "GlossList": {
                "GlossEntry": {
                    "GlossTerm": "Standard Generalized Markup Language",
                 }
            }
        }
    }
}

}

If the modification was, say, to 16 bytes in the string "Standard Generalized Markup Language" (or "example glossary"), changing that to a random 16 byte string (which is the appropriate modification model for XTS), with nontrivial probability all the bytes will be within the JSON string alphabet (and not "), and hence that change would not be detected, as the modified string would still be valid JSON.