How can I visually explain M of N encryption (Shamir Key Sharing)? I'm trying to find a simple way to explain M of N keys to end users, where 2 keys would unlock something.

So far, all I found was this complex example where the key threshold was 1 (just one key of any lock will unlock this):

Larger version here.

Lacking any commonly accepted illustration, or image, is there any visual way to express M of N keys (Shamir Secret Sharing)?

I've used the following a number of times in lectures, and it always goes over well with a technical audience.

I start by asking them How many points do we need to uniquely define a line? The answer I get back is always 2.
Next I ask If I give you a single point in the X,Y plane, how many lines can you draw through that point? The answer I always get back is infinite.
Finally I say, Let's consider I have some secret (usually I use 42 for the obvious reason) and I want to share this secret with many people so that any two of them could get together and reconstruct the secret.

At this point, depending on the audience, I will either ask how I could accomplish this, hoping they get the idea to somehow encode 42 into the line (e.g., as the y intercept). Or, I will just tell them how it works.

All of this can be shown visually, which I would try to add pictures here, but I don't have time at the moment.

For even non-mathematical audiences, if I start with #2 above (draw a point on the board or in a slide and ask how many straight lines can be drawn that pass through this point), it works well. Then I move to #1, then #3.


Are collisions possible on the output of Blowfish? I'm using the Blowfish block cipher to encrypt messages of 64 bit without using any block cipher mode of operation. Can I still have a collision?

I'm asking this to understand if Blowfish is susceptible to the birthday attack when used on plaintexts of 64 bit.

No, you cannot, unless you have repeated messages, or use different keys. A block cipher such as Blowfish is a keyed random permutation or bijective mapping.

That means for each key any plaintext block is mapped to exactly one ciphertext block during encryption, and the ciphertext block is mapped to that particular plaintext block during decryption.

For different keys there are different mappings. So if you mix keys you may get a collision.


Would this authentication on a Diffie-Hellmann-key-exchanged channel work? Before I ask my question, let me say that I don't know the math behind OTR, so I don't know if the process of authentication in OTR is any similar to this.

Alice and Bob have exchanged keys using Diffie-Hellman key exchange
There's a man-in-the-middle - Eve.
This is the encryption "circuit": Alice -- e_alice -- Eve -- e_bob -- Bob
Both Alice and Bob use e to express the encryption key they use.
Thus in conditions where there is no MitM, e_alice == e_bob
Alice wants to verify that there is no MitM, so uses a verification question (and an answer) (like OTR in XMPP):

Q: Do you have a cat?

A: Yes

Note: Obviously use strong values for A. Don't ask about the presence of a cat, but rather cat's name (ideally if it's a unique name containing numbers and special characters) :P

Alice sends Q to Bob
Bob sends hash(e_bob+A). hash is any safe hashing algorithm, e_bob is the encryption key Bob uses, and A is the answer, salt in this context.
Alice compares received == hash(e_alice+A). In case this is true, there is no MitM.

In this context:

The hashing algorithm for zero-knowledge-proof
The encryption keys are a pre-shared (by the key exchange) secret
The answer is used as salt (while being another pre-shared secret), so Eve can't think: "Oh look, that's a sha1 hash. Let's try to crack it. Oh look it's our encryption key -- that's a no-go"
Possibly add additional encoding like base64 to minimize chance of hashed contents being in wordlists. (hash(base64(e_bob+A)))

Question: Are there any serious vulnerabilities, or would this work for authentication for insecure encrypted channels?

In the question as it stands now, nothing prevents Eve to relay Do you have a cat? to Bob, get the answer A = Yes by testing A for Yes or No against hash(e_bob+A) obtained from Bob, then send hash(e_alice+A) to Alice and defeat the protocol.

In a now-gone comment, it was added that we

  should use "strong values" for A; only Q is sent, plain A is never sent.

Notice that then, in order for Alice to perform a check, A must be known to Alice in advance. If this "strong value" (or even the convention to use it the way described) is known to Alice and Bob, but not Eve, then the technique works.

If only the "strong value" is unknown to Eve, it acts as a secret key in an ad-hoc protocol (for something academic we'd want to use this "strong value" as key to HMAC of message e)

If the convention is unknown to Eve, that's not cryptography in the modern sense of Kerckhoffs's second principle; and that's brittle, and can't be generalized.


Increased AES key lengths vs keyphrase entropy I'm selecting an AES key size for a LUKS partition using XTS-PLAIN64.

XTS will effectively reduce the AES key strength in half.

The default key size for AES XTS-PLAIN64 is 256 bits (meaning 128 bits effective). Given exponential progress making quantum computing ever more a reality, I was thinking to increase the key size.

I believe that AES is only defined on key sizes of 128, 192 and 256 bits, but cryptsetup/LUKS does allow me to select a key size of 384 or 512 bits.

I am aware that in theoretical related-key attacks certain cases AES256 may be less secure than AES192, but I'm not going to be using related keys.

What are the implications of using a 384- or 512-bit AES key?
Even if using XTS with AES256 (128 bit effective strength), would my 90-bit entropy keyphrase and 15,000 PBKDF2 iterations of SHA-512 still be the weakest link in the chain?
How would I work out how many bits of entropy and iterations are needed to make the keyphrase and the AES128 encryption the equal-weakest links in the chain?

If you could answer using finger-puppets in preference to complex formulae (where possible), that would be appreciated - I'm relatively new to the world of crypto.

I believe that AES is only defined on key sizes of 128, 192 and 256
  bits, but cryptsetup/LUKS does allow me to select a key size of 384 or
  512 bits.

AES itself is only defined for 128, 192 and 256 bits keysize.

However, XTS involves two instances of AES which can (and should) be keyed independently, meaning XTS-AES-256 really is 2 instances of AES-128 and 384 is two instances of AES-192 and 512 is two instances of AES-256.

  Even if using XTS with AES256 (128 bit effective strength), would my
  90-bit entropy keyphrase and 15,000 PBKDF2 iterations of SHA-512 still
  be the weakest link in the chain?

A break of AES by a quantum computer is stil decades away given the current state of quantum computers. Honestly I wouldn't worry about it if I'd need to worry about secrecy for less than say 50 years.

And yes your 90-bit-entropy passphrase will still be the weakest link. After all to brute-force that password, one would need about $2^{104}$ SHA-512 evaluations which is still much faster than even the "weak" $2^{128}$ AES evaluations. To get a comparable security level you either need to pick a (longer) passphrase or increase the iteration count by about $2^{20}$ which is about a million, meaning you'd be looking at 15 billion iterations which will take a lot of time to the point where it won't be acceptable to wait.

  How would I work out how many bits of entropy and iterations are
  needed to make the keyphrase and the AES128 encryption the
  equal-weakest links in the chain?

To brute-force an $n$-bit key, you need about $2^n$ operations. To brute force a password with $k$ bits of entropy you need about $2^k$ operations and you can slow this down by a factor of $t$ which is the iteration count (in this case, you can also use more memory which will make attacks more expensive). So what you want, is:

$$\log_2(t) + k=n$$


What is the importance of Rcon in Rjindael's key expansion from a security prespective? I do not see why the Rcon function is important, it looks like a waste of cycles.

$$\operatorname{Rcon}(i) = 2^{i-1} \bmod p(x)$$ is in  $\operatorname{GF}(2^8)$, where $p(x)$ is the irreducible polynomial $x^8+x^4+x^3+x+1$.

According to Section 3.8 of "The Design of Rijndael", authored by the cipher's creators, the purpose is to eliminate symmetries in the key schedule:

  The non-linear function is realized by means of the application of $\mathrm S_\mathrm{RD}$ to the four bytes of the column, an additional cyclic rotation of the bytes within the column and the addition of a round constant (for elimination of symmetry). The round constants are independent of $\mathrm N_\mathrm k$, and defined by a recursion rule in $\operatorname{GF}(2^8)$:

(Emphasis mine.)

Section 5.8 elaborates a bit more on this:

  For the key schedule in Rijndael the criteria are less ambitious. Basically, the key schedule is there for three purposes.

  The first one is the introduction of asymmetry. Asymmetry in the key schedule prevents symmetry in the round transformation and between the rounds leading to weaknesses or allows attacks. Examples of such weaknesses are the complementation property of the DES or weak keys such as in the DES [28]. Examples of attacks that exploit symmetry are slide attacks.

(Emphasis mine.)

To summarize: Adding the round constants $\mathrm{Rcon}$ is a very cheap way (it's not that many cycles) to make each step of the key schedule slightly different, avoiding a variety of attacks that have become apparent in the past.


compact hardware implementation of inversion based 8-bit s-boxes $\DeclareMathOperator{\GF}{GF}$
I cannot figure out how should I determine the matrix for transmission over $\GF(2^8)$ to $\GF(((2^2)^2)^2)$ in compact hardware implementation of inversion based 8-bit s-boxes.

In https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=8&ved=0ahUKEwjTrd3xsPzVAhVD5xoKHbHWDVAQFghUMAc&url=https%3A%2F%2Fcore.ac.uk%2Fdownload%2Fpdf%2F36718483.pdf&usg=AFQjCNFhSmTqjJz99DmRt8-19g7S-nXqaw , the author has searched among all potential $\GF(((2^2)^2)^2)$ to find the isomorphism tower field for inversion computation with the least area resources; and in page 24 it is showed that how the transmission matrix should be determined. However, I do not know if my $\GF(2^8)$ is different from AES, how should I build the corresponding matrix.

In fact, I do not know if the values of y, z and w would be different, and how should I determine them in the new $\GF(2^8)$!

I would appreciate if someone help me with this problem?

$\DeclareMathOperator{\GF}{GF}$
You can rebuild the transition matrix by using the fact that it is linear (which is why you make a transition matrix) and that it is a field isomorphism. Also, the solution is not unique: you may find several distinct transition matrices that will ultimately allow you to compute inversions in $\GF(2^8)$, but going through different representations in the tower of fields.

In general, you want to find the mapping of $\GF(2^k)$ within $\GF(2^n)$, for $k$ a divisor of $n$. By field isomorphism, $0$ is $0$, so you now want to consider the non-zero elements. For any $x \neq 0$ in $\GF(2^k)$, you know that $x^{2^k-1} = 1$ (since the non-zero elements in a field form a multiplicative group). But a polynomial equation of degree $2^k-1$ cannot have more than $2^k-1$ solutions. So the elements of $\GF(2^n)$ that actually are the elements of $\GF(2^k)$ are exactly the solutions to $x^{2^k-1} = 1$.

Moreover, the multiplicative group of non-zero elements in a field is cyclic. So, for any $k$ that divides $n$, there exists at least one value $g$ whose order is exactly $2^k-1$. In fact about half of them should be such generators. To find an element of of order exactly $2^k-1$ in $\GF(2^n)$, apply the following:

Generate a random non-zero element $h$ in $\GF(2^n)$.
Compute $g = h^{(2^n-1)/(2^k-1)}$.
Order of $g$ is guaranteed to be a divisor of $2^k-1$. You just have to verify that it is not a strict divisor, by computing $g^e$ for any $e$ that divides $2^k-1$. For an AES S-box with $n = 8$, number of elements is so small that trying all of them is a workable strategy. So simply check that $g^e \neq 1$ for all $e$ from $1$ to $2^k-2$.

Therefore, you can compute your mapping in the following way:

$0$ maps to $0$.
Select an element $g$ of order exactly $2^n-1$ in the tower of fields.
Select an element $g'$ of order exactly $2^n-1$ in the target field ($\GF(2^n)$).
Define that $g$ maps to $g'$. Thus, for all integers $i$, $g^i$ maps to $g'^i$. By trying all $i$ from $0$ to $2^n-2$, you will cover all non-zero elements.

At that point you have a complete transition map. The corresponding matrix (since that map is linear) is obtained by simply selecting the map elements for $1$, $z$, $z^2$, $z^3$... $z^{n-1}$.

You might also want to have a look at this article by Boyar and Peralta. They built the smallest known so far circuit for computing an AES S-box. Notably, they begin in the same way as Canright, but they don't make a full tower of fields; instead, they stop at $\GF(2^4)$, for which they compute a fast circuit with a heuristic approach, which appears to yield better results than the full tower. They also explore the problem of minimal circuit for a linear transform.


Why does the TLS spec for TLS-PSK say not to derive the shared secret from a password? According to a note at the end of section 2.2 of the TLS 1.3 spec (RFC 8446),

When using an out-of-band provisioned pre-shared secret, a
critical consideration is using sufficient entropy during the key
generation, as discussed in [RFC4086].  Deriving a shared secret
from a password or other low-entropy sources is not secure.  A
low-entropy secret, or password, is subject to dictionary attacks
based on the PSK binder.  The specified PSK authentication is not
a strong password-based authenticated key exchange even when used
with Diffie-Hellman key establishment.  Specifically, it does not
prevent an attacker that can observe the handshake from performing
a brute-force attack on the password/pre-shared key.

Is the vulnerability of concern here that observing a handshake would allow an attacker to brute force the shared secret offline based on the PSK binder?
And, if an attacker could recover the shared secret, is confidentiality of the previously-observed TLS-PSK stream compromised? Or would this only allow the attacker to compromise future streams (e.g. by spoofing the server and/or client as a man-in-the-middle?)

Is the vulnerability of concern here that observing a handshake would allow an attacker to brute force the shared secret offline based on the PSK binder?

Sometimes; there are two ways for TLS 1.3 to negotiate with a PSK; with the PSK only, or with a PSK and an (EC)DH.  If an (EC)DH is used, the vulnerability of concern here is that a client (who does not initially know the PSK) would be able to attempt a negotiation with a server, and as a result of that exchange, run an offline test on a large number of possible PSKs.  On the other hand, if only a PSK is used, then yes, a passive attacker could go through and test the various PSKs (and then decrypt the encrypted data).
When (EC)DH is used, then what an attacking client would do is send the client hello (with the appropriate pre_shared_key identifier, and an honest DH key share, that is, one for which he knows the private value); the server would respond with a server hello, followed by "encrypted extensions".
This encrypted extension is encrypted with a key which is based on stuff the client knows (nonces, the DH shared secret), and the PSK.  What the client can do, for each guess of teh PSK, plug that into (with the inputs he already knows) into the TLS 1.3, and derive the corresponding session key, and then use that key to verify the authentication tag in the encrypted extension.
Once he finds a PSK that makes the authentication tag validate, he can then use that PSK to masquerade as either the client or the server in future exchanges (or do an active MITM).

Or would this only allow the attacker to compromise future streams (e.g. by spoofing the server and/or client as a man-in-the-middle?)

TLS 1.3 allows either PSK-only mode, or a PSK along with an (EC)DH exchange.  If a PSK-only mode is chosen, then the attacker can passively listen in.  If the client decides to do PSK plus (EC)DH, then the attacker cannot passively listen into future (or past) streams; this allows only active attacks.


Are shorter password hashes safe? How much can I shorten a password hash before it begins to impact security?

Suppose that I use PBKDF2 (correctly salted) with HMAC-SHA256 as the PRF.  From what I've seen, it's typical to use 256 bits of output, since that matches what comes out of the PRF.

My intuition suggests that there would be no security impact if this output were truncated to 128 bits.  Is this correct?  My reasoning here is that salting prevents multi-target attacks, and that collisions are unimportant in the context of password verification.

My intuition suggests that there would be no security impact if this output were truncated to 128 bits. Is this correct? My reasoning here is that salting prevents multi-target attacks, and that collisions are unimportant in the context of password verification.

Correct, there is no practical security impact. The preimage security of the hash function is what matters for password hashing, and 128 bits is long enough to prevent brute force preimage search. You could probably even go shorter than that, but database space is usually cheap which is why using the full 256 bits is common.

In principle, with a 129+ bit entropy password you would lose some security, as a brute force attack to find some password with the same hash would become faster. Such passwords are very uncommon, however, and the brute force would remain infeasible even if theoretically faster.

(If SHA-256 is found to be very weak after some new attack all bets are off. The attack could allow a faster preimage attack on truncated output or it could not. The opposite could even be the case.)


Is it safe to generate GCM/GMAC intermediate tags? I would like to use GCM/GMAC in next manner:

abcd|Tag0|efgh|Tag1|ijkl|Tag2| ... |wxyz|TagN

The nuance is each tag I gonna generate is not from its last block but the all previous plain- or cipher text preceding last tag. Otherwise speaking, last tag let authenticate the whole received stream, for example:

Tag0 authentifies 'abcd'
Tag1 authentifies 'abcdefgh'
Tag2 authentifies 'abcdefghijkl'
TagN authentifies 'abcdefghijkl...wxyz'

I know that xor`ing of two tags together discards H and gives you some info about the internal cipher context.

So, my questions are:

Can xor`ed tags info be useful for any kind of attack?
What weakness does this scheme have?

Update. The full scheme of how I want to use GCM/GMAC

I have one randomly generated key
I have one randomly IV
I gonna encrypt and authenticate a bytestream of unknown length divided into blocks
After each block I gonna produce an intermediate tag that should authenticate all previous bytes of the stream
After intermediate tag generation, I gonna continue encryption flow further

Scheme from above with the single encryption function call may be considered as a scheme with separate calls but with the same Key, IV, and partially data.

Call 0:
'abcd'|Tag0

Call 1:
'abcdefgh'|Tag1

Call 2:
'abcdefghijkl'|Tag2

Call N:
'abcdefghijkl...wxyz'|TagN

Can xor`ed tags info be useful for any kind of attack?

Yup; by using the same IV for multiple generated tags, the attacker can effectively recover the internal GCM value $H$, and with that, generate tags for any arbitrary data.

(You stated that xor'ing the two tags discarded $H$; unless you are using the notation $H$ to mean something other than the secret value that the GMAC polynomial is evaluated at, this is not correct.  It does discard the $Encr(IV)$ value that is exclusive-or'ed with the polynomial evaluation.

GMAC works this way: it takes a ciphertext (and AAD), formats them into a polynomial, and evaluates that polynomial at a point H.  Then, it adds (xors) in a value that depends on the IV.  So, to attack this, the attacker would take the two ciphertexts (and AADs), format them into the polynomials (with the tags as the constant coefficient), and then subtract (xor) those two polynomials. What he ends up with is a polynomial that he knows that evaluates to 0 at $H$; all he needs to do is find a zero of that polynomial.

That turns out to be a feasible task; in fact, with a second polynomial (which requires a third GMAC tag evaluated with the same IV), it becomes easy (the Euclidean Method over polynomials works).

This attack relies on the fact that the same IV is used for every tag; if a different IV is used (say, incrementing the IV whenever you generate a tag), this doesn't work, and it turns out to be secure.


Where is the SSH RSA modulus actually sent? This might be a stupid question but: When RSA key pairs are generated, there is a pubkey and a private key file. Where is the modulus? Is it appended to the keys? I can't find any information about that.

The modulus is part of the public key. For RSA, the public key consists of the pair $(n,e)$ where $n$ is the modulus and $e$ is the public exponent.

The SSH public key file contains both, typically one after the other. There's a number of ways to encode this information. The gory details of these encodings I leave to this in-depth answer (it includes a section on SSH).

The SSH private key file contains pretty much all numbers associated with the key generation process. If you want to take a look yourself, try running the following command

openssl rsa -in test.key -text

where test.key is your private key file.


How might one create a system of election by lot (sortition) that is both secure and verifiable? I've been puzzling recently over sortition, a democratic method of selection for public office which I find very fascinating. Basically, instead of choosing candidates like Hillary Clinton or Donald Trump through voting, under sortition citizens would be randomly selected to fill public offices (in which, under many models, they would then be FORCED to serve for some period of time). There are of course many nuances, but that is the general gist. It would be rather like jury duty in the modern United States.

One particular problem for which I haven't been able to find a fully-formed solution online is ensuring that the random selection is actually random (so that it statistically represents the full population, one of the goals of sortition when a large-enough body is selected, rather than representing special interests or folks who paid off the people in charge).

Let me be clear: I am not a cryptology expert by any means. Indeed, I am only in high school and have never taken a proper computer science course.

Nevertheless, I was wondering if anyone here had any ideas (phrased at a fairly elementary level) for how fraud in the random selection could be prevented. (EDIT: While, as pointed out in the comments below, you could just have blind-folded people pull the names out of a hat, that might not be enough to keep citizen confidence high given the high-stakes and temptation for bribery and other such shenanigans.)

I've been wondering if maybe there could be a connection to RSA public-key encryption, cryptographic hash functions or other one-way functions, Bitcoin, etc (all those are subjects I know at least a bit about). I'm thinking there'd need to be a way for everybody to verify that the sortition wasn't rigged in any way (perhaps through some sort of blockchain?). But the method of choosing (let's say it's a function of some sort) couldn't be too simple because it would probably also need to be difficult for anyone to predict in advance what input would map to a given output, right? (If a selected individual for a public office was an output but people could predict which inputs would lead to that individual getting selected, then the choice of inputs into the function might get rigged by special interests, right?)

And, also, if you're utilizing a fully determinate mathematical function that would be, of course, not truly random (although maybe that's okay - political pollsters don't do truly random sampling either in that sense, but no one really seems to mind). So there's that issue too -- what do we do when we say we want "random sampling" but also want to be able to verify that the sample wasn't tampered with? (I have heard of the topic of pseudo-random functions - is that related to this perhaps?) Perhaps randomness can be approximated well enough by introducing real-world data observations that are somewhat unpredictable?

Sorry for the length and it could be that these are fairly elementary questions (or maybe they are in fact very hard questions, I have no idea). I sincerely thank anyone who responds with any thoughts they may have on any aspects of this question.

One last thing: If there is a potential solution to this question that involves basic prime number/modulus RSA stuff, that would be really awesome -- since that's one of the few crytology concepts I actually sort of know. :) I don't really care at this point if potential solutions would actually work out in the super-complicated real world. I'm more concerned with finding something that's superficially plausible given the very elementary knowledge of cryptology I currently possess (e.g., basic RSA). Once I get more advanced I could then come back and refine everything.

I'm going to try to answer a more modest version of your question.

Imagine that the Dishonest Society, a small club of 100 members, needs to take care of an Arduous Task that will require 5 people to complete.  The members are lazy and so there are no volunteers.  The members also don't trust each other very much, so they want to use a _sortition_ protocol to elect a random committee to do the Arduous Task.

Let's assume for the following that the members have all come to agreement on the membership list of their club:

$$
M = \{ M_1, M_2, \dots, M_{99}, M_{100} \}
$$

A physical protocol

The intuition is that the members will collectively generate a random
number, and then each member will try to guess the number.  We'll rank
the members based on how close their guess was to the random number, and
select the 5 lowest-ranked members for the committee.

First we have to decide "how big" our numbers will be.  We are going to
have 100 guesses, so let's pick the range 0 through 8190, which should be enough. All of our calculations will be done modulo 8191.  Because 8191 is $2^{13}-1$, a Mersenne prime, we are actually working in the finite field $\mathbb{F}_{8191}$ -- it will come in handy later when we look at the cryptographic protocol.

Now obviously we need the members to commit to their guesses before we generate the random number, so each member $M_i$ secretly makes a guess $g_i \in \mathbb{F}_{8191}$.  We don't trust the members to be honest,
so we'll ask them to put their guess inside a sealed envelope and write
their name $<M_i>$ on the outside.  Once all the members have prepared
their guesses, we put all of the envelopes in a box and lock it.  If a
member tries to cheat by writing down a nonsense guess, we'll find out
later when opening the envelopes.  (And if a member tries to put someone
else's name on his envelope, we assume someone will catch him when he
attempts to put it in the box.)

Next the members need to generate a random number.  $\mathbb{F}_{8191}$
is fairly large, so dice would be impractical.  Instead we will ask each
member $M_i$ to pick a random number $r_i \in \mathbb{F}_{8191}$.  Then
we have them write $r_i$ on a slip of paper and toss it into a hat.  Once
all members have put their random numbers in the hat, we can sum them up
to get a truly random number that no member can influence:

$$
r = \sum_{i=1}^{100} r_i \pmod {8191}
$$

It is easy to see that as long as at least one member was honest and selected their $r_i$ at random then the result $r$ is also random.  It
is also easy to see that none of the members knew anything about what
$r$ would be at the time that they made their guesses $g_i$.  And they
can't go back and change their guess, because it's in a sealed envelope
inside a locked box.

Now we can open the box with the guesses and calculate each member's
ranking based on how close their guess $g_i$ was to the chosen number $r$:

$$
rank(M_i) = r - g_i \pmod {8191}
$$

The committee for the Arduous Task can now be formed by choosing the 5 lowest-ranked members.  Ties can be broken by a roll of the dice.

A cryptographic protocol

Assuming that all of the players can communicate with each other over a secure authenticated channels (standard in the multiparty computation literature) we can transform this physical voting protocol into a cryptographic protocol:

$M_i$ makes a random guess $g_i \in \mathbb{F}_{8191}$.
$M_i$ broadcasts a commitment $Com(g_i)$.
Wait until every $M_i$ has broadcast their commitment.
$M_i$ picks a random number $r_i \in \mathbb{F}_{8191}$.
$M_i$ sends each $M_j$ an additive share $[r_i]_j$ such that $\sum_{j=1}^{100} [r_i]_j = r_i$.
$M_i$ broadcasts $r'_i = \sum_{j=1}^{100} [r_j]_i$ and $g_i = Open(g_i)$.
Each player can now calculate the ranking of every other player as:

$$
rank(M_i) = g_i - \sum_{i=1}^{100} r'_i
$$

We use a commitment scheme to force each player to select their $g_i$ before they have received any information about $r$.  Because the
commitment hides $g_i$ until the openings are broadcast, the players
must select their $r_i$ before they have any information about the
other players' choices of $g_i$.

We use a secret sharing scheme so that no player (or coalition of players) has enough information to determine the $r_i$ of any other player, and so
this allows all of the players to send their $[r_i]_j$ shares to each
other simultaneously.

In the real world we'd want to also use a linear message authentication
code to verify each of the $[r_i]_j$ shares;  otherwise a dishonest
player could lie about $r'_i$ in step 6.  We'd also want to consider a
dishonest player who aborts in step 6 (without sending his $r'_i$ or
his $Open(g_i)$) after learning enough information to determine that he would be one of the "losers".

No fancy public key cryptography required!  :)


Implementing symmetric encryption algorithms with whole words Scenario

I have some unique requirements to encrypt text:

symmetric encryption;
the encrypted text will be a valid text (that means that humans could read it and not just “gibberish”);
I can not replace the key from time to time (that means no temporary \ one time key algorithms);
each word must be always encrypted to the same word (and only to one word).

These needs are important to support the following use cases:

a third party will get the encrypted text and will be able to index it for searches (effective indexing needs basic morphology, this is why need number 2 is important);
when someone sends this third party an encrypted word(s) it will be able to find the texts that associated with these words (this is why needs number 3 and 4 are important).

But I also have some flexibility in the system:

I can always add more words to a dictionary (if need in the encryption / decryption process);
both sender and receiver has access to this dictionary (always synced).

Example scheme

So basically I can use some sort of a dictionary and map words and replace each word in the encrypted word (like Caesar cipher but for words).

Every time I encounter a word I can add it to the dictionary as both original word and encrypted word.

For example:

Word: “I” Encrypted word: “Cat”
Word: “Love” Encrypted word: “Dog”
Word: “You” Encrypted word: “Home”

Now the text “I Love You” will be encrypted to “Cat Dog Home”. This fits all the needs that I have. But as you probably know, this is a very week encryption.

To make it stronger I was thinking about randomly inserting words that I know that are fake (no mapping to a real words), this (maybe?) prevents statistical analysis of the language (common words and etc).

For example:
 - Encrypted word: “Boy” is fake.
 - Encrypted word: “Test’s” is fake.

Now the text “I Love You” will be encrypted to “Cat Test’s Boy Dog Test’s Home Boy”. This fits all the needs that I have. But I believe this is still weak, so I’m looking for something better.

Symmetric ciphers

I’ve read about symmetric encryption algorithms like Blowfish, Twofish and AES-256 and from my (limited) understanding they are all algorithms that replace one byte with another and they consider to be strong encryption methods.

Is it possible to implement a symmetric cipher, but instead of operating on bytes it will operate on words?

NOTE

After further research I've come to the understanding that this question is more misleading than helpful.

The question asks about encryption but directs to obfuscation - and so may some of the answers.

I believe that noobs (like me) will be more distracted and misled than gaining anything from this.

Your best bet is, I think, to do it the other way round.

encrypt securely using a proven algorithm.
make the encrypted text human readable.

For example: AES-256 encode "Squeamish Ossifrage" using some key. Get, say, 512 bits of absolute gibberish. That is 64 bytes of 8 bits each; each byte can have one of 256 values.

Get a dictionary of 256 words (possibly, short words?). Read the 64 bytes, and for each value transform it into the appropriate word, giving you a "sentence" of 64 words:

Cat Hue Way Ten One Bat Bob Nod Ben Elk Joe Sex Van Eke ...

To decode, read in each word, and look for it in the dictionary. It is the 42nd word ==> read it as byte with a value of 42. Put all the bytes one after the other and get back the encrypted text, AES-256 decode it and Bob's your uncle.

This way, approximately 100 bytes of text become 60 bytes of encrypted binary code and those become 240 bytes of rehumanized code (each word is 3 letters plus one space). Or 180 bytes if you camelcase it: BobTenHueNitPinZoo... . You've got an overall expansion of about 1:2 or 1:3, which is quite reasonable.

And at the core you've got AES-256. Nobody wants to mess with AES :-)

Word becomes word

You want 'Cat' to always be encrypted as 'Dog'. This presents two problems. In the first place you either need to specify all the possible input words, or accept that some words will become gibberish; possibly pronounceable gibberish (there are algorithms for that) but still gibberish.

For example you can use a dictionary, consisting in a simple scrambling algorithm. When you find word #1138 in the cleartext, encrypt 1138 - this can be done with bit swapping if the dictionary has a size that is an integer power of two, for example 65536 words - so that it becomes another number within the same dictionary, say 31794. Word 1138 ("Horse") becomes word 31794 ("Staple").

What if a word is not in the dictionary? Then you need to encrypt it as a different word that is surely not in the dictionary (or you wouldn't be able to decrypt it). So Cat becomes Dog, Horse becomes Staple, Battery becomes Correct... and rumplestiltskin becomes xyzbatelkjoesexvanekewayhuejimsixnoddandinsupfoxfenjoeputits - where the xyz prefix warns the decoder that what follows is an encrypted sequence.

Or if you can store the new word in the dictionary, then you can simply use its MD5 to index it in 32 bits, or 4 bytes, or 4 three-letter words; giving you xykjimsuptitbat. The xyk prefix now tells the decoder that what follows is a 32-bit MD5 hash. Sender and receiver must agree on the dictionaries and now they also need to keep them synced.

Your encrypted sentence would become something like

Fence, xykjimsuptitbat!
Normal bog nuclear cascade iron irksome
Welcome japanese brillig sympathetic
Anathematize copper bleat irksome kill airplane
Severn'emporium zip cascade enormous

and here's the second (and possibly third) problem: on long texts, some words will repeat and lend themselves to analysis. Here, irksome and cascade are present twice each. Which makes one suspect that they (or at least one of them) might be a common English word such as "it", "the", "of", or something like that. Just as database applications need to be wary of little Bobby Tables, this kind of encryption schemes need to fear young Etaoin.

Also, you know which words are not common (by their prefix), so that you can tell between a normal sentence and 'Twas brillig, and the slithy toves... at a glance.

Notice the punctuation is kept, therefore it is quite easy to surmise that emporium is either 'll, 'm, 's, 't or 've; not too many English words contain a quote sign (a dozen? Twenty? Still too few).

To encrypt anything except very short texts, and seldom at that, means that an attacker will (relatively) quickly discover that xykjimsuptitbat actually means supercalifragilisticexpialidocious. In other words, this is not encryption -- it is "mere" obfuscation.

So... why do you have such a "dangerous" requirement?

I'll go out on a limb and guess that you need this to be able to run searches on the encrypted texts. There are techniques that allow you to do this securely, but they all exploit some features of the search being performed; in other words, there is no one-size-fits-all solution that is also proved and secure (i.e. demonstrably at least as secure as some proven, or at least widely adopted, solution). But if you supply some more information we might be able to help.

Or, of course, you may need it for some other reason altogether - but without knowing the why, one is hard put to come out with a how.

Some search schemes

There are several possible "searches". First of all let us consider that all searches by necessity disclose some information, and if you allow powerful enough searches, this is exactly equivalent to having the text unencrypted (you basically run a (sort of) Hangman game with the ciphertext - what is called a oracle attack).

Now a "search" could be the operation of querying "What records contain a particular keyword among a given set?", or "What records contain this arbitrary keyword?", or "What records contain this arbitrary user supplied text?", or even "What records match this regex?". There has been quite some work on the matter; try googling for 'PEKS'.

The easiest (and most secure) case is that where you have a fixed set of keywords. So in the records

 1: Shall I compare thee to a summer's day?
 2: Thou art more lovely and more temperate.

you can search by thee, day, art or thou, but not by summer.

You can implement this by simply appending to the encrypted text a sequence with the keywords - which could as well be in cleartext:

 1: blindalasbirigudacomefosseantani|Thee|Day
 2: tarapiatapiocalasupercazzolaprematurata|Thou|Art

After a search for Thou we know that it is contained in record 2, and nothing else. And as you see, the more keywords we store, the less security we have. Store all keywords, and you might as well not encrypt at all.

The above scheme can be made more space efficient by noticing that the encrypted text is actually never used, so you can just store the keywords.

Otherwise, we're just obfuscating; and therefore we might just as well go for performance.

For example you might XOR all records with a so-called "worm" (we're talking Vigenère cipher here) of, say, 16 bytes, and expand all letters to their hexadecimal equivalents. The resulting text is vulnerable to several possible attacks, but could still be thought of as "encrypted". To search, you XOR the search string with the 16 possible rotations of the worm - SAYHELLOWORLDNOW, AYHELLOWORLDNOWS, YHELLOWORLDNOWSA..., hex-encode it, and use the result as a normal text search. It will be anywhere from 1.x to 16 times slower depending on storage retrieval performance, but it will work.

The most promising possibilities exist wherever the actual search is not under control of the Searcher - he may submit texts to the search engine, but can not act on behalf of it, and for instance, is limited in the submission and retrieval speed (in other words, there is no real feasibility of a large scale dictionary/oracle attack). For instance, you could have a MySQL engine with a search function implemented as a closed source, loadable UDF module.


How do you calculate the linear approximation of an S-BOX? I've been following this very good tutorial on linear cryptanalysis, and I'm stuck at the linear approximation part. I have no idea what input and output masks are. I don't understand what he's doing and why. Can somebody please help?

You might want to check out this stackoverflow question: What is Bit Masking?

Basically, the mask selects certain bits from the words, where a word is a vector (a row) of bits. The input mask selects certain bits from the input word, and the output mask selects certain bits from the output word.

The goal is to find a set of output bits that can be expressed as a linear combination of input bits with the highest probability. "A linear combination" in this case basically means no bitwise AND/OR gate are present in the expression, only XOR gates. This is relevant because when you have something like $\text{out} = a \oplus b \oplus k$, where $\oplus$ is XOR, then you can trivially solve for $k$ by computing $k = \text{out} \oplus a \oplus b$.


How would multiple uses of a vigenère cipher be decrypted on paper (classic)? As far as I can tell (from reading the Wikipedia article about it) decrypting a message encrypted with the vigenère cipher is possible on paper.

But what would happen if the message is encrypted multiple times with a set of different keywords?

  "Thwaites challenged Babbage to break his cipher encoded twice, with keys of different length. Babbage succeeded in decrypting a sample, which turned out to be the poem "The Vision of Sin", by Alfred Tennyson, encrypted according to the keyword "Emily", the first name of Tennyson's wife. Babbage never explained the method he used. Studies of Babbage's notes reveal that he had used the method later published by Kasiski, and suggest that he had been using the method as early as 1846."
  Link to the Kasiski examination

(I must admit, I don't quite understand how to apply the method mentioned above effectively).

An example message:

First time (keyword: "ASIMPLEPASSWORD")
This is a secret message that was encrypted multiple times with a vigenere cipher
ASIM PL E PASSWO RDASIMP LEPA SSW ORDASIMPL EPASSWOR DASIM PLEP A SSWORDAS IMPLEP

Second time (keyword: "RANDOM")
TZQEXDEHEUJAHDHSKISTELPTOSOSEFRQXFTOQJLLALZVWIEMELTXWANACSEHRWKUESIG
RANDOMRANDOMRANDOMRANDOMRANDOMRANDOMRANDOMRANDOMRANDOMRANDOMRANDOMRA

Third time (keyword: "UNKNOWNTOYOU")
KZDHLPVHRXXMYDUVYUJTRODFFSBVSRIQKIHAHJYOOXQVJLSYELTXWANACSEHRWKUESIG
UNKNOWNTOYOUUNKNOWNTOYOUUNKNOWNTOYOUUNKNOWNTOYOUUNKNOWNTOYOUUNKNOWNT

Result
EMNUZLIAFVLGSQEIMQWMFMRZZFLIGNVJYGVUBWIBCTDOXJGSYYDKKWATQQSBLJUHSOVZ

The reason I'm asking is simple research (and curiosity). I'm writing a story involving encrypted messages in a fantasy setting (so, no computers!). In-depth knowledge about the cipher (including methods and formulas known today) can be used, though.

I'ld like to see if this method would be impossible to crack by "classic means/hand", or if it has it's own (perhaps obvious to experts) weakness.

How would an expert in this field approach the problem?

At what point would that expert either realize the message was encoded multiple times or mistakingly believe it's not a vigenère cipher?

What additional hint or information would that expert need to decrypt the message?

My impression is that it would at most take a longer ciphertext to be decrypted. Imagine first the scenario where the different keys have the same length:

$K_1=hello$

$K_2=world$

In that scenario, the keys add up and the result of applying $E_{K_2}(E_{K_1}(m))$ can be expressed as one single operation: $E_{K*}(m)$, where $K*=dscwr$. Therefore, not a lot is two encryptions are nested with keys of the same length.

If you use keys of different lengths, you'll meet the same combination of letters at some point. Let's say you have a key of length 3 and a key of length five:

$K_3=abc$
$K_5=rolex$

After the position 15 ($5 \cdot 3$), you'll encrypt again a value with the same combination as in the position 1. Therefore, it is as if you had two 15-character keys:

$K_{15}'=abcabcabcabcabc$

$K_{15}*=rolexrolexrolex$

So, for this case in particular, you win nothing.

Now, for the most general case, keep in mind that no paper cipher is a serious rival against the existent computational power. However, if by some clever narrative you manage to limit the powers of the adversary to just paper based attacks, there are paper algorithms much stronger than Vigenère. You can start by taking a look at Solitaire: https://www.schneier.com/cryptography/solitaire/


How many KDF rounds for an SSH key? What is the best practice on choosing how many key derivation function (KDF) rounds/iterations when generating an SSH key pair with ssh-keygen?

Am I correct in saying that it is unnecessary if the passphrase is strong enough? Is there some kind of formula for how long it would take to crack a private key given the passphrase length and KDF rounds?

My guess is that the default value of 16 for when generating an Ed25519 key is small enough to be almost imperceptible for normal use (logging into a server from the command line), but adds significant expense to any brute-force attempts. I'm wondering if it's worth increasing it.

I did also tried to find a good value for the -a flag, in a MacBook Pro Mid14 (i7), trying to login in to a Debian 8.5, I had this results:

-a 1000 Took about ~20s.
-a 100 Varies between ~3.5s to ~6s.
-a 64 (4x default value) ~3 to ~9s.
-a 16 (default) ~2s ~2.5s.

In the end I just stick with the default since I'm not a paranoiac and I don't like to wait, however I did found in my research a value of 100 is not uncommon to choose.


mode of operation in cryptography We need to choose a mode of operation for a Telnet like application where the average message size is between 7 and 1024 bytes. What is the best mode of operation in this case?

a.  CBC
b.  CFB
c.  CTR
d.  Any of the above is ok

I would pick e) none of the above. None of those modes offers integrity protection, so unless integrity is handled elsewhere, your application is wildly insecure. An attacker could modify bits in transit and do nefarious things.

Of the three, CFB and CTR are the worst for the application and should be very easy for an attacker to mount successful attacks, changing commands being sent to the server that are properly formatted. CBC would take a little more creativity, but shouldn't be too hard for an intelligent attacker.


What is the best-practice for encrypting small files? I would like to know how to store a sensitive file; a credential of sorts.  I want to password-protect it, obviously.  It would be appropriate - in my application - to prompt the user for the password each run.  There are proper apps - like SSH - that password-protect private keys and so on, and that's the model and best-practice I'd like to follow.

What is the best-practice for encrypting small files?  I'm thinking of generating a random key to encrypt the file with and using a block cipher.  And then encrypting this random key with the user's password, and trying to salt and stretch that password.

In the same way that storing password hashes is something you should turn to a proper 'stretching' function like bcrypt/scrypt/PBKDF2 (ideally via a library like Python's passlib) rather than rolling your own, are there proper algorithms and libraries for password-protecting files?

The most important best practice in cryptography is: Don't invent your own algorithm, and to a lesser degree, don't invent your own protocol. An encrypted file format is a protocol.

Use an established format, like the OpenPGP message format, for your files. (This does support password-based encryption, too.)

This has the main advantage:

You can be quite sure that it is correct, i.e. no mistakes in the design which would allow easy cryptanalysis. (Not 100% sure, but at least a lot more eyes looked at it than will ever look at your own protocol.)

Another nice bonus is that your customers then are able to use the encrypted files also without your program, if necessary (e.g. when your program is not available on the system, has bugs, gets lost, or similar).


Is EKE attackable by a brute-force password search? So I'm trying to properly implement the EKE protocol and I'm using C# with the Windows CNG and ECDH key exchange. I need to use this because it's FIPS certified and all that jazz.

So what I'm understanding about EKE is the fact that it depends on the fact that the public keys are completely randomized, therefore not verifiable plaintext. Otherwise it would be easy to run a dictionary attack against the protocol because the public keys are encrypted using the pre-known password.

Here's my problem: I noticed that in the CNG algorithm, the public key is a large byte array and it is completely randomized except for the first 6 bytes are always the same. From there on its completely randomized. This leads me to believe that if I wanted to run a dictionary attack against that, all I would need to know is what the first 6 bytes were and I could validate that I was able to decrypt that public key or maybe even brute force it.

To protect against this, I could easily truncate off the first 6 bytes and encrypt the rest of the completely randomized byte array with the password and then just add those 6 bytes back on either endpoint to calculate the secret key.

I'm pretty sure that's right but I'm discovering that cryptographic systems are fiendishly tricky and I wanted to run it past you guys to make sure I'm thinking about this correctly.

Doing EKE over an EC group is a tricky (and is something that RFC6124 avoids).  The problem, as you note, is preventing an attacker from being able to determine whether a possible decryption is impossible (and hence he can remove that potential password from the list); that turns about to be considerably more involved than you would expect.

Even if you skip the first six bytes, well, the EC X and Y coordinates are not actually randomized (even though they look random); these coordinates are actually integers (if you're doing even-characteristic EC, field elements, don't worry about the distinction) which are related by an equation (perhaps $y^2 + ax = x^3 + b \mod p$) that's easy to check; this would easily allow an attacker to do a dictionary attack.

Now, all this can be handled; you can just use the X coordinate (ECDH still works just fine; however, your ECDH package might not support that), and you can deal with the problem that about half of the bit patterns are not possible EC X coordinates (and that's also easy to check); you could modify the encryption algorithm to deal with that as well.

On the other hand, all this is rather tricky for someone who isn't used to working with Elliptic Curves.  I would strongly recommend that you use either EKE using a MODP group (as RFC6124 has; don't forget you have you use the nonstandard generators that RFC6124 has), or go with SRP.


One time pad (OTP) perfect secrecy with different key space Let say
$K_{0} = \left \{  0,1\right \}^n$
$K_{1} = K=\left \{ 0,1\right \}^n$ \ $0^n$
$[b\leftarrow \left \{0,1 \right\}, k \leftarrow K_{b}:b=1|k \neq 0^n]$ --- (1)
Key is chosen using constraints (1).
Is this scheme perfect secret assuming OTP is used as encryption scheme.

I thought of using Shannon theory (|K|>=|M|) of perfect secrecy but the key distribution is different. Therefore I could not come up with any solution.

Also: What's the probability of constraints 1? If we can find also we can say that given scheme is perfectly secret or not.

It cannot be perfectly secret : if $C = M \oplus K$ is your encrypted message, all the possible values of $M$ do not happen with equal probability. Indeed, the case $M = C$ (corresponding to $K = 0$) is twice less liquely to happen. You cannot have $H(M) = H(M|C)$; if e.g. $M$ is drawn uniformly at random, the distribution of $M$ given $C$ is clearly not the uniform distribution.

  What's the probability of constraints 1? If we can find also we can say that given scheme is perfectly secret or not.

The probability distribution of $M$ given $C$ is $1/2(1/2^n + 1/(2^n-1))$ for every $M \neq C$, and $1/2^{n+1}$ for $M = C$. Hence the distribution of $M$ given $C$ is clearly not uniform.


Constructing an integer with specific totient without factorization Given $N(=pq)$, but not its factorization. Somehow you manage to know, that $k$ divides $\phi(N)$. Is it possible to come up with an integer $N^{*}$, for which $\phi(N^{*})=\phi(N)/k$, without factoring $N$?

Remark: $p$ and $q$ are distinct odd primes (if not, we can factor $N$), thus $\phi(N)=(p-1)(q-1)$. Define $p'=(p-1)/2$ and $q'=(q-1)/2$. It holds $\phi(N)=4\,p'\,q'$.

What's asked is not always possible. As a counterexample, assume $k=2$ (which is a possible $k$, from above remark), and $p\equiv 3\equiv q\pmod4$ (which covers about 25% of RSA keys). If we could find $N^*$ with $\phi(N^{*})=\phi(N)/k$, it would hold $\phi(N^*)=2\,p'\,q'$ with $p'$ and $q'$ odd. Therefore¹ $N^*$ would be of the form $2^s\,r^t$ with $r$ prime, with $\phi(N^*)=(r-1)\,r^{t-1}$. Therefore we could factor $N^*$, yielding $r$ and $e$, thus $\phi(N^*)$, thus $\phi(N)$, allowing to factor $N$.

Still with $k=2$, $p\equiv3\pmod4$, but this time $q\equiv5\pmod8$ (which covers another about 25% of RSA keys), we have $\phi(N^*)=4\,p'\,q''$ with $p'$ and $q''=(q-1)/4$ odd, and the two possible (non-exclusive) options are²

that $N^*$ is of the form $2^s\,r^e$ with $r$ prime, which we handle as above.
that $N^*=(2\,p'+1)\,(2\,q''+1)$ with $(2\,p'+1)$ and $(2\,q''+1)$ distinct primes, in which case $N^*=p\,((q+1)/2)$, thus $\gcd(N,N^*)$ will be $p$, yielding a factorization of $N$.

More generally, if what is asked was possible, there is some chance that at least one of the following holds:

$\gcd(N,N^*)$ reveals a factor of $N$.
we can factor $N^*$ (including but not limited to $N^*=2^s\,r^t$), then can compute $\phi(N^*)$, thus $\phi(N)$, allowing us to factor $N$.

I have a feeling that's a fair chance for random $N$ when $k$ is small.

Independently: When $k$ is large, and especially when it is prime, it's value is revealing: it must divide $p-1$ or $q-1$, thus $\gcd(N,j\,k+1)$ will be $p$ or $q$ for some $j$, and it is worth trying to find $j$ by enumeration at least when $\sqrt N/k$ is small enough and there is no reason to believe that $\max(p,q)/\min(p,q)$ is large.

When $k$ has a large prime factor $k'$ that we can find, that $k'$ must divide $p-1$ or $q-1$, and we may be able to use the same approach to factor $N$. And with a bit of luck, the product $k'\,k''$ where $k''$ is a large factor of $k/k'$ will divide $p-1$ or $q-1$, allowing to factor $N$. And even if we can't fully factor $k$, because the largest factor we find is composite, it  still has a fair chance to divide $p-1$ or $q-1$, allowing to factor $N$.

I vaguely conjecture (would not bet the house) that there are vanishingly few semiprimes $N$ such that an oracle knowing its factorization could reveal $k$, $N^*$ as in the question without the combination of the above techniques being of great help to factor $N$. In other words, what's asked would demonstrably be impossible for overwhelmingly most $N$.

¹ This uses the following lemma: if $\phi(m)\equiv2\pmod4$, then $m$ is of the form $2^s\,r^t$ with $r$ prime. Proof of that lemma can be by contraposition using the expression of Euler's totient: $$\phi\left(\prod_{p_i\text{ distinct primes}} {p_i}^{e_i}\right)=\prod_{\text{same }(p_i,e_i)}(p_i-1)\,{p_i}^{(e_i-1)}$$

² This is left as an exercise to the reader, using the same kind of argument as for the above lemma.


Encrypt-and-mac IND-CCA security I have been stuck all day trying to understand how to show that an Encrypt-and-Mac ($SE_{EaM}$) scheme is not IND-CCA secure. I have seen this similar post, however it is slightly different and the notation in the selected answer confuses me.

The line of thought I want to follow is this: While the $MAC$ is perfectly UF-CMA secure it could still reveal information on the message since its computed directly from it and not the ciphertext (like in encrypt-then-mac). Consequently this would mean that $SE_{EaM}$ is not even IND-CPA secure, and therefore not IND-CCA secure. I want to know first if this line of reasoning is sound.

In terms of actually showing this, is it feasible to simply suppose that the $MAC$ scheme could afford no privacy to the message whatsoever. The post I referenced seems to have done that by adding the message in the clear to the actual tag ($t = m|t$), if I misunderstood I would appreciate clarification. If this is valid how could I use this in a IND-CPA game of $SE_{EaM}$?

I hope it will then become clearer how to show in a reduction that since IND-CCA implies IND-CPA, my $SE_{EaM}$ scheme is not IND-CCA. Or maybe I am looking at it completely wrong, in which case do let me know.

Thanks and happy new year!

There is an excellent paper from Bellare and Namprempre that addresses the security properties of composite schemes in a rigorous and formal manner. Regarding IND-CPA security of Encrypt-And-MAC the paper has this to say:

  E&M does not provide IND-CPA. E&M does not preserve privacy because the MAC could reveal information about the plaintext. This is true regardless of whether the MAC is weakly or strongly unforgeable. We provide details assuming that the MAC is strongly unforgeable below.

  Let $\mathcal{MA = (K_m, T , V)}$ be a given MA scheme. We define an MA scheme $\mathcal{MA'}$ which is the same as the given one except that it prepends the first bit of the message to the tag. Formally $\mathcal{MA' = (K_m, T', V')}$ has the same key generation algorithm as the given MA scheme and the following tagging and verification algorithms:

  Algorithm $\mathcal{T'(K, M)}$
  Parse $M$ as $x||M'$ where $x$ is a bit
  Return $x||\mathcal{T}(K, M)$

  Algorithm $\mathcal{V'(K, M, \tau)}$
  Parse $M$ as $x||M'$ where $x$ is a bit
  Parse $\tau$ as $s||\tau'$ where $s$ is a bit
  If $x = s$ and $\mathcal{V}(K, M, \tau') = 1$ then return $1$
  Else return $0$

  It is easy to see that if $\mathcal{MA}$ is SUF-CMA secure then $\mathcal{MA'}$ is SUF-CMA secure. However, if $\mathcal{MA'}$ is used as the base message authentication scheme in the E&M composition method, the resulting symmetric encryption scheme will not achieve IND-CPA because the first bit of the message is provided to the adversary via the MAC. The adversary can use this to break the scheme in the IND-CPA sense as follows. It queries its $\mathrm{LR}$ oracle with two messages $M_0$, $M_1$ such that the first bit of $M_0$ is $0$ and the first bit of $M_1$ is $1$. It gets back ciphertext $C = C'||\tau$ . It lets $s$ be the first bit of $\tau$ . As per our construction above, $s$ is the first bit of $M_b$ and hence $s = b$, so the adversary returns $s$. The advantage of this adversary is one.

  In fact, we can make a stronger statement. Not only do there exist schemes for which the E&M method fails to provide IND-CPA, but it will fail to be so for most of the commonly defined MA schemes, including CBC-MAC and HMAC, because the latter are MACs. Indeed, an adversary can use the MAC present in the ciphertext of the composite scheme to see whether the same message has been encrypted twice, something which should not be possible if the scheme is to meet a strong notion of privacy like IND-CPA. This attack is successful regardless of whether the underlying MAC is weakly or strongly unforgeable.

  E&M does not provide IND-CCA and NM-CPA. Since both IND-CCA and NM-CPA imply IND-CPA, the above means that E&M provides neither IND-CCA nor NM-CPA secure.

So your line of reasoning that you provided in your question is correct. We can use the fact that a MAC can leak information about the plaintext to break such a schemes IND-CPA security. Then, it follows that, since IND-CCA implies IND-CPA, a scheme that is not IND-CPA is not IND-CCA.


Is it safe to operate over the prime sub-group of Curve25519? Referring to D. J. Bernstein's paper Bernstein-Curve25519 on Curve25519, the group $\{\infty\} \cup (E(F_{p^2}) \cap (F_p \times F_p))$, where $p$ is the prime $2^{255}-19$ and $E$ is the elliptic curve $y^2 = x^3 + 486662x^2 + x$, has size $n = 8p_1$, where $p_1$ is the large prime $2^{252} + 27742317777372353535851937790883648493$.

In the same paper, he suggests clearing the 3 least significant bits of the 255-bit secret scalar $k \in [1, n-1]$ (for elliptic curve scalar multiplication over Curve25519), that is, making $k$ a multiple of 8, to prevent small sub-group attacks. Note that this also reduces the effective security level of the curve to $\approx 2^{252}$.

Instead, is it equally safe to choose the scalar $k$ from $[1, p_1-1]$, that is, operate over the prime sub-group of Curve25519? This does not change any of the curve operations, only the scalar is chosen differently. Also, small sub-group attacks are not possible since $k < p_1$ in this case, and the effective security level is again reduced to $\approx 2^{252}$.

Theoretically, yes you can do that. The idea you have is correct: we can simply choose an integer $k\in[1,p_1-1]$ to determine our public key $Q=[k]P$. The effective hardness in solving the discrete logarithm comes from the large prime order subgroup, so in that case we lose nothing.

However, it is not true that small sub-group attacks are not possible. We are still working over a curve $E$ which contains points of small order, let's say $P_2$ is a point of order 2. Now I engage in a Diffie-Hellman key exchange by sending over my (malicious) "public key" $P_2$. In turn I receive back $[k]P_2$, given that your secret key is $k$. Then
$$k\equiv0\bmod{2}\iff [k]P_2=\mathcal{O}.$$
Hence I have learnt $k\bmod{2}$.

How should we prevent this? In the obvious way: before computing $[k]P_2$, we first check $8P_2\neq\mathcal{O}$. As poncho notes, this prevents only this specific attack. The more generalized attack, where we send $P_s=[k']P+Q_s$, for $Q_s$ a point of small order, still works and can instead be prevented by checking that $[p_1]P_s=\mathcal{O}$. As mentioned, this is quite expensive.

What we can do instead, is only allow our scalars to be $0\bmod{8}$ (i.e. the three lsb's all zero), so that there is nothing to be learnt in the first place. Therefore we have an inherent resistance against small sub-group attacks, which is not true if $k$ were prime. This is exactly what happens for Curve25519.


What is the inverse function of the finite field GF($2^3$) and GF($2^4$)? I am currently reading a paper Cryptanalysis of a Theorem Decomposing the Only Known Solution to the Big APN Problem. In this paper, they mention that they used $I$ which is the inverse of the finite field GF($2^3$) with the irreducible polynomial $x^3 + x + 1$. This inverse corresponds to the monomial $x \mapsto x^6$. Can anyone tell me how this inverse function of the finite field was defined? I understand that there are multiplicative inverses of elements in the finite fields. Are these two the same thing?

How can the inverse function of the finite field GF($2^4$) be derived?

Yes, the only sensible interpretation I can see is that they're talking about the multiplicative inverse.

In particular, the multiplicative group of a finite field is cyclic, and contains all the non-zero elements of the field.  This implies that its order is the size of the field minus one, i.e. $2^3 - 1 = 7$ for ${\rm GF}(2^3)$, and thus that $a^6 \cdot a = a^7 = 1$ for all $a \in {\rm GF}(2^3)$, which means that $a^6$ is the multiplicative inverse of $a$.

Similarly, the multiplicative group of ${\rm GF}(2^4)$ has $2^4 - 1 = 15$ elements, and thus the multiplicative inverse of any non-zero element $a \in {\rm GF}(2^4)$ can be calculated as $2^{14}$.  More generally, in any Galois field ${\rm GF}(p^n)$, the multiplicative inverse of $a$ equals $a^{p^n-2}$.

A point of notation perhaps worth making here is that by $a^6$ above I mean the field element $a$ raised to the sixth power using the field multiplication rule — which itself can be represented as polynomial multiplication followed by reduction modulo an irreducible monic polynomial, if the elements of ${\rm GF}(2^3)$ themselves are represented as polynomials over ${\rm GF}(2)$ of order less than 3.

The reason this can be confusing is that, in this representation, expressions like "$x$" and "$x^6$" could themselves represent specific field elements, written as polynomials of a single variable $x$.  (Of course, $x^6$ cannot be the canonical polynomial representation of any element of ${\rm GF}(2^3)$, since its order is too high.)  Where such notation is used, as in your question, it's usually a good idea to avoid using the symbol $x$ for any other purpose except as the formal variable in the polynomials representing the field elements.  In particular, it should not be used to designate an arbitrary field element (except, of course, for the specific field element canonically represented by the first order monomial $x$).


How many points are there on the X25519 curves? The order of the base point, $l$, is 2^252 + 27742317777372353535851937790883648493

However, the base point group is nested within other large groups, the largest of which is of size $8l$.

There are also nested small subgroups, the largest of which is a small subgroup of size $8$.

Is it therefore correct to say that the total number of possible points (on either Curve25519 or Ed25519), including the identity point that both the small and large subgroups share, is: $8l + 7$

No the total number of points on the curve is still $8l$.

The curve order (total number of point on the curve) is simply the subgroup order multiplies the co-factor. This is true for all subgroups.

For the small subgroup of order $8$, its co-factor is $l$.


In what mode does Signal applies cryptography over voice and data? I have read all of the technical documentations provided via signal and so far I have figured out that signal intitializes a common key via X3DH key agreement and manages the keys via double rachet algorithm. Also I have figured out that uses the X25519 and X448 curves as well.

But I still have a burning question how actually encrypts the Instant messages ans especially how does encrypts real time voice and video. For real time encryption as far as I know is used either a stream cipher or a block cypher in counter mode with session keys that get renewed when counter is expired (eg. WPA2 uses RSA) when "traditional" cryptographic schemes are used.

But what about the Signal application how is able to encrypt voice and video in real time? Did actually somehow uses elliptic curve cryptography like a block cypher in counter mode. (in other words "replaces" the block cypher algorithm with eliptic curve one)?

The double ratchet is used to derive symmetric key material. Then
it uses AES-256 in CTR mode for encryption and HMAC-SHA-256 for authentication. Also check the source code.


Difference between Pseudorandom Function vs randomly chosen function I am currently going through a course in cryptography.
In this, I stumbled upon Pseudorandom Functions. I got a little idea of Pseudorandom Generators which map an input string (key) to an extended string.
However, I do not understand the pseudorandomness in case of a function.

In the book Introduction to modern cryptography by Katz and Lindell, I found this:

  Since the notion of choosing a function at random is less familiar than the
  notion of choosing a string at random, it is worth spending a bit more time on
  this idea. From a mathematical point of view, we can consider the set $\operatorname{Func}n$
  of all functions mapping $n$-bit strings to $n$-bit strings; this set is finite (as we
  will see in a moment), and so randomly selecting a function mapping $n$-bit
  strings to $n$-bit strings corresponds exactly to choosing an element uniformly
  at random from this set.

  How large is the set $\operatorname{Func}n$? A function $f$ is exactly
  specified by its value on each point in its domain; in fact, we can view any
  function (over a finite domain) as a large look-up table that stores $f(x)$ in
  the row of the table labeled by $x$. For $f_n\in\operatorname{Func}n$, the look-up table for $f_n$
  has $2^n$ rows (one for each point of the domain $\{0,1\}^n$) and each row contains
  an $n$-bit string (since the range of $f_n$ is $\{0,1\}^n$). Any such table can thus be
  represented using exactly $n\cdot2^n$ bits.

  Moreover, the functions in $\operatorname{Func}n$ are
  in one-to-one correspondence with look-up tables of this form; meaning that
  they are in one-to-one correspondence
   with all strings of length $n\cdot2^n$.

  We conclude that the size of $\operatorname{Func}n$ is $2^{n\cdot2^n}$ .
  Viewing a function as a look-up table provides another useful way to think
  about selecting a function $f_n\in\operatorname{Func}n$ uniformly at random. Indeed, this is exactly equivalent to choosing each row of the look-up table of $f_n$ uniformly
  at random. That is, the values $f_n(x)$ and $f_n(y)$ (for $x\neq y$) are completely
  independent and uniformly distributed.

  Coming back to our discussion of pseudorandom functions, recall that we
  wish to construct a keyed function $F$ such that $F_k$ (for $k\gets\{0, 1\}^n$ chosen
  uniformly at randomly) is indistinguishable from $f_n$ (for $f_n\gets\operatorname{Func}n$ chosen
  uniformly at random). Note that the former is chosen from a distribution over
  (at most) $2^n$ distinct functions, whereas the latter is chosen from a distribution over all $2^{n\cdot2^n}$
   functions in $\operatorname{Func}n$. Despite this, the "behavior" of these
  functions must look the same to any polynomial-time distinguisher.

Can anyone please explain me this concept in easier terms?

Random function -- function $F$, that is selected randomly from the set $Func$ of all possible functions (with given domain and range).

Pseudo-random function --- family $\{F_k\}$ of functions, that is indexed by the parameter $k$ (which serves as a number). It is pseudo-random, because if someone picks $k$ secretly and lets you interact with $F_k$, it should look like you are working with a random function, whereas in fact it is chosen from a much smaller set, not from the set of all possible functions.


For RSA keys, is the safety of a given key-length different for signing vs encryption? I'm wondering if considerations of key-length are different when thinking about signing vs encryption. If for some reason, it was safter to use smaller keys for signing that would be interesting.

No, the security is about identical, as the underlying RSA problem is the same.

Besides that, non-repudiation is usually managed differently with regards to legal requirements. Providing confidentiality (encryption) is a rather different use case than non-repudiation (signing a contract).

It is also possible to use signatures for authentication rather than non-repudiation. In that case you may be able to get away with smaller signatures if the authentication and key is only valid for a limited amount of time.

All in all, the key strength should be considered given the use cases, threat model and of course the system parameters. Defining a minimum RSA key size without considering the system is not a good idea.

Notes:

It could be possible to assign a notary that immediately signs the document after signature generation by the other party. The notary should of course use a key of sufficient strength.
I've used the notion of a larger key, but what you're really after is a stronger key. Usually larger keys are stronger for the same algorithm though.
If you go over a 16Ki key size then the key size doesn't matter much anymore. The key will only be broken if RSA itself is broken (e.g. using a hugely powerfull Quantum Computer).


Is it okay to use an HMAC of the plaintext and a (possibly distinct) key as the IV for symmetric cryptography? I was thinking of how to create an IV for a block cipher that doesn't require stored state, and I came up with the idea of using an HMAC of the (padded) plaintext and a (possibly distinct) key as the IV.

This seems to be secure:

The IV will only be reused if there is an HMAC collision or if the
plaintext and key are the same.  The former would imply that the HMAC is
broken and the latter is harmless, since it is just producing the output
twice.
The HMAC is verified after decryption, but before padding is checked, so
padding-oracle attacks should not be an issue.

In particular, if the HMAC and the block cipher use different keys, there
seems to be a very simple proof of security, assuming that either (1) the HMAC cannot be distinguished from a random function or (2) the block cipher is secure against maliciously-chosen (but unique) IVs:

The attacker cannot forge the HMAC, since this would require knowledge of
the signing key.
Since the signing and encryption keys are different in this case, and the
HMAC is assumed random, malicious IVs cannot be triggered by an attacker.

Alternatively, if the cipher is secure against malicious (but unique) IVs, then the security of the cipher+security of the HMAC seem to prove the security of the system.

This (obviously) provides no protection against replay attacks, but that
requires state anyway.

However, I am not a cryptographer so I do not trust my conclusions on this
matter.  If this technique is secure, it would appear to be quite useful in
practice, as it is simple and provides both encryption and authentication.

The scheme you describe is essentially same as the "SIV construction"* introduced by Rogaway and Shrimpton in their 2007 paper "Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Key-Wrap Problem".

This construction takes a PRF (such as HMAC) and a conventional IV-based encryption scheme (such as, say, a block cipher in CTR mode), and constructs a deterministic authenticated encryption scheme by first feeding the plaintext (and any associated header fields) into the PRF to obtain a pseudorandom authentication tag, and then using this authentication tag as the IV for the cipher.

In the paper, Rogaway and Shrimpton show that, assuming that the underlying PRF and cipher are secure**, the resulting scheme satisfies a security definition they call DAE security.  They supply several equivalent versions of this definition, of which perhaps the easiest to paraphrase in plain English is the two-part version given in the appendices, which says that a determinstic encryption scheme is DAE secure if:

a (polynomial-time) attacker, given access to the encryption oracle, is unable to distinguish it (with non-negligible advantage) from a random oracle with the same output length, and
the attacker, also given access to the decryption oracle, is unable to forge a message (that is, produce a valid ciphertext that it did not receive from the encryption oracle) with non-negligible probability.

They also define a related security notion called MRAE, or misuse-resistant authenticated encryption, which is basically the same as DAE security except that the encryption and decryption functions take an additional (public) input called a nonce.  They show that:

any DAE secure encryption scheme that supports associated data (i.e. additional header fields that are authenticated but not encrypted) can be used as an MRAE scheme, simply by treating the nonce as part of the associated data;
when used with a random nonce (of sufficient length), an MRAE secure encryption system is a secure nonce-based authenticated encryption scheme in the conventional sense (and, in particular, is IND-CCA2 secure); and
when the nonce is repeated, omitted, or even controlled by the attacker, an MRAE scheme still remains DAE secure.

In conclusion, yes, this is indeed a secure way to construct a deterministic authenticated encryption scheme — assuming, as always, that the implementation is correct, the underlying primitives are secure, and none of the assumptions of the proofs are violated.
It does leak slightly more information than randomized encryption schemes, namely whether or not two plaintexts are identical, but no more than that.  (Of course, like all general-purpose encryption schemes, it also leaks information about the length of the plaintext.)

Also, a particular detail to pay attention to, when implementing this construction in environments where timing or other side channel attacks may be possible, is that both the PRF (e.g. HMAC) as well as the encryption layer need to be checked for such vulnerabilities.

(In conventional Encrypt-then-MAC schemes, the MAC layer is not vulnerable to most kinds of side channel attacks, since it only operates on data that has already been encrypted.  Of course, even for conventional schemes, comparing the authentication tags can be vulnerable to side channel attacks, so... it just goes to show that one needs to be careful when implementing crypto.)

*) Not to be confused with the SIV mode of operation they define later in the paper, which is an instance of the SIV construction using a block cipher in CTR mode as the encryption layer, and a multi-input variant of CMAC as the PRF.  Yes, it's a bit confusing.

**) The specific security property they require of the cipher is IND\$ security, or indistinguishability from "fake" cipher that outputs purely random ciphertext.  The main difference between IND\$ and standard IND-CPA or semantic security is that the former does not permit any detectable redundancy in the ciphertext, even if it leaks nothing about the plaintext.  It seems to me that the difference here is mostly technical, and that an IND-CPA secure scheme could be used just as well, if the definition of DAE security was also relaxed to permit such redundancy, yielding something like a deterministic analogue of RCCA security.


SHA-256 : Finding two strings that the first n bits of hash value are same How can I find two strings that have the same hash value for first $n$ bits in SHA-256? I'm implementing it by Python and I have the following ideas and problems:

Keep generating two random string

What is the length of the string that I need to generate?
How to avoid generating the existing string again?
How many string should I generate in total?

Hash the two random string and store in a dictionary

import hashlib in python
{random string : hash value}

Loop the dictionary to check if there is two hash value share the same first n bits and return the two strings as a result

Please give me some advice on it.

If you use the same size input, there may no be a collision at all. It is better to increase the input size like double of $n$. Note that the input is padded so that the input to $\operatorname{SHA256}$ it is multiple of 512-bit.

  Keep generating two random string

You need to store all the hashes to see that there is a collision. If you don't store you may miss it. Since you are not storing, you can use an LFSR to generate uniquely, if you want.

Actually you should use Rho Method for this one, which is a low memory collision search.

Pick a random hash value $h_1=h_1'$
and compute $h_2 =\operatorname{SHA256}(h_1)$ and $h_2' = \operatorname{SHA256}(\operatorname{SHA256}(h_1'))$.
Continue to iterate $h_{i} = \operatorname{SHA256}(h_{i-1})$ and $h_{i}' = \operatorname{SHA256}(\operatorname{SHA256}(h_{i-1}'))$

These two sequences will eventually enter into a cycle, and there will be a tail (rho-shape $\rho$). The cycle start is the collision point.

Note: this algorithm is also known as Robert W. Floyd's Tortoise and Hare which is used for cycle detection.

  Hash the two random string and store in a dictionary

This can be better since hash tables can effectively search, up to amortized $\mathcal{O}(1)$-time Generate the hashes and look upon the hash table - if exist you have found, not exist then insert the new hash.

The performance is really depending on the value of $n$. If the value of $n$ is too big, you may choose the Rho method. Since when the needed memory becomes larger than your system memory, you will be slowed.

  Loop the dictionary to check if there is two hash value share the same first n bits and return the two strings as a result

In this case, you already store the data in the Python dictionary. Python dictionary is already implemented by hash tables. Therefore, you only need to use Python's existing dictionary functionalities.

If you want to use a double dimensional array (or similar structure) to store the value and hash you  You first calculate all of the hashes up to a predetermined amount $n$, then sort the array with an $\mathcal{O}(n \log n)$-time sorting algorithm. After the sort, all you need to iterate and see that are there any adjacent elements is the same. This can be done in $\mathcal{O}(n)$-time


Solve congruence with gcd In a solution to the problem of finding $q$ in

$$
c_1^{e_2}\cdot 5^{e_1e_2} - c_2^{e_1}\cdot 2^{e_1e_2} = q^{e_1e_2} \bmod n
$$

it is given as:

$$
q = \gcd\big(c_1^{e_2}\cdot 5^{e_1e_2} - c_2^{e_1}\cdot 2^{e_1e_2}, n\big)
$$

How can $q$ be found like that?

The way $c_1$ and $c_2$ have been obtained, algebra has shown that the quantity $z={c_1}^{e_2}\,5^{e_1\,e_2}-{c_2}^{e_1}\,2^{e_1\,e_2}$ is such that $z\equiv q^{e_1\,e_2}\pmod n$, where $n$ is an RSA modulus with $q$ one of the prime factors of $n$, $e_1$ and $e_2$ are RSA exponents valid for the modulus $n$.

From $n=p\,q$, we know that $q$ divides $n$.

From $z\equiv q^{e_1\,e_2}\pmod n$, and since $q$ divides $n$, we know that $z\equiv q^{e_1\,e_2}\pmod q$. Since neither $e_1$ nor $e_2$ are zero, it holds $q^{e_1\,e_2}\equiv0\pmod q$. Therefore, $z\equiv0\pmod q$, that is $q$ divides $z$.

Hence, $q$ is a common divisor of $n$ and $z$. With $n=p\,q$ with $p$ prime, it follows that one of the following holds:

$z=0$
$\gcd(z,n)$ is $q$
$\gcd(z,n)$ is $n$.

The way $z$ was constructed gives no particular reason to believe that $p$ divides $z$, and that's highly unlikely for a random integer. It follows that $\gcd(z,n)=q$ is the only likely possibility in the above three.

The quantity ${c_1}^{e_2}\,5^{e_1\,e_2}-{c_2}^{e_1}\,2^{e_1\,e_2}\bmod n$ can efficiently be computed from givens, and that allows to compute $\gcd(z,n)$ (since the first step of that can be to reduce $z$ modulo $n$), and thus allows to compute $q$.


Is simple XOR with secret key using DHE secure? Client and server have given generator 3 and modulus which is 256 bit prime same all the time for all clients and server (simply hardcoded).

They both generate a private exponent and send result to each other and generate secure key. This all is done over insecure channel. That's all simple Diffie-Hellman exchange.

After this step every sent packet is encrypted over simple XOR block cipher by secure key's bytes, in this case 256bit long block.

Is this way of encryption any secure and if yes, how much, if no, what are ways to reverse it, as it is so simple and doesn't use much resources?

In addition to the problems that user595228 has mentioned, well, an attacker can easily solve a discrete log modulo a 256 bit prime; from that, he can recompute the shared secret, and that would give him the entire message.  To be secure, you really need at least a 1024 bit prime; with a 2048 bit prime being greatly preferred.


SHA-1:Is there any mathematical result that gives us the minimum number of 1's in a 160-bit SHA-1 hash output? Is there any mathematical result that gives us the minimum number of 1's in a 160-bit SHA-1 hash output? What is the probability that a 160-bit SHA-1 hash output contains at least 128 1's?

No, theoretically a SHA1 hash can be any 160-bit value, including the string of 160 zeroes.

As for your second question, if we fudge a little bit and consider SHA1 a truly random function this becomes the same question as the following:

If we flip 160 coins, what is the probability that at least 128 of them will be heads?

Solution is left as an exercise to the reader; I suspect this might be a homework question.


What is Perfect forward secrecy? I have read that when a user contacts an entity like a bank, it creates a pre-master key and then selects a master key for subsequent communications.

  Can the lack of PFS, create a security flaw if the pre-master key and
  master key are random and different for each session?

  How can the knowledge of the private key help a hacker to decrypt old
  communications? Are the pre-master key and master keys stored on the
  server?

I have also read that just like PFS, it works by using an ephemeral/time-varying key.

  So can any key exchange/encryption algorithm, which ensures keys are
  discarded after each session, be regarded as a PFS system?

I am finding it hard to understand the differences.

As indicated in Forward Secrecy Article of Wikipedia;

  In cryptography, forward secrecy (FS), also known as perfect forward secrecy (PFS), is a feature of specific key agreement protocols that gives assurances your session keys will not be compromised even if the private key of the server is compromised.  Forward secrecy protects past sessions against future compromises of secret keys or passwords. By generating a unique session key for every session a user initiates, even the compromise of a single session key will not affect any data other than that exchanged in the specific session protected by that particular key

$$\text{perfect forward secrecy} = \text{forward secrecy}$$

  how can lack of PFS, create a security flaw if the pre-master key and master key are random and different for each session?

Generating a unique session key that cannot be reconstructed then it is already forward secrecy. The process of key generation, as a result, requires a randomly generated numbers, as in Diffie–Hellman key exchange

  how can knowledge of the private key, helps the hacker to decrypt old communication? are the pre-master key and master keys stored by the server?
  In forward secrecy,

There is no way if the forward secrecy is applied since one cannot construct old (randomly generated) keys from the pre-master and master keys.

  I read like PFS, works by using an ephemeral/time-varying key.

Yes, your reading is correct. The key is called ephemeral if generated for each key exchange protocol. Note the little difference, Wikipedia states a case that ephemeral keys in some cases used more than once.

  So could any key exchange/ encryption algorithm which ensures keys are discarded after each session be called as PFS?

You need to discard once the key is used, otherwise, you let the attacker decrypt the old messages that he stored before attacking your machine to steal the master key.

What is the reason for storing the old cryptographic keys when you don't need them? Delete them as soon as the usage is finished. In this way, you are betraying the Forward secrecy, forget them!


Are different elliptic curves compatible? Regarding SubtleCrypto and curves P-256, P-384 and P-521.
Can I mix two different curves for key derivation?
For example performing key derivation between P-256 and P-521.
EDIT:
Can I mix two different curves to derive data?
(So not to derive keys, it is not what I meant)

No, it is not possible to mix domain parameters / curves when performing key derivation.
First of all, the implementations are likely to fail if they find curve identifiers. These can be single protocol specific bytes, OID's or named curves or full parameter sets, depending on the protocol.
Second, it is very likely that implementations will reject the public key value if the key value identifies the curve. It might also be that the key is related to the curve field (at least 2x curve field size for uncompressed keys and 1B + 1x curve field size for compressed keys).
Thirdly, it should try and see if the point is actually on the curve, it is very possible that this fails as well, if the implementation is correct. Some curves are designed in such as way that such checks are not necessary.
Finally when the operations are performed then the calculations would result in a non-matching "shared" secret. Subsequent validation that the shared secret is valid would fail (e.g. using an explicit MAC calculated from the shared secret or the first message MAC, usually from derived keys).
So no, you cannot "mix curves" in general, there needs to be some way to make sure that both sender / receiver use the same set of domain parameters / curve. This is rather independent of SubtleCrypto, of which I'm not a full expert (but it is a rather generic cryptographic API, so yeah).


Why does the SRP-6 calculation of B include a multiplier k = 3? In SRP-6 $B$ is calculated as $B=kv+ g^b, k=3$. What is the purpose of $k$, and why was it fixed as $3$?

(In SRP-6a, this value $3$ is replaced by $k = H(N,g)$, but this question is about SRP-6.)

The purpose is to prevent a two-for-one guessing attack, where an active adversary, impersonating the server, can test two password guesses per attempt. The attack and why the multiplier prevents it is described in Section 2 of the SRP-6 paper (ps). (According to MacKenzie, it was discovered by Bleichenbacher.)

In brief, the attack goes like this:

Instead of $B = v + g^b = g^x + g^b$ with a random $b$, the attacker calculates $B = g^{x_1} + g^{x_2}$ with two password guesses.
The client uses the value $B - g^x$, meaning if $x=x_1$ they get $g^{x_2}$ and if $x=x_2$ they get $g^{x_1}$.
The attacker calculates two session keys, based on $x=x_1, b=x_2$ and $x=x_2, b=x_1$. If either of these matches with the $M_1$ sent by the client, they have found the password.

If the attacker does not know the discrete logarithm of $k$, i.e. the number $l$ for which $g^l = k$, they cannot try two guesses at once with the version 6 protocol where $v$ is multiplied by $k$.

The paper shows why $k=3$ is a safe choice for generic $g$ and $N$.

(The hashed $k$ fixes it for maliciously chosen $g$ and $N$ as well.)


Reverse output of general Fibonacci LFSR Suppose we have some Fibonacci LFSR, and it outputs some sequence.

How to change starting LFSR so, that it outputs exactly same sequence, but in reverse order?

The Fibonnacci LFSR whose feedback polynomial is the reverse of the given LFSR polynomial will produce the sequence in reverse. Here by
reverse is meant $x^mg(x^{-1})$ where $g(x)$ (of degree $m$)
is the feedback polynomial
of the given Fibonnacci LFSR.  Note that the initial loading
of the LFSR must be changed to the ending of the given output sequence
(in reverse order).


Diffie-Hellman: Does the size of the prime modulus depend on the potential size of the secret? I'm writing my own cryptosystem that uses One Time Pad and Diffie-Hellman to generate keys for the OTP.  I am using Rails on the server side and Javascript for the client side.

Please don't tell me this is insecure and I shouldn't do it.  I'm doing this purely for educational purposes and in no way will this be deployed in a non-experimental sense.

Since this is OTP, I need a keystream that is at least as long as the message being encrypted.  From what I have read, it seems like DH needs a ridiculously large safe prime modulus.  Or does it?

Every character needs a different random key, so for a string that is 10 characters long the DH key exchange needs to happen 10 times to create an array of common secret keys for that string.

However, I seem to be getting what may be integers that are way larger than necessary.

Let's say that the user makes an array of private keys:

var userPrivateKeys = [9,12,0,23,7,8,4,7,15,24]

And a 2048-bit safe prime modulus with 2 as the generator:

var prime = 32317006071311007300338913926423828248817941241140239112842009751400741706634354222619689417363569347117901737909704191754605873209195028853758986185622153212175412514901774520270235796078236248884246189477587641105928646099411723245426622522193230540919037680524235519125679715870117001058055877651038861847280257976054903569732561526167081339361799541336476559160368317896729073178384589680639671900977202194168647225871031411336429319536193471636533209717077448227988588565369208645296636077250268955505928362751121174096972998068410554359584866583291642136218231078990999448652468262416972035911852507045361090559

var generator = 2

The array of shared keys for the user ends up looking like this:

var userPublicKeys = [512,4096,1,8388608,128,256,16,128,32768,16777216]

After the user and the server exchange their public keys, we get this as the common key:

var commonKeys = [134217728,2.2300745198530623e+43,1,1.725436586697641e+69,72057594037927940,16777216,17592186044416,1.78405961588245e+44,6.216540455122333e+85,1]

Holy....

Those integers are way way larger than the modulus of the alphabet, or even the modulus of ASCII.

I [think I] understand that the prime modulus must be huge in the context of creating keys to be used in ciphers like AES, but what about in the context of having different random keys for each character in OTP?

For example, let's say that my messages only feature letters a through z, and I have a smaller modulus:

p = 27
g = 3

userPrivateKeys = [9,12,0,23,7,8,4,7,15,24]

Our algorithm would be:

2^a mod 27

or in Javascript...

Math.pow(2, a) % 27

And we'll have generated a list of public keys:

userPublicKeys = [26,19,1,5,20,13,16,20,17,10]

That's way more manageable.

So in this context, is there a problem with the prime modulus being so small?

As far as I can tell, the only way to break this is through exhaustive search; since OTP cryptext contains no information about the original message, exhaustive search would be infeasible.  I have read of other possible ways of breaking this and DH in general, but usually I don't understand them or they either depend on one of the secrets being known.

So is there something I'm missing?

Well, for one thing, you are not using a "One Time Pad".  A "One Time Pad" means, by definition, that someone generates a pad of numbers using true randomness (and not algorithmicly), and that no potential adversary has any information on what that pad may contain.  Then, that pad is given to both the sender and the receiver, and then the sender uses it to disguise the plaintext, in a way that the receiver (with the pad) can recover the plaintext, but the adversary, who doesn't have the pad, gets no information about the plaintext (because with the ciphertext and any potential plaintext, there is a possible pad that makes that possible, and the adversary has no way of deciding which potential pad is more likely.

Instead, you are performing a series of Diffie-Hellman operations to generate shared secrets, and then using those shared secrets to perform a stream encryption.

Here is why this is distinction is important; you state:

  the only way to break this is through exhaustive search; since OTP cryptext contains no information about the original message

This would indeed be true, if you were using an OTP; the attacker would literally have no information beyond the ciphertext, and the ciphertext would indeed reveal no information about the plaintext.  However, the ciphertext is not the only thing the sender and receiver are exchanging, you mention previously that:

  the user and the server exchange their public keys

That is, there is information available to the attacker in addition to the ciphertext that he can use.  That is, instead of being informationally secure (which OTP is), you also hope that the attacker cannot use the public keys to recover the shared secret (pads), that is, you hope that the problem of recovering the shared secret is just too difficult for the attacker.  In other words, you hope that you are computationally secure.

Here, in that light, when you ask:

  is there a problem with the prime modulus being so small?

The question you are asking is "is Diffie-Hellman computationally secure, even if the modulus is tiny".  The answer to that is "no, it is not".  For MODP groups (which are the groups you are using), it appears that DH can be broken unless the modulus is at least 800 bits (actually, attacks against modulii that size haven't actually been demonstrated, but there have been attacks against related primitives, and we believe those attacks can be converted into attacks against Diffie-Hellman).

There are other groups that can be made smaller and still are believed to be secure (for example, an elliptic curve group is probably pretty secure even if the curve is only 200 bits or so); however you won't get anywhere close to "an ASCII value".

When we use Diffie-Hellman like this, what we generally do is perform a single Diffie-Hellman operation to generate a single (large) shared secret, and then give that shared secret to a Key Derivation Function; the output of that KDF may be then presented to a Stream Cipher, whose output is then used to actually encrypt the data