Cryptanalysis of Linear Feedback Shift Registers It is well known that simple m-sequence linear feedback shift registers have a linear algebraic structure and therefore the generator seed can easily be deduced using the Berlekamp-Massey algorithm. Are there any other algorithms that can that can be used to "break" LFSR's and if so how does the algebra of said algorithm(s) compare to the Berlekamp-Massey algebra?

The Berlekamp-Massey algorithm is an iterative algorithm that solves the following problem.

  Given a sequence $s_0, s_1, s_2, \ldots$ of elements of a field, find the
  shortest linear feedback shift register (LFSR) that generates this sequence.

Here, LFSR is a linear array of $n$ elements with initial value
$$(s_0, \quad s_1,\quad  \ldots, \quad s_{n-2}, \quad s_{n-1})$$ and successive values
$$(s_0, \quad s_1, \quad \ldots, \quad s_{n-2}, \quad s_{n-1})\\
\downarrow\\
(s_1, \quad s_2, \quad \ldots, \quad s_{n-1}, \quad s_n)\\
\downarrow\\
(s_2, \quad s_3, \quad \ldots, \quad s_n, \quad \quad s_{n+1})\\
\downarrow\\
\cdots \quad \cdots$$
where the array contents shift leftwards at each step (clock cycle)
so that the field elements falling
off the left end (the LFSR output) are the given sequence, while
the field elements shown as entering the LFSR on the right*
 are being computed as a linear combination of the LFSR
contents at the previous step.  In particular, for $i \geq 0$,
the state transition can be expressed as
$$\biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+n-2}, \quad s_{i+n-1}\biggr)\\
\downarrow\\
\biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+n-1}, \quad \sum_{j=0}^{n-1}c_{n-j} s_{i+j}\biggr),$$
that is, the linear combination
$c_ns_i + c_{n-1}s_{i+1} + \cdots + c_1s_{i+n-1}$ of previous
LFSR contents is being fed back into the right end of the LFSR
as $s_{n+i}$
(and hence the name linear feedback shift register).

As mentioned previously, the Berlekamp-Massey algorithm
finds the shortest LFSR that generates the given
sequence meaning it figures out the values of the
$c_i$ elements.  The iterative process consists of finding
the shortest LFSR that generates the first $t$ elements
$s_0, s_1, \ldots s_{t-1}$ and checking if the LFSR
finds $s_t$ correctly. If so, $s_{t+1}$ is checked,
while if not, the $c_i$'s are updated so that the
revised LFSR generates $s_t$. If the sequence was
indeed created by a
$n$-stage LFSR as described above, the Berlekamp-Massey
algorithm finds all $n$ coefficients $c_i$ after
examining $s_0, s_1, \ldots, s_{2n-1}$.  From this
point onwards, the Berlekamp-Massey algorithm can
continue checking the rest of the sequence (if so
desired) but does not need to update the $c_i$'s
because each check of the next symbol simply reports
back that everything is OK.

Let $S(z) = \sum_i s_i z^i$ and $C(z) = -1 + \sum_{i=1}^n c_iz^i$
denote generating functions of the given sequence and
LFSR feedback coefficients. Then, the equation
$$s_{i+n} = c_ns_i + c_{n-1}s_{i+1} + \cdots + c_1s_{i+n-1}$$
is equivalent to saying that the coefficients of $z^{i+n}$
in the product $C(z)S(z)$ is $0$ for all $i \geq 0$. But
the coefficients of $z^0, z^1, \ldots, z^{n-1}$ are not zero.
When only the first $2n$ symbols $s_0, s_1, s_{2n-1}$ have been
looked at, what the Berlekamp-Massey algorithm has solved (thus
far) is the congruence
$$C(z)S(z) \equiv D(z) \bmod z^{2n}$$
where $\deg D(z) < n$.  Indeed, Berlekamp's formulation
of what is now called the Berlekamp-Massey algorithm
envisioned solving congruences
$$C^{(m)}(z)S(z) \equiv D^{(m)}(z) \bmod z^{m}$$
(where $\deg D^{(m)} \leq m/2$) iteratively for
$m=1, 2, \ldots, $ until arriving at the desired
solution at $m = 2n$.

Finally and at long last, the extended Euclidean algorithm
for polynomial greatest common divisors can be used to
solve the congruence
$$C(z)S(z) \equiv D(z) \bmod z^{2n}.$$
Define $\hat{S}(z) = s_0 + s_1z + \cdots +s_{2n-1}z^{2n-1}$
and start the extended Euclidean algorithm to find the
gcd of $z^{2n}$ and $\hat{S}(z)$.  The extended Euclidean
algorithm begins with $r_0(z) = z^{2n}, r_1(z) = \hat{S}(z)$ and
finds the sequence of remainder polynomials
$r_2(z), r_3(z), \ldots$ etc where $r_i(z)$ is the remainder when
$r_{i-2}(z)$ is divided by $r_{i-1}(z)$. It also
expresses each $r_i(z)$ as
$$r_i(z) = \alpha_i(z)r_0(z) + \beta_i(z)r_1(z)$$
where polynomials $\alpha_i(z)$ and $\beta_i(z)$
are computed iteratively.  Consider the smallest
value of $i$ for which $\deg r_i(z) < n$.  We have
$$r_i(z) = \alpha_i(z)z^{2n} + \beta_i(z)\hat{S}(z)$$
and so
$$\beta_i(z)\hat{S}(z) \equiv r_i(z) \bmod z^{2n}.$$

Notice that the Euclidean algorithm processes the
the $s_i$ in descending order of subscripts whereas
the Berlekamp-Massey algorithm processes the $s_i$ in
ascending order of subscripts. The Euclidean algorithm
can be reformulated to process the $s_i$ in increasing
order of subscripts in which case it is virtually
indistinguishable from the Berlekamp-Massey algorithm.
Either way, the algorithms have very similar
computational
complexity.

For details on the extended Euclidean algorithm and its
connections to the Berlekamp-Massey algorithm, see
R. E. Blahut's Algebraic Codes for Data Transmission,
Cambridge Press 2003.


Using encryption schemes for identification I've been researching how to implement a post-quantum SSL-like connection authentication, especially correct identification&authentization of the server/client. Because good post-quantum digital signature algorithms are generally unavailable (McEliece-based CFS is slow, NTRUsign is impractical, MQ schemes are generally broken and hash-based schemes have limited number of signatures which doesn't go very well with automated on-demand signing), I've been trying to find a good scheme that would not produce signatures, but would just verify whether there really is the holder of the given private key on the other side of connection.

There are several approaches to such identification (Stern's scheme etc.), but because we already have good post-quantum encryption schemes, I've been wondering whether one could use them like in following scheme:

A has some kind of data connection to B. A wants to know if B is really the guy identified by public key PubB, therefore A wants to determine whether B can do operations that depend on key PrivB. (PubB and PrivB is the keypair of some asymmetric encryption scheme)
A generates a random string S, encrypts it with PubB, and sends it to B.
B decrypts the message to S', and sends it back to A
A compares received S' with S, if they are equal, B was able to use PrivB and therefore it is (cryptographically) indeed B.

Questions:

Is there any good reason why this would not work? (consider the connection somehow secured against MITM-like disruption, as this is not the purpose of the question and the solution is relatively simple)
Is there any problem with sending decrypted plaintext S' back? Especially for fighting the fact that in this case B would simply act as a decryption oracle for PrivB for anyone connected, would it help if B was sending back only H(S'), where H is some cryptographic one-way (possibly hash) function?

Thanks for any thoughts&suggestions,

-exa

Well, that would work, but identification is not enough for SSL.

You would need to make the PKE scheme one-way against CCA1 attacks. $\:$ (On the

other hand, it wouldn't need any semantic security.) $\:$ Sending back H(S') would change

the required security notion to one that's even farther from what's been studied.

You could use a tag-based PKE scheme that is one-way against tag respecting CCA2 adversaries to allow the private key holder to also authenticate data to the verifier, which would be enough for SSL. $\:$ (Although it would take 2 messages from the server and 1 from the client, rather than just 1 each.) $\:$ Also, hash-based signature schemes using fractal trees don't necessarily have a limited number of signatures.


What is the structure of a Server Key Exchange Message structure when using a psk identity hint? I need to know the structure of a server key exchange message when using a psk identity hint.  I know the general structure but I can't find an example of where the identity hint fits in.  Thanks.

RFC 4279, section 5.2, says this about identity hints:

In the absence of an application profile specification specifying
otherwise, servers SHOULD NOT provide an identity hint and clients
MUST ignore the identity hint field.  Applications that do use this
field MUST specify its contents, how the value is chosen by the TLS
server, and what the TLS client is expected to do with the value.

So what this means is that it is up to you, the application designer, to define the hint structure. From the TLS point of view, the hint is an opaque sequence of bytes (no longer than 65535 bytes, but otherwise arbitrary).

In this answer, it is claimed that the "hint" was used directly in the key derivation system in the case of a protocol called "NETCONF", but this was dropped during the definition of the RFC (i.e. draft 4 has it, not draft 5 and subsequent). Even if the PSK support was not ultimately used in NETCONF, this shows how such a definition  is to be done: each protocol that leverages TLS-PSK is supposed to specify the hint format and processing.


Why does the Fiat-Shamir heuristic not work without a random oracle? Consider the following three stage interactive zero knowledge proof in round $i$

The prover sends some commitment $a_i$ to the verifier.
The verifier picks a challenge $c_i\in \{0 ,1\}$
Depending on the challenge, the prover responds with $r_i(c_i)$ that convinces the verifier of his knowledge.

The Fiat-Shamir heuristic converts this into a non-interactive game by using a random oracle to generate a string $c$ whose bits are then used to decide each $c_i$. However, under the assumption that such oracles don't exist, we instead use a one way function on all the commitments to generate $c = f(a_1, a_2,\dotsc,a_n)$. This is known to be insecure. I've tried to read the paper in the Wikipedia page but still do not quite see the issue.

I assume the weakness is that the prover can somehow choose $a_i$ in a manipulative way so that the challenges $c_i$ are controlled by the prover but the argument for how the prover can do this is not very clear to me.

Why exactly is the Fiat-Shamir heuristic insecure in the absence of a random oracle or some other trusted source of randomness?

Background: The Fiat–Shamir heuristic converts a certain class of interactive zero-knowledge proof systems—$\Sigma$-protocols, where prover proposes random commitment, verifier responds with random challenge, and prover answers with proof—into signature schemes using a random oracle to determine the challenge from the commitment.

Using a random oracle means that everyone has access to the same independent random challenge as a function of the prover's commitment.
The signer can pretend to have been given an independent random challenge in a simulated interactive zero-knowledge proof.
Everyone else can reproduce the interaction given the message and commitment with the same challenge, in order to verify the resulting transcript as a signature.

The ROM theorems of Pointcheval & Stern exploit $\Sigma$-protocols in which the proofs for two different challenges for the same commitment leak the secret key with high probability, and use that to show that a ROM forger can be used to leak the secret key.  The basic idea is the forking lemma:

If you have a forger as a Turing machine, you can pause it just before it queries the random oracle, duplicate the state of the machine (‘fork’ it, in the parlance of our times), and then run it forward twice with two different random oracles.
If the forger makes $q$ queries to the oracle, and you pick one of the $q$ queries uniformly at random to fork the machine, there's about a $1/q$ chance that you picked the query to the random oracle to choose the challenge—and hence about a $1/q$ chance that you got two different signatures with the same commitments but different challenges, leaking the key.

(The forger could also return a forgery without using the random oracle to determine the challenge, of course—but there is a negligible probability they will guess the challenge the random oracle would have returned, and if their guess is wrong, whatever they return won't agree with the challenge that all the verifiers will be using.)

The random oracle model is essentially a model for how forgers are designed.  That is, a ROM theorem is a statement of the form: If a forger is designed generically in terms of a hash function, then there is a way to break some underlying problem, using that forger as a subroutine.  The proof shows how to use that forger as a subroutine, by passing it specially crafted random oracles that have the correct distribution on outputs but also do nefarious things behind the scenes to exfiltrate the goods from the forger.

What Goldwasser & Kalai showed about Fiat–Shamir—much like Canetti, Goldreich, & Halevi showed about signatures in general—is that there exists a $\Sigma$-protocol such that there is a forger for the signature scheme obtained by using Fiat–Shamir heuristic with any particular hash function even if it is secure in the random oracle model, using a series of complexity-theoretic tricks to make $\Sigma$-protocols that throw tantrums when the challenges have certain forms, which a forger can exploit to forge signatures in a Fiat–Shamir scheme that uses any particular hash function.  Of course, the forger, in this case, is not written generically in terms of a hash function; although there exists a forger for any hash function, each forger itself depends intimately on the details of the hash function.

The tricks are elaborate and I won't go into details here, but the point is not that (e.g.) the Schnorr signature scheme is insecure—rather, it's that the Fiat–Shamir heuristic does not always produce a secure signature scheme given a secure $\Sigma$-protocol even if the signature scheme would be secure in the random oracle model.  So you can't formally draw the implication that a ROM theorem of Schnorr signature security guarantees a Schnorr signature forger can be used to compute discrete logs—but it would be rather surprising if Schnorr's identification scheme interacted with (e.g.) SHAKE128 to break the security of the signature scheme derived by Fiat–Shamir.


How to find irreducible polynomial for Barreto-Naehrig curves? As described in this paper(section 3) to implement pairing on Barreto-Naehrig curves. The prime in their case is $p=82434016654300679721217353503190038836571781811386228921167322412819029493183$ and to implement the pairing it is important to find an irreducible polynomial of the form $ W^6-\xi$ in $\mathbb{F}_{P^{2}}$ where $\xi \in \mathbb{F}_{P^{2}}$. However, I can not understand how to find such $\xi$. I have written some scripts in Magma to find such $\xi$ but not successful.Also in that paper they have mentioned that there are some properties of the prime $p$ which is useful in finding such $\xi$ but I can't understand how to use them? Can someone please tell me how to find such irreducible polynomials?

I am using  Pari/GP as a calculator.   In order to keep the presentation small, I will not use the $p$ you mentioned, but a toy value $p=31$, which fulfils all requirements from the paper.

First lets define p:

p= 31

Then we have to define the finite field $GF(p^2)$ via the defining (irreducible) polynomial $y^2- \beta$, i.e. $y^2+2$:

GFp2 = Mod (y^2+2, p)

Now we define $\xi$:

xi = -1 - y

( Please note that  $\sqrt \beta = y$ by the defining polynomial of $GF(p^2)$ )

Now let Pari check that $x^6- \xi$ is irreducible in $GF(p^2)$:

lift(factorff (x^6-xi, p, GFp2))

Pari responds as

[Mod(1, 31)*x^6 + (Mod(1, 31)*y + Mod(1, 31)) 1]

This says that the polynomial is irreducible.

(The "lift" call is only used to make the output more readable )

As a final test, show that $x^6 - \xi^2$ factors:

lift(factorff (x^6-(xi*xi), p, GFp2))

Pari responds as:

[  Mod(1, 31)*x^3 + (Mod(1, 31)*y + Mod(1, 31)) 1]

[Mod(1, 31)*x^3 + (Mod(30, 31)*y + Mod(30, 31)) 1]

Mathematically, this means:
$$x^6- \xi^2 = (x^3+ \sqrt \beta+1)(x^3-\sqrt\beta-1)$$


Recommended way to Implement One Time Password? I need help with the process/commands needed to implement the below functionality:

I'm modeling an OTP System, in which the user would request an OTP and the app will send him one. Later the user will use the OTP to use some functionality or something, and the OTP needs to be validated.
Constraints:

The OTP cannot be stored in the Clear.
Need to use Thales payShield 9000, that I have available, sending HOST COMMANDS.

This is the process:

App A request an OTP using a User Account
App B Generates the OTP for that User Account and send it to App A
App B Can't store the OTP in clear, so it must use the HSM to, in some way, store the OTP that can be validated later
App A, later, sends the OTP to App B which validates it (using the HSM) and then procedes to send the approval to App A

My apologies if this doesn't make sense, and I don't have idea what I'm doing.

I do not fully understand the scheme you are describing, especially the interactions between your apps A and B. I'll try to describe a sensible HSM usage for a  OTP based authentication.

I think you have a little misconception about how a typical OTP is usually handled. There is no need to store an OTP ever, it is always calculated upon use. The typical scenario is, that the user (his OTP calculating app) and the server both store a shared secret. From that secret and some additional information (like a timestamp if you use TOTP, or a counter if you use HOTP) the one time password is calculated using the HMAC algorithm.

This HMAC calculation can be done in software (if you use a normal app on your phone, like FreeOTP) or in hardware (like a PKCS#11 token) on both sides. The server side in your case, could use your HSM which stores the user's secrets to do the HMAC calculation. For a real massive multi user setting, you will probably have to create the shared secrets on the HSM dynamically from a master secret to overcome storage restrictions.

The specific procedure how you calculate your 6 digit (or whichever length you need) OTP ist outlined in the RFCs for HOTP and TOTP.


What is the advantage of adversary if the random number repeats? In proof of CPA-security of encryption scheme $(r, F_k(r)\oplus m )$
where:

$F_k$ is a keyed function
$r\in_R\{0,1\}^n$ is a random number,
on page 85 of Introduction to modern cryptography we have

The value $r^*$ is used when answering at least one of A’s encryption oracle queries: In this case, A may easily determine whether $m_0$ or $m_1$
was encrypted. This is so because if the encryption oracle ever returns
a ciphertext $\langle r^*,s \rangle$, si in response to a request to encrypt the message $m$,
the adversary learns that $f(r^*) = s\oplus m.$

My question is how can the adversary use $f(r^*)$?
Haven't we assume that the adversary doesn't know about $f$?

What I understand is that if we have used the keyed function $F_k$, then since the adversary doesn't know $k$, the knowledge of $F_k(r^*)$ can't be used because s/he still needs lots of time, that is $2^{|k|}$, to check which function $F_k$ where used. So it seems to me using the encryption scheme is secure even we repeat the random number $r$.
It seems that I am missing something but I can't find it.

Thanks to @fgrieu I've got the point I've missed.
The point is the adversary doesn't want to find the keyed function, of course, s/he would be happy if knew it, but s/he wants information and wins some game.
So Let's think like an adversary and we have asked $z$ queries $m_1, \cdots, m_z$ and got $\langle r_1, F_k(r_1)\oplus m_1\rangle, \cdots , \langle r_z, F_k(r_z)\oplus m_z\rangle$. We can have the following information from the queries' answers.
$F_k(r_1) = F_k(r_1) \oplus m_1 \oplus m_1$
$\vdots$
$F_k(r_z) = F_k(r_z) \oplus m_z \oplus m_z$
Then we choose $m'$ and $m''$ and get one more ciphertext $F_k(r')\oplus m_b$. If random number r repeats, for example r'= r_i, then we can do the following computation
$F_k(r_i)\oplus m_i \oplus m_i \oplus F_k(r') \oplus m_b = m_b$
And we exactly know which message was encrypted just by checking whether $m_b = m'$ or $m_b=m''$.
Even the adversary still doesn't know the $F_k$ we used he win CPA-game.


Which one is faster GCM AES-128 or Curve25519? As I know the symmetric encryption algorithms are faster than asymmetric encryption algorithms. But when I test GCM AES-128 and Curve25519 encryption time, I find Curve25519 is faster than GCM AES-128.
Is that normal?
Is GCM AES-128 slow?

By the way, I use these python libraries for the comparison:

PyNaCl for Curve25519 (using the box)
Cryptography.io for AES-GCM

I performed the tests with Ubuntu 16.04 64-bit on an Intel Core i7-2640M and ran the tests multiple times with differing input lengths.

The speeds for curve25519 are (1 kB):
Encryption 6.29425048828e-05 sec
Decryption 2.31266021729e-05 sec

The speeds for GCM are (1 kB):
Encryption 0.000115156173706 sec
Decryption 0.000576972961426 sec

You are not just using Curve25519. You are using a Python wrapper to NaCl, which is a high level crypto library that uses Curve25519 for Diffie-Hellman computation to derive a secret value. This secret is then used to encrypt with a particular algorithm, defaulting to Salsa20/Poly1305. So this library performs hybrid cryptography, where the data itself is encrypted with a fast, authenticated stream cipher. Although functionally the API is high level, execution certainly isn't: it's a highly focused, minimal implementation that is focused on both speed and security.

The cryptography library on the other part uses OpenSSL to speed up AES-GCM implementations. If a high enough OpenSSL library is used then AES-NI as well as CMUL for the GMAC operations should be available on high end CPU's that support it. However, it is completely possible to use an older library or one that isn't compiled for AES-NI. OpenSSL is an old generic library that may also have some more overhead; it isn't targeted forspeed in the same way that NaCL is.

If you have larger messages then the speed difference is simply due to speed differences in implementation of Salsa20/Poly1305 and AES in GCM mode. Salsa20 is a fast stream cipher, while GCM mode can generally be accelerated by hardware.

Beware that testing for speed is particularly tricky, especially on higher level languages. Differences in startup time of the compiler parser may already influence the results. You need a loop for the startup time and a loop for the testing. Both loops should contain the algorithm.

Also note that the random number generation may be pretty different on each platform.


How does hash speed vary based on string length? Surprisingly I have not been able to find an answer to this question on Google.

If I have a function that is based on any of the popular hashing algorithms used for password generation, by what percentage/magnitude does the speed change when the string length increases? Assuming the salt is retrieved from the function.

Function GetHash("CAT")

Function GetHash("I like cats, cats are great, I am a longer string")

I am looking only for the most approximate of answers, for example the difference might be tiny (<1% increase in time for a longer string), or it might be twice as slow (100% increase), or it might be more.

Contrary to the other answer, I'll be assuming the hash function is of the password-oriented kind; and my answer will be: input size has almost no influence on speed in good practice, even for much longer input than in the question.

Password-oriented (or entropy-stretching, key-stretching) hash functions are, for example, suitable to transform a (password, salt) pair into a hash, with (salt, hash) then stored in a database, allowing later checking a (password, salt) pair by recomputing hash and comparing it against the one found in the database along salt, without allowing to directly extract password from a (salt, hash) pair.

Such hashes actually have three inputs: password, salt, and a workfactor which controls the effort required to compute the hash output. Said effort is parameterized to make testing a list of (say) the 10 million most common choices of password somewhat costly. For example, with a workfactor such that computing one hash requires 0.1s on the CPU normally used, the 10 million passwords are tested in 12 days with that CPU, hours with a server having many CPUs, perhaps a fraction of hour for a well-equipped adversary using ASICs or FPGAs (example publicly for sale). Choice of workfactor is a compromise between effort for legitimate use (translating into delay and power spent at each password use, capital investment for more powerful hardware); and security: the lower the effort to compute a hash, the cheaper it will be to find a common password from a leaked (salt, hash) pair.

An example of password-oriented hash is PBKDF2 with PRF an HMAC with (e.g.) SHA-256 as the hash, as standardized by NIST Special Publication 800-132. A safer one is Bcrypt. An arguably even safer one is Scrypt with HMAC−SHA-256, which can leverage multiple CPUs and ample RAM on the legitimate user's machine as a mean to dramatically raise the investment cost necessary for a parallel attack in a reasonable timeframe. The recent state of the art is captured by the results of the Password Hashing Competition.

For all these functions, a choice of the workfactor giving even minimal security, and password and salt inputs even orders of magnitude larger than in the question, the execution time overwhelmingly depends on workfactor; somewhat on code quality and CPU used; and very marginally on the size of password and salt (up to a limit of perhaps 1MB for each second of the execution time as controlled by workfactor). In a nutshell, that's because the password and salt inputs, when long (typically: more than about 64 bytes) are only processed once and reduced to something of fixed small size (using a hash such as SHA-1 or SHA-256), which is then repeatedly processed, with the repetition count controlled by workfactor.

Update: Maarten Bodewes pointed in comment that things might be different for the common PBKDF2 using HMAC-SHA-256 as the PRF. My analysis (below) is that timing dependency w.r.t. the size of the password won't happen for software implementations offering good security, but only for those sub-optimal from a security standpoint by a factor of about 2 or more.

The bulk of the execution time for PBKDF2 using HMAC-SHA-256 as the PRF is spent iterating $m_j=\operatorname{HMAC}(P,m_{j-1})$, where $P$ is the password input, and (with $H=\operatorname{SHA-256}$):
$$\operatorname{HMAC}(P,m)=\begin{cases}
H((P\oplus\text{opad})\|H((P\oplus\text{ipad})\|m))&\text{if }|P|\le64\text{ octets}\\
\operatorname{HMAC}(H(P),m)&\text{otherwise}
\end{cases}$$
where the $x\text{pad}$ are 64-octet constants, and the $P\oplus x\text{pad}$ are with $P$ right-padded with zeroes to 64 octets. When $|P|\le64$ and $|m|=32$, computing $\operatorname{HMAC}(P,m)$ involves 2 invocations of SHA-256 each with 96 octets of data, thus a total of 4 invocations of the round function of SHA-256.

A good implementation of PBKDF2 should maximize the security obtained for a given execution delay, thus should be speed-optimized. Therefore, a good implementation of PBKDF2 using HMAC-SHA-256 as the PRF should

replace $P$ with $\operatorname{SHA-256}(P)$ if $P$ is more than 64 octets;
pad $P$ to 64 octets by appending zeroes to the right and pre-compute $P\oplus\text{ipad}$ and $P\oplus\text{opad}$
apply the round function $R$ of $\operatorname{SHA-256}$ to these, obtaining the 32-octet $h_\text{in}=R(\text{IV},P\oplus\text{ipad})$ and $h_\text{out}=R(\text{IV},P\oplus\text{opad})$
in the core loop dominating the execution time, compute $m_j=R(h_\text{out},R(h_\text{in},\operatorname{pad}(m_{j-1})))$ using 2 invocations of $R$, and combine that $m_j$ by XOR into a separate 32-octet value.

Only steps (1) and (2) can have a timing dependency w.r.t. to $|P|$. All steps of PBKDF2 conceivably movable in the core loop 4 are shown.

If the implementation uses SHA-256 as a black box, but still performs (1) and (2) out of the core loop, it is bound to have 4 invocations of $R$ in the core loop, rather than 2. This is not best practice at least in software, because it lowers the protection against password search by a factor of about 2; but it does not introduce any dependency of the execution time of the core loop w.r.t. to $|P|$.

If the implementation moves (2) in the core loop, but not (1), it is likely that it will have some time dependency w.r.t. $|P|$ in the core loop (about linear, with some slope likely positive up to and including $64$ octets; then stable at the value obtained for $|P|=32$ afterwards). There will however be a fixed 4 invocations $R$ per core loop, and in any half-decent software implementation using a compiled language that will dominate the execution time, making the time dependency w.r.t. $|P|$ small.

If the implementation fails to perform (1) out of the core loop, then likely its core loop will exhibit a time dependency w.r.t. $|P|$, with a stiff steps at $|P|=65$ octets corresponding to going from 4 to 6 $R$, then steps about half as stiff at $|P|=120+k\cdot64$ octets for each additional $R$. That's a strong time dependency w.r.t. $|P|$, but only for implementations seriously inadequate from a security standpoint for the range of $|P|$ considered.

Hashes optimized for speed (like MD5, SHA-1, or SHA-256) should not be used alone for password storage and validation, because their very speed is a devastating weakness; worse, that weakness increases as time passes, for even nowadays Moore's law significantly speeds-up tasks which run well on parallel engines.


ECDSA: Why is SigningKey shorter than VerifyingKey Total Crypto Noob here.

I was wondering why in ECDSA the Signing Key is so much (half of) shorter than the Verifying key?

Lets look at some python code:

import ecdsa
import binascii
signing_key = ecdsa.SigningKey.generate(curve=ecdsa.SECP256k1)
verifying_key = signing_key.get_verifying_key()
print(binascii.hexlify(signing_key.to_string())
print(binascii.hexlify(verifying_key.to_string())

b'662ab496304f2d99aca32d813dbcba3c3ae10ab2b3359fbe43b05ee40b458cec'
b'6632feae645469c16cb31d7e1364cae247bd4322040d7089476614399bcf59b2fccf5060686ab09ee64e1b768ba037184e9a87001a4897a745721f99000b44ee'

lets assume I send verifying keys over the network or store them someware, it would be nice if they were not so long. Is there a way to compress them?

I assume it would be really bad to use the keys vice versa, but I don't understand why.

The secret $s$ in ECDSA is a value in the range 1 and the order of the group (exclusive). Some parameters are chosen in such a way that you can simply generate any value within the amount of bits as the chance that you're outside of the range or choose 0 is very small indeed. The public key is a point on the curve, calculated by performing $w = s \cdot G$ - using (modular) point multiplication as $G$ is the base point of the curve.

Generally the value $s$ is just encoded as an unsigned statically sized, big endian integer of the same size as it takes to encode the order of the group in bytes. The public point $w$ however can be encoded in different ways. You've shown a simple concatenation of two unsigned statically sized big endian x,y coordinates. That means of course that it is two times the size of the secret $s$. To get the values of x and y you first have to split the public point encoding exactly in half and then decode the separated values of x and y.

Usually this "flat" encoding (i.e. without structure) is preceded by a byte with value 04 to indicate that it is an uncompressed point. It is however possible to create a compressed point, which is just a single bit larger than the x value. Unfortunately that bit is not available in the encoding of x, so generally the point x is prefixed by a byte with either value 02 or 03 (depending on the value of x and y). Then the value of y can be retrieved by uncompressing the point. So yes, you can "shrink" the public key.

Bitcoin is even sneakier and allows you to recreate the public key out of the signature. That's probably worth a separate question though.

Note that you must first trust the public key before you can use it to verify any signature. If you don't know who's public key you're using, then you do not know who's signature you're verifying either.


RSA and possible range of $\phi(n)$ If $n = p_1 p_2$ for primes $p_1 \ne p_2$, $\phi(n)$ is $\phi(p_1)\cdot\phi(p_2)$. Does that mean that the possible range of $\phi(n)$ is somewhat narrow, that $(p_1-1) \cdot (p_2-1)$ (that is, $\phi(n)$) is close to $p_1\cdot p_2$ (that is, $n$)?

$n - \phi(n) = p + q - 1$.  $p$ and $q$ are secret uniform random 1024-bit prime numbers.  Is a difference of near $2^{1024}$ ‘close’?


The equivalence of exponentiation and multiplication over elliptic curves I am trying to convert $(g^a)^{i^2}\mod p$ to an equivalent Elliptic Curve expression.
Let's assume a base point $G$ over an appropriate ECC.
Will $(g^a)^{i^2}\mod p$ be equivalent to $G\cdot a\cdot i^2$ (where the dot operation is multiplication over the elliptic curve)?

So this is more a question of notation than anythig else. So let's examine the notation.

$$\left(g^{a}\right)^{i^2}\bmod p$$

which is equivalent to

$$g^{a\cdot i^2}\bmod p$$

means the following: Consider the group $\mathbb Z _p^*$, that is the set of non-negative integers smaller than $p$ along with the neutral element $1$ and the group operation of multiplication modulo $p$ and write this group multiplicatively with $g\in\mathbb Z_p^*$ and $a,i$ being normal integers.

Now if, instead we wrote the above as an additive group (which is merely a change of notation!), we would replace $\cdot$ with $+$ and exponentiation $g^x$ with multiplication by a scalar $x\cdot G$. So the above expression immediately becomes $(a\cdot i^2)\cdot G$ (up to commutativity and associativity). And the commutativity is a given on elliptic curves (because otherwise DH key exchanges wouldn't work).


How to create a PEM file for storing an RSA key? I have an RSA private key $\{d,n\}$ and a public key $\{e,n\}$, where $n$ is the modulus, and I also have the prime factors $p$ and $q$ of $n$.

I want to create a PEM file containing this information, so that I can decrypt a file encrypted with the public key using OpenSSL.
How can I do this?

RFC 2313 specifies the RSAPrivateKey ASN1 structure as a SEQUENCE containing the INTEGERs

$0$;
$n$;
$e$;
$d$;
$p$;
$q$;
$d\bmod(p-1)$;
$d\bmod(q-1)$;
$q^{-1}\bmod p$.

The PEM format consists of such a structure encoded as Base64 and framed by the typical BEGIN/END RSA PRIVATE KEY header and footer lines.
Thus, you can use any ASN1 library you like to encode the private key parameters. For example, with Python's pyasn1 module, a private key file's contents can be obtained as follows:
import pyasn1.codec.der.encoder
import pyasn1.type.univ
import base64

def pempriv(n, e, d, p, q, dP, dQ, qInv):
    template = '-----BEGIN RSA PRIVATE KEY-----\n{}-----END RSA PRIVATE KEY-----\n'
    seq = pyasn1.type.univ.Sequence()
    for i,x in enumerate((0, n, e, d, p, q, dP, dQ, qInv)):
        seq.setComponentByPosition(i, pyasn1.type.univ.Integer(x))
    der = pyasn1.codec.der.encoder.encode(seq)
    return template.format(base64.encodebytes(der).decode('ascii'))

The parameters dP, dQ and qInv are most easily (as in: lines of code) computed as follows:
dP = d % (p-1)
dQ = d % (q-1)
qInv = pow(q, p-2, p)


How to determine proportion of quadratic residues in elliptic curve group? I'm using a 'try and increment' method to hash to an Elliptic Curve point, explained below.

With security parameter $k$, EC equation $y^2 = x^3 + ax + b \mbox{ mod } q$, we have:

$ u = sha256(\mbox{message}) $

$\mbox{for } i = 0 \mbox{ to } k - 1, \mbox{ do:} $

$ \quad x = (u + i) \mbox{ mod } q$

$ \quad \mbox{if } x^3 + ax + b \mbox{ is a quadratic residue in } \mathbb{F}_q \mbox{ then }$

$ \quad \quad \mbox{ return } Q = (x, \sqrt{(x^3 + ax + b}) $

$ \mbox{return Q = nil, nil}$

With the EC group generator order $n$ and the field order $q$, I would imagine that the proportion of $x \in \mathbb{F}_q$ that do not result in quadratic residues is calculated $\frac{q - n}{q}$, which would be negligible, and hence require a very small security parameter, but I have read (for example here and here?) that the proportion is close to $\frac{1}{2}$, which would require use of a much larger $k$. This is also stated here, with $p$ as $q$ and $E$ as the EC group:

  An element $a$ of $\mathbb{F}_p$ is said to be a quadratic residue if there exists a nonzero $b \in \mathbb{F}_p$ such that $b^2 \equiv a \mbox{ mod }p$. In $\mathbb{F}_p$, there are exactly $(p-1)/2$ quadratic residues.

  Finding points $(x, y)$ on $E$ amounts to finding those values of $x$ such that $x^3 + ax + b$ is a quadratic residue modulo $p$; hence we might expect $x^3 + ax + b$ to be a square modulo $p$ about half of the time.

How large should the security parameter be?

How do I work the proportion of $x$ coordinates, knowing $n$ and $q$, that will not result in $x^3 + ax + b$ that is a quadratic residue?

I have read that the proportion is close to $\frac{1}{2}$

That is, in fact, correct; it is (for large $p$) extremely close to $\frac{1}{2}$; hence if you need your hashing process to fail with probability at most $2^{-64}$, you need your parameter $k \ge 64$

  I would imagine that the proportion of $x \in \mathbb{F}_q$ that do not result in quadratic residues is calculated $\frac{q - n}{q}$, which would be negligible

I believe that's where you're getting confused; you appear to be reasoning "we know there must be $n-1$ solutions to $y^2 = x^3 + ax + b$; there are $q$ possible values of $x$, and as $q \approx n$, then almost every possible value $x$ must be part of a solution.

The part that you're missing is that, for (almost) every value of $x$ which is a solution, there are two possible $y$ values that correspond to it; that is, if the pair $(x,y)$ is a solution to $y^2 = x^3 + ax + b$, then so is $(x, -y)$.  The sole exception to this is if $(x, 0)$ is a solution, there are at most 3 possible $x$ values that satisfy this; as 3 is tiny compared to $q$, we can ignore this for this analysis.

Because of this, there are approximately $(n-1)/2$ possible $x$ values that are possible solutions to the equation; that is, that result in a quadratic residue.  Because $n \approx q$, $(n - 1) / 2 / q \approx \frac{1}{2}$


What happens when domain parameter $q$ in DSA is not prime number Suppose that attacker creates domain parameters $(p,q,g)$ where $q$ is not prime number (but $q$ still divides $p-1$) and that signer generates new key pair using these domain parameters.

How exactly can an attacker take advantage of this situation?

Well, it makes the discrete log problem easier; hence it makes recovering the private key easier

The DSA private key is a value $k$, and his public key is the value $g^k \bmod p$.  $g$ has order $q$; if $q = q_1 \cdot q_2$, then the attacker can compute $(g^k)^{q_2} = (g^{q_2})^k$. The value $g^{q_2}$ has order $q_1$, and so he can solve that problem in $O(\sqrt{q_1})$ time; that gives him the value $k \bmod q_1$.  Similarly, he can recover the value $k \bmod q_2$ in $O(\sqrt{q_2})$ time; from that, he can reconstruct the original value $k$ in what turns out to be a total of $O(\sqrt{ max(q_1, q_2) })$ time, rather than the $O(\sqrt{q})$ time it would take if $q$ were prime.


Zero-knowledge proof using quadratic residue: why two options? In the zero knowledge proof using QR, why do we even bother with the server sending us $b = 0$ back? As I understand it, the server selects $b = 0$ or $b = 1$. If $b = 0$, then the client (Alice) generates a random number $r$ and sends back $r^2 \bmod x$, while if $b = 1$, then Alice sends back $r^2 \, y \bmod x$. How is $b = 0$ of any value though? Why can't we just stick with $b = 1$?

Let me attack if you (the verifier) always select $b = 1$ as a random challenge.

The zero-knowledge proof for QR.

Let us recall the zero-knowledge proof for QR.
The common inputs are $y$ and $x$ and the prover possesses a witness $w$ which satisfies $w^2 \equiv y \pmod{x}$.

The prover generates a randomness $r \gets \mathbb{Z}_x$ and sends $a = r^2 \bmod{x}$.
The verifier rejects if $a \equiv 0 \pmod{x}$; Otherwise, the verifier sends a random challenge $b \gets \{0,1\}$.
The prover sends a response $z = w^b \cdot r \bmod{x}$.
The verifier checks if $z^2 \equiv y^b \cdot a \bmod{x}$.

An attack for a fixed challenge $b$

If you always select $b = 1$,
I can deceive you while I do not know $w$.

I choose a random value $\tilde{z} \gets \mathbb{Z}$ and compute $\tilde{a} = \tilde{z}^2 \cdot y^{-1} \bmod{x}$. I send $\tilde{a}$ to you.
You select a "random" value $b = 1$ and send it to me.
I send $\tilde{z}$ as a response.
You finally obtain $\tilde{z}^2 \equiv y \cdot \tilde{a} \bmod{x}$, since I select $\tilde{a}$ to satisfy this equation.

This attack shows that the protocol cannot be sound if the challenge is unique.
Hence, the verifier should flip at least one coin.

Why $b \in \{0,1\}$

In the soundness proof, we retrieve a witness as follows:
Running the (cheating) prover twice with distinct challenges, we obtain two accepting transcripts
$$(a, b_0, z_0) \text{ and } (a, b_1, z_1).$$
Since they pass the verification, we have
$z_0^2 \equiv y^{b_0} \cdot a \pmod{x}$
and
$ z_1^2 \equiv y^{b_1} \cdot a \pmod{x}$.
Therefore, we have $z_0^2 \cdot y^{-b_0} \equiv a \equiv z_1^2 \cdot y^{-b_1} \pmod{x}$
and $(z_1/z_0)^{2} \equiv y^{b_1-b_0} \pmod{x}$.
If we select a challenge from $\{0,1\}$, the difference $b_1 - b_0$ is $1$ or $-1$.
Hence, we obtain $z_1/z_0$ (or $z_0/z_1$) as a quadratic residue of $y$.

The point is that the difference $b_1 - b_0$ is always $\pm 1$.
This means that you can choose $b$ from another set, say, $\{2,3\}$ or $\{3,4\}$.

You can read explanations in the textbooks, e.g., Barak's lecture note.


Padding vs Hashing Encryption Key I am making a program for personal use that will not contain super-sensitive information.  I am using this to explore cryptography. Would it be acceptable to use a password to generate a key for AES, or should I make a file, store it somewhere separate of the program, and call it for encryption/decryption.  If the password is too short to be an AES key, should I hash it or pad it?

I just realized that I could link to my stack overflow account! I am sorry if this question is misplaced.

You cannot assume that a text-based input is an acceptable replacement for a key in cryptographic algorithms. The default assumption used to design algorithms is that the key is generated randomly; specifically, generated in such a way that the key is unpredictable and comes from a uniform random distribution of all possible keys.

If you use text instead of random bits there are plenty of problems:

You reduce the number of keys that need to be tested
Your input will have patterns that may make your key more likely to belong to a class of weak keys. If a set of weak keys exists for an algorithm, using one of them will cause the algorithm to exhibit biases that could make it insecure.
Passwords chosen by humans are far more predictable than the typical person assumes. If you need to keep encrypted data safe then you need to be smart with your password.
A password might be shorter or longer than an algorithm's normal key size. (Padding and truncating here is a bad idea, especially when password- based key derivation functions exist.)

How one might (correctly) encrypt a file using a password:

Generate a new random password not used for any online services
(or otherwise shared with anyone). How do you do that?

Don't use things like your favorite sports team or a birth date.
Generate a random string of characters from something like /dev/urandom. A string, if the length is $n$ and the characters come from an alphabet of size $m$, has up to $\log_2(m^n) = n \log_2(m)$ bits of entropy
Generate a string of $n$ random words from a dictionary of $m$ words, using spaces or periods or commas as word separators. This also has $n \log_2(m)$ bits of entropy.
If you want to generate a memorable password, no computer required, and you have a fair six-sided die, then use Diceware. I recommend one of the EFF lists over the original word list.
Make sure your password has enough entropy to prevent brute force guessing. The minimum you want is probably 100 bits. Some might say 80 bits or 128 bits. (When you generate a password for websites you can go much lower, but that's because it's a different application of passwords.)

Generate a nonce
Use a key derivation function. For example, scrypt if (you commit to using a lot of RAM), bcrypt, or Argon2d. The functions I listed accept passwords as input and "stretch" them. They make brute force guessing harder by making the attacker and the person who has legitimate access to the file do extra work. Use it to derive a symmetric key of 256 bits (if it's available even if entropy isn't 256 bits and you fear quantum computing) otherwise choose a key size and algorithm with at least 128 bit security level.
Create an output file, store the nonce in plaintext, then append the ciphertext and authentication tag of the encrypted input file to the output file.
Remove data from the original plaintext file from any storage place or memory where someone could gain access to it.

To decrypt a file use the same key derivation function, check that the authentication tag is correct, and decrypt the data using the nonce and key.

There are some details and warnings I am leaving out because they're answered in other questions here, at http://security.stackexchange.com/ and on many other websites.


Keccak and compression functions Keccak follows a sponge construction. Can we say that Keccak employs a compression function?  Generally speaking, for sponge constructions, can we say that there is an underlying compression function?

The sponge construction does not have a compression function in the sense of traditional hash constructions like Merkle–Damgård.  Instead, it operates using a permutation function $f$ which "mixes" or "absorbs" the input into the state of the algorithm.  Strictly speaking, it does take an input larger than the output it produces, but this function is actually reversible and so is not comparable to one-way compression functions like in MD5 or SHA-1.


Enigma - How many possibilities does the plugboard have? I try to relate my own calculation with the real result being about 150.738.274.937.250.
The plugboard has 26 letters, and you have 10 wires to connect pairs of letters.
My idea was to calculate first how many possible pairs you can have.
26*25/2 = 325 [(a,a) not allowed, and (a,b)=(b,a) so divide by 2 to remove duplicates]
or just 26C2 = 325.
And out of 325 pairs to choose 10 pairs there are 325C10 = 3.150.234.554.696.452.080 possibilities to connect pairs with 10 wires.
Where is my way of thinking wrong?

out of 325 pairs to choose 10 pairs, there are 325C10 possibilities to connect pairs with 10 wires.

This accounts for the fact that we can not choose a pair that has both letters identical to an earlier pair, but misses that we can not choose a pair that has any letter common with an earlier pair.
A correct line of thinking is: imagine that the 20 ends of the 10 wires are numbered, and we assign a letter incrementally to each of them. That's 20 distinct letters to choose among 26, and order matters, giving $26!/(26-20)!$ ways. But the order of the 10 pairs does not matter, thus divide by $10!$. Further, the order for the two letters assigned to any of the 10 wires does not matter, thus divide by $2^{10}$. We end up with $26!/(6!\,10!\,2^{10})=150,738,274,937,250$ distinct ways.


Three-way key exchange with elliptic curves without pairing Assume that there are three users, each with their own secret key $d_i$ and the corresponding public key $Q_i = d_i \cdot P$, such that $Q_i$ is a point on an elliptic curve and $P$ is a base point on this elliptic curve.

Is $d_1 \cdot Q_2 \cdot Q_3$ equal to $d_2 \cdot Q_1 \cdot Q_3$ or $d_3 \cdot Q_1 \cdot Q_2$?

How can three users compute a shared key without knowing $d_1 \cdot Q_2$, $d_2 \cdot Q_1$, $d_3 \cdot Q_1$, $d_3 \cdot Q_2$, $d_2 \cdot Q_3$ and $d_1 \cdot Q_3$? The only things that each user knows are his own secret key $d_i$ and other users' public key $Q_1, Q_2, Q_3$. Can this be done without pairing?

Without pairings, there is no known single round tripartite key-exchange algorithm. However, it is possible to do it in two-rounds. For example, refer to the Burmester-Desmedt conference key protocol (http://www.cs.fsu.edu/~burmeste/eurocrypt_plus_proof.pdf) which in fact works for an arbitrary number of users.

This being said, would it be possible to find a protocol along the line you are suggesting? The key problem would be to define the product of two points $Q_1Q_2$ on an elliptic curve. Moreover, for your idea to produce a common key $d_1\cdot Q_2Q_3=d_2\cdot Q_1Q_3=d_3\cdot Q_1Q_2$, you would like this definition of the product to be both bilinear and non-degenerate. Thus, your definition of the product of two points would be some (possibly new) kind of pairing.

Moreover, if the product of two points $Q_1$ and $Q_2$ is again a point on the elliptic curve, you would have an (efficient) algorithm for the computational Diffie-Hellman in this group. From a security point of view, this is bad, because there are reductions that use such an algorithm to solve the discrete logarithm problem once the computational Diffie-Hellman becomes easy (For example see http://www.stanford.edu/class/cs259c/finalpapers/dlp-cdh.pdf).

As a consequence, the most likely answer to your question is: no, it can't be done without pairings.


Does there exist a public database of RSA-2048 moduli and their factors? Provided some modulus for RSA 2048, is there a way I could look up if

the modulus
and their factors

exists online?

TL;DR
It's not possible, because there are way too many prime numbers.
It's possible that there might be a database with some of these numbers, but not a database with all the possible numbers. There are just way too many prime numbers to fit them all in one database.

How many 1024-bit prime numbers are there?
To get a 2048-bit modulus you multiply two 1024-bit prime numbers together. Using $$\frac{n}{\ln(n)}$$ we can estimate the amount of prime numbers with the length of 1024-bits. The amount of 1024-bit numbers is $2^{1023} - 1$.
$$2^{1023} - 1 \approx 8.9 \times 10^{307}$$
We then apply the approximation:
$$\frac{8.9 \times 10^{307}}{\ln(8.9 \times 10^{307})} \approx 1.25 \times 10^{305}$$
We now have an approximation of how many 1024-bit prime numbers there are.

How large is the database?
If you want to put them all in a database you just have to calculate the number of these primes multiplied with their size (which is of course 1024-bits). That gives you the size of your database in bits:
$$1024 \times 1.25 \times 10^{305} \approx 1.28 \times 10^{308}$$
So as you can see this database would be way too large and it wouldn't be practical to even try to fit them in any database.


Partial-Message Collisions on Iterated Hash Functions In Cryptography Engineering by Ferguson et al it says the following is a problem with iterated hash functions:

  Because hashing $m$ and $m'$ leads to the same value, $h(m||X) = h(m'||X)$... for all values for $X$.

I don't see at all how this follows from $h$ being iterated? If some general input $x$ is preprocessed into $x_1...x_t$ then $h(x) = H_t = f(H_{t-1},x_t)$ where $f$ is the compression function. Now, if $m,m'$ both have lengths that are multiples of the block size then the assertion certainly is true, as follows:

Suppose $m = m_1...m_s$, $m' = m'_1...m'_t$ and $h(m)=h(m')$, i.e. $$H_s = f(H_{s-1},m_s) = f(H'_{t-1},m'_t) = H'_t$$ Assuming for simplicity that $X$ is preprocessed into a single block (also denoted by $X$), we get $$h(m||X) = f(H_s,X) = f(H'_t,X) = h(m'||X)$$ All in good order. But suppose now that $h(m)=h(m')$ but $m||X$ and $m'$ are preprocessed into single blocks $M$ and $m'$ resp, so that $m'||X$ is preprocessed into two blocks (denote the preprocssed $X$ by $X$ yet again). We then get $$h(m||X) = f(H_0,M)$$ $$h(m'||X) = f(H_1,X) = f(f(H_0,m'))$$

How does it follow simply from $h$ being iterated that the two are equal?

If you go through what Ferguson said, I'm sure he'll include a condition that $m$ and $m'$ are the same length, which is also a multiple of the hash block size. In this case, $m||X$ and $m'||X$ will not be preprocessed into single blocks; instead, they'll be processed as (at least) two blocks; one being $m$ (or $m'$), and the rest consisting only of $X$.

What's crucial is that the state of the hash function after processing $m$ and $m'$ are the same.  Because the state is the only way the hash function 'remembers' what came before, it'll do the same thing in both cases when processing $X$; hence $h(m || X) = h(m' || X)$


Which cascade is safest? Which cascade in VeraCrypt is the safest?
(assuming same password, keyfile strength etc)
a] Serpent(Twofish(AES))
b] AES(Twofish(Serpent)

What could the difference be? I can't think of any and I don't uderstand why there are 2 options. Which one would you choose and why?

Both options for the 3-cipher cascade are equally safe.

All three algorithms are strong with no known issues.  Veracrypt uses them in well-studied modes that also have no known issues.

If you were worried about one of the algorithm implementations being vulnerable to some sort of side channel attack, then I would use that one as the last to be applied.  But in the context of most Veracrypt usage, someone who can mount a side channel attack, will probably just install a keystroke logger and steal the password directly.

So bottom line:  There is no real difference, and you can arbitrarily choose one with no real impact.

You also ask for an opinion about what the community would choose, so I'll offer mine:  The real threat is bad passwords or implementation bugs not weak algorithms, so I'd go with the highest performance single-pass algorithm.  A three cascaded cipher implementation is overkill.


Complex Numbers on Elliptic Curves & Usage in Tate Pairing I'm working with understanding the internals of the Tate Pairing. I was going through an example of the curve $E: y^2 = x^3 + 3x$ over $\mathbb{F_{11}}$. The author is showing the computation of $e(P,Q)$, where $P=(1,9)$ and $Q = \phi (P) = (10,9i)$ using Miller's Algorithm. Through this algorithm, the author chose a point $Q' = (6,6)$ and then computes $S = Q + Q' = (8+7i, 10+6i)$. This is where I'm having an issue, I can't seem to determine how the complex addition of points occurs in elliptic curves, and I'm looking for an explanation in the usage for the Tate pairing.

Paper being referenced : http://www.win.tue.nl/~bdeweger/downloads/MT%20Martijn%20Maas.pdf , Section 4.3.1

Fix a field $k$.  Consider the polynomial $x^2 + 1$ in $k[x]$.  If $x^2 + 1$ is irreducible over $k$, then obviously the quotient $k[x]/(x^2 + 1)$ is also a field, of $\#k^2$ elements if $k$ is finite.  Note that $x^2 + 1 \equiv 0 \pmod{x^2 + 1}$, so $x^2 \equiv -1 \pmod{x^2 + 1}$; hence if we take any linear polynomials $f_0 = a_0 x + b_0$ and $f_1 = a_1 x + b_1$, we can work out the product modulo $x^2 + 1$ by the standard rules of arithmetic, substituting $-1$ wherever we see $x^2$:

\begin{align}
  f_0 \cdot f_1
  &\equiv (a_0 x + b_0) \cdot (a_1 x + b_1) \\
  &\equiv a_0 a_1 x^2 + a_0 b_1 x + b_0 a_1 x + b_0 b_1 \\
  &\equiv a_0 a_1 \cdot (-1) + a_0 b_1 x + b_0 a_1 x + b_0 b_1 \\
  &\equiv (a_0 b_1 + b_0 a_1) x + b_0 b_1 - a_0 a_1
  \pmod{x^2 + 1},
\end{align}

which, as it happens, is exactly the same arithmetic as for the familiar complex numbers, because $\mathbb C \cong \mathbb R[x]/(x^2 + 1)$ can be constructed exactly this way.  Drawing on the analogy, we name the indeterminate variable $i$ rather than $x$ for the polynomials in $\mathbb F_{11}[i]$ so that we can write $i^2 = -1$ in the field $\mathbb F_{11^2} \cong \mathbb F_{11}[i]/(i^2 + 1)$.


Is there a format preserving cryptographically secure hash? I want a way to 'scramble' strings (like words, names) in a predictable way but I don't ever want to (myself or anyone else) be able to 'unscramble' the strings.

I found that perhaps what I am looking for is a cryptographically secure hash.

But can it do these things

1 - preserve the length of the original string?

2 - preserve the format (keep numbers as numbers, or characters within certain ranges)

3 - Collision resistant

4 - Reusable for a finite length of time - like over a few minutes to a few months (i need to reuse the algorithm over and over so that a string 'scrambled' today will come out the exact same way in the future using the same algorithm)

EDIT:  The reason why I use the term cryptographically secure hash is that it is supposed to be 'practically impossible' to invert.  It is the impossible to invert feature that I am looking for. I do not care to recover the meaning or content of the original message. i.e. For example using encryption, I do not want someone to be able to determine a 'key' by analyzing the output message, or find patterns in the output message that would enable them to determine the input message.

I think the closest to what I seek is probably Format Preserving Encryption, however, the concern is the fact that the encryption is reversible.  I'm curious if it can be made irreversible. Then a hash came to mind.

Cryptographically secure hashes usually work on bitstrings of arbitrary length and output a fixed length bitstring. The secure part is being collision resistant and preimage resistant, so that you have a practical oneway function, and those are the properties you want for "scrambling".

As fgrieu psted in the comments, one easy way to do this is to utilize an encryption scheme, and use the plaintext for the key as well. That means, in order to decrypt the ciphertext you would need the plaintext. Formally:

$$F(p):= E_p(p)$$
with $E_k(p)$ denoting an encryption method with key $p$. If you want to utilize format preserving encryption, you might have to make adaptions how the plaintext actually is used for the "key input".

One more remark: Usually the key should be generated uniform randomly, and depending on your format, this might not be true. Therefore, if you use a normal hash function on the input $p$, then you should get a uniformly distributed hash value, and if you use this as key, you should be fine. Theoretic remark: In the random oracle model this should work just fine. So, we can adapt this to:

$$F(p):= \hat{E}_{H(p)}(p)$$

with a format preserving encryption function $\hat{E}_k(p)$ and a cryptographically secure hash function $H(p)$, where the key length $|k|$ is equal or less than the length of the output of the hash function $|H(p)|$.


Is RSA inspired by Diffie Hellman? I read a bit of A Method for Obtaining Digital Signatures and Public-Key Cryptosystems that introduced RSA in 1977, and, while learning the steps in RSA a few days ago, I noticed that they are similar to the Diffie-Hellman key exchange. Was RSA inspired by Diffie-Hellman, published the year before in 1976, as in does the cryptography rely on earlier work and re-use parts from Diffie-Hellman and modular exponentiation, and the secret being the inverse of the encrypted message?

Was RSA inspired by Diffe-Hellman, published the year before in 1976

Update

I met Ron Rivest at MIT's LCS35 time capsule unveiling and asked him this question for you.

The answer is yes.

Original Answer

In "The first ten years of public-key cryptography", the following social relationships are mentioned:

  Ron Rivest had been a graduate student in computer science at Stanford while I was working on proving the correctness of programs at the Stanford Artificial Intelligence Laboratory. One of my colleagues in that work was Zohar Manna, who shortly returned to Isreal and supervised the doctoral research of Adi Shamir, at the Weitzman Institute.

So Rivest went to the same school where Whitfield Diffie was working, and Zohar Manna apparently brought the knowledge to the attention of Adi Shamir.

So they certainly must have been aware of Diffie and Hellman's work.

In fact, the original paper on RSA cites the paper "New Directions in cryptography" by Diffie and Hellman, so that's pretty much a smoking gun that proves that they were building off the work of Diffie and Hellman.


What is required to decrypt an encrypted file? At the risk of sounding stupid and being laughed at...I must ask this question. What is required to decrypt an encrypted file? Obviously you need the appropriate key to decrypt, but is any other information needed in order to correctly decrypt the content?

Please forgive me as I am just learning cryptography and this is the first time I've had to handle encrypting/decrypting files in a program.

Here is the scenario. I have a Python program that generates a file. This program also needs to encrypt that file and then send it to someone else. I'm using a library called keyczar for my cryptography tools. And I'm encrypting the file using AES-256.

My concern is that the person receiving the file won't be able to correctly decrypt the file because they'll be using their own system to perform the decryption process. What exactly does the person receiving the file need to correctly decrypt the file? Do they only need the AES key? Or do they need to know details about the encryption process such as the header, initialization vector, and signature?

KeyCzar is a cryptosystem on its own. It defines a container format, with a header, IV, ciphertext and possibly a (symmetric) signature. The keys it uses are also not just keys, they contain additional information. These "keys" may even contain multiple keys, i.e. an additional one for the signature creation.

To decrypt KeyCzar encrypted files you need a program that is compatible with KeyCzar. Many libraries can be downloaded from the KeyCzar GitHub site. Alternatively you can implement your own library given the specifications hosted on the same site. KeyCzar can be used from the command line as well.

In general you need to understand the protocol (and protocol version) that is being used to encrypt/decrypt files. Just specifying that something is encrypted using AES-256 doesn't say much at all.

Note that KeyCzar also contains methods for asymmetric encryption. You should however first be able to trust the public key of the receiver for that to be useful.


Question on monoalphabetic substitution Question:
  A stream of cipher operates on a data stream of 6-bit characters using a simple mono-alphabetic substitution technique. Estimate and explain the number of different substitution alphabets possible. The key is effectively the substitution alphabet, which can be expressed as a $384$-bit number (i.e. $64×6$ bits).

  Discuss the security of this system compared with DES/3DES and a one-time pad, providing a full justification for your conclusions.

This is a past exam question which I am struggling to solve. I am not a security expert, nor intending to move in that direction as a career path. The module is part of my MSc course and has nothing to do with my career.

Answer (what I have so far):

The number of different substitution alphabets is $26!$ (factorial), assuming use of the English alphabet. It is also assumed that letters can be in any position and cannot repeat themselves.

Why is the key suddenly expressed as a $384$-bit number? I don't understand. Why $64·6$?
We don't have $64$ characters in our alphabet...if each character within the English alphabet is represented with $6$ bit, then it should be $6·26=156$ bits. Correct?
Now I am thinking if the question says $64$, maybe the alphabet is custom (like including uppercase letters and some numbers + characters), so the number of permutations is $64!$ (factorial). Is this correct?
What does this key look like (or an example of such a key)?
I understand key substitution with a single key word. For example:

abcdefghijklmnopqrstuvwxyz
hatredbcfgijklmnopqsuvwxyz
Can you help me determine what the substitution alphabet key should look like?
I went to Wikipedia's page Six-bit character code and became even more confused. Is this link even relevant?

I would appreciate examples more than answers. Thank you. If you find my question too long, please ignore the part about comparison with other encryption systems.

The format they are proposing for the key seems to be some sort of bit-packed array. First, with 6 bits, there are 64 possible values (0-63). Now, imagine you have replacement rules (your key) like these:

0 -> 17
1 -> 43
2 -> 12
...
63 -> 8

Which means: when encrypting, replace all occurrences of the value 0 with 17, all 1s with 43, etc. These values may correspond to letters, but that is not necessary at this point. As the numbers on the left side of the mapping table are sequential, an alternative form of writing this key would be $17,43,12,...,8$. This could easily be transformed into the more verbose initial version. Each number in the list takes 6 bits to represent (since it must also be $<64$), and there are 64 of them, so total bits to store the key is $64*6=384$.
In a way, this key size is deceiving. Key of size $l$ bits normally implies that there are $2^l$ possibilities for the key. Here, you were right to use factorials. There are only $64!\approx 2^{296}$ possible keys. To understand why this is true, think about what happens if the key is sent, but the last 6-bit number is left off. We can figure out which one it is just by seeing which value hasn't been used yet. Even if the last two 6-bit numbers are left off, there are only two possibilities for the key ($a,b$ or $b,a$). So clearly, sending 384 bits means that we are sending more than we strictly need.
The 6-bit character code is just one possible way to convert these 6-bit numbers the algorithm uses into characters that are useful for humans.


What encryption types are illegal in the U.S.A I live in the USA. I am a developer, interested in creating an application with encryption. I am interested in learning what the illegal/restricted encryption types are.

Clarify:

What are the encryptions that are not accessible to a regular programmer that is not working for a company.

Effectively none.  Some ciphers are patented so you won't find them in OpenSSL.

In 1995 Bill Clinton signed an Executive Order 13026 that transferred control of encryption from the department in charge of munitions export to the commerce department.  Since then there has been a period of liberalization where now the only true restrictions are on exporting to countries under embargo.

You are free to write software that uses any key length to protect the messages.


Repeating nonce in CTR mode Can anybody explain in detail why repeating nonce is dangerous in CTR mode?

Two cases to explain

When plain text is repeated for each nonce.
When plain text is unique for each nonce

.

In counter mode the block cipher operates as a PRNG, essentially like the keystream generator of a synchronous stream cipher. The key and the nonce determines the starting-point of the PRNG, thus if the nonce is ever reused with the same key, the keystream produced is the same.

Why is this bad? Because if you ever figure out the plaintext corresponding to the ciphertext of one message encrypted with the repeating keystream, deducing the keystream is trivial ( ciphertext = plaintext XOR keystream ), and you may easily decrypt any other message encrypted with the same keystream. (Essentially a known-plaintext attack).

To answer your specific questions:

If the same plaintext is encrypted with the same nonce (and the same key), the ciphertext is identical.
If the plaintext is "unique" (different is perhaps more accurate), the ciphertext is different. But as explained above, if the adversary gains knowledge of any plaintext-ciphertext pair, (s)he may decrypt all the other messages.


Should AES.decrypt(ct, wrong_key) return blank or wrong result? I am trying to use AES as cipher for an application I am building.
I am using a JavaScript library (https://code.google.com/p/crypto-js/) to perform encryption and decryption with AES.
When I perform decryption, this happens:

AES.decrypt(ct, right_key) == 'message decrypted !' //true

AES.decrypt(ct, wrong_key) == '' //true

The problem is that I am using this decryption in a process in which there shouldn't be any way to determine if the key was right or wrong. I would like something like this to happen:

log(AES.decrypt(msg, wrong_key)) // 'random string fsdijw'

So that the result is 'compliant' to the expected result but it's not the expected result, and there is no way to understand if the key was right or wrong depending on the result of the decryption.
I asked my professor and he told me that AES is probably bad implemented in that library, but he didn't understand my problem so clearly.

I wonder if the behavior described in the first snippet of code is expected or actually AES has been bad implemented in that library.
If it was expected, is there any other cipher algorithm that doesn't allow to understand if the key was right or wrong from the result of decryption?

AES is a block cipher and would return wrong data when a wrong key is used. It only works on a single block of data (16 bytes). The default CBC mode of operation enables you to encrypt multiple blocks of data. The padding then enables you to encrypt plaintexts of arbitrary length. The padding has to be removed somehow after the decryption.

You're seeing a blank output, because your data is short and the padding removes more bytes than necessary. Here is how the default PKCS#7 padding is implemented in CryptoJS:

unpad: function (data) {
    // Get number of padding bytes from last byte
    var nPaddingBytes = data.words[(data.sigBytes - 1) >>> 2] & 0xff;

    // Remove padding
    data.sigBytes -= nPaddingBytes;
}

So, it looks at the last byte of the decrypted byte and removes as many bytes from the ciphertext. If data.sigBytes is negative, it would handle it like 0 bytes where decrypted. If your message is longer than 255 bytes, then the decryption is guaranteed to print something, but it won't be as long as the initial plaintext. If you always want to print something then you need to decrypt without padding.

I wouldn't call this implementation wrong, because PKCS#7 padding is specified for up to 256 padding bytes, but rather data.sigBytes -= Math.min(nPaddingBytes, blocksize); would have been probably better.

Zero padding might be better suited in your case, because it's highly unlikely that a decryption with a wrong key results in a plaintext that ends with many zero bytes at the end that have to be removed. But such as padding should not be used when there is a chance that you might encrypt a plaintext which ends in 0x00 bytes.

  So that the result is 'compliant' to the expected result but it's not the expected result, and there is no way to understand if the key was right or wrong depending on the result of the decryption.

This is not generally possible with a block cipher. A decryption with wrong key can result in some arbitrary plaintext bytes that doesn't have to make up a string with valid ASCII or UTF-8 encoding and if you try to force it, you will get errors, which can be used to distinguish the correct key from a wrong key.

If you're always encoding the plaintext to Hex, then you can get away with using arbitrary keys.

Related:

Does AES specify error messages when using the wrong password to decrypt?
Is it possible to find data which makes sense when decrypted with different keys?


in Bilinear pairings, what is the difference between Type 2 and Type 3? in Bilinear pairings, what is the difference between Type 2 and Type 3?

I understand in Type 2, there exists an efficiently computable homomorphic function $\phi : G_2 \rightarrow G_1$ , which is not present in Type 3 pairings.

But what I don't understand is what is the use of the homomorphism in cryptography?

For those who might need a refresher, for a bilinear pairing $e : G_1 \times G_2 \rightarrow G_T$ , we define

Type 2: $G_1 \neq G_2$ and there is an efficiently computable homomorphic function $\phi : G_2 \rightarrow G_1$
Type 3: $G_1 \neq G_2$ and there is NO efficiently computable homomorphic function

Note that you do not have an efficiently computable homomorphism from $G_1$ to $G_2$, but in Type-2 you have an efficiently computable homomorphism $\psi: G_2 \rightarrow G_1$ and in Type-3 you do not have one.

  But what I don't understand is what is the use of the homomorphism in cryptography?

Well, if you have a tuple $(aP',bP',cP')\in G_2^3$ with $P'$ being a generator of $G_2$, you can check if $e(\psi(aP'),bP')=e(\psi(P'),cP')$ holds. Consequently, the decisional Diffie Hellman (DDH) problem is easy in $G_2$, but remains hard in $G_1$. In cryptography, this is typically formalized as the so called external Diffie Hellman (XDH) assumption.

In a Type-3 setting, as you can not map between $G_2$ and $G_1$, the DDH seems to be hard in $G_1$ and in $G_2$. In cryptography, this is typically formalized as the so called symmetric XDH (SXDH) assumption.

So if you have a Type-2 pairing, then you have the XDH setting and if you have a Type-3 pairing, you have the SXDH setting.


Computing the cardinality of the co-domain of specific modular exponentiations Consider the following function:

$f: \mathbb{Z}_n \rightarrow Y,~x \mapsto x^e \bmod n$,

where $n = p \cdot q$ is an RSA modulus and $\gcd(\varphi(n),e) \neq 1$ (contrary to what's required for a public RSA exponent) with $\varphi(n) = (p-1)\cdot (q-1)$.

How can the cardinality of $Y$ be computed or estimated (in terms of $n$ and $e$)?

One way to approach this problem is to first look at the simpler problem of that cardinality of $x^e \bmod p$ where $p$ is prime, and $gcd(p-1, e)$ might not be 1.

In that case, we have two cases: $x \equiv 0 \pmod{p}$, which makes it obvious that 0 will always be a possible postimage, and $x \in \mathbb{Z}^*/p$; in this second case, that group is isomorphic to the simpler group $\mathbb{Z}/{p-1}$; considering that simpler group, it should be obvious that there are $\frac{p-1}{gcd( p-1, e)}$ possible postimages.  Combining the two gives us $1 + \frac{p-1}{gcd( p-1, e)}$ total postimages.

Now, going back to your original question, $p$ and $q$ are relatively prime, and so by the Chinese Remainder Theorem, any pair of inputs $x \bmod p$ and $x \bmod q$ are possible.  In addition, a postimage $x^e \bmod n$ is possible iff the corresponding postimages $x^e \bmod p$ and $x^e \bmod q$ are both possible.

The upshot of this is that the total number of possible postimages is the product of the number of postimages mod p times the number of postimages mod q.  Or, in other words,

$$|Y| = \lgroup 1 + \frac{p-1}{gcd( p-1, e)}\rgroup \cdot \lgroup 1 + \frac{q-1}{gcd( q-1, e)} \rgroup$$

We see that if $\gcd( \phi(p), e) = 1$, then $gcd(p-1,e)=1$ and $gcd(q-1,e)=1$, and this formula simplifies to $|Y| = pq = n$

I know that you asked for a function depending on $n$ and $e$, however since it is believed to be computationally infeasible to compute $gcd( \phi(n), e )$, coming up with even a formula to estimate $|Y|$ looks impractical.


Why do we use 1024 / 160 bit primes in DSA? I am looking at DSA's parameter generation and don't understand why for $p$ a 1024 bit prime is needed if $q$ is chosen as a $160$ bit prime. I thought that the security of DSA relates on the discrete logarithm problem. A good protection against algorithms solving the DLP is to work in a big order subgroup. I would choose $p$ as a safe prime, so that $p = 2q + 1$. Then $p$ has a bit size of $\approx 160$ bit and the biggest sub group has size $q$. I guess I cannot do this but what is the explanation for this?
I have taken the variable names from Wikipedia (https://en.wikipedia.org/wiki/Digital_Signature_Algorithm). Here an excerpt of the parameter generation part:

Decide on a key length $L$ and $N$. This is the primary measure of the cryptographic strength of the key. FIPS 186-3 specifies $L$ and $N$ length pairs of (1024,160), (2048,224), etc.
Choose an $N$-bit prime $q$. $N$ must be less than or equal to the hash output length.
Choose an $L$-bit prime modulus $p$ such that $p–1$ is a multiple of $q$.
Choose $g$, a number whose multiplicative order modulo $p$ is $q$. This may be done by setting $g = h^{(p–1)/q} \bmod p$ for some arbitrary $h (1 < h < p−1)$, and trying again with a different $h$ if the result comes out as 1. Most choices of $h$ will lead to a usable $g$; commonly $h=2$ is used.

The algorithm parameters (p, q, g) may be shared between different users of the system.

There are two ways to solve a discrete log problem over $Z^*/p$, that is, given $g$ and $h$, find $x$ with $h \equiv g^x \bmod p$:

If the point $g$ generates a subgroup of size $q$, use a general Discrete Log algorithm (such as Pollard Rho) to recover $x$ in $O( \sqrt{q})$ time.
Use the Number Field Sieve algorithm to attack the discrete log problem in $Z^*/p$.  NFS is typically seen as a way to attack the factorization problem; it can also be applied (with some additional complexity) to compute discrete logs.

Because of this second possible method, using $p \approx 2^{160}$ would be a serious weakness.


Is there an efficient algorithm that allows to obtain a uniform distribution of all possible $4$-bit permutations from a single keyless $4$-bit S-Box? Let $S$ denote a keyless permutation that operates on $4$-bit inputs and returns $4$-bit outputs (that is, $S$ is a $4$-bit S-Box).

In this question, $x_0$ denotes an arbitrary bitstring that ends with 0000 (four zero bits) such that the length $L$ of $x_0$ is a multiple of $4$ and there is no upper bound for $L$. Then $x_0 + i$ denotes a bitstring that represents the sum of $x_0$ and $i$, assuming that $x_0$ is interpreted as a single natural number and all ($L - 4$) leading bits of $x_0$ are not affected. For example,

000001010000 + 1 =  000001010001,
000001010000 + 14 = 000001011110,
000001010000 + 15 = 000001011111

Does there exist an efficient iterative construction $F(x)$ based on $S$ so that the length of $F(x)$ is $4$ and a tuple $$\{F(x_0), F(x_0 + 1), \ldots, F(x_0 + 14), F(x_0 + 15)\}$$ is a sequence of $16$ different $4$-bit elements for any $x_0$ (that is, each $x_0$ generates a permutation of $4$-bit values), and all of the $2^4! = 20922789888000$ possible permutations are equiprobable if $x_0$ is a sequence of random bits followed by four zero bits (assuming that the length of $x_0$ is $4n$, where $n$ is an arbitrarily large natural number greater than $1$)? If it is not possible for all permutations to be absolutely equiprobable in the mathematical sense, then at least the distribution of permutations must be as uniform as possible and look “pseudo-random”.

In Haskell the recursive function

f s x = s (g 16 (x `div` 16) (x `mod` 16))
  where g 1 _ = id
        g n x = t (n-1) (x `mod` n) . g (n-1) (x `div` n)
        t x y z = if x == z then y
                            else if y == z then x else z

runs for any function s that is a permutation on [0..15] through all permutations on [0..15] if you let x run through all numbers 0...20922789888000*16-1.

Of course, s doesn't matter much, so I'd set s = id, and look at the definition of g using t: t x y is simply exchanging the values x and y, keeping all other values the same.

Now g n x is a(n arbitrary!) permutation on [0..n-1] depending on x: x mod n determines which element to exchange with n-1 (all other elements are untouched) and x divided by n is used as parameter to for defining recursively g (n-1).

If you pick n uniformly from 0..20922789887999, the permutation g n will be a uniform random element of the symmetric group on [0..15].


AES Sbox with alternative polynomial I've used the C++ prog I found on the web to generate the standard Sbox with poly 0x11b, and also modified it to use a lookup table of all the multiplicative inverses of the 256 values, which also works fine.  I'm now trying to generate alternative Sbox using polynomial 0x11d, as used in the paper by Das, Zaman & Ghosh, but without much success.  I've again generated all the multiplicative inverses for the poly and used them in a lookup table, but I do not get the same results as the paper's authors.

The paper's tables in Appendix A are wrong.

For the entries in the first line of Table A1(a) I independently get:

0A 15 3F 2C 90 3B 19 51 FD EF 28 8C 83 A0 A7 36

and the fourth value (for input 03h) matches the OP's computation.

Note: there are fixed points (including 23h), invalidating the list of the valid additive constants, which is about the only attempt at an addition to self-citation [15] (at least, Appendix 1 table 2b appears correct and is available for free there).

Recommendation: if working on that paper is an assignment in a crypto course, question the competence or/and honesty of the assigner.


Are there encryption schemes with which it takes (significantly) longer to encrypt than to decrypt? Are there encryption schemes with which it takes (significantly) longer to encrypt than to decrypt?

I am thinking of a specific situation in which a server continuously receives encrypted messages from different senders and has to decrypt each single one of them. To cope with the possibly large amount of messages the decryption process should be fast. However, to avoid that the senders send a large amount of automatized messages, the encryption process should take much longer.

Ideally, the time to encrypt a single message should still be acceptable, but it should become unfeasible to send a large amount of messages in a short time. The specific type of encryption does not matter and the server can be assumed to have all the necessary keys for the decryption of the messages (without the key, of course, the decryption process should take much much longer!).

In other words, sending a message should be "expensive", while receiving the message should be "cheap". Is there an encryption scheme that shifts the computational load to the side of the sender, so that it takes longer to encrypt than to decrypt a message?

Perhaps not of relevance if the question is meant in a purely thoretical (i.e. asymptotical) sense, but the CBC encryption mode is inherently sequential, while decryption can easily be performed in parallel.


Frequency Attacks on Encrypted Database I'm trying to build an encrypted database where we can't trust on the database manager. And since encrypt data in a deterministic way is bad, attackers can recover information doing frequency attacks, I had the following idea:

|Names         |bucket|
|0xF32(Michael)|2     |
|0x321(Simon)  |1     |
|0xG3F(Simon)  |1     |
|0xT2A(Ana)    |1     |

As u can see Names is encrypted in a random way, and the bucket is calculated with some function where f(Simon) = 1;
And now if a client wanna get all Simons in the database he will execute f(Simon) =1 and query the database where the bucket value = 1. In this way, database will give to client Simon and Ana's value. And the client will discard Ana. In this way, database will not know what values correspond to Simon.

My main problem is a way to get a function where it gives me collisions but not a lot.

The problem

Frequency attack is a big problem for databases. For example, these two 1 2 articles represent the attack in CryptDB. This can have serious results, especially if you consider that the encryption is enough. You can find more about frequency attack if you search. There is no clean solution if you have to query over the encrypted data and if you don't know about the distribution of the columns.

The pioneer work

Hacıgumüş et. al was a pioneer in this subject; Executing SQL over Encrypted Data in the Database-Service-Provider Model. Their work used partitioning of the data into buckets. The first column etuple contains the encryption of the columns in concatenate form and the columns are bucketed. You query over the bucket columns and decrypt the etuple on the returned query result. On section 2.1 you can find partition example functions.

Using hash

Using a trimmed hash function at first may seem like a solution but not necessary. We are not under control of the output of the hash functions. The two most frequent data in a column may have the same trimmed hash result. Therefore one needs to check the buckets.

Another not enough solution

There was an article about, that I couldn't find it1, was proposing dividing the data into equal size buckets. This works requires preknowledge of the frequency.

The technique was in the simple term normalizing the data into buckets that is differs from your solution. For example; assume that we have 5 different data in a column with the following name and amounts; $\{(a,5),(b,10),(c,20),(d,40),(e,25)\}$ then they proposed to partition into buckets that can contain at most 10 elements;

$$\{(a,5,10), (b,10,10),(c_1,10,10),(c_2,10,10), (d_1,10,10),(d_2,10,10),(d_3,10,10),(d_4,10,10), (e_1,10,10),(e_2,10,10),(e_3,5,10) \}$$ where the sub indexes are different encryption of same value, that can be satisfied by a fixed IV for CBC mode per bucket.

For the query, you have to store the bucket information in your appliaction server. Wait; if attackers see the row count of returned result from the DB, they can identify some buckets. For example, if you query $a$ they can know that it is either $a$ and $b$.

Note 1: If you are not carefully bucketing, the row count will have a similar result for bucketing. For this one may assume that the attacker has limited time on the attack and can say only a few queries may be leaked. This totally depends on your risk analyzes.

Note 2: if the frequency of the data changes over time, you may need to re-bucketing

1 I'll link if I can find someday.


Key management and derivation - Allow changing of the passphrase I'm working on a program, which allows encrypting files before storing it on a cloud service. Currently I'm trying to figure out how to derive and store the keys.

First, I wanted to use a simple passphrase from which the file encryption keys are derived using PBKDF2HMAC and a file specific random salt. This helps providing unique nonce/key pairs, which is required for GCM mode.

Now one additional feature would allow changing the passphrase without re-encrypting and re-uploading all files. The new key derivation would look like this: The passphrase is used to generate a decryption key, again using PBKDF2HMAC with salt. This key can be used to unwrap a master key file, which is encrypted and authenticated using AES-KW. This master key is randomly generated and matches the key size used for file encryption. To generate unique keys for every file the master key is then XORed with a file specific random salt, which acts as a one-time-pad. To change the passphrase one would unwrap the master key and wrap it again using a different passphrase. I know that this technique does not allow revoking passphrases. Any previously used passphrase and master key file can still be used to decrypt the data.

While I am quite sure, that this method is secure (given that all random generated keys and salts are truly random) it seems a bit complex. Is there a reason to avoid the obvious extension to the first method? That is: Changable passphrase decrypts random master passphrase (using GCM mode), which again decrypts the files.

If you want to allow sharing of files between users without sharing their master key and/or pass phrase, you need to allow for something like this extra layer of "indirection" complexity.

However, per-file keys must be crated from HKDF(master_key, file_nonce) or a similar one-way key derivation function. Using simple XOR in this case would expose the master key to anyone with whom a per-file key is shared.

A file share would be simply taking the per-file key and wrapping it using some key known to the "destination" user. The "owning" user doesn't need this information, as they can always re-derive the per-file key using their master key and the per-file nonce.

Note that you will want to use a string such as "per-file key derivation" as the info parameter to HKDF to provide "domain separation". That is, you are using the source key and a nonce as input, and then deriving a key for a specific purpose. You don't want to generate the exact same key and use it for a different purpose later on, you would use for example a different info parameter if you were going to generate something else from the same master_key and file_nonce.


Is the decompression of compressed and encrypted data without decryption also theoretically impossible? We have two communication points in an information system, call them A(lice) and B(ackup).

B has to store encrypted data received from A. The storage of B is encrypted, but not compressed1.

B should have no option to decrypt the data of A2.

However, the data channel between A and B are too narrow, compared to the data volume, making the compression of the communication a requirement. However, encryption maximizes the entropy of the content, making it incompressible.

Another option would be to compress the data, and then encrypt it, but then B should be able to decrypt the data to decompress it.

My first idea was that these requirements are contradicting, as it seems with the practical tools known to me. But I am not sure, how does it look from a theoretical view?

Is an encryption possible, what does not worsens the compressibility of the data in it, despite that it is "enough" secure?

1The reason is here data safety and the support of incremental backups, if it matters (I think, it doesn't).

2It has obvious security reason - a backup storage having all data of a complex network becomes a security bottleneck.

The decompression of compressed-then-encrypted data is not possible without the decryption key, at least for compression and encryption schemes independent of each other. We can make a theoretical argument for that: compression schemes compress only a small portion of possible plaintexts (that happen to be the ones where compression is used in practice), and slightly expand the others (e.g. random data). Encryption makes it impossible to distinguish if two ciphertexts of equal size correspond to plaintext that compression compressed, or not; thus prevents any meaningful decompression.

In the question's situation, the classical solution (described as "Another option" in the question) is to compress at A, then encrypt, then transfer the compressed+encrypted data to B. On retrieval, that same compressed+encrypted data is forwarded from B to A (or A'), decrypted, then decompressed. This reduce bandwidth for backup and retrieval, and storage requirements at B.

B does not need to decompress or decrypt the data at any point: the question's "but then B should be able to decrypt the data to decompress it" is true, but a non-issue. B does not need the key, and (thus) can't decrypt.

What is an issue is direct access to a portion of a huge data set: for many common compression algorithms, that requires transfer of all the data before the point being accessed (sometime, all the data). This is solved by a split-then-compress-then-encrypt strategy, where the plaintext is split in segments that are compressed independently, then enciphered independently (or mostly so). But the splitting tends to reduces compression, especially for short segments.

Another issue is that the compression ratio leaks to an eavesdropper, and that reveals something about the data. This can be a serious issue: for voice, it has been shown to be enough to understand what's being said!


Is the AES encryption scheme CPA secure? Give a 256 bit key space and 128 message space would AES block cipher as the encryption scheme be CPA secure?

You are mistaken about what an encryption scheme is. As CodeInChaos pointed out AES is a primitive and we assume that it is a preudo random permutation. That is an assumption since the way AES is built means that we won't be able to formally prove that it is one. With that PRP we try to build modes of encryption that might or might not be CPA-secure
I encourage you to read Mihir Bellare course notes and especially the chapters about Symmetric encryption and pseudo random functions http://cseweb.ucsd.edu/~mihir/cse207/


Is it possible to cryptographically prove when was the last time a ciphertext was decrypted/encrypted? I want to provide a service that encrypts and decrypts documents and I want to provide the users with proof that I haven't stolen their secret key and read their documents.

I know I can prove when a document was last modified with cryptographic timestamping.  Is it possible to prove a document was or was not encrypted/decrypted in a given time period?

Off the top of my head, I'm thinking maybe there's some way to arrange that some kind of proof-of-work would be needed to encrypt/decrypt a document, but I'm not comfortable with inventing my own crypto.

Updated answer:

No, this is not possible with cryptography.
You have the ciphertext and you have the key.
For all anyone knows, you could have made a copy of those to some other computer and decrypted the ciphertext without telling anyone.
There's no way (with cryptography) to prove you haven't done that.

One approach would be to implement a secure service and hire an independent auditor to audit your code and architecture and certify that you appear to have set things up in a way that protects your customers' data.  You could hire an independent security pro to review your system and write a public report that customers can view.  I don't know if this would give potential customers a better sense of comfort or if it would be worth the money.

The only approach I can think of, to solve this through technical means, would be to use trusted computing.  Trusted computing relies upon trusted hardware (TPMs), and its support for remote attestation would allow you to prove to others what code you are running.  You could publish the source to your software to allow anyone to verify that your software doesn't make a copy of their keys or their data, and use remote attestation to prove that you're using that good software.

However, using trusted computing in this way is extremely complicated.  Trusted computing is bleeding-edge stuff; it's an engineering and management hassle of major proportions.  Moreover, most customers probably won't have the patience, skills, or desire to undertake all of the tasks that would be required to verify that your system works properly.

So, I think there's no technical solution for your problem.  You'll have to rely upon your customer's trust, your reputation, contractual guarantees, and other social/legal means, instead of technical solutions.

A comment: your problem is more an information security problem than a cryptography problem.  Are you familiar with IT Security?

Original answer:

I think you need to define the problem better, to identify who are the principals/participants and what is the threat model.

If the decryptor knows the ciphertext and decryption key and wants to subvert the protocol, you cannot prove that the decryptor didn't decrypt the ciphertext.

The decryptor can prove that he did decrypt the ciphertext (using a zero-knowledge proof of knowledge, possibly with some timestamping).  However, he cannot prove that he read the decrypted message or paid attention to it or acted on it, so I suspect this will be basically useless in practice.

If you can limit access to the ciphertext or the decryption key, then you can prove some partial statements.  For instance, if you don't release the ciphertext to anyone until time $t$, you can prove that no one could possibly have decrypted it before time $t$.  If you know the key, though, you won't be able to prove that you didn't release it before time $t$ (except possibly through use of TPMs / trusted computing), so you'll probably need to be trusted for this to be meaningful.

There are many other possible scenarios -- to propose a specific solution, we'll probably need to know the threat model and requirements in a bit more detail.


Does the SHA-256 sum of a 256-bit key help you crack it? If I have the SHA-256 sum of a 256-bit AES key, can I determine the key any faster than if I merely had a ciphertext and the corresponding plaintext?

The practical answer is "not really". With that said, here's a more nuanced answer:

If you only have a single AES-256 plaintext/ciphertext pair (one block, that is), it's not actually possible to bruteforce the key. AES has a block size of 128 bits, so the probability of any given key having that plaintext/ciphertext pair should be $2^{-128}$. That number is quite small, except for the fact that there are $2^{256}$ possible AES-256 keys, so there should be about $2^{128}$ keys with this plaintext/ciphertext pair. In other words, even a bruteforce search would still leave us with about $2^{128}$ possible keys. With access to a SHA-256 hash of the key, we can instead search for a preimage of the hash, which should leave at most a few possible keys (those keys can then be checked against the AES plaintext/ciphertext pair).

So, in theory, the hash should help an attacker in the above situation. Of course, in practice, it's impossible to search a key space of $2^{128}$, let alone $2^{256}$, so the above has no practical implications.

A more interesting question is whether an attacker who knows both $\text{SHA-256}(k)$ and $(m,E_\text{AES-256}(k, m))$ can combine that knowledge in order to use some more efficient method.

Here's an example of how this kind of problem could happen. Suppose we have two secure cryptographic hash functions $f$ and $g$, each operating on 256-bit inputs and producing a 256-bit output. Let $f(m) = \text{SHA-256}(m)$ and $g(m) = f(m) \oplus m$ (where $\oplus$ is XOR). I haven't checked this example carefully, but $g$ should still be preimage resistant. If an attacker is given either $f(k)$ or $g(k)$, then they should be unable to determine $k$ without a brute force search. However, if the attacker is given both $f(k)$ and $g(k)$, then they can compute $f(k) \oplus g(k) = f(k) \oplus f(k) \oplus k = k$ to recover the original input.

As far as we know, there aren't any interactions like this between SHA-256 and AES-256. This kind of situation definitely deserves caution, since as far as I know, the algorithms were not explicitly designed to avoid interaction between the two. That said, there does seem to be a fair amount of confidence that there will not be any surprising relationships discovered between AES-256 and SHA-256.

In most cases, it's better to derive separate keys for separate uses. Instead of using $k$ directly, use $k$ to compute two subkeys $k_1$ (for AES-256) and $k_2$ (for SHA-256). There are a variety of ways to do this. My favourite is to use HKDF (that RFC is surprisingly readable), which might look like this:

$k_1 = \text{HKDF-Expand}(k, \text{0x01}, 32) \\
k_2 = \text{HKDF-Expand}(k, \text{0x02}, 32)$