Is AES secure for java application licensing? I have to license a java application and want to code a quick implementation, the scheme I came up with is:

The Application calculates a string X which we assume to be the md5 sum of the computer's mac address, the current date and some other information.
the application returns a string Y equal to the last 16 digits of X to the user
the user contacts the Software Support office giving Y and the office encrypts Y using AES with a secret key and returns a string Z equal to the last 16 digits of the encrypted Y
the user inputs Z in the application and this checks that Z is equal to its own Z which is calculated the same way as at the Software Support. If the two are the same the software unlocks.

Now I would like to know whether two assumptions are reasonably safe or not:

Assume a cracker knows how Y is calculated and can calculate it for its own copy of the software and uses this Y to request a Z to the support center and unlock his copy of the software. Is it possible he will be able to calculate for every possible Y he wants a matching Z to unlock any copy of my software?
Because my software contains the encryption key inside the application bytecode a cracker with enough knowledge can decompile the encryption key and create his own Z to unlock the program (assume I tried my best obfuscating the code). A solution would be to use public key cryptography, however this would be useless in my opinion because if a cracker is able to decode the compiled bytecode of the application he will totally bypass whatever encryption scheme I will put because in the end there will always be a part of the code checking for a condition and setting that condition always to true will bypass any encryption scheme I will come up with. is it true?

To begin with, let's assume that the attacker cannot extract the AES key from your software.  That means the best they can do is a chosen-plaintext attack on AES: choose a block $Y$, request its encryption $Z$, repeat as many times as desired and try to use the results to figure out something useful about the encryption of other plaintext blocks.

Since AES is believed to be IND-CPA secure, i.e. indistinguishable from a random permutation under chosen plaintext attacks, this is not likely to work.  If the attacker cannot somehow distinguish AES from a random permutation (which, if AES is as secure as it's assumed to be, they shouldn't be able to do), all they can do is try to compile a long list of plaintext/ciphertext pairs and hope that the key they want to crack is found in the list.  But as long as you don't truncate the inputs too much, that isn't likely to happen either.  (You don't specify what you mean by a "digit", but as long as one digit contains at least 4 bits, 16 digits amounts to at least 64 bits, which should be sufficient.)

However, that's all assuming that the attacker cannot just extract the AES key from the software.  If they can, then creating their own license key generator will be trivial.  Note that, from the attacker's perspective, extracting the AES key is much more useful than just modifying the software to disable the key check: knowing the AES key allows them to create valid license keys for any copy of the software on any platform, including future upgrades.

Extracting the key is also likely to be easier than modifying the code, especially if you use the standard system crypto library for your AES implementation.  (As CodesInChaos notes, the attacker can just run the code under a debugger and log all system library calls it makes; the call to AESEncrypt() or whatever ought to stand out as a good target for a breakpoint.)  Using your own obfuscated AES implementation could make it a bit harder, but that's not really guaranteed to work either: crypto code tends to look fairly distinctive when decompiled, and even if the attacker fails to realize that they're looking at AES, they could still just lift the code and its inputs wholesale.

Thus, if you don't want anyone to be able to write key generators for your software, I'd strongly suggest using digital signatures instead.  If you don't want to do that, your other option is to just obfuscate the heck out of your code and accept the fact that a skilled and determined attacker will be able to reverse engineer it and write a license key generator.  Or, you know, consider whether you really even need a license key in the first place.


Secure multiparty sum computation corruption bound In Section 3.4 of the book Secure Multiparty Computation and Secret Sharing, it is claimed that for a secure multiparty computation problem with $n$ parties, the optimal corruption bound (concerning passive adversaries and information-theoretic security) is $n/2$, that is, at most $n/2$ passive adversaries are allowed in order to have information-theoretic security. It is claimed that this bound is optimal because there exist functions that cannot be computed securely if there are $\geq n/2$ adversaries. In particular, in the first paragraph of Section 3.4 of the book, there is one sentence: the multiplication subprotocol breaks down. The book and other papers provide analysis for Boolean functions, e.g., AND, OR and XOR functions. My question is: What is the corruption bound for secure multiparty integer sum computations? More specifically, given $n$ parties $P_1,\cdots,P_n$, each $P_i$ holds a secret integer $x_i$ (assuming that all $x_i$'s are inside a finite field $\mathbb{F}$) and they want to securely compute $S=\sum_{i=1}^nx_i$. Inside these $n$ parties, $t$ of them could be semi-honest adversaries and we are concerned with information-theoretic security. Also assuming complete communication graph. I am trying to apply the Shamir's secret sharing scheme. For this problem, is the corruption bound $t<n/2$ or $t<n$?

For just computing a sum, the information-theoretic bound (assuming semihonest) is $t<n-1$.

Why $n-1$ and not $n$?
In the case of $t<n$, we can allegedly tolerate up to $n-1$ corrupt parties. If we are computing a sum, and the $n-1$ parties know the sum $S$ and their own inputs ($x_i$), they can simply compute the sum of their inputs and subtract that from $S$ to learn the private input of the single honest party. Therefore, there must be at least two honest parties if we are computing the sum.


Decomposing an ideal in intersections Let $R$ be an ring, and let $(a),(b)$ be the ideals generated by $a,b\in R$ respectively. Let $c=a\cdot b$ and $(c)$ the ideal generated by $c$.

I am supposing that, given $c$, it is computationally difficult to deduce $a,b$ (because the group of units of $R$ is large).
Suppose that we are given $c$ and we have a test function $T:R\to \{0,1\}$ that outputs 1 if the input is in $\{a,b\}$ and 0 otherwise.

Is it an algorithm to parameterize a list of ideals $I_1,I_2$ such that $(c)=I_1\cap I_2$? It looks to my that writing all such decompositions is essentially the same as listing all solutions $x,y$ such that $c=xy\in R$. Is that so?

I am interested in the particular case $R=\mathbb{Z}[x]/(x^{2^k}+1)$, and the coefficients of $a,b$ are bounded in magnitude by $B\in \mathbb{Z}_+, B>2$.

For all units $u$,  $(a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u)\hspace{-0.04 in}\cdot \hspace{-0.05 in}\left(u^{-1}\hspace{-0.06 in}\cdot \hspace{-0.04 in}b\hspace{-0.02 in}\right)$  is a factorization of $c$, and  $a^{-1} \hspace{-0.06 in}\cdot \hspace{-0.04 in}(a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u)$  and  $\left(\hspace{-0.04 in}\left(\hspace{-0.02 in}u^{-1}\hspace{-0.06 in}\cdot \hspace{-0.04 in}b\hspace{-0.02 in}\right)\hspace{-0.06 in}\cdot \hspace{-0.04 in}b^{-1}\hspace{-0.04 in}\right)^{\hspace{.04 in}-1}$  both give $u$, so [either factor and which side it is] is enough to deduce $u$.

Let "the modified factors" be  $a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u$  and  $u^{-1}\hspace{-0.06 in}\cdot \hspace{-0.04 in}b$ ,  let N be the number of units,

and suppose the guesser makes at most q+1 guesses.

Game 0:  The guesser wins if and only if at least one of its guesses is $u$.

Game 1:  The guesser wins if and only if at least one of its

guesses is [either modified factor and the modified factor's side].

Game 2:  The guesser wins if and only if at least one

of its guesses is at least one of the modified factors.

Game 3:  The guesser may indicate at most one of its guesses as "final", but regardless,

it wins if and only if at least one its guesses is at least one of the modified factors.

Game 4:    The guesser may indicate at most one of its guesses as "final".

After each guess that is not indicated as final, the guesser is sent 0.

The guesser wins if and only if at least one of its guesses is at least one of the modified factors.

Game 5:    The guesser may indicate at most one of its guesses as "final".

After each [guess that's not indicated as final] which is not one of the modified factors,

the guesser is sent 0.  After each [guess that's not indicated as final]

which is one of the modified factors, the guesser is sent 1.  The guesser wins

if and only if at least one of its guesses is at least one of the modified factors.

Game 6:    The guesser may indicate at most one of its guesses as "final".

After each [guess that's not indicated as final] which is not one of the modified factors,

the guesser is sent 0.  After each [guess that's not indicated as final] which is

one of the modified factors, the guesser is sent 1.  The guesser wins if and only if

[it indicated a guess as final] and that guess was at least one of the modified factors.

Game 7:    The guesser may indicate at most one of its guesses as "final".

After each [guess that's not indicated as final] which is not one of the modified factors,

the guesser is sent 0.  After each [guess that's not indicated as final] which is

one of the modified factors, the guesser is sent 1.  The guesser wins if and only if

[it indicated a guess as final] and that guess was the modified factors.

Game 8:    The guesser may indicate at most one of its guesses as "final".

After each [guess that's not indicated as final] which is not one of $\{\hspace{-0.02 in}a,\hspace{-0.02 in}b\hspace{-0.02 in}\}$, the guesser is sent 0.  After each [guess that's not indicated as final] which is one of $\{\hspace{-0.02 in}a,\hspace{-0.02 in}b\hspace{-0.02 in}\}$, the guesser is sent 1.

The guesser wins if and only if [it indicated a guess as final] and that guess was $a,\hspace{-0.02 in}b$.

In Game 0, there are only q+1 guesses for N equally-likely possibilities,

so the probability of winning Game 0 is at most (q+1)/N.

As explained before, $u$ can be deduced from [either modified factor and the

modified factor's side], so for each Game-1 guesser, there's a Game-0 guesser with the

same winning probability.  Thus the probability of winning Game 1 is also at most (q+1)/N.

For each Game-2 guesser, there's a Game-1 guesser with half the winning probability (just guess the side at random), so the probability of winning Game 2 is at most twice the maximum probability of winning Game 1.  Thus the probability of winning Game 2 is at most (2*(q+1))/N.

For each Game-3 guesser, there's a Game-2 guesser with the same winning probability.

(Just ignore the presence or absence of a "final" indication.)

Thus the probability of winning Game 3 is at most (2*(q+1))/N.

For each Game-4 guesser, there's a Game-3 guesser with the same winning probability.

(Just send it 0 after each guess that's not indicated as final.)

Thus the probability of winning Game 4 is at most (2*(q+1))/N.

Game 4 and Game 5 only differ when a win is already guaranteed,

so the probability of winning Game 5 is at most (2*(q+1))/N.

The only difference between Game 6's winning conditions and Game 5's winning condition

is that the former's winning condition is a restriction of the latter's winning condition, so the probability of winning Game 5 is at most (2*(q+1))/N.

For each Game-7 guesser, there's a Game-6 guesser

with at least as large a winning probability.

(Just pick one part of its indicated-as-final guess).

Thus the probability of winning Game 7 is at most (2*(q+1))/N.

For each $u$, the equations $\;\;\; a\cdot u \: = \: c \;\;\;$ and $\;\;\; u^{-1} \cdot b \: = \: d \;\;\;$ both have a unique solution, so exactly N choices of $a,\hspace{-0.02 in}b,\hspace{-0.02 in}u$ yield modified factors $c,\hspace{-0.02 in}d$. $\;\;\;\;\;\;\;\;$ That means the

distribution of modified factors is uniform, so identical to the distribution of $a,\hspace{-0.02 in}b$.  Thus the probability of winning Game 8 is at most (2*(q+1))/N.

Finally, observe that Game 8 is exactly the game for guessing $a,\hspace{-0.02 in}b$ given $c$ and [at most q queries to the test function].  Therefore, for all adversaries which make at most q oracle queries, their success probability is at most (2*(q+1))/N, where N is the number of units.

As mentioned by Chris Peikert,

Input: $R$

Output:  $R,\hspace{-0.02 in}R$

is "an algorithm to parameterize a list of ideals $I_1,I_2$ such that $(c)=I_1\cap I_2$".

That will be "the same as listing all solutions $x,y$

such that $c=xy\in R$" at least when $R$ is commutative.

(Finiteness might also be enough; I can't figure that out right now.)

However, there are rings in which $1$ can be factored into two non-units.


Why does Merkle-Damgård hashing involve putting the padding at the end instead of at the start? Pretty much the title. We have that $x$ is a prefix of $PAD(x)$, instead of being a suffix - was that an arbitrary choice or is there a reason for it? Thank you.

I can only provide a programming sense to this;
One may not know the size of the message beforehand (streaming), when finished, the length-padding can be executed nicely at the end. Otherwise, the system must store all of the messages to calculate the size, this will be very bad for constrained environments.


How is STS more secure than regular DH I'm trying to understand the STS protocol (using the wikipedia page as source), but I don't see how this protocol is any more secure than DH regarding man in the middle attacks.

If Alice and Bob don't know each others public keys, and have no secure channels at all, then an attacker (Charlie) could forge asymetric keys (x',x'G) and (y',y'G), and make independant connections between Alice and Bob for each of the 8 steps of the basic STS protocol as described on the wikipedia page.
Alice would believe Bob's key is y'G, and vice versa.
Charlie would be able to decrypt each of the signatures using the two different shared secrets (xy'G and x'yG), and then sign (y'G,xG) with xy'G and sign (yG,x'G) with x'yG and encrypt them again. So the encryption and signing of the (yG,xG) pair doesn't seem to make any difference to me.

If Alice and Bob have a secure channel allowing them to exchange their public keys then I don't see a way for a MITM attack even with regular DH.

Can someone help me identify where I'm wrong ?

Note the first paragraph of the page:

  In public-key cryptography, the Station-to-Station (STS) protocol is a cryptographic key agreement scheme. The protocol is based on classic Diffie–Hellman, and provides mutual key and entity authentication. Unlike the classic Diffie–Hellman, which is not secure against a man-in-the-middle attack, this protocol assumes that the parties have signature keys, which are used to sign messages, thereby providing security against man-in-the-middle attacks.

It's worth mentioning that this is to be expected --- the notion of "identity" in cryptography is different than in real life, and is probably best thought of as "knows the private key corresponding to some public key".
Given this, users must have a way to share public keys free from adversarial behavior (otherwise an attack like you describe can easily go through).
This is the purpose of Certificate Authorities in the modern web, and while they're a cryptographically inelegant solution (they're explicitly a trusted third party, where much of cryptography can be phrased as removing trusted third parties), removing them seems difficult.

Note that this protocol explicitly mentions authentication, while DH doesn't.
This is what enables you to MiTM DH.
Of course, in practice people use a separate digital signature scheme with DH key exchange for authentication --- so what's the difference?

Something that should become fairly clear rather early in cryptography is that how you combine primitives matters.
ECB mode can use secure primitives but still be insecure.
Just like that, DH can use a secure signature scheme and still be insecure.
This was the basis of the Logjam attack in 2015, where you could MiTM TLS 1.2 via (among other things) taking advantage of poor use of signing in the DH key exchange.


How can we verify if a function is indeed a one way function? How do we show that the addition function f (x, y) = x + y (where |x| = |y| and
x and y are interpreted as natural numbers) is not one-way?

I can see that the idea is to find any pair x and y which add up to x+y. But how do we ensure that the lengths are same i.e. |x| = |y| ?

First we need to precisely define what this function is. You don't give enough details, so I'm going to go with this.

  The function $f$ takes as input a string of even length $n = 2m$. It interprets each half as an unsigned $m$-bit integer, computes their sum, and outputs it as an unsigned $m+1$-bit integer.

So the function is defined only on inputs of even length; however this is not a problem because if we need a function defined on all inputs, we can just drop the last bit when the input length is odd.

The one-wayness game is as follows, on security parameter $n = 2m$:

A string $x$ of length $n$ is chosen uniformly.
$y = f(x)$ is computed.
The adversary is invoked with input $(y,1^n)$, and outputs a string $x'$.

The adversary wins if $f(x') = y$. In order to show that $f$ is not one-way, we must show that there is an adversary $A$ and a polynomial $p$ such that for infinitely many $n$, $A$ wins with probability at least $1/p(n)$. We will construct an adversary $A$ which wins with probability $1$ for all $n$.

Since $y = f(x)$ for a uniformly chosen $x$ of length $n$, it is the sum of two uniform integers in $\{0,\dots,2^m-1\}$. Thus $y$ will be an integer in $\{0,\dots,2^{m+1}-2\}$. $y$ will not be uniformly distributed (think of how the sum of two dice is more likely to be 7 than 12), but this is not a problem because our $A$ will win with probability $1$ for all values of $y$.

$A$ works as follows. If $y$ is even, it outputs $x' = (y/2,y/2)$, and otherwise it outputs $x' = ((y+1)/2,(y-1)/2)$. In both cases, it zero-pads each half so that it is of length $m$. It is clear than in each case we have $f(x') = y$, so the adversary always wins.


Name for identical operations for encryption and decryption Is there a name for the property of a cryptographic algorithm that the operations for encryption and decryption are identical, i.e.

$E_k(x) = D_k(x)$ and accordingly $E_k(E_k(x)) = x$?

An example for this would be most stream ciphers; are there any other, possibly block ciphers, with that property?

It seems like a good thing to avoid in a cipher design (otherwise, any encryption oracle would automatically become a decryption oracle); is there a name for the absence of that property as a security feature?

A cryptographic algorithm where the operations for encryption and decryption are identical is called a reciprocal cipher.
As dfaranha mentioned, this is mathematically an involution.

Most mechanical cipher machines use a reciprocal cipher, so it wouldn't need a seperate "encode mode" and "decode mode".

Some of the more famous reciprocal ciphers are:

The Enigma machine was a reciprocal cipher machine
ROT13
Beaufort cipher
Kama-sutra ciphers
XOR-based stream ciphers
One Time Pads (both XOR and Beaufort cipher versions)

Many modern single-block ciphers are built with a Feistel network structure that, in each round, cascades a reciprocal permutation P ("swap the left and right half of the block") and a keyed reciprocal substitution cipher S, to build a non-reciprocal bijective encryption function E(x) == P(S(X)) != D(X) = S(P(X). It is widely believed that practically any non-linear function can give adequate security if it is iterated over enough rounds.
While the overall cipher is not reciprocal, the parts that are reciprocal allow such ciphers to share parts between the encryption and decryption, so implementations use significantly less space (less code or less hard-wired ASIC area) than they would if they implemented encryption and decryption completely independently.

There are variants of the one-time pad that are not reciprocal (for example, using the Vigenère algorithm), but they are no more secure.


Using Permutation polynomial to compute a MAC Is the following MAC secure?

For a block $y_i$ in a file, we defined a MAC as follows: $Mac_i:PRF(k,i) \cdot g^{y_i \cdot r_i} \bmod p$.

Where $p$ is a prime number, $g \in \mathbb{G}$,$PRF(k,i)$ is a pseudorandom function whose output is distributed uniformly random over $\mathbb{G}$, $k$ is a $l$ bit key, and $i$ is index of value $y_i$ in the file .

** More importantly, we define a polynomial ring $R[x]$ and $f(x) \leftarrow R[x]$. Where $f(x)$ is a linear permutation polynomial that has the form $ax+b$, where $a,b$ are picked uniformly random from $R$. We define $r_i$ as: $f(x_i)=r_i$ where $x_i \in \textbf{x}$, and  $\textbf{x}$ is a pulbic vector and $R$ is $\mathbb{Z_p}$.

It is clear that if $r_i$ is picked randomly the above Mac would be secure for a file. So when we define a mac for a block at index $i$ in a different file, we change the key $k$ to $k'$. However, here I use a permutation polynomial and by definition, its output is distributed uniformly random in $\mathbb{Z_p}$ and I make the elements in $\textbf{x}$ public (for some computation which is not the focus of this conversation).

So I pick the polynomial,$f$, once for a file, and for each block $i$, I evaluate $f$ at the corresponding value in $\textbf{x}$, so $r_i=f(x_i)$. Note that there are $|R|^2-|R|$ different linear polynomials in the field $R$.

Please let me know if it needs more explanation.

It is clear that if $r_i$ is picked randomly the above Mac [defined in the second paragraph] would be secure.

Actually, that's not at all clear.  I would claim that if I were given that values of $Mac_i(a)$ and $Mac_i(b)$, I could compute the value of $Mac_i(x)$ for any $x$, as long as $a-b$ is relatively prime to $p-1$.  To do this, I need the value of $p$, $a$ and $b$, but not $k$, $r_i$, or for that matter, $g$.

To do this, I would compute $X = Mac_i(a) / Mac_i(b) \bmod p$; that value is $X = PRF(k,i) \cdot g^{a \cdot r_i} / PRF(k,i) \cdot g^{b \cdot r_i} = (g^r_i)^{a-b}$

I then compute $X^{(a-b)^{-1}}$, giving me the value $Y = g^r_i$.

I then compute $Z = Mac_i(a) / Y^a = PRF(k,i) \cdot g^{a \cdot r_i} / g^{r_i \cdot a} = PRF(k,i)$

Once I've done that, I can compute the $Mac_i$ of an arbitrary value $Mac_i(x) = Z \cdot Y^x = PRF(k,i) \cdot g^{r_i \cdot x}$


Google is using RC4, but isn't RC4 considered unsafe? Why is Google using RC4 for their HTTPS/SSL?

$ openssl s_client -connect www.google.com:443 | grep "Cipher is"
New, TLSv1/SSLv3, Cipher is RC4-SHA

Isn't RC4 unsafe to use?

Academically speaking, RC4 is terrible; it has easy distinguishers ("easy" means "can really be demonstrated in lab conditions"). It is also hard to use properly. However, SSL/TLS uses RC4 correctly, and in practice the shortcomings of RC4 have no real importance.

The power-that-be at Google decided to switch to RC4 by default because of the recent "BEAST" attack, which demonstrates (again, in lab conditions) a compromise of a Paypal cookie. There is no such dramatic demonstration for an attack on RC4 as used in SSL, so it was estimated that using AES-CBC with SSL/TLS 1.0 was "more risky" than using RC4.

The academically "right thing" to do would be to use AES-CBC with TLS 1.1 (or any ulterior version), which has no problem with BEAST and none of the RC4-related weaknesses either. However, Google makes money in the real world, and, as such, they cannot enforce a configuration which would prevent a third of their user base from connecting.


Why does AES-GCM need a hash/MAC in TLS? "TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256" is just one example for a cipher suite, as far as I'm concerned it means this:

It uses the TLS protocol, exchanges keys with Elliptic Curve Diffie Hellman Ephemeral, whose public keys are signed with RSA and afterwards AES 128 bit is used with the Galois Counter Mode, which provides authenticated encryption. The last function is a hash algorithm which is used for calculating the message authentification code for each packet.

Given that AES-GCM already provides integrity, why is an additional hash algorithm for authentication needed? Or am I mistaken with the interpretation of this?

From RFC 5246, section 6.2.3.3: AEAD Ciphers:

  AEAD ciphers take as input a single key, a nonce, a plaintext, and
     "additional data" to be included in the authentication check, as
     described in Section 2.1 of [AEAD].  The key is either the
     client_write_key or the server_write_key.  No MAC key is used.

However in RFC 5246, section 5: HMAC and the Pseudorandom Function:

  In addition, a construction is required to do expansion of secrets
     into blocks of data for the purposes of key generation or validation.
     This pseudorandom function (PRF) takes as input a secret, a seed, and
     an identifying label and produces an output of arbitrary length.

  In this section, we define one PRF, based on HMAC.  This PRF with the
     SHA-256 hash function is used for all cipher suites defined in this
     document and in TLS documents published prior to this document when
     TLS 1.2 is negotiated.  New cipher suites MUST explicitly specify a
     PRF and, in general, SHOULD use the TLS PRF with SHA-256 or a
     stronger standard hash function.

Finally, in  the hash function of the HMAC is also used to authenticate the handshake in the Finished message using the master key; see RFC 5246, section 7.4.9: Finished:

  Hash denotes a Hash of the handshake messages.  For the PRF
        defined in Section 5, the Hash MUST be the Hash used as the basis
        for the PRF.  Any cipher suite which defines a different PRF MUST
        also define the Hash to use in the Finished computation.

So it is used for key derivation and authentication and for a final confirmation that the handshake succeeded, not for generating the MAC over the data messages.


Strategy to crack a presumed substitution cipher The ciphertext given is:

ejitp spawa qleji taiul rtwll rflrl laoat wsqqj atgac kthls iraoa twlpl qjatw jufrh lhuts qataq itats aittk stqfj cae

I've done frequency analysis on the text. That yielded the following results:

A(15), B(0), C(2), D(0), E(3), F(3),  G(1), H(3), I(6), J(6), K(2), L(11), M(0),
N(0),  O(2), P(3), Q(7), R(5), S(6), T(15), U(3), V(0), W(5), X(0), Y(0),  Z(0)

There are 120 characters total. The format of the ciphertext does not match the format of the quote from which it was created.

The most common digrams (in order of most frequent to least, max 6, min 2):

at, it, tw, lr ,ta, ej, ai, ao, aq, ll, ts, wl, ji, hl, ja, sq, oa, qj

The most common trigrams in the same order (max 3, min 2):

atw, ita, jat, jit ,eji, twl, oat, aoa, qja

I've tried substituting character a few at a time to see if I could start to make out some words, but every time I have ended up with letters next to each other that don't make any sense.

I don't need the exact answer, but if someone could help point me in the right direction I would appreciate it. The answer would be great too, but I'd really like to understand the process here.

There are different approaches to crack a substitution cipher.

A human would use a different strategy than a computer. But as the word boundaries are not preserved it will be rather challenging for a human solving this cipher.

The quipqiuq tool mentioned by John is using word lists, but there are other methods as well.

Resources:

http://reflectionsonsecurity.files.wordpress.com/2011/03/fast-reliable-cryptanalysis-of-simple-substitution-ciphers.pdfThis paper proposes to use the genetic algorithm.
http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-simple-substitution-cipher/Describes how to crack a substitution cipher using the hill-climbing algorithm.
http://www.cryptoden.com/programs/Ari_Pat_WW.htmlThis solver is using the hill climbing approach. The good thing is that you can study the Javascript code. I think this tool expects the cipher text in upper cases.
http://www.guballa.de/pages/geocaching/substitution-solver.phpThis solver uses the hill climbing approach as well.

Note: If feeding your cipher text one of the online tools above you will notice that the word "sherlock" was used to generate the cipher alphabet.


Why in cryptographic schemes we always assume that the key and plaintext are independent? Why do we always assume in cryptographic schemes that the key and plaintext are independent? What if the plaintext depends on the key? How can this endanger security? Is this assumption essential for both symmetric and asymmetric algorithms?

What if the plaintext depends on the key? How it can endanger security?

Well, one trivial example where it can is if you are using RSA (without padding), and encrypt one of the prime factors. Someone seeing the ciphertext could immediately factor the modulus (by computing the GCD of the modulus and the ciphertext), thus endangering security.

There is a formal name for systems where this provably can't happen; circular security.  See this paper for a public key cryptosystem that can securely encrypt any polynomial function of the private key (up to a degree bound).

My personal opinion: If you really need to do this sort of thing, I think a hybrid scheme such as the Integrated Encryption System would suit your requirement quite nicely.


Login security and plaintext of a password stored in Argon2i to derive a key via halite safe? I'm using Symfony 4. I have set parameters on all my Argon2 stuff below so that it takes 1s per iteration. This website is supposed to encrypt HIPAA information.

Basically I have a table like this

username varchar(50),
password varchar(255)

In the password field I'm storing passwords with Argon2i. Users login and it verifies their password in the database (this is all done with Symfony login).  After that users are presented with another screen to enter a passphrase. They enter the second password (this password is shared among all employees of the company).

I have another table like

key_pass varchar(255),
salt varchar(50)

the second password is used with password_verify against the value of key_pass which is a password stored with Argon2i.  If it's successful, then I use Halite (aka scrypt provided by libsodium in this scenario) to derive a key using the value of salt.  Basically the whole thing looks like this:

if (password_verify($view->getPassword(), $encryption->getKeyPass())) {
   $encryption_key = EncryptionKey::deriveFromPassword(
      $view->getPassword(),
      $encryption->getSalt()
   );
}

This key would be used to decrypt the rest of the data in the db.

So three questions:

1) Is this form of double authentication even helping security?  I mean basically in the end if the attacker gets the second passphrase they don't even need the first login (assuming they have direct access to the data).  I suppose it just makes the web site more secure since they can't even attack the second passphrase without having the first via the web site?

2) Is using the second passphrase to derive the key safe?

3) Assuming #2 is "yes", in the event I want to change the second passphrase (i.e. - employee leaves company), is this possible without re-encrypting all of the data using the new derived key? If no, what possible implementations/alternatives could allow for that? Perhaps storing another key encrypted in the database and using the above derived key to decrypt that and then that key is the real key that decrypts other data in the db? If that works would Halites Symmetric::encrypt be secure enough for the second key?

Thanks for any help!  I've been researching this stuff for months but I'm no security expert - would REALLY appreciate somebody just validating all this that I came up with

1. Is this form of double authentication even helping security?

Possibly, but in general, asking users to remember two passphrases is asking too much. It is less likely that either one of them will be secure enough to be used as password.

  2. Is using the second passphrase to derive the key safe?

Probably, but sharing a password among all the other employees is certainly not secure.

Besides that, using both Argon2i and scrypt on the same input material only slows down your service, while an adversary only needs to perform the fastest one (from their perspective).

If a key is derived after verification of the password then a Key Based KDF such as HKDF can be used.

  3.  ... is this possible without re-encrypting all of the data using the new derived key?

No, for that you'd need a data key as you're describing.

  If that works would Halites Symmetric::encrypt be secure enough for the second key?

Sorry, but that's off topic here; we cannot vouch for the security of a crypto system or library. You can of course do worse than libsodium to encrypt data, but if it is secure also depends on system and implementation details.


Robust authentication and integrity for short OTP message Using any of the wonders of modern cryptographic technology, how is it possible to package a tweet-sized plaintext, which is to be encrypted with a proper one-time pad, to ensure its integrity and give it authentication? For these last two services we aim for at least a 128-bit level of assurance. We also want to indicate message order, with a tag, at the same level of protection.

Here are some ways to do it:

1.) One method would be to use a Carter-Wegman MAC.

2.) Another would be to use NaCl / Libsodium with the ChaCha20 stream cipher and the Poly1305 authenticator.

3.) Use an HMAC such as HMAC-SHA-256.

Is there another way that is reliable?

Thank you very much.

If you want to be consistent with OTP usage, then you should use a One Time MAC. Currently it seems the easiest path for that is to simply use Poly1305, but remember that you must never reuse keys for Poly1305, just like you can't reuse keys in OTP. (In particular, don't use the key generation routine used by ChaCha20-Poly1305 to derive the Poly1305 key from a nonce/key pair).

Using HMAC doesn't make much sense: if you're using OTP, that's probably because you don't trust any particular block cipher, so you shouldn't trust any particular hash or MAC algorithm.


In NTRU digital envelope, do everyone know the hash function $H$ used? I have a simple question about the NTRU original cryptosystem using a digital envelope.

The article can be found here: http://grouper.ieee.org/groups/1363/lattPK/submissions/ntru.pdf

It is said that we need a generating function $G$ and a hash function $H$.

Suppose that Alice wants to send a message to Bob. Then she will use some generating function $G$ and some hash function $H$.

Bob recieves the ciphertext $e$ and at a certain point of decryption it is said that Bob should compare $c''$ and $H(c',b)$.

Suppose that Eve exists.

My question is: Do Bob and Eve know $G$ and $H$? In the way the decryption is described, Bob needs to know $H$, but it's not clear if he knows it.

Thanks in advance.

Yes, these are public parameters of the system.

Note that NTRU is not implemented exactly this way any more. The most up-to-date current spec is EESS#1, which can be obtained from https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/doc/EESS1-v3.1.pdf.


Why are these specific values used to initialise the hash buffer in SHA-512? I'm reading the book Network Security Essentials written by William Stallings.

To create a message digest with SHA-512, we have to go through some steps:

append padding bits.
append length
initialize hash buffer
... so on.

In the book is written for step 3:

  A 512 bit buffer is used to hold intermediate & final results of
  the hash function. The buffer can be represented as eight 64-bit
  registers (a,b,c,d,e,f,g,h). These registers are initialized to
  the following 64-bit integers (here in hexadecimal values):

 a = 6A09E667F3BCC908
 b = BB67AE8584CAA73B
 ...

  up to register h.

Why are these specific hexadecimal values used, is there any particular reason behind this? I know why they are necessary, but why these specific ones?

The initial hash values for SHA-512 are the 64-bit binary expansion of the fractional part of the square root of the 9th through 16th primes (23, 29, 31, ..., 53). That is:

$$I_0 = \left \lfloor \mathrm{frac} \left (\sqrt{23} \right ) · 2^{64} \right \rfloor$$
$$I_1 = \left \lfloor \mathrm{frac} \left (\sqrt{29} \right ) · 2^{64} \right \rfloor$$
$$\cdots$$

And obviously the reason they use primes is that their square root is always irrational, which makes for a nice, random-looking number. Taking the square root of four would be less interesting, as it would give 0. It also means the constants are relatively independent from each other, as none of them can be easily expressed in terms of any other, which might be a weakness - but that probably doesn't matter as much.

They are chosen this way because while they generally don't need to be anything in particular, as long as the chosen numbers don't have some special properties (i.e. setting them to zero might be a bad choice), the designers of SHA-512 wanted people to know that the numbers weren't chosen so as to stealthily introduce a backdoor in the algorithm (for instance, if a certain combination of initial values were chosen, it may have been possible for the NSA to break  the hash function more easily) which would be very difficult to confirm or refute as it would require months, perhaps years of cryptanalysis.

Using publicly available numbers that anyone can recreate, here the fractional parts of some prime square roots, solves this problem - there is no way anyone can change these numbers (nobody can change the square root of 23, for instance), and it is considerably harder to design an algorithm to have a backdoor under set constants, than to design the algorithm first and work out those constants later on.

The first few digits of $\pi$ or $e$ are popular choices too, but only if you use the first digits. If you were using, say, the digits starting at position 94858991, I would get very suspicious.

See Nothing up my sleeve number, also this similar question.


Is AES a linear hash? So, having read a variety of documentations on AES encryption, I came to the unknowledgeable conclusion that the key schedule applied to the array of chunks, and not just the 14 cycles on a single chunk. Thus I concluded that AES was not a linear hash, such that ciphering sequential equivalent chunks would produce a set of non-equivalent chunks.

I guess I kinda didn't pay attention though - I just used AES encryption source code to cipher an array of the same character, and got a very linear result. x-)Is the AES key constant for all chunks? And should I be using a block-cipher mode other than ecb? Or is AES strong enough on its own?

The full AES key schedule used by each call to the AES block cipher. The use of the key schedule does not stretch across different calls for different block encryptions.

Internally, the 14 rounds (for 256 bit keys) of the AES round function use each of the 14 round keys. Those 14 round keys are what comprise the key schedule.

The linear property you observed is indeed correct when AES is used this way. Each block is encrypted without context, and always encrypts to the same ciphertext. This method is called ECB mode. In the real world, that property is a weakness and a different mode like CBC would be used to destroy that property (although the key schedule is not used to do so).


Zero-Knowledge proof of inequality I think it's neat how a person can prove that two discrete logarithms are equal without actually revealing the value.

So, conversely, is there a way for me to prove that two discrete logarithms are not equal without revealing either logarithm's value?  Assume that I know (by construction or by oracle) the discrete logarithm value for any pair of elements (from the 4 given elements) and I thereby know that all are unique.

A zero-knowledge algorithm for proving inequality of two discrete logarithms was given e.g. by Camenisch and Shoup in Section 6 of Practical Verifiable Encryption and Decryption of Discrete Logarithms (CRYPTO'03).

Quoting  from the paper:

  Let $G=\langle g \rangle$ be a group of prime order $q$. The prover
  and verifier have common inputs $g, h, y, z \in G$ where $g, h$ are
  generators of $G$ and $log_g y \neq log_h z$. The prover has the
  additional input $x = log_g y$. The prover and the verifier then
  engage in the following protocol.

  The prover randomly chooses $r \in Z_q$, computes the auxiliary commitment $C = (h ^x/z)^r$, and sends $C$ to the verifier.
  The prover executes the protocol denoted $PK\left\{(\alpha, \beta) : C = h^\alpha (\frac{1}{z})^\beta \wedge 1 = g^\alpha (\frac{1}{y})^\beta \right\}$ with the verifier. (Note that this is a
  proof of equality, so we know how to do this).
  The verifier accepts if it accepts in Step 2, and if $C \neq 1$; otherwise, the verifier rejects.

  This constitutes an honest-verifier proof system for proving that
  $log_g y \neq hog_h z$.


Diffie-Hellman key size to symmetric formula? I've noticed that on every site I checked I kept finding the relationship between D-H key size and symmetric encryption equivalent as a table, like:

384 - 56

768 - 80

1792 - 112

2304 - 128

10753 - 256

...

But I never found the formula that is actually used to calculate this equivalence. From what I can see by key size growth there is some square root of asymmetric key employed, multiplied by something, but I couldn't reverse engineer the formula myself.

Could anyone point me in the right direction? Thank you.

Your intuition is correct: for the same security parameter, the size of asymetric keys of symmetric keys is (at least) proportional to twice the size of a symetric key, or equivalently, 2^{sym. key} is proportional to the square root of 2^{asym. key}.

The reason for that is that symetric cryptography does not need any particular structure for the operations involved - in fact, it tries to avoid any kind of structure. As a consequence, a symetric scheme with a key of size k will be bruteforced in time O(2^k), by searching for all the possible keys.

Asymetric schemes, however, do heavily rely on algebraic structure. And this structure gives more power to an adversary: a computational problem in a group of order p with no more structure (a generic group) can be solve in time O(sqrt(p)). This is related to the birthday paradox. A classical example is Shank's baby-step giant-step algorithm (or its space-efficient variant, the Rho-Pollard algorithm), which allows to solve the discrete logarithm problem in a group of size p in time O(sqrt(p)).

Hence, if your public key scheme works over a group, you cannot avoid using keys at least twice bigger than in the symetric case. This size of the keys will be sufficient if there is no better attack than the generic attack (the baby-step giant-step approach) in the group you use. This is the case, for exemple, for well-chosen elliptic curves; hence the ElGamal cryptosystem over suitable ellipic curves might use keys "only" twice bigger than standard symetric keys. But in some other groups, like finite fields, or the RSA group, the group has more structure than a "generic" group, and there exist way better attacks on problems, such as factorization and discrete logarithm, than the baby-step giant-step attack. Hence, for cryptosystems based on such groups, the keys will in general be way bigger - and that time, the recommanded size of the key does simply depends on the best know attack.


Do I need to implement multi precision arithmetic operations? I want to implement Elliptic Curves arithmetics (for edu purpose and better understanding) for special NIST primes: point addition, exponentiation, etc.. all operations needed for EC encryption/decryption, digital signatures, and key exchanges. I'm interested in only special NIST primes, not in implementation for a general curve. Do I need to implement a multi-precision arithmetic for some fixed word size (32, 64) such as add/sub, reduction, inversion, Montgomery reduction, and so on? As far as I understand these primes are selected so that implementation is fast comparing to a general implementation.

Whatever the curve, it's needed to use multi-precision integer arithmetic in ECC cryptography, at least for a few modular operations modulo the Ellitic Curve group order, since that's large (192-bit is the bare modern minimum). For the field, where the most compute-intensive operations are, there are alternatives with fields other than prime order groups. See for example Thomas Pornin's Efficient Elliptic Curve Operations On Microcontrollers With Finite Field Extensions (note: in this work, extensions applies to field, not microcontrollers).
For curves on prime-order field (as in the question), it's indispensable to have multi-precision integer arithmetic for field operations, and the performance of modular operations is central to the overall performance. Special attention to side channels, including timing, must be taken when manipulating confidential information (when signing and decrypting, and to some degree when encrypting; that's usually not a concern for signature verification).
For prime field using special NIST primes (as in the question), speed optimizations are possible. That's the reason to use such primes. All correct generic multi-precision integer arithmetic techniques and libraries (including GMP) work with these primes, but in general do not take advantage of the special form for speedup. Such techniques and libraries are thus adequate to get correct results, but not to get the best possible performance. More often that not, they also do not give adequate protection against side-channel leakage. Only some functions of GMP are written with this in mind.


Does an encryption algorithm exist where encrypted data can be decrypted by multiple private keys? Suppose I have Company1 with their own Public/Private Key Pairs and another Company2 with their public/private key pairs and yet another Company3 with their public/private key pairs.

Is there any way/algorithm to encrypt a piece of data, given we provide Company1 and Company2 public keys to it, such that the encrypted data can be decrypted by EITHER ONE of their private keys. i.e. upon receiving the encrypted data, Company1 can use their private key to see what it actually is, and so can Company2, without them knowing each other's private keys. Also, Company3 should in no way be able to decrypt that data.

I've also been looking at Shamir's Secret Sharing algorithm. It works somewhat for our use case, assuming we encrypt each share using PGP and share it to the companies. In our specific use case, the bottleneck is that any data sharing between the companies happens on a shared ledger/database -- so by default everyone sees everything. Also not sure what the maximum number of shares are in this case, as its possible the list will grow to hundreds of shares being generated.

Yes, quite easily, with key encapsulation and the appending the symmetric key twice (encrypted for each company):

Encrypt the data with a random symmetric key, for instance an AES key;
For each recipient, encrypt the symmetric key with the respective public keys of the recipients.

The ciphertext is the combination of the encrypted message and wrapped key for each recipient.

More theoretically, you could use identity-based encryption, which is close to what you describe. That does require a common setup, though, and possibly someone having a master key.


Question on RSA trapdoor permutation You plan to use a public-key cryptosystem based on the RSA trapdoor permutation in three different real-life applications, in which the attacker has, respectively, only one of the following resources:

a single computer,
a collection of computers distributed across the Internet, and
a quantum computer.

When choosing the length of the modulus n for the RSA trapdoor permutation, you plan to choose a different length for each of the above three attacker resource scenarios. Which of the following length settings is closer to your choice?

A. (a): 1024; (b): 2048; (c): 4096
B. (a): 512; (b): 1024; (c): I would not use RSA
C. (a) 2048; (b): 4096; (c): I would not use RSA
D. (a) 512; (b): 1024; (c): 2048

Not sure how to do this. Can anyone help me with this and explain why?

My own answer would be: 2048, 2048, and still 2048 bits.

Why ? Because:

2048-bit is the current "standard recommendation"; it has been so for quite some time, and is likely to remain so for quite some time (decades). See this site for pointers.
There are plans for removing support for keys shorter than 2048 bits in some widespread software, e.g. Firefox. Using shorter keys invites future interoperability trouble and maintenance headaches.
There are widespread systems (in particular hardware, such as smart cards and HSM) which have trouble with keys larger than 2048 bits. Even when longer keys are supported, the computational cost rises quite sharply with the key size, so you don't want to overdo it (if your algorithm is super-secure but too heavy, then people will look for ways not to use it, and so goes security down the drain).
If your enemy has access to a quantum computer, then he has resources which are way beyond your wildest dreams. Remember that hiring a few thugs to break your kneecaps is cheap; an attacker with a budget of more than 10k$ will just do that, instead of trying to unravel your public key with computers. Then an attacker who can afford a machine that does not seem to exist at all... Contrary to a quantum computer, a tiny camera concealed in your own glasses is doable with existing technology, and will reveal all your secrets. Worrying about quantum computers is therefore misdirected paranoia.

Your examiner would probably dislike this answer, though. He probably expects that you answer "don't use RSA" when the attacker has a quantum computer, so that you show that you have understood that a quantum computer will make short work of RSA keys of any size.


Maximum value of negligible probability? We can see on many papers for cryptography that there are many uses of negligible probability to ensure something (security, correctness, etc).
How can we say that some probability is negligible?

I want to know the maximum value of negligible probability.
In other words, if we have a some probability $1/k$ for some $k$.
What is the minimum $k$ that provides negligible probability?

Thank you.

It depends on context.

In a theoretical context, baring other definition, a probability is negligible if it decreases exponentially (or: faster than any polynomial of fixed degree) with some security parameter $k$, often a number of bits in the key; while the computational effort to use the system grows no faster than some polynomial of $k$.

In a practical context, if the probability is for one try of the adversary, and more tries will increase that probability about linearly, something like $2^{-80}$ used to be considered adequate, $2^{-128}$ is considered adequate for a decade or two baring hypothetical future quantum computers usable for cryptanalysis, $2^{-192}$ and $2^{-256}$ are sometime specified (because of security classification levels, and because that improves confidence when considering said quantum computers). Lower values will do, of course. Higher values (like $2^{-64}$) wight still make sense if the stakes are low and lowering that probability was costly, or forbidden by law.

In a practical context, if the probability is with all the parameters influencing it (effort of the adversary, number of users, size of plaintext..) set to credible values maximizing the probability, then $2^{-10}$ to $2^{-40}$ is reasonable, depending on how damaging the low-probability event would be. Lower values will do, of course.


Why do $\alpha$ and the private key value in diffie-hellman should be from $2$ to $p-2$ I just started learning Diffie-Hellman Key Exchange. I couldn't get the reason of making $\alpha$ and private key for Alice and Bob constrained between $2$ and the prime number generated minus $2$ (=$p-2$). Why should it be $2$ less than the prime? Is there a specific reason for this?

The reason for both is that the generated values are trivial to detect / exploit and should be avoided and your RNG is deeply flawed if you actually get those values because the chance for this lies around $2^{-2000}$ if you use an appropriate parameter set.

Now for the math:
You need to choose your secret exponent $x$ such that $1\leq x\leq p-2$, with $p$ being the prime defining the multiplicative Field $\mathbb Z_p^*$. Your generator $\alpha$ needs to be chosen such that $2\leq \alpha \leq p-2$. The source for these constraints is the famous Handbook of Applied Cryptography, 1996, Menezes et al (page 516).

The constraints for the secret exponent apply because $\alpha^0$ meaning $x=0$ is $1$ and thereby fully insecure. If you use $p-1$, Fermat's little theorem applies and you get $\alpha^{p-1}\equiv 1\pmod p$ which is also trivially insecure. You can't get any value beyond $p-1$ because you can reduce those $\bmod (p-1)$ which allows you to reduce $p-1$ to $0$, $p$ to $1$ and so on.

As for the generator, you want to have one that generates a large group (via exponentiation) and this trivially excludes $1$ and $0$ which will you only ever give the sets $\{0\}$ and $\{1\}$ respectively. So they are a really bad choice for $\alpha$. You also can't chose $\alpha=p$ because you can then reduce this every time $\alpha=0$ as all operations are carried out $\bmod p$. Now what about $\alpha=p-1$ (the last edge case)? First you need to note that $p-1\equiv -1 \pmod p$ and if you exponentiate that you'll only get $(p-1)^x \equiv (-1)^x \equiv \pm 1 \pmod p$ which is the set $\{1,p-1\}$ and thereby a really bad choice.


In the STS Authentication Protocol, why are the signatures encrypted? From Wikipedia:

(1) Alice → Bob : g^x
(2) Alice ← Bob : g^y, E_K(S_B(g^y, g^x))
(3) Alice → Bob : E_K(S_A(g^x, g^y))

I know there should be something I'm missing, but I cannot think of why E_K(...) is used. Isn't the signature sufficient? Even if there was a MITM, having S_B(...) or S_A(...) isn't very useful. What am I missing here?

The encryption of the signatures

$\;$ keeps the identity of the initiator (Alice) confidential, even against active attackers
$\;\;\;\;$ and
$\;$ keeps the identity of the responder (Bob) confidential against passive eavesdroppers
$\;\;\;\;$ and
$\;$ provides some protection against identity misbinding attacks,

$\;$ although not as much as a good protocol should have

.


Is LPN not as important as LWE and SVP? I've been learning about lattice cryptography and have noticed that most resources such as this survey by Chris Peikart, the Winter School on Lattice Cryptography etc don't include material on LPN, and typically only discuss SIS and LWE. According to this post, Are LPN and LWE problems equivalent?, LWE is a generalization of LPN. From what I understand, SVP (derived from SIS), and LWE are common lattice trapdoors. Is LPN not an important lattice trapdoor worth discussing? If it isn't, why is that the case?

LPN is code-based problem, not a lattice problem. These are quite similar, but are defined with respect to different notions of "distance" (Hamming vs $\ell_p$-norm). In general while there are broad parallels between the worlds of lattices and codes, these parallels are not exact.

A particular example is the hardness of computing the "smallest element" of code/lattice. For codes it is the minimum distance problem, for lattices it is the shortest vector problem. Stronger hardness results are known for MDP (SVP's best hardness results require randomized reductions, MDP's are deterministic). Other mathematical problems can vary wildly in difficulty --- the "sphere packing" problem for codes is much simpler than for lattices.

Of relevance to cryptography are worst-case to average-case reductions. This has been a large motivating factor for lattice cryptography since its inception in the 90's, but similar results for codes were only developed last year (and I believe the results themselves are somewhat weaker, but am not an expert). This paper states that its the first construction of collision-resistant hash functions from $\mathsf{LPN}$, which might help highlight the technical difference in the state of the art for lattice-based cryptography vs. code-based cryptography (for the construction of certain primitives).


Key Entropy meaning Help Can anyone help me understand key entropy the mathematics behind it and the uses for it?
I understand most of it but I just want to understand what does $\log 2$ do like if I do. $\log 128 / \log 2 = 7$?

The Professor has really confused me here on this one on what the $\log 2$ mean? formula;
$Entropy = \log(Phrases)/\log 2$

The professor gave this formula, too: How many bits can represent $X$ phases? Just take the $\log X$, and divide by $\log 2$.

The Professor has really confused me here on this one on what the
  $\log 2$ mean? formula: $\text{Entropy} = \log(\text{Phrases})/\log 2$

If I understand the problem correctly, you are asking what the $\log 2$ is doing there in the denominator. This is essentially to ensure that the base of the logarithm (whether it's $10$ or $e$ or $2$) doesn't matter and you always get the computation result as a base-2 logarithm.

As a quick reminder: The base in a logarithm is the $b$ for which you are looking to find the $x$ such that $b^x=a$ for $x=\log a$.

  How many bits [are needed to] represent $x$ [phrases]?

So you have $x$ values and you want to know how many bits you need to have in order to identify all of them. Well, first note that 1 bit can address 2 values, 2 bits can address 4 values, 3 bits can address 8 values, etc. $n$ bits can address $2^n$ values. Thus we are looking for the smallest value $n$ such that $x\leq 2^n$. So we first compute a logarithm, to an arbitrary base, on both sides of the inequality, which yields $\log x\leq \log(2^n)=n\cdot \log 2\Leftrightarrow \log x/\log 2\leq n$, thus $\log x/\log 2$ bits are sufficient.


Machine Learning to improve Encryption algorithms Can machine learning be used to improve encryption algorithms e.g.image encryption algorithms that use ECC ?

No. There is large consensus that:

There is nothing special about image encryption algorithm, they are just encryption algorithms.
ECC is useful for such algorithms inasmuch as they need to be made public-key. That's done by way of hybrid cryptography. Directly encrypting images with ECC cryptography would have terrible performance, thus is not worth serious consideration.
There's no clear need to improve any of these algorithms in a way where machine learning seems to be necessary or even helpful.

In a quite different direction: Machine learning also has a poor track record at attacking modern cryptographic algorithms, but that idea may not be worthless. Perhaps machines one day will learn cryptanalysis.


Known-plaintext attack on Blowfish in ECB mode The protection scheme I faced recently seems so weak nowadays that a simple exhaustive key search would be enough to recover the user key in an acceptable amount of time (it's OK, since almost no practical benefit could be gained from knowing the plaintext), but I'm just curious whether the key recovery could be accomplished even faster and more intelligently.

The scheme consists of using Blowfish encryption with 40-bit key, with ECB mode of operation — i. e. no initialization vector, no feedback. This is countered by having a separate key for each document (or related set of documents), and by compression of documents.
On the other side, those documents are always ZIP archives with a single file packed in them, generally with the most simple capabilities. As a result, the first 32 bits (one Blowfish word) always contain the ZIP's local file header signature; the following 32 bits are usually constant for a given data producer, i. e. can be compared against a fixed value or can be verified partially. Further data is varying, but can be verified for plausibility as well.

The question is: does the knowledge an exact value of single block of plaintext give any advantage to key recovery — beyond the ability to easily check for a match in brute-force attack? Every discussion on that topic that I found claimed that Blowfish can't be reversed, but provided no proof for this; moreover, those topics were concerned about other modes than ECB and substantially longer keys. Then I started searching for discussions on recovery of subkeys instead of the original user-supplied key, and found this recent paper:

“All Subkeys Recovery Attack on Block Ciphers: Extending Meet-in-the-Middle Approach”, Takanori Isobe and Kyoji Shibutani, Sony Corporation
presentation of the same paper for Symposium On Applied Computing, 2012

The full paper seemed too general for me, with little explanation on used symbols. The only thing I understood is that for key length of 40 bits there should be more than one 64-bit block of known plaintext, which is not the case for me. The other bad thing is that I didn't notice anything about the round-wise subkeys (the P-array) there — they were talking about substitution boxes only. The last slides of presentation put me in even much more confusion, since they claim that subkey recovery attack is effective with keys longer than 292 bits.

PS. Regarding the speed of brute-force attack against Blowfish. My initial implementation in .Net performed about 2800 checks per second, reimplementation in pure C with heavy inlining raised the bar up to 27'500 in a single thread and about 200'000 in 10 threads on a Core i7-2600 with hyper-threading — that's just 64 days for a complete range scan. And, although Blowfish is believed to be GPU-unfriendly, an OpenCL bcrypt implementation shows even more performance, the more so that bcrypt is a heavier form of Blowfish.

If there was a full 64-bit block of known plaintext, there would be a very fast attack using precomputation.  You can build a precomputed table of all $2^{40}$ ciphertexts.  Once you've got the precomputed table, recovering a key (given a ciphertext) would require just a single lookup in the table, so recovering a key would be extremely fast.  Storing that table would require something like 5 Terabytes of storage, which isn't too bad: it might cost you \$300 or so to buy 5 TB of storage.  The precomputation takes $2^{40}$ trial encryptions (key schedule + a single block encryption using Blowfish), e.g., 64 days for your implementation.  Once you've built the precomputed table, cracking each file/ciphertext could be done almost instantaneously.

If 5 TB of storage feels like too much, a variant of this would be to use the Hellman time-space tradeoff (or, if you prefer the "hyped" version, "rainbow tables").  That attack also requires a precomputation that takes about the same amount of time: $2^{40}$ trial encryptions.  However, its storage costs are much lower: storage for a table containing about $2^{27}$ entries (instead of $2^{40}$ entries), which corresponds to about 700 MB of storage.  The trade-off is that cracking each file/ciphertext takes a bit longer: about $2^{27}$ Blowfish trial encryptions, or about 700 seconds.  So, once you've built the precomputed table, cracking each file/ciphertext can be done very quickly: not instantaneously, but much faster than exploring the entire space of all $2^{40}$ keys.

These precomputation attacks are not of any benefit if you only have a single file to crack, but if you expect that you'll want to crack multiple files/ciphertexts, then the precomputation attacks can be beneficial: they allow you to amortize the cost of the precomputation across many different files/ciphertexts.

However, you say that you only have 32 bits of known plaintext, not a full 64-bit block of known plaintext, so these precomputation attacks are presumably not applicable to your particular setting.

FYI, the Isobe-Shibutani paper is not going to be helpful to you.  Their basic attack on reduced-round Blowfish takes at least $2^{160}$ steps of computation and thus is completely impractical -- not to mention that it only attacks a reduced-round variant of Blowfish with 8 rounds, whereas the real Blowfish uses 16 rounds.  Their attack on the full 16-round Blowfish takes $2^{288}$ steps of computation, so is ridiculously impractical.  In short: that paper is completely irrelevant to any real-world attempt to mount key-recovery attacks on Blowfish.


Is there a method/protocol to validate a self-signed certificate by comparing a shortened hash? I'm working on a solution where an iPad should connect to a server software running on a laptop using TLS with a self-signed certificate that was automatically generated on the laptop during the installation of the software there. I need to make sure there is no man-in-the-middle attack, so the obvious solution would be to take a hash of the cert with a function that is second preimage resistant and show the hash on the laptop and iPad.

The problem is that carefully comparing all the digits of a SHA-256 hash, for example, takes a while so I'd rather have a method that is (almost) as secure and works by comparing only 10 digits or so.

In principle that must be possible because the numeric comparison protocol of Bluetooth works like that. Details see on page 13 of this document: http://u.cs.biu.ac.il/~lindell/PAPERS/BT-numeric.pdf

Is there an easy method or protocol to shorten the string of digits that has to be compared but without too much overhead? Re-implementing the way this is solved for Bluetooth seems like a lot of work.

TL;DR: Using words instead of strings / images may be a good solution for short, easy-to-verify codes and using locality / time dependent verification codes strengthens short hashes as would using password-hashes.
Additionally to the improvements to comparability of the hash proposed by A. Toumantsev, I will propose three extra measures which I believe may be more unconventional than his solution but will adapt to your situation in a better way.
The challenge you're facing
You need to reduce the output size so much that a user won't get tired comparing two outputs, making the comparison short and / or interesting is the obvious solution.
At the same time you need to ensure that the output is not too short, or an attacker will be able to brute-force keys with the same output and thus will be able to fool the user and accept a man-in-the-middle attack.
Improvement 1: Don't use images or QR-codes, use words!
Images tend to be difficult to compare properly and chances are that the user screws up the comparing process as much he can do with long number strings, in fact if the image is high-resolution it may actually prove more difficult to do a proper comparison.
Randomly selecting a word in the user's native language for each byte (or maybe two bytes) and showing the user a "sentence" consisting of 16-32 such words may actually be feasible for full comparison. This would then benefit from the Stapled Horse batteries effect and be easier to remember / check, much like passphrases are easier to remember than passwords.
Of course this only a suggestion and actual tests are required in order to find the most effective solution.
Improvement 2: Buy yourself strength by imposing time limitations
You are in the lucky situation that the parties wanting to verify each other's public key can communicate. This way you can randomize the verification process, because if an attacker found a key that passes your 64-bit test, he will probably fail your randomized test, so just let both devices exchange a random nonce and display the properly encoded $\operatorname{HMAC-SHA256}_{\text{Nonce}}(\text{PublicKey})$ for verification to the user. If you let this HMAC expire after an hour or so, you effectively only give an attacker that time amount for finding an appropriate second-preimage.
This trick with a 128-bit nonce would allow you to reduce the shown value's size to somewhere around 64-128 bit (less would slowly become dangerous again) while still maintaining strong security.
You may also want to give the user an option to mark a certificate / key as "verified" for this method.
Improvement 3: Password hashes
You can combine the above three methods with a password-hash that takes a few hundred milliseconds on your devices (using the nonce as the salt and the key as the password). This way an attacker has to spend a considerable amount of effort for each key generation, slowing down any brute-force attack attempts. With this method you can probably gain 10-20 "bits" of security without any problems, allowing you to shorten the displayed value even more.


Reversing ITUbee's diffusion operation One of the functions used in ITUbee's round function is $L$ which is defined as $L(A, B, C, D, E) = [E \oplus A \oplus B, A \oplus B \oplus C, B \oplus C \oplus D, C \oplus D \oplus E, D \oplus E \oplus A]$. Is this operation invertible?

Yes, it's invertible. Consider:

$(E \oplus A \oplus B) \oplus (B \oplus C \oplus D) \oplus (C \oplus D \oplus E)$

to get the value of $A$. The values of $B, C, D$ and $E$ can be calculated in a similar manner.


What parts of AES encryption result are safe to pass on the network I'm using AES to encrypt the message.
both sender and receiver know the passphrase, but only sender knows IV and salt

I assume that receiver also needs to know IV and salt to decypher text;

is it safe to pass IV and salt along with the cyphertext over an unsecured network, or will this compromise the security?

I'm using https://code.google.com/p/crypto-js to send encrypted messages between multiple clients.

IVs and salts are public, so they are safe to pass with the ciphertext. They should be authenticated along with the ciphertext though.


Recovering the key in an ElGamal Signature Scheme variant From page 318 in Stinson's "Cryptography: Theory and Practice", question 7.3:

Suppose that Alice is using ElGamal Signature Scheme. In order to save time in generating >the random numbers k that are used to sign messages, Alice chooses an initial random value >$k_0$, and then signs the $i$th message using the value $k_i = k_0 + 2i \mod (p-1)$ >(therefore $k_i = k_{i-1} + 2 \mod (p - 1)$ for all $i \geq 1$).
(a) Suppose that Bob observes two consecutive signed messages, say ($x_i$, sig($x_i, k_i$)) and ($x_i+1$, sig($x_i+1, k_i+1$)). Describe how Bob can easily compute Alice's secret key, $a$, given this information, without solving an instance of the Discrete Logarithm problem. (Note that the value of $i$ does not have to be known for the attack to succeed.)

In class we demonstrated how to solve for $k$ if $k$ was reused between messages, so I figured we could do something similar to that. However, this didn't work since a big part of that solution was to solve for $r \equiv \alpha^k \mod p$ since the $r$s were the same. This time, however, they aren't.
$$r_i \equiv \alpha^{k_i} \mod p $$
$$r_{i+1} \equiv \alpha^{k_i + 2 \mod (p-1)} \mod p$$
So we're kind of at a loss here on where to go. Basically all I've come up with so far is "solve for $k$ first since we can define any $k$ in terms of another". So if anybody could lend a hand, that'd be greatly appreciated.

Well, we can approach it this way: if we denote the hashes of the two consecutive messages $H_1, H_2$, the signer used the internal values $k, k+2$, resulting in signatures $(r_1, s_1), (r_2, s_2)$, then we have (and all this arithmetic is modulo $p-1$):

$s_1 = (H_1 - x r_1) k^{-1}$

$s_2 = (H_2 - x r_2) (k+2)^{-1}$

where $x$ is the secret key we're interested in.  Rearranging, we get:

$s_1k = H_1 - x r_1$

$s_2(k+2) = H_2 - x r_2$

where we know the values of $r_1, s_1, r_2, s_2, H_1, H_2$; there's only two unknowns ($k, x$) which both appear as linear terms; we just solve the two simultaneous linear equations, which immediately gives us $x$.

It is easy to see that this observation can be extended to the case where the difference between two different internal $k$ values is something the attacker can guess.


Is a stream cipher similar to One-Time Pad using hash secure? I've read some Q&A about combining OTP with hash on this site, but I still wonder why some answers said that using hash for OTP key is not strong enough to resist brute force attack?

Assuming that the key is never reused and the adversary has unlimited computational resources so that the adversary can try all keys easily. Is the adversary able to find out which one is correct from all of the plaintexts after getting all possible plaintexts?

For example, if the adversary gets "Give me 100 dollars.", then he might get "Give me 200 dollars." too. If he can't filter out the wrong plaintext, how does he know the correct key and crack it?

I know the amount of possible plaintext depends on the amount of possible hash value, but if the adversary gets at least two possible plaintexts and has no any method to distinguish the right one from them, will this cipher encrypted by hash key have any chance to be cracked by brute force attack? If no, then are there any flaws in this encryption technique? (Ignore the message authentication problem)

If you are imagining something like 256+ bits of key -> SHA-256 -> one block keystream that you XOR with the plaintext, that is indeed almost the same as one-time pad. However, there is no advantage to doing that, considering you might as well have used the original key directly as a one-time pad.

If, instead you use a password-based hash, a dictionary attack or similar can be successful, and unless the password has more entropy than the output size of the hash, the attacker can at least rule out some possible messages, meaning it lacks perfect secrecy.

Even in the first case, where your key is high entropy, the fact that you run it through a hash function will affect the possible outputs and their frequencies, so a computationally unbounded adversary would gain some information about the contents of the message – some options may be impossible and some may be more probable.

In practice, using a (password-)hash to produce a keystream amounts to a stream cipher, and assuming your key/password has enough entropy and you do not reuse the same key/password for other messages, it is very likely secure. From a confidentiality point of view, that is: stream ciphers (and OTP) are malleable so you want authentication if the integrity of the message matters.

(Insert obligatory recommendation to use standard ciphers in practice.)


Bijection Between Real View and Simulated View I have some basic idea about cryptography and trying to understand zero knowledge proof, so pardon my ignorance and stupidity. I am trying to formalize sigma protocol in Coq theorem prover, and so far everything is correct except the special  honest verifier zero knowledge proof. The definition of special honest verifier zero knowledge proof [1]:

  There exists a p.p.t. algorithm S (simulator) which given any v ∈ L_{R} and
  any challenge c ∈ C produces conversations (a, c, r) with the same probability
  distribution as conversations between honest P and V on common input v and
  challenge c, where P uses any witness w satisfying (v, w) ∈ R.

So, the definition roughly translates to:

Pr[Real_view (v, w, c)] = Pr[Simulator_view (v, c)]

But, say for the moment, if I do no want to do probabilistic reasoning inside Coq, and I write that there is a bijection between the real view and simulator view with making all the randomness explicitly:

f : Real_view (v (* statement *), w (* witness *),
               c (* challenge from verifier *),
               r (* random coin toss of prover *)) <->
    Simulator_view (v (* statement *),
                    c (* challenge of verifier *)
                    z (* response chose randomly *)

So my question is: is producing f sufficient for showing special honest verifier zero knowledge proof? The axiom would roughly look like this.

SHVZK : forall (v ∈ Statement) (w ∈ witness) (H : (v, w) ∈ R)
               (c ∈ Challenge) (r ∈ Randomness) (z ∈ Response),
  exists f : Real_view (v, w, c, r) <-> Simulator_view (v, c, z),
             verify (Real_view (v, w, c, r)) = true /\
             verify (Simulator_view (v, c, z)) = true.

[1] https://www.win.tue.nl/~berry/2WC13/LectureNotes.pdf

I came up with something which, I believe, avoids the probabilistic reasoning for Sigma protocol, but I will be very happy for your constructive criticism.  Before I proceed, please have a look at my modelling of sigma protocol in Coq, specifically the axiom Special_Honest_Verifier_ZKP.

Module Type SigmaProtocol.
  Parameter (Statement : Type) (* Statement x *)
            (Witness : Type) (* witness w *)
            (Rel : Statement -> Witness -> bool) (* decidable relation *)
            (RandCoin : Type) (* random coin *)
            (Commitment : Type) (* commitments *)
            (Challenge : Type) (* challenges *)
            (Response : Type) (* response *).

  Parameter  (initial : RandCoin -> Commitment)
             (challenge : Challenge)
             (response : Statement -> Witness ->
                         RandCoin -> Challenge ->
                         Response)
             (verify : Statement * Commitment * Challenge * Response -> bool).

  Parameter (simulator : Statement -> Challenge -> Response ->
                         Statement * Commitment * Challenge * Response)
            (extractor : Challenge -> Response -> Challenge -> Response -> Witness).

  Axiom Completness : forall (s : Statement) (w : Witness) (r : RandCoin)
                        (e : Challenge),
      Rel s w = true -> verify (s, initial r, e, response s w r e) = true.

  Axiom Special_Soundness : forall s c e1 e2 r1 r2,
      e1 <> e2 ->
      verify (s, c, e1, r1) = true ->
      verify (s, c, e2, r2) = true ->
      Rel s (extractor e1 r1 e2 r2) = true.

  (* Probablistic Reasoning could have made it nicer *)
  Axiom Special_Honest_Verifier_ZKP  : forall (s : Statement) (w : Witness) (e : Challenge),
    forall (r : RandCoin), verify (s, initial r, e, response s w r e) = true <->
                      forall (z : Response), verify (simulator s e z) = true.

End SigmaProtocol.

Let's take a brief detour, assume that we were doing a probabilistic reasoning, then our real view and simulated would have looked like:

Real_view (s : Statement) (w : Witness) (e : Challenge) := do
  r <- G (* generate a random value from some group G *)
  let a := g^{r} (* commitment *)
  let z := r + e * w  (* compute the response *)
  return (s, a, e, z)

Simulator_view (s : Statement) (e : Challenge) := do
 z <- G (* random element from some group G *)
 return (s, g^z s^(-e), e, z)$

 Special_Honest_Verifier_ZKP  (s : Statement) (w : Witness)
  (e : Challenge) (H : Rel s w = true) :=
  Pr [Real_view  s w e] =
  Pr [Simulator_view s e]

Based on two probabilistic view, we could have shown that two are equal. Intuitively,
in $Real\_view$, statement $s$, witness $w$, and the challenge $e$ is fixed, so the only thing that vary is the
random coin drawn uniformly from some group $G$. The probability of drawing an element uniformly
from a given set $S$ is 1/|S|, so the value of $\Pr [\text{Real_view  s w e}] = 1/|G|$.
By the same token of reasoning, $\Pr [\text{Simulator_view s e}] = 1/|G|$ which concludes that
both probabilities are equal. However, the only problem is that we are not doing probabilistic reasoning,
but not all all hope is lost.
One key observation to escape this probabilistic reasoning is
that we can make the randomness $r$ and response $z$ as
explicit parameter. Consequently, our probabilistic program would turn into
a deterministic Coq program.

Real_view (s : Statement) (w : Witness) (e : Challenge)
  (r : RandCoin):=
  let a := g^{r} in (* commitment *)
  let z := r + e * w in  (* compute the response *)
  (s, a, e, z)

Simulator_view (s : Statement) (e : Challenge)
 (z : Response) :=
 (s, g^z s^(-e), e, z)

Now that our views are deterministic, we need to find a way to model
the probability distribution of the two views. We solve this problem
by showing a bi-implication  between  the real view and simulated view.
We show that real view and simulator's view align with each other.
In terms of Coq, it is expressed as:

 (* Probablistic Reasoning could have made it nicer *)
 Special_Honest_Verifier_ZKP  (s : Statement) (w : Witness)
  (e : Challenge) (Rel : Statement -> Witness -> bool)
  (H : Rel s w = true) :
  forall (r : RandCoin), verify (Real_view s w e r) = true <->
  forall (z : Response), verify (Simulator_view s e z) = true;

The axiom $Special\_Honest\_Verifier\_ZKP$ says that for any  given
fixed statement $s$, witness $w$, challenge $e$, relation $Rel$, and assumption that $Rel$ $s$ $w$ holds,
then for every random coin $r$  and a accepting real transcript, simulator can construct
an accepting transcript from all random response drawn from response space.


Single public key for NaCL signing and encryption? Bob wants to use NaCL (specifically the Python NaCL library) to both a) sign some publically available plaintext for anybody to authenticate as being written by Bob and b) encrypt some other secret plaintext for Alice.

NaCL encourages signing and encryption with different keypairs. Bob would like any recipient to be able to prove that the same person controls the NaCL signing key and the NaCL encryption key used in the two above cases. What is a safe way to do this?

Is there some safe way to sign the private key used for encryption with the signing keys?
If Bob computes a derived keys from some master key can he give out the master public key, and then have people verify that the signing public key and the encryption public key are derived from it?
If (2) what is a safe way to derive keys from some master key?
If (2) how can somebody verify the signing and encryption public keys are derived from the master public key?

Ideally Bob would be able to give out a single NaCL public key and then anybody receiving a signed or encrypted plaintext would be able to verify that the corresponding private key was used.

I've read the relevant documentation on djb's site and this post and the Python NaCL library documentation. In the latter all of the examples use completely unrelated keys for the two different functions.

Is there some safe way to sign the private key used for encryption
  with the signing keys?

What you're talking about is also commonly referred to as "keychain" or "keyrings", a concept popularized by programs like GPG, which do exactly this:
They generate one master signature key, which you securely distribute and which then "certifies" the other public keys to belong to you. This way you can keep your master key offline and only use to sign your everyday encryption public key and your everday signature public key.


Are LFSRs enough for this? Consider the following experiment:

  Let there be a machine which runs (ie. continually clocks) an LFSR of size (ie. number of bits) $b$, having a button that, when pressed, extracts the next $t$ bits from the LFSR, prints them onto a paper ticket, deposits the ticket into a sealed, opaque urn, and complements every bit in the LFSR (ignore, for the sake of argument, the case where the LFSR gets reset to all zeroes); the machine continues to run normally afterwards.

  Now place this machine in a room, completely isolated from the outside, and have a number (say $n$) of players form a line and, one by one, step into the room and press the button. After all $n$ of them are finished, retrieve the sealed urn.

  The LFSR's feedback polynomial, initial state and clocking frequency are public parameters, as are the numbers $b$ and $t$.

Now there's an attacker whose purpose is to match at least one ticket in the urn to one of the players. The attacker has access to all the public parameters, knows the order in which the players are lined up, can measure the time each one enters the room (but cannot, obviously, know exactly when a player pushes a button, since that happens inside the isolated room), and may collude with a fraction q of the players in order to achieve its goal.

The questions, then, are:

Which parameters (ie. $b$, $t$, $q$, clocking frequency is a little trickier) can ensure the attacker has no more chance of succeeding than he would by guessing?
Would replacing the LFSR by an ASG be any better? any worse?

A note on clocking frequency: for technical reasons, the clocking frequency is forced to be relatively low, say no more than 2kHz (ie. one clock pulse every one two-thousandth of a second).

A note on collusion and what the players can and can't do: the players can be assumed to have at their disposal a timing device of their choosing, with the accuracy they see fit (if this proves to be too powerful an advantage, an analysis with restrictions is greatly appreciated!); a player does not see the number they get (they actually don't get it per se, since the number goes into the urn).

The rationale behind all this is that we're trying to generate true-ish random numbers from an LFSR: the random variable to harness is the times at which the button is pressed, the LFSR is there just to provide for confusion of the generated values; if one where to use the number of seconds since the experiment's beginning, the attacker could easily match the tickets to the players; if one where to use the LFSR without complementing, the attacker could compare them according to the order in which the LFSR (all of whose parameters are public) generates them; I believe (with absolutely no basis!) that complementing after each extraction could do the trick.

English is not my mother language, I'm sorry if I haven't made myself clear enough, please do ask for clarifications if needed.

This is not homework, tough it may look like it :)

EDIT: It has been brought up more than once in the answers that knowing so much and being able to do so much, gives the attacker too much power, so i decided to make the LFSR's initial state secret. Now the last paragraph in the explanation above should read:

  The LFSR's feedback polynomial and clocking frequency are public parameters, as are the numbers $b$ and $t$. The LFSR's initial state is secret, and unknown to the attacker.

Here is an attack that I think will, with excellent odds, allow certain determination of which value is on the ticket of colluding players; and consequently give an advantage on guessing the tickets of these colluding players, and a (typically lesser) advantage on guessing the tickets of honest players. I'm assuming:

The adversary knows the value on every ticket (as confirmed by a comment), with no ambiguity about that under orientation of the ticket.
It is not known the initial state of the LFSR (as now explicit).
All players press their button haphazardly, which when the exact instant is unknown sorts of partially reseed the LFSR.
The adversary knows exactly when $m$ consecutive players pressed the button (because these $m$ players collude with the adversary), thus exactly how many steps of the LFSR there has been between theses presses; this allows the adversary to express the state of the LFSR at the key-presses of the colluding players as a linear function of the (assumed unknown) state when the first colluding player pressed the button.
$n$ is low enough that the adversary can perform some processing for each of the (at most) $n!/(n-m)!$ distinct orders of values for colluding players ($n=15$, $m=10$ means that about $11\cdot10^9$ orders are to be considered, and would be very feasible).
$t$ is large enough that it is likely that only a single of these ticket order matches the linear functions; there are $b$ unknown bits, $(n-1)\cdot t$ known bits, thus by an entropy argument (based on the vague and unproven hypothesis that the haphazard behavior of players makes the system of linear equations unremarkable), there should typically be a single possible order of values when
$$m\cdot t\gg b+\log_2(n!/(n-m)!)$$

It is then easy to check a candidate order, and deduce the $b$ bits of initial state. Just plug $m={2\over3}n$ for $2\over3$ of the players colluding.

Also, if the uncertainty on when the honest players pressed (assumed to have uniform distribution in an interval with $u$ steps, with that the product of time per frequency) is such that $u\ll2^t/(n-m)$, we can often guess the (value on the) tickets of other players immediately before and after the $m$ colluding players; even all of them if $u\ll2^t/(n-m)!$ or something on that tune.

Further (as the saying attributed to the NSA goes, and illustrated by a sizable improvement in version 5 of this answer): attacks only get better; they never get worse. In particular, I have not fully exploited the information that can be gained from the known value on the tickets of the honest players, which is significant if $u\ll2^t$; or speedups possible for many parameters to dramatically cut down on $n!/(n-m)!$ explorations; or what improvements could be achieved when colluding players press at a chosen instant, rather than at a random but known instant.

The above does not give a condition that would insure an adversary can't succeed. Here are some thoughts towards that. I'll consider that the LFSR is maximum-length (has period $2^b-1$, or equivalently uses a primitive polynomial and is never all-zero); and that a key-press occurring when the LFSR is all-one prints an all-one ticket, but leaves the LFSR as if no key-press had occurred.

Assume a player stays exactly $u=2^b-1$ clock periods in the room, and consider the 4 variables

LFSR state $I$ on entrance
LFSR state $P$ as sampled by key-press (of which $t$ out of $b$ bits are printed)
LFSR state $O$ on exit
number of clock periods $w$ between entrance and key-press, with $0\le w<2^w$

It holds that $P=M^w\cdot I$ and $\hat P=M^w\cdot O$, where $\hat P$ is the bitwise complement $\bar P$ of $P$ except that all-ones is unchanged; and $M$ is the $b\times b$ sparse matrix corresponding to advancing the LFSR by one step.
When any of $I$ $P$ $O$ $w$ is fixed, these relations defines a one-one mapping from any of the other three variables to either of the two last variables. Note: when $w$ is unknown, finding it (or $P$ if also unknown) seems to be a discrete logarithm problem; I consider an adversary able to solve that.

It follows that when an honest player stays in the room for much longer than $2^b-1$ clock periods, to an adversary knowing only one of the LFSR states on entry or exit,

the other of these states is indistinguishable from a uniformly random non-zero variable,
the value printed on the ticket has the same distribution as for a random sampling (all-zero with odds $2^{b-t}-1\over2^b-1$, any of the other $2^t-1$ values with higher odds $2^{b-t}\over2^b-1$).

The above two unknowns are however strongly related.

If we see the LFSR as an entropy pool,

an honest player staying in the room for much longer than $2^b-1$ clock periods refills that entropy pool to its full capacity $c=\log_2(2^b-1)$ bit
however knowledge of the value of a ticket reveals at most $r=\log_2(2^b-1)-\log_2(2^{b-t}-1)$ bit of information when $t<b$ (this occurs when the value printed is all-zero), or $r=\log_2(2^b-1)$ bit when $t=b$ (the value printed can't be all-zero).

From this I tentatively conjecture that with all but very small $b$, the adversary has negligible advantage if at least $h$ honest players, who each stay in the room for much longer than $2^b-1$ periods, stand between any two players colluding with the adversary, and
$$h\cdot c\ge (h+1)\cdot r \text{ , that is } t<b \text{ and } (h+1)\cdot\log_2(2^{b-t}-1)\ge\log_2(2^b-1)$$

The condition is constructed as: in a sequence of $h+1$ players, at least as much entropy is injected as revealing all the ticket values consumes. My intuition is that this condition is enough that the adversary can't learn more about the state of the LFSR when a player presses a key than knowledge of the corresponding ticket value would reveal, and/thus is unable to tell if an hypothesis on which ticket belongs to who is more or less likely.


How is a fake private key used in CloudHSM? I've noticed that AWS CloudHSM uses an openssl command to generate a fake private key for web servers that offloads cryptographic functions to a CloudHSM. How does this key work? And what purpose does it serve?

As an example from the AWS CloudHSM docs:

Generate a fake private key using:

openssl genrsa -engine cloudhsm -out <web_server_fake_PEM.key> 2048

While we ( / I) don't know exactly what the fake private key is, there are two sensible (standard?) guesses we can make here. For a confirmation we probably would need access to the CloudHSM OpenSSL engine implementation.

So first, why do we need a fake private key at all? Well, we need a way to tell the system (a.k.a. AWS' HSMs) about which key we are talking and OpenSSL doesn't support identifiers or handles natively with the CLI interface, so we need a work-around and these fake private keys are exactly that. They are means to designate specific keys within the HSMs.

So what do these files actually contain? There are two sensible options:

They contain a handle, that is an identifier. This means that they essentially just contain a string which says "if you see me, use key X on HSM-cluster Y", but they don't actually contain the private key.
They contain the encrypted private key. This means that the HSMs would (symmetrically?) encrypt the private key and put it in this file, so they don't have to keep it in their own storage. This may be accompanied with an identifier for the symmetric key, similar to (1). Also this would mean that deleting the key is as simple as deleting all copies of the fake private key and no interaction with the HSMs for key deletion is required.


Can quantum computers put computer security in jeopardy? There are many articles about quantum computers describing how powerful they are in computing and that they can solve very complicated equations in a short time.
One of the biggest security measures that provide safety for computer security is that sometimes it takes years to break a piece of encrypted data.  Will this safety remain after a quantum computing revolution?
The question is:

Can they do such complicated computing?
Is it possible quantum computers put computer security in jeopardy?

can they (quantum computers) do such complicated computing (cryptanalysis)?

Not currently. Current quantum computers (including the adiabatic variants specialized in quantum annealing) do not perform anything useful for cryptanalysis. In the future: we don't know.

  Is it possible quantum computers put the computer security in jeopardy?

It is reasonable to worry for the long term. There's therefore a lot of activity to be prepared for quantum computers useful for cryptanalysis. The quasi consensus is that 256-bit symmetric crypto (AES-256, SHA-512, SHA3-512 and the like) will remain safe in the foreseeable future. Most currently used asymmetric/public-key crypto (RSA and others based on factorization; DSA, DH, Schnorr signature, ECDSA, EdDSA, ECDH and others based on discrete logarithm) may not, especially for the smallest key sizes currently considered safe. But practical quantum-safe asymmetric cryptography seems feasible, and is in the works. There's preliminary standardization effort at NIST.

This related question asks how to predict when and if quantum cryptopocalypse is coming.


Workaround to implementing Forward Secrecy In the case where I am self-signing my digital certificates, if I just change my certificate (generate a new one) every week or month, will this have (sort of similar to) the same effect as implementing Forward Secrecy, since I should have a new private key every time?

Please correct me if I'm mistaken.

Thanks.

This only works if you are absolutely certain that you're properly erasing the old private keys. This is harder than it seems; you have to be sure that you're leaving no traces anywhere, including on backup media or scattered around your hard drive. With proper forward secrecy methods, the keys never leave RAM, which makes erasing them securely much, much easier. Furthermore, this only happens after a week or a month or whatever; if you erase the private certificate monthly, then an attacker who acquires the certificate at the very end of the month (before you erase it) can decrypt the whole months' worth of messages.

There is very little reason to do this. ECDHE is not slow; while it's a bit slower and more computationally intensive than RSA, that difference shrinks rapidly as security increases (at 2048-bit RSA keys, there's a very small difference). Furthermore, ECDHE does not have anywhere near as many implementation pitfalls as securely erasing a private certificate weekly, and doesn't leave the week- or month-long interval for private key theft. Just use ECDHE.


Definition of randomly generate in the parallelepiped I am reading the [CLT13] paper regarding multilinear maps over the integers and I have some troubles in understanding what the following random generation means:

The vectors of the matrix $r_i \in \mathbb{Z}^n$ are randomly and independently chosen from the half-open parallelepiped spanned by some vectors $\pi_1,...,\pi_n \in \mathbb{Z}^n$.

What I've understood: Those $r_i$ can be written as $r_i = a_1\pi_1+...+a_n\pi_n$ where each $a_i$ is random in $\mathbb{Z}$. Is it correct?
You might want to search for the word span to see exactly what the authors meant in the paper.

As @LeoDucas already commented, the answer is contained in Appendix E (page 22) of the same paper: