Bouncy Castle elliptic curve from explicit parameters (E-521) I'd like to use a curve that's not included in the Bouncy Castle EC named curves spec, specifically E-521.

According to the BC javadocs, you need a few values in order to do this: q, a, and b for the curve, then G and n for the parameter spec.

import org.bouncycastle.math.ec.ECCurve;
import org.bouncycastle.jce.spec.ECParameterSpec;
...
ECCurve curve = new ECCurve.Fp(
            new BigInteger("883423532389192164791648750360308885314476597252960362792450860609699839"), // q
            new BigInteger("7fffffffffffffffffffffff7fffffffffff8000000000007ffffffffffc", 16), // a
            new BigInteger("6b016c3bdcf18941d0d654921475ca71a9db2fb27d1d37796185c2942c0a", 16)); // b
ECParameterSpec ecSpec = new ECParameterSpec(
            curve,
            curve.decodePoint(Hex.decode("020ffa963cdca8816ccc33b8642bedf905c3d358573d3f27fbbd3b3cb9aaaf")), // G
            new BigInteger("883423532389192164791648750360308884807550341691627752275345424702807307")); // n
KeyPairGenerator g = KeyPairGenerator.getInstance("ECDSA", "BC");
g.initialize(ecSpec, new SecureRandom());
KeyPair pair = g.generateKeyPair();

I think q is the field.

Would a and b be base points?

What should be used for G and n?

In order to do this, first convert the Edwards curve to Montgomery form, then to Weierstrass form, per this thread.

But, as the above thread explains, as well as CodesInChaos' comment, this will result in poor performance.

Thanks to CodesInChaos for pointing me in the right direction despite the stupid question.

Also see:

Elliptic Curves of different forms
http://samuelkerr.com/?p=431 which has a nice Python script for going from Montgomery to Weierstrass


Why does CTR mode XOR the plaintext into the output of the block cipher rather than XORing the plaintext into the input of the block cipher? As I understand it, CTR mode essentially turns a block cipher into a stream cipher like so:

        _______________
       |       |       |
       | nonce |   i   |
       |_______|_______|
               |
        _______V_______
       |               |
       |  block cipher |
key -->|  (encryption) |
       |_______________|
               |
               V
plaintext --->(+)---> ciphertext

But by turning it to a stream cipher, one must be very careful not to reuse a nonce.  It seems like it would be safer to do it like this:

        _______________
       |       |       |
       | nonce |   i   |
       |_______|_______|
               |
plaintext --->(+)
               |
        _______V_______
       |               |
       |  block cipher |
key -->|  (encryption) |
       |_______________|
               |
               \---> ciphertext

While it still would be unwise to reuse a nonce, it seems like the effects would be less devastating if it were misused in this way.  I see one main disadvantage, and that's that with the first formulation, only the encryption part of the block cipher need to be implemented, whereas with this second formulation, both encryption and decryption need to be implemented.

My questions are:

Does this latter mode of operation have a name?
Are there any obvious weaknesses in this latter mode?
Are there any other reasons why CTR is defined the first way?

There are some serious problems with this design that would preclude it from being standardized, so it probably does not have a name.
The 2 visibly main flaws are as follows:

If the plaintext follows a pattern similar to the block counter, the
block cipher inputs may repeat, exposing information about the
plaintext (exact same issue as reuse of nonce, but could happen
multiple times per message, example given at end)
Plaintexts with a length not equal to a multiple of the block size
would need the length included with the ciphertext in order to
decrypt, as the full block output is required to decrypt, or they
require padding of the last block.

The structure of CTR has several desirable properties that your example does not.
It allows encryption without padding or additional length data to decrypt. It allows
precomputation of the cipherstream prior to the plaintext being available, which
can mean huge speed improvements if there is enough memory available and message
plaintext is available at irregular intervals. CTR can also be processed in a highly
parallel manner, and requiring the plaintext as an input could slow that down if it
is not available immediately.

Here is an example of a duplicate block:

"THIS IS A TEST SIMPLY TO EXPLORE WHAT WILL HAPPEN IF WE ENCRYPT THIS IS A TEST WITHOUT A SECURE MODE"

Block 0 plaintext = "THIS IS A TEST S", block 4 plaintext = "THIS IS A TEST W"

In this example, the input to the block cipher will be the same for block 0 and 4 for this message, regardless of the nonce, as "W" becomes "S" when xor'd with the block counter for block 4. Lots of data types have similar types of repeating information with only small changes, such as image files and executable programs. This is almost as bad as ECB for potential plaintext recovery.


Is there any block-cipher, format-preserving or similar encryption method with known cycle size? (without short-cut, with known source/runtime vars) E.g. given a $n$-bit message $m_0$ and an encryption function $f$
After applying the function $c$ times it will result in $m_0$ again.
$f^1(m_0) = f(m_0) = m_1$
$f^2(m_0) = f(f(m_0)) = f(m_1) = m_2$
..
$f^c(m_0) = m_c = m_0 $
On top of that an inverse function $f^{-1}$ with about equal computation time should exist as well. Also no short-cut in computing $m_i$ is allowed. It always either require the knowledge of  $m_{i-1}$ or $m_{i+1}$. Given two messages $m_i$, $m_j$ there should be no easy way to compute the difference $|i-j|$
Some example but with unknown cycle size would be AES.
I'm looking for an encryption method with known cycle size $c$ for all $m_0 \in  \{0,1\}^n$
.
Further notes:

$m_0$ will be a random number. An additional (fast) function is allowed
which select only numbers with certain properties

instead of $m_0$ a small known offset $k$ is allowed as well. With this
$m_c$ can be different to $m_0$ but $m_{c+k} = m_{k}$

'hacking'-time should scale linear with cycle size $c$

(Edit) Update: Additional requirements

an attacker has full access to the source code and runtime variables. All computations done at the local computer
given two valid random messages $m'$ the chance should be high they are part of the same cycle (lets say $>10\%$ or at least $>0.4\%$). Or in other words different cycles are allowed but not much more than $10$ or $256$ as max limit (lower is better, except $<20$ would even be better than just $1$)
exact cycle size don't need to be known. An approximation $\pm 50\%$ is sufficient (but if it contains multiple cycles those should be similar to each other ($\pm5\%$) )

Other than in most cryptography problems the relation in between should be encrypted not the messages themselves.

CAUTION: The following matches the requirement "no short-cut in computing $m_i$ is allowed. It always either require the knowledge of  $m_{i-1}$ or $m_{i+1}$. Given two messages $m_i$, $m_j$ there should be no easy way to compute the difference $|i-j|$" only with respect to an adversary not knowing the key. That goes straight against the added requirement that an adversary has "access to runtime variables".

Well make an explicit construction from an $n$‑bit block cipher $E$ with the desired keyspace. Note $D$ the matching decryption.
Make a public partition of the blockspace $\{0,1\}^n$, assimilated to $[0,2^n)$ by e.g. big-endian convention, into intervals of size $c$ or slightly more according to the allowance for $k$. When $c$ is a power of two (e.g. $c=2^n/8$), that can be $2^n/c$ intervals of size $c$. When $\left\lfloor2^n/c\right\rfloor\ge(2^n\bmod c)$ [thus including any case with $c\le2^{n/2}$ ], that can be $\left\lfloor2^n/c\right\rfloor-(2^n\bmod c)$ intervals of size $c$, and $2^n\bmod c$ intervals of size $c+1$.
Define $h$ the bijection on $\{0,1\}^n$ that, to $x$ in a certain interval of said partition, associates the next integer in said interval if that's still in said interval, or the first integer in said interval otherwise. When $c$ is a power of two, that can be $h(x)\underset{\text{def}}=c\left\lfloor x/c\right\rfloor+(x+1\bmod c)$.
Define $f\underset{\text{def}}=D\circ h\circ E$. That is $f$ the bijection on $\{0,1\}^n$ with $f(x)=D(h(E(x)))$. That $f$ has the property "After applying the function $c$ times (within allowance) it will result in $m_0$ again" thought in the question, and has matching decryption $f^{-1}=D\circ h^{-1}\circ E$.

I conjecture that under the ideal cipher model for $E$, the resulting block cipher $f$ is secure when the number of (adaptive) queries an adversary can make remains negligible compared to $c$.
One slight implementation difficulty is avoiding side-channels in the implementation of $h$ and $h^{-1}$.


How are hash functions analyzed in an open competition? There was a well-known SHA-3 Competition held between 2007 and 2012, where the winner would be standardized as SHA-3. Now that the competition has ended and NIST has released reports on the different rounds. From the Round 3 report it looks like all five finalists are fairly competitive. It'd be interesting to understand why Keccak stands out in the competition and becomes the winner.

In the report, NIST mentioned several aspects of security analysis such as domain extenders, security margin, etc. However, NIST also admits that no  finalist was considered to be a clear winner or loser from the security analysis in the same report. What kinds of cryptanalysis methods do we have at hand? Given the fact that no candidate algorithm is broken, how do we determine (or gain confidence) that one is better than another?

To assert the security of a Cryptogaphic primitive, one usually uses differential cryptanalysis (that is the first tool but not the sole one).
From the report you can read:
1. Security

Grøstl and JH have differential properties that extend through most
or  all  of  the  rounds,  while  the  remaining  three  candidates  only  have  distinguishers that extend through about half of their rounds.

and also :

Keccak  received a  significant  amount  of  cryptanalysis,  although
not  quite  the  depth of  analysis applied to BLAKE, Grøstl, or Skein. This cryptanalysis left Keccak with a huge security margin –only five out of its 24 rounds has been broken by a near-collision attack. Keccak’s large security margin,  after  significant  cryptanalytic  effort,  suggests that  Keccak  will  remain  secure  in  the future.

The idea here is to have a kind of security feeling between the different kind of constructions. I was recently participating in the design of a new scheme, we were paying a really big attention to the constants we were choosing in order to avoid differentials (or even worse, iterative differentials)...
2. Speed and Hardware support
All the finalist have a the speed required, while the ARX designed scheme have the software advantage, using hardware instructions leads to even faster hashing. Thus Keccak being hardware friendly helped it to get the edge.

Keccak provides an excellent set of performance trade-offs – it is broadly competitive with SHA-2 in software, while providing much better throughput/area performance in hardware.

3. Scheme
Keccak also provide a new kind of scheme that is completely different to the usual Merkle–Damgård construction: the Sponge construction.
4. Conclusion

Keccak has a large security margin, good general performance, excellent efficiency in hardware implementations,  and  a  flexible  design.  Keccak  uses  a  new  “sponge  construction”  domain  extender,
which  is  based  on  a  fixed  permutation,  that  can  be
readily  adjusted  to  trade  generic security strength for throughput, and can generate larger or smaller hash outputs, as required. The
Keccak  designers  have  also  defined  a  modified  chaining  mode  for  Keccak  that  provides authenticated encryption.

TL;DR:
Lets say that you want to buy a new computer. You have $Computer_1$ and $Computer_2$ in front of you. Both have:

the same price,
the same CPU (speed),
the same RAM size (security),

but $Computer_2$ also provides you as a plus PCIe card support (sponge construction). You know that at the moment you don't need that PCIe support... Which one do you chose ? I get the feeling that you would go for the second one because you don't know what the future is made of and you will want to upgrade if possible later and that might use PCIe.


About numberical comparison in Attribute based encryption The first CP-ABE scheme in [BSW07] gave an example how to present a numberical comparison (e.g., a<11) to a Boolean access tree. But it seems like this feature is not implemented in Charm.

In the paper, the access policy a<11 is presented as:

("0***" OR ("*0**" AND ("**0*" OR "***0")))

And one attribute a=9 is split to 4 attributes for encryption:

"1***", "*0**", "**0*" and "***1".

My question is:

Is it true that the access policy only use "0" bit string? If yes, it is safe enough to encrypt the message with 2 attributes "*0**" and "**0*" (i.e., "1***" and "***1" are not needed)?
Do you know a reference that describes how the choice of gates are made?

Is it true that the access policy only use "0" bit string? If yes, it is safe enough to encrypt the message with 2 attributes *0** and **0* (i.e., 1*** and ***1 are not needed)?

First off, a numerical attribute such as *0** is nothing more than the ASCII string "*0**" which is then hashed.

The following is a user's secret key:

$$\text{SK}=\left(D=g^{\left(\alpha +r\right)/\beta}, \forall j\in S:D_j=g^r\cdot H\left(j\right)^{r_j}, D^{'}_j=g^{r_j}\right)$$

All $r$ and $r_j$ are chosen randomly and independently which means that the attributes ($D_j$ and $D^{'}_j$) of a secret key are not linked together in any way.

A user can or the attribute authority can safely remove multiple attributes without invalidating the whole key. The remaining attributes can still be used to decrypt ciphertexts provided that the remaining attributes satisfy the access policy. This is true for (almost?) all schemes that utilize monotonic access structures as is the case with BSW-ABE.

However, this cannot be true for schemes that utilize non-monotonic access structures. Such access structures can be used to model negation of attributes. In such schemes, all attributes are linked together. If they weren't, then it would be possible for a use to remove a negated attribute and be able to decrypt more ciphertexts.

1*** and ***1 are not needed to satisfy the policy: a<11. However, if the attribute authority removes all attributes containing a 1, then it would limit the expressiveness of the access policy. Furthermore, access policies containing attributes with a 1 can be reduced to improve the policy evaluation performance.

  Do you know a reference that describes how the choice of gates are made?

This is off-topic. I don't know a natural language description of this, but you can certainly try to deduce the algorithm by looking at the code. cpabe has the original implementation of that in C and JCPABE has an extended implementation of that in Java.


Why AEAD instead of encrypting with a simple hash? I hear a lot about AEAD encryption (GCM, EAX, ...). Why is it unsecure (it seems to be as AEAD exists)
to do do that: Imagine a block of data, hash it, append the hash to the data, then encrypt the result (data + hash) ? I would intuitively think that it is not possible to currupt the data then corrupt the hash to hide the changes as both are encrypted.
EDIT: I found something that that made me realise the utility of the header in AEAD, it stores informations like the algorithm used, however I don't need a header in my case, so is it ok to encrypt(data + hash(data))?

So suppose we define our encryption scheme as follows:
$E(K, M) = \operatorname{CTR}(K, M || H(M))$,
where $H$ is a hash function (e.g., SHA2-256), and $\text{CTR}$ is the counter mode-of-operation of some underlying blockcipher (e.g., AES-128). Now suppose we observe the ciphertext $C = C_M || C_T $ of a known message $M$ and want to modify some bits in $C$ so that it decrypts to some other message $M'$. Here $C_M$ denotes the part of the ciphertext which contains the encrypted part of the message itself, while $C_T$ contains the encrypted part of the hash of the message. In more detail:
$C = \overbrace{10000110100011}^{C_M} || \overbrace{1100010}^{C_T}\\
\phantom{C} = \overbrace{00100011110010}^{M} || \overbrace{0010100}^{T = H(M)} \\
\hspace{3.5cm} \oplus \\
\phantom{C =}\ \underbrace{10100101010001 || 1110110}_{\text{CTR keystream}}$
For simplicity, suppose we want to create $M'$ by flipping bits 1, 3, and 13 in the original message $M$. First we start by simply flipping bits 1, 3, and 13 in $C_M$. This gives
$C' = \overbrace{\color{red}{0}0\color{red}{1}001101000\color{red}{0}1}^{C_{M'}} || \overbrace{1100010}^{C_T}$
When the $C_M'$-part is decrypted, this will yield $M'$ due the properties of the CTR mode-of-operation:
$\overbrace{\color{red}{0}0\color{red}{1}001101000\color{red}{0}1}^{C_{M'}}\\
\hspace{1.5cm} \oplus \\
10100101010001 \dots \quad (\text{CTR keystream})\\
\color{red}{1}0\color{red}{0}000111100\color{red}{0}0 \quad = M'$
However, now the hash won't match anymore. So we also need to modify $C_T$ into $C_{T'}$ such that when $C_{T'}$ is decrypted it yields $T' = H(M')$, i.e., the correct hash of our modified message $M'$. But this is easy since we know $M$ and $C_T$: first compute $T' = H(M')$ and suppose $T$ and $T'$ differs in bits, say, 2, 3, and 7, i.e. $T' = H(M') = 0\color{red}{10}010\color{red}{1}$. Now we simply flip bits 2,3, and 7 in $C_T$ to get $C_{T'}$, and this will decrypt to $T'$. Thus our full ciphertext is:
$C' = C_{M'} || C_{T'}$,
which when decrypted yields:
$C' \oplus \text{CTR keystream} = M' || T' = M' || H(M')$.
Note that this attack won't work as-is on another mode-of-operation which doesn't provide integrity. However, analogous attacks are usually easy to come up with. For example, see here for the analogous attack on CBC-mode.
In conclusion: your suggested scheme, albeit natural, fails to provide integrity. That is why modes like GCM, CCM, and EAX exist.


Is there a feasible method by which NIST ECC curves over prime fields could be intentionally rigged? The NIST elliptic curves P-192, P-224, P-256, P-384, and P-521, prescribed in FIPS 186-4 appendix D.1.2, are generated according to a well defined process, but using an arbitrary random-looking seed value of 160 bits. For this reason a page of DJB's website calls them

  Manipulatable: The curve-generation process has a large unexplained
  input, giving the curve generator a large space of curves to choose
  from. Consider, for example, a curve-generation process that takes
  $y^2=x^3-3x+H(s)$ meeting various security criteria, where $s$ is a large
  random "seed" and $H$ is a hash function. No matter how strong $H$ is, a
  malicious curve generator can search through many choices of $s$,
  checking each $y^2=x^3-3x+H(s)$ for vulnerability to a secret attack;
  this works if the secret attack applies to (e.g.) one curve in a
  billion.

Is that feasible? More precisely, is there an openly known method making that feasible? If not (as I suspect), is there additional rational argument (or even informed opinion) about the feasibility, or in-feasibility, of such intentional rigging, and the associated effort? Or perhaps, some more info on how the seeds have been chosen?

Note: I have not found a deep study of that precise point in the answers to these related questions.

I'd say that the whole argument hinges around a "secret attack" that possibly the NSA may know of, enabling them to break some instances of elliptic curves that the rest of the World considers as safe, because the secret attack is, well, secret.

This yields to the only possible answer to your question: since secret attacks are secret, they are not known to people who are not in the know (duh), and thus there is no "openly known method making that feasible", by definition. Since we don't know, in a mathematically strong sense, whether such a thing as a "secure elliptic curve" can exist at all, "no known attack" is about the best kind of security assumption that you will ever get.

Now if we look closely, we may note that the NIST curves have been generated with a strong PRNG: given a seed value $s$, the curve is $y^2 = x^3 + ax + H(s)$ with $a = -3$ (a classic value for this parameter; it gives a slight performance improvement for point doubling in Jacobian coordinates) and $H$ a deterministic PRNG. Here, the PRNG is what is described in ANSI X9.62 (section A.3.3.1) and is based on an underlying hash function, SHA-1 in the case of the NIST curves. For practical purposes, we can consider this PRNG to act as a random oracle. What this means is that even if NSA knows of some secret method to break some elliptic curves, they would still have had to do quite some work in order to find a seed which yields a curve which "looks good" (in particular, a curve with a prime order) and yet is among the set of "breakable curves". For instance, if only one curve in $2^{100}$ is weak against this unknown attack, then NSA would have faced an average of $2^{100}$ SHA-1 invocations (at least), a ludicrously high number.

Therefore, unless we add to the speculation another "unknown attack", this time against SHA-1 (specifically, the PRNG of X9.62 A.3.3.1 with SHA-1 as hash function), we must assume that if the NSA knows of a secret breaking method for some elliptic curves and used it to rig the NIST curves, then that method must be able to break a non-trivial proportion of possible curves. So we are not talking about a handful of special-format weak curves, but something really devastating.

We have no proof that elliptic curves are inherently strong, however we have some "intuition" that the apparent strength of curves against discrete logarithm is linked to the notion of canonical height (see also this presentation). If that intuition is correct, then there cannot be more than a very small proportion of "weak curves" (e.g. the curve $y^2 = x^3 + ax$ is weak if the base field is a 256-bit field); chances of hitting a week curve with a randomly generated $b$ parameter would be extremely remote. In that sense, the postulated "unknown attack" of NSA, in order to be usable to rig generation of the NIST curves, would also have to prove wrong the intuition of many mathematicians specialized at elliptic curves.

I think that the paragraph above is the closest you can get to a mathematical rational argument about why the NIST curves are not rigged.

I do have a second argument, though, which I find rational, though it is from economics, not mathematics: we cannot measure how secret a secret attack can be. Remember that the primary users of US-government-specified cryptographic parameters are US corporations; a primary goal of NSA is to protect these corporations against foreign enemies (competitors). Purposely pushing the use of rigged curves, where the rigging uses the knowledge of some as yet unpublished attack, is very risky: this will hold only as long as some half-crazed mathematician from the deepest of Siberia does not find the same attack. As Leibniz explained, scientific discoveries seem to happen to the whole World at the same time; everybody thinks the same things simultaneously. That's a notion which is well-known to academics: publish fast or perish.

So if the NSA does its official job properly, then it must not promote the use by US businesses of tools which are known to be flaky and thus potentially exploitable by anybody. NSA cannot ensure that it has a monopoly on mathematics...

This contrasts with the DualEC_DRBG backdoor, where there is a known method to rig it (by careful choice of the two involved curve points), but, crucially, it is equally obvious that people who did not get to choose the curve points cannot exploit the backdoor. That is the kind of backdoor that NSA can safely promote, because they know they can keep it under their exclusive control.

This also contrasts with the 56-bit DES key, where the backdoor was obvious (key amenable to exhaustive search) but could be exploited only through accumulation of sheer processing power; in the 1970s, USA had a known big advantage over USSR in that field, and they knew it. When computing power became available too generally, they switched strategies and decided to promote strong encryption methods (3DES, then AES): they prefer it when their enemies cannot break encryption, even if that means that they cannot break it either.


How to test if a number is a primitive root? How to test if a number is a primitive root, assuming the $\text{mod}\enspace m$ where $m$ is a prime? And if not?

Is it not enough if the number is relatively prime to the modulus or prime?

I'll write down what I've done and would like to know if I'm right:

I tested if the modulus is prime with the Rabin-miller test. It was prime, so I used python program to factor $m-1$ since $\phi(m) = m - 1$. It printed out $2$ and another prime. So then I calculated $g ^ q \bmod (m-1)$ for all factors where $q$ is the factor and they were $\neq 1$. So $g$ should be a generator, right?

For all $m$, if $m$ is a positive integer then

$g$ is a primitive root mod $m$ $\;$ if and only if

$0\leq g< m$ $\:$ and $\:$ $\operatorname{gcd}(\hspace{.015 in}g,\hspace{-0.01 in}m) = 1$ $\:$ and $\;\;$ for all prime factors $q$ of $\phi$$(m)$, $\: g^{(\phi(m))/q} \not\equiv 1 \pmod m$.


Academic papers on ECDSA security What are the most authoritative papers on the security analysis of ECDSAs?

I`m mainly looking for comparisons of how secure different curves are considered to be, what potential methods are there of discovering a private key based on the public key, and possibly the methods of cracking the entire curve.

Moreover, papers that relate to Koblitz curves are preferred.

I'm just reading the book Advances in Elliptic Curve Cryptography, and Chapter II (by Dan Brown) is about provable security of ECDSA.

It lists some necessary conditions for the ECDSA components (group, conversion function, RNG, hash function), each with an associated forgery. For example, the group has to be resistant against discrete logarithms, as well as semi-logarithms.

With some additional conditions, we also get stronger unforgeability results, e.g. modeling the hash function as a random oracle means that semi-logarithm resistance also implies active existential unforgeability (i.e. the strongest result). Alternatively, modeling the group as an ideal group permits using only the necessary conditions on the hash function.

The book also contains sketches for the proofs.

Of course, this says nothing about whether a specific elliptic curve or class of curves really has the necessary semi-logarithm resistance, which seems to be what you really need.


HMAC versus encrypted hash When encrypting a message with a symmetric key, it seems like the best practice is to first encrypt the message, then run the cipher text and key through HMAC, appending the result to the cipher text. The receiver can strip off the hash, HMAC the cipher text and key, and verify that the hashes match. This tells the receiver that the person who made the HMAC had the secret key, and that the message was not tampered with.

But why can't the sender instead hash the cipher text, then encrypt the hash with the secret key? The receiver would decrypt the hash with the same key, hash the cipher text, and verify that the hashes match. Wouldn't this give the receiver the same assurance, and isn't this how it's done in public key cryptography, when the sender wants to sign the cipher text?

$\newcommand{\concat}{\mathop{\Vert}}\newcommand{\AES}{\mathrm{AES}}$You are asking whether you can take a secure—specifically, IND-CPA—message cipher $E_k$, say AES256-CTR, and a fixed public collision-/preimage-/2nd-preimage-resistant hash function $H$, say SHA-256, and compose them in the form $$c \concat E_k\bigl(H(c)\bigr), \quad \text{where} \quad c = E_k(m)$$ to encrypt a message $m$ with a key $k$, and get a secure authenticated encryption scheme—specifically, IND-CCA3.  (I'm eliding details of nonces and input separation for the moment.  Figuring out how to fit them into this post is left as an exercise for the reader.)

This looks awfully close to encrypt-then-MAC, with the putative MAC $(k, c) \mapsto E_k\bigl(H(c)\bigr)$.  Unfortunately, on its own, that is not a secure MAC.  However, the input $c$ is an encrypted message, so that analysis doesn't end the discussion.

This also looks close to encrypt-and-MAC with the putative MAC $(k, m) \mapsto E_k\bigl(H(E_k(m))\bigr)$, which maybe is secure but it would take careful analysis to say, partly because it's not used in isolation—you also reveal $E_k(m)$ to the attacker.  I haven't done the analysis and I don't know anyone who has, so I won't say one way or another whether this is secure.

All that said, if you change this a little bit by using a secret choice of hash function $H_r$, giving $$c \concat E_k\bigl(H_r(c)\bigr), \quad \text{where} \quad c = E_k(m),$$ then you get the structure of, e.g., AES-GCM, which is a secure authenticated encryption scheme.

The family of functions $H_r$ in AES-GCM is called GHASH, and it isn't even preimage-resistant, let alone collision-resistant, to anyone who knows the index $r$—but $r$ is secret, perhaps derived alongside $k$ from some master key $k_0$.  Since its security requirements are more modest—in technical jargon, it must be an $\epsilon$-almost-universal hash family—GHASH is very fast and cheap to evaluate compared to SHA-256 or any other collision-resistant hash function, as long as you have fast binary polynomial multiplication and reduction.

(In software, you need special CPU instructions to do this fast in constant time, which are not widely consistently adopted in CPU instruction sets or standard programming languages, just like you need special CPU instructions that aren't widely consistently adopted to evaluate AES fast in constant time.  But you could use another stream cipher such as Salsa20 and another hash family such as Poly1305 which works in a prime field—these require no special CPU instructions to evaluate fast in constant time.  Note, however, that this is a little different from NaCl crypto_secretbox_xsalsa20poly1305, which is structured to also defend against a reforgery attack on Carter–Wegman many-time authenticators like AES-GCM uses.  For an even more variegated menagerie of authenticated encryption schemes, check out the CAESAR competition.)


Why is cryptographic model not considered formal methods? I have just started looking at different methods for analyzing the security of cryptographic protocols. According to my reading, there are two main approaches in this area. The first approach is so-called Dolev-Yao (or formal) model, where cryptographic messages are represented as symbolic terms in term algebras. The second one is closer to real implementations of cryptographic protocols, where primitives are seen as probabilistic algorithms and the attacker is a polynomial-time probabilistic Turing machine. The security of cryptographic in the latter approach is often defined as security games.

My confusion is that the former approach is referred as formal methods in the literature, but not the second one. Looking at the definition of formal methods in Wikipedia, it says "formal methods are a particular kind of mathematically based techniques for the specification, development and verification of software and hardware systems". According to this definition, I do not see why the second approach cannot be seen as formal methods. In fact, the first one is just one abstract level higher than the second one and provides weaker security guarantees. So to my understanding, they are both formal verification techniques for security protocols, and therefore should be both seen as formal methods. Could anyone help me to clarify this?

Disclaimer: I'm currently doing a PhD in Formal Methods and Cryptography and I'm not really sure of my answer.

The first application of Formal Methods is to be applied to pieces of software. The goal is to prove security properties on them. These are usually safety critical softwares (those you find in planes, trains, nuclear facilities...) This field is called Software Verification.

I mostly consider Formal Method as a way of arguing, a way of thinking or proving. In this case, Formal means without ambiguity. Thus you could consider any approach with such mindset in the domain of Formal Methods.

To answer your question, [from my point of view,] both approaches qualify as in the Formal Methods (and I don't see why they should not).

E.g. Easycrypt, a tool to make proofs in game based model and probabilistic models is based on Why3. And I'm pretty sure that Why3 is part of the Formal Methods approach using theorems provers and SMT solvers such as Alt-Ergo or Z3.


Homomorphic/Paillier crypto system for use case?: overflow for multiple counter exponent possible? Different cipher factor needed all the time? Recently I read about homomorphic cryptosystem. They might solve a problem. To do this there need to be some modifications from standard version.

Using Paillier here but a solution for other also fine.

E.g. given two cipher text $c_1,c_2$ with generator $g$ and factors $r_i$:
$c_i = g^{m_i} r_i^n \mod n^2$
$n=p\cdot q$, with $p,q$ primes

Now if they get multiplied
$c_1 \cdot c_2 \equiv g^{m_1} r_1^n \cdot g^{m_2} r_2^n = g^{m_1+m_2} (r_1r_2)^n \equiv g^{m_1+m_2} r^n \mod n$
The factors $m_1, m_2$ get added. If they get $n$ or larger they start over again. In normal use case that is prohibit by selecting a larger $n$.

Now I'm looking for a way to get this overflow for a special kind of $m$. Image an election with 3 candidates and their votes counted in one exponent.
E.g. candidate 1 has 5 votes, 2 has 6 and 3rd 42 votes, exponent of $g$ could be ${005006042}$. In another region it's ${133700123}$. If ciphers multiplied those exponents get added and sum up all votes for each single candidate. This exponent form only allows up to $999$ total votes for each candidate (assuming the total exponent number is $<n$).

In my use case there will always be some exponent overflow, no matter how big $n$ is. But instead the whole exponent it should be one for each candidate.
E.g. $700.800.900$ and $400.100.200$ should add up to $100.900.100$ instead of $1100.901.100$.
Is there a way to have multiple overflows in exponent? Or an alternative way for multiple counters?

Elements also get subtracted, so there need to be an underflow as well.

As far as I understood each cipher can(should?) have its own $r$. For my use case it need to be associative in some way. It need to be the same cipher independent of order and direction. E.g. adding 5 votes to a cipher should result in same ciphertext as adding 5 times one vote to the same cipher. That should work if there is only one $r$ (for each candidate)(+$r^{-1}$ for subtraction). But a single $r$ works against security, or?
You know another way to achieve this? Some way to check if two different $c_1\not= c_2$ have the same exponent without encrypting it would also work.

It won't work anyways because even in case it would be secure with one $r$ and the exponent can get overflow for each candidate the ciphertext with same exponent will be different after an overflow happened.

  Do you really mean deterministic (that is, one particular m always maps to the same c)

Given two ciphertext with same exponent ($\mod n$) before and after overflow. The 2nd would be result after adding $n$ times one vote to first.
$c_0 = g^0 \cdot r^n \mod n^2$
$c_{i+1} = c_i \cdot c_{add+1} = c_i \cdot g^1 \cdot r^n = g^i \cdot r^{in+n}$
$c_a=g^a \cdot r^{an+n} \not=g^{a+n} \cdot r^{an+n^2+n}=c_{a+n}$ $\mod n^2$
(because $r^{\phi(n^2)}=1$ and $n^2 \not = \phi(n^2)$  )
Decryption resolve in same $a$ but exponent of $r$ is different and with this those two ciphertexts.


What is the difference between uniformly and at random in crypto definitions? Very often in the description and analysis of a cryptographic protocol there is a need for a an element $k$ that is sampled

  uniformly AND at random.

Is there a redundancy in the definition with uniformity and randomness?

If no what is the rigorous difference of uniform and random? Does it mean that the numbers of the distribution are random (they came from PRG) and each of them are picked up uniformly--meaning with equally probability?

If you sample a random element, then you sample it according to some distribution.

Uniformly then means that you sample from the uniform distribution, i.e., you sample it from a set where drawing each element is equally probable. Let us assume you have a set of 4 elements, then sampling uniformly at random from this set, every element is drawn with probability 1/4.

However, you could also sample a random element according to some other distribution, e.g., say two elements have probability 1/3 to be drawn and the remaining elements have probability 1/6 each.


find solutions that solve the equations I am implementing a timing attack on RSA for school and I need to generate two sets of messages $Y$ and $Z$ for which holds:

$ (Y^d \mod N) \cdot Y < N $ and
$ (Z^d \mod N) \cdot Z > N $

where $d$ and $N$ are known. How can I efficiently find solutions for $Y$ and $Z$?

I have tried using a random function but it takes too long to complete or it doesn't complete at all.

Finding a $Z$ is easy. This condition is fulfilled for all $Z>n/2$, and most of the smaller values of $Z$ too. There are only a few values fulfilling the condition for $Y$, and since this is almost the negation of the condition for $Y$, most numbers will fulfill it.

When looking at the condition for $Y$, you can model $Y^d \mod N$ as a random number between 0 and $N$.
This leads to a success chance of approximately $ 1/Y $.

Thus a good strategy for finding a $Y$ is starting with $ Y = 2 $ and incrementing by one on each attempt, i.e. trying 2, 3, 4,... This should find a number fulfilling $ (Y^d \mod N) \cdot Y < N $ quite quickly.

Total chance of finding an $ Y \le n$ is:

$1-\Pi^n_{i=2}(1-1/i) = $

$1 - \frac{(n-1)!}{n!} = $

$ 1- 1/n $

Which quickly converges to 1


Cracking a key using a combination of partial keys As part of a cryptanalytic attack I've carried out, I used a divide-and-conquer strategy to divide the secret key $k$ into several equal-sized partial keys $k = {k_1, k_2, ...}$.

The attack works successfully against these partial keys, and outputs a list of possible values for each partial key along with their likelihood. The list is ordered by likelihood such that the first value of the output is the attack's best guess for that part of the key.

This likelihood also tells me what kind of confidence exists in each partial key -- a certain high likelihood value means that the correct partial key will almost surely be in the first 10 best guesses; some other lower likelihood value means that the partial key guesses aren't as good and you only expect to find the correct partial key after testing 120 guesses.

What is the optimal strategy (in terms of number of attempts) to combine the partial key guesses into a guess of the entire key?

For this, let's imagine that, from the lists of partial key values, I want to build a list of possible (complete) key values, ordered by likelihood.

My best guess for the complete key is, trivially, the best guess for each partial key, and thus that's the first item in my list. For the second item in that list, I will take the partial key which has less likelihood, and instead of using the best guess, I'll try the second best guess and see if that works.

Now, how do I proceed to complete my list? I've already tried the second best guess of the least confident partial key, but indeed I could continue, and just brute-force the least confident partial key. After, I could do so for every other partial key, from least confident to most confident.

This approach is sensible, however, it may not be optimal. It seems to me that if I know the expected position of the correct value for the lists of each partial key, perhaps I don't actually need to test all the positions of the least likely partial key first, and actually, one of the more confident partial keys perhaps has the correct answer as the second best guess.

If I can define which kind of strategy is optimal, then I can finally reach my goal of computing the expected position of the correct value of the key in the candidate list of complete keys, in terms of the expected position of the correct values for each partial key. This is because my final goal is to get some measure of entropy (guessing entropy, for example) for the complete keys calculated from the partial keys.

If you know any scholarly sources (conference papers, articles, books, etc. for further reading) for this kind of problem and possible solutions, that'd be greatly appreciated.

If you know the probabilities $P(k_1), P(k_2), \dots, P(k_n)$ of candidate keys $k_1, k_2, \dots, k_n$, the fact that the probability mass function $P$ factors into a product for independent subkeys is irrelevant; if you sort the $k_i$ by descending $P(k_i)$ so that the most probable answer is $k_{\pi(1)}$ with probability $P(k_{\pi(1)})$, the second-most probable answer is $k_{\pi(2)}$ with probability $P(k_{\pi(2)}) \leq P(k_{\pi(1)})$, etc., then this minimizes the expected number of guesses because each successive guess covers the maximal fraction of probability mass left unguessed so far.

Specifically, the expected number of guesses is $$\sum_{i=1}^n i\cdot P(k_{\pi(i)}).$$  Any transposition of the weights that puts a higher weight $P(k_{\pi(i)})$ on a larger number $i$ will lead to a higher weighted sum.


how does hkdf generate 2 keys? Hi I am new to cryptography and am confused as to how HKDF generates two separate keys from one single key/password. Is it as follows?

Key 1: HKDF-Extract(salt, IKM) -> PRK

Key 2: HKDF-Expand(PRK, info, L) -> OKM

OR is it that

Key 1: HKDF-Extract(salt, IKM) -> PRK

Key 2: SHA-512(PRK)

Where Key 2 would be HMAC-key?

Could it be that one key is derived using pb-kdf and hmac-key is derived using hkdf?

The extract and expand steps of HKDF are just two phases of one algorithm run. The PRK created my the extract step is not meant to be used as a key (even though it would not be a problem securitywise).

So if you need to derive two keys from one IKM value, you run the whole algorithm (that is: extract & expand) once with an appropriate info string (like "key1", for instance) and then you run the whole thing a second time with the same salt and IKM but a different info string (like "key2").


Different literature padding for Merkle-Damgard I don't think this question addresses what I want to ask. I was taught that the Merkle Damgard scheme worked as in this picture:

Here I assume that we are inserting a pad in filling the last block of the message. Probably, we set a new block if all blocks are full. This is a particular case for SHA1 but I don't think it makes a difference.

However, in the book Introduction to Cryptography by Hans Delf and Helmut Knebl they propose the following scheme:

If one has a function $f:\mathcal{B}^{N+r} \rightarrow \mathcal{B}^N$ and wants $h:\mathcal{B}^{*} \rightarrow \mathcal{B}^N$ then one takes $m \in \mathcal{B}^{*}$ and proceeds as follows:

$m' = m||1000 \cdots \in \mathcal{B}^{kr}$ where you add enough zeros to complete the block. Then one divides $m' = m_1||m_2||\cdots||m_k$ with $m_i \in \mathcal{r}$ and adds a block $m_{k+1}$ which contains the initial size of $m$ with the rest of the block filled with zeros.

What I ask for

I could go probably to Merkle and Damgard's original paper. But I don't know if their padding scheme was ok since I see that there has been some discussions on it. So I ask, are this paddings schemes both correct or has any of them proved insecure?

The customary (and secure) padding is the one you have been taught: at the end of the message add a single 1 bit, then just enough (possibly none) 0 bit(s) to reach the end of a block less the size devoted to the length (64-bit before the 512-bit limit for MD5, SHA-1, and SHA-256; 128-bit before the 1024-bit limit for SHA-512); then add the length (little-endian for MD5, big-endian for SHA-x).

The padding that you describe based on Hans Delf and Helmut Knebl is equally secure, but often uses one more block than the other.


Mixing xor with modular addition Having two known constant A and B, and one unknown X, can we solve the following equation :

(A xor X)+ X=B

where xor is the bit-wise xor operator and + is the modular addition. For example, A,B and X can belong to the set{0,1,...,255} so the addition is modulo 256.
This equation can be a replacement for classical xor operation used by stream ciphers. If this equation cannot deterministically be solved then a known plain-text attack cannot be mounted against the cipher to deduce the keystream....

For any $n>0$ and any fixed $A$ the function $f_A : x \mapsto (A \oplus x) + x \bmod 2^n$ is affine over the field with 2 elements, i.e., $f_A(x\oplus y) = f_A(x)\oplus f_A(y)\oplus A$ (as $A = f_A(0)$).

A proof that the analog map $g_A : x \mapsto (A \oplus x) - x \bmod 2^n$ is affine, you can find in Louis Goubin's CHES 2001 paper A Sound Method for Switching between Boolean and Arithmetic Masking. For $f_A$ I do not know any published reference.

$f_A(x) = B$ is equivalent to $f_A(x)\oplus A = B\oplus A$, so you have to find out if the vector $B\oplus A$ is in the image of the $\mathbb F_2$-linear map $x\mapsto f_A(x)\oplus A$, and if it is, a preimage $x$. This is linear algebra, hence easy from a complexity-theoretical point.

For solving the linear equation you have first to check if $B\oplus A$ is a linear combination of the image of a bases, so taking the base $1, 2, 4, 8, 16, \dots$ you have to look if $B\oplus A$ can be written as a sum of a subset of the vectors $f_A(1)\oplus A=((A\oplus 1)+1\bmod 2^n)\oplus A$, $f_A(2)\oplus A=((A\oplus 2)+2\bmod 2^n)\oplus A$, $f_A(4)\oplus A=((A\oplus 4)+4\bmod 2^n)\oplus A, \dots$ using something like Gaussian elimination.

If it is, and let's say, for $I\subseteq \{0, 1, \dots, n-1\}$ you get $B\oplus A = \bigoplus_{i\in I} (f_A(2^i)\oplus A)$, then $x = \bigoplus_{i\in I} 2^i$ is your solution. EDIT: In general, you will get all solutions in this way. Linear algebra tells us that the set of solutions is either empty or an affine subspace, i.e., of the form $\{x_0+v| v\in W\}$ where $x_0$ is any solution and $W$ is an $\mathbb{F}_2$-subspace of the $n$-dimensional vector space of $n$-bit vectors.

So from a security point, I do not expect an improvement using this equation,  (EDIT:) as the solution set can be efficiently calculated and described (using one solution and a basis of $W$ of order $\le n$).


How does the Concat KDF work? I am writing an application using JSON Web Encryption with ECDH using the X25519 Curve. The RFC says that ECHD-ES derived secret is run through a Concat KDF.
Given that many cryptographers seem to be bashing JWT and the JOSE standard for having too many options to shoot yourself in the foot I want to make sure I am not using an insecure mode of JWE.
RFC 7518 JSON Web Algorithms (JWA) states

Key Agreement with Elliptic Curve Diffie-Hellman Ephemeral Static (ECDH-ES)
This section defines the specifics of key agreement with Elliptic
Curve Diffie-Hellman Ephemeral Static [RFC6090], in combination with
the Concat KDF, as defined in Section 5.8.1 of [NIST.800-56A].

Following the reference leads to 152 page NIST PDF that I don't fully understand. I am a developer not a cryptographer. I am using the Nimbus JOSE library in my application and it has an implementation of ContcatKDF.java derive function there.
Questions:

How does Contcat KDF work?
Is it considered secure?

It derive function gets called with SHA-256 as the hash function concatKDF = new ConcatKDF("SHA-256"); from ECDHCryptoProvider.java which computes the number of cycles using this.
Moderator note: crypto-SE is not a code review site. The code was replaced by links to the code. It's still here if needed.

Looking at it closely, the linked RFC formally references SP800-56Ar2 section 5.8.1, which buries in 5.8.1.2.1:

Note: When the single-step KDF specified in Section 5.8.1.1 is used with H = hash as the auxiliary function and this concatenation format for OtherInfo, the resulting key-derivation method is the Concatenation Key Derivation Function specified in the original version of SP 800-56A. (emphasis mine)

Based also on this, I guess that when the authors of the RFC wrote "Concat KDF, as defined in Section 5.8.1 of [NIST.800-56A]", they had in mind  SP800-56Ar1 section 5.8.1, titled "Concatenation Key Derivation Function (Approved Alternative 1)", which is what I would use if I had to implement the thing. I suggest to ignore the RFC's reference to the aforementioned SP800-56Ar2, which seems to be a well-intentioned but unfortunate change; as well as the currently applicable SP800-56Ar3.
Big picture: that KDF hashes the concatenation of a 4-byte counter initialized at 1 (big-endian), the shared secret obtained by ECDH, and some other information passed as input. The counter is incremented and the process is repeated until enough data was produced. The concatenation of the hashes, truncated as needed, forms the output to be used as key. Except for the data hashed and the position of the counter (at start rather than end), this is similar in principle to MGF1 of RSASSA-PSS and RASAES-OAEP in PKCS#1v2.2.
If the hash is SHA-256 as now in the question, as well as in this code which claims to successfully implement something (without stating clearly against what it is tested), I do not see that this KDF has an exploitable weakness of cryptographic nature in the context. This is not a statement about code.


Cryptographic hash function question Consider the following question:
Given a $n$-bit cryptographic hash function $H$, how many messages should we expect to hash before before finding a message $x$ such that $H(x) < 2^{n-k}$, for some integer $k$.
For me, this question does not make a lot of sense. A cryptographic  hashing function has always a fixed size on the output, such as SHA1 with 160 bits. It does not really matter what $x$, the message to be hashed, is $\operatorname{len}(\operatorname{SHA1}(x)) = 160\,$bits. In this case $\operatorname{len}(H(x)) = n$. Because of this, it is sufficient to hash a unique, random message. Because the size of the hashed $x$ is always going to be $n$ bytes, and $(n\text{ bytes }< 2^{n-k})$ is always true for any positive integer $k$.
Please do not give the answer, if you do, hide it ! :) I just want to better understand the question.

In cryptography, we often assimilate bitstrings to integers. Unless otherwise specified, that is per big-endian binary, where a bitstring $S$ of $n$ bits $b_0,b_1,\ldots b_{n-2},b_{n-1}$ is assimilated to integer $s$ with
$$s=\sum_{i=0}^{n-1}b_i\,2^{n-1-i}$$
E.g. bitstring 00010001 (which is 8-bit) is assimilated to integer $16+1=17$. Bitstring 0000000000010001 (which is 16-bit) and bitstring 10001 (which is 5-bit) also are assimilated to integer $17$. Note that for some purposes like hashing, we can't assimilate these bitstrings, even though they are assimilated to the same integer.
$H(x)<2^{n-k}$ compares $H(x)$, which is a bitstring (or perhaps a bytestring for a programmer), to $2^{n-k}$, which is an integer (an element of $\mathbb Z\,$). Some kind of transformation is needed. This is a sure sign that in the question, $H(x)<2^{n-k}$ must be read as:

the integer assimilated to the bitsring $H(x)$ is less than the integer $2^{n-k}$.

Note: In the circumstance it's also OK to assume little-endian binary, which uses the simpler $s=\displaystyle\sum_{i=0}^{n-1}b_i\,2^i$, but one should first get convinced this won't change the result.

There are several things wrong with stating

the size of the hashed $x$ is always going to be $n$ bytes, and $(n\text{ bytes }< 2^{n-k})$ is always true for any positive integer $k$.

If the question considered the size of "the size of the hashed $x$", it would be written $|H(x)|<2^{n-k}$, rather than $H(x)<2^{n-k}$.
Even with the statement understood as $|H(x)|<2^{n-k}$, the argument given would be wrong, with a counterexample the choice of $k=n$.
Cryptographers measure size of bitstrings and integers in bits (not bytes) unless otherwise stated. BTW, the bit size of non-negative integer $s$ is $\bigl\lceil\log_2(s+1)\bigr\rceil$, or equivalently the size of the smallest bitstring assimilated to $s$ (equivalently per big-endian or little-endian binary).


Which cipher is used in the new 5G network? I think that the stream ciphers SNOW 3G and AES are used in 4G (LTE). But I can't find which cipher is used in 5G networks and how encryption is done. Is there any official documentation?

Ericson's white paper lists them as

  The strong and well-proven security algorithms from the 4G system are reused. These are encryption algorithms based on SNOW 3G, AES-CTR, and ZUC; and integrity algorithms based on SNOW 3G, AES-CMAC, and ZUC. The main key derivation function is based on the secure HMAC-SHA-256.

Notably, all of them are stream ciphers as CTR mode converts any block cipher into a stream cipher.

SNOW 3G is a word-based synchronous stream cipher developed by Thomas Johansson and Patrik Ekdahl at Lund University.
ZUC uses a 16-stage LFSRs with each stage in $GF(2^{31}-1)$ and produces a 32-bit word on each tick.


How to authenticate two devices with CA? i am trying to figure out a man-in-the-middle safe authentication scheme for some devices. I understand that this could be achieved via CA's.

But what is unclear to me is how can the authenticity of a device be guaranteed in such a setup. To me it seems that a DEV3 (an imposter) could easily send its public key to the CA, which is then signed by the CA. Also, DEV3 probably has CA PUB key.

Here is a doodle :

The problem asked is not easily solved. To authenticate using cryptography as Dev1 in a way that a rogue Dev3 does not allow to imitate, Dev1 must know some secret key (or private key) that Dev3 does now contain (or does not allows to either extract or misuse), but that the CA can verify because it knows it (or knows the corresponding public key). Conventional cryptography (including public key cryptography, but perhaps not PUF-based cryptography or/and novel uses of quantum cryptography, which I won't consider further) has nothing else to offer.

The easiest workaround is to consider that Dev1 is whatever can prove being able to use the private key associated to the first public key for which the CA computes a certificate for something allegedly named Dev1, and have the CA reject any further attempt at obtaining a certificate under the name Dev1 (possibly: with the exception of duly authenticated certificate renewal requests if these are in the picture). When done properly, that can prevent Dev1 from working at all when it can be impersonated, which is better than nothing.

One method of solving the problem rather than working around it is to perform step 2 in an assumed secure location (e.g. factory) where the authentication of Dev1 is performed by non-cryptographic means.

Another method is to inject a secret key in Dev1 at a secure location, known also to the CA, so that step 2 can be performed with authentication using secret-key cryptography. That secret key can be a random octet string assigned at the secure location, and securely communicated (associated to the identifier Dev1, or the public Media Access Control address (MAC) of Dev1 if it has no name at that stage) to the CA, or the other way around.

As a more convenient variant of the above, the secret key can be a so-called diversified key, obtained using a key derivation function from a master key (known to the entity operating the secure location and the CA) and whatever identifies Dev1; the benefit is that only the master key needs to be securely communicated from/to the CA, which can recompute the diversified key of all devices. Note: for key diversification we do not need an entropy-streching key derivation function, and can use e.g. HMAC or AES (with the master key as key, and the identification as the other input); or any of the functions in NIST SP 800-108.
The key can be a Message Authentication Code of the Media Access Control address. The collision in TLA is accidental.

There are other methods, like embedding the same secret in all devices, and hoping it will not be extracted or misused; but they tend to have no operational advantage compared to the previous one when there is a CA, and be more brittle.


Dieharder input data format. Do I need new line at the end? I am testing my sequence for randomness using Dieharder with a command like dieharder -a -g 202 -f in.txt >>result.txt

my in.txt looks like

#==================================================================
# generator mt19937  seed = 316179543
#==================================================================
type: d
count: 40000004
numbit: 32
1635395663
 509326050
4144493458
...  // 40M more lines of numbers
3557717321
//Does Dieharder need this empty line before the end of file?

If 3557717321 is the last number in tested sequence, does Dieharder expect an empty line after it? Shoud the file end with 3557717321 or 3557717321\n?

Looking at the source, file_input_get in dieharder-3.31.1/libdieharder/rng_file_input.c: you are safe with a single newline after the last decimal number, as supplied by Java's writer.println. You do not need an extra newline. If there was a problem, DieHarder would stop with "# file_input(): Error: EOF on (filename)" or "Error: converting (stuff) failed. Exiting."

But this is kinda off-topic.


Scrypt as a KDF with one-time high-entropy input I'm looking at using Scrypt as a KDF. Assume the following:

the input will always be high-entropy random bytes generated by a CSPRNG
the length of the input can vary from between 8 to 32 bytes
the input-bytes are never re-used for generating another key
the salt is also generated by a CSPRNG
dklen (aka, output key length) can var from 64 bits to 1024 bits, depending on the algorithm for which the key is being used)
the cpu/memory/parallelization difficulty factors are user-defined, obviously with higher values resulting in higher security, but more processing time.  These factors are set at the client's discretion
all key-expansion happens client-side
please don't be concerned with the practicalities of implementing such a system, it's beyond the scope of this question

Assuming that brute-force attacking a KDF is faster than brute-forcing the key itself, I understand that more KDF processing-time equates to more protection from such attacks.  However, I've seen recommendations such as HKDF and KBKDF (discussed here), however I'm hesitant to use one of these protocols for various reasons (they're less-widely used/recognized, there isn't a lot of source code around for them, etc).  Would Scrypt be a good fit for this scenario?  Does it have any weak points, in which other protocols would be stronger?

If you have a high entropy input, then scrypt isn't a good choice. It's purpose is to compensate for the low entropy of a password. Don't ask the user for memory/cpu factors, you don't need them if the input is high entropy. You don't need a salt either.

Simply use an input of at least 16 bytes from a secure random number generator.

I recommend using one of the following:

PBKDF2 with a single iteration. This is actually what scrypt uses internally to consume the input and produce the output.
HKDF - It's a very nice and simple design, standardized by NIST, has a RFC. Implementing it on top of HMAC-SHA-2 is trivial. It's my first choice as a KDF if the input has high entropy.


Impossibility vs implaussiblity What is the difference between implausibility vs impossibility in the context of Crypto? I came to know that differing input indistinguishability Obfuscation (diO) implausibile but not impossible. Can I know the difference between the two terminologies?

This is a fairly clear cut mathematical distinction and not really phraseology nor semantics, especially in the sciences.

Implausible ~= Unlikely

Go back 10 years and consider the SHA-1 hash function.  Reversing this function is (was) hard and therefore very unlikely.  Today this has been kinda achieved in being able to generate collisions, but at great computational expense.  This has started us on a path where perhaps tomorrow Google might improve on the technique and allow SHA-1 reversal on mobile phone level computational power.  Or to only need the computational power of the iPhone10 when it starts selling.  This fate befell MD5.

Similarly, Ivan Verykleverkov might be working in his Moscow University dorm room today at improving Shor's Algorithm.  If the Verykleverkov Algorithm allows easy factorisation of primes on non quantum machines, RSA encryption and Blum Blum Shub random number generators become useless cryptographically overnight.

The theme here is something that is unlikely now does not preclude it (on a logical or mathematical basis) from becoming likely tomorrow.

Impossible = Impossible

Decrypting a properly applied One Time Pad (OTP) encryption is impossible.  If the pad was generated using true entropy, there is no mathematical solution to reversal.  The only solution is brute force attack leading to many possible alternative solutions.  Contextual and semiotic analysis may ween some out (as implausible) but you'll still be left with many plain texts each of equal validity.  This perfect secrecy is the OTP's draw and reason for all the related questions on this forum.

So in summary, one means the cryptography is currently secure but might be broken with future scientific advances whilst the other is mathematically proven to be secure for all time.


Traitor tracing - determining a set of codewords I am reading some notes and having trouble understanding the following example:

Let $F$ be a finite set of size $q$, where $q ≥ 2$. Let $n$ be an integer, where $n ≥ 2$.
For a subset $X ⊆ F^n$ of words over $F$ of length $n$, and for $k ∈ \{1, 2, . . . , n\}$,
we define $X(k)$ to be the set of $k$th components of words in $X$, and we define
the set desc$(X)$ of descendants of $X$ by
desc$(X) = X(1) × X(2) × · · · × X(n).$

For example, if $X = \{0000, 0111, 0012\}$ then $X(1) = \{0\}, X(2) = X(3) =
\{0, 1\}, X(4) = \{0, 1, 2\}$ and desc($X$) is the following set of words:
$\{0000, 0100, 0010, 0110, 0001, 0101, 0011, 0111, 0002, 0102, 0012, 0112\}$.

I know that the descendants of $X$ is also defined as the set of new words that could be produced by a coalition of pirates who posses all the words in $X$. In the example above I can't see how we know $X(1) = \{0\}$ etc? Or then how we desc($X$) is the following set of words:
$\{0000, 0100, 0010, 0110, 0001, 0101, 0011, 0111, 0002, 0102, 0012, 0112\}$? For example, how is it that we know that $0111$ is in the set but $1111$ is not?

Note that there are two words in $F$ which disagree on the $k^{th}$ coordinate if and only if  $|X(k)|>1.$

All three words in $F$ have $0$ as their first symbol so $X(1)=\{0\}.$

Thus all descendants have 0 in their first coordinate.

By definition of the direct product $\times,$ the descendants are formed by entering all elements of $X(1)$ in the first coordinate, those of $X(2)$ in the second coordinate, etc.


Why can't eavesdropper not make up own private key on diffie hellmann? I try to understand diffie hellmann and I wonder why an attacker just can't make her own secret key and go along with the ride?

She'd be ending up with just the same shared key.

Let the private keys be:
$$sk_A = 14, sk_B=12, sk_E=8$$

Let's assume the base is $g=2$ and the prime is $p=17$.

Alice would have a public key of $pk_A=13$ ($g^{sk_A} \bmod p = 2^{14} \bmod 17 = 13$) and publish it and Bob would have a public key of $pk_B=16$ ($g^{sk_B}\bmod p = 2^{12} \bmod 17 = 16$). Eavesdropper would end up with $pk_E=1$ ($g^{sk_E}\bmod p = 2^{8} \bmod 17 = 1$).

Now Alice can take the public key of Bob to arrive at the shared secret ($pk_B^{sk_A}\bmod p = 16^{14} \bmod 17 = 1$) and Bob can do so as well.

But can't the eavesdropper not always do the same procedure with her private key? In other words won't $g^{sk_E} \bmod p$ always lead to the same shared key?

(I updated the numbers so that prime is bigger than the exponents).

Eve does not have the same information. It's only with you poor choice of numbers did you get the phenomena where the number you chose for Eve happens to match.
In general this doesn't happen, and with careful choice of parameters and large numbers the chance for this happening is negligible.

You chose an unsafe prime $17=2^4+1$ rather than a safe prime of the form $p=2*q+1$ when q is also prime. You then chose $g=2$ which only spans a group of size 8. $2^8=1\space mod\space 17$ rather than for instance g=3 which can produce the full range.

For Alice and Bob it is guaranteed: $(g^{P_a})^{P_b}=(g^{P_b})^{P_a} = g^{P_aP_b}$
Since Alice and Bob aren't using Eve's public key, she can't calculate the shared key with them.
In the vast majority of cases she will end up with a different number.

In your example the shared key came out 1, and many guesses by Eve work (but not all). Because the public key for Alice and Bob came out with low rank (2 and 4). Using a large safe prime and a generator will make this highly unlikely.

It is considered very difficult to calculate $g^{ab}$ from $g^a$ and $g^b$ without knowing either a or b. Eve guessing a random key isn't likely to help. For random $e$ in almost all cases $g^{ae}\ne g^{ab}$


Understanding the Hidden Subgroup Problem specific to Integer Factorization I've been reading about the Hidden Subgroup Problem (HSP), specifically trying to understand how it is related to the integer factorization problem. I've read What exactly is the impact of the hidden subgroup problem on cryptography? but it doesn't cover the specifics I am having trouble putting together.
To define the HSP:

Given a group $G$, a subgroup $H \leq G$, and a set $X$, we say a function $f : G \Rightarrow X$ separates cosets of $H$ if for all $g_1, g_2 \in G$, $f(g_1) = f(g_2)$ if and only if $g_1H = g_2H$.
Hidden subgroup problem: Let $G$ be a group, $X$ a finite set, and $f : G \Rightarrow X$ a function such that there exists a subgroup $H \leq G$ for which $f$ separates cosets of $H$. The function $f$ is given via an oracle. Using information gained from evaluations of $f$ via its oracle, determine a generating set for $H$.

What I can't figure out is how to reduce the integer factorization problem to an HSP problem, and then why the (abelian) HSP problem is not solvable in polynomial time without a quantum computer using e.g. Shor's algorithm.

Let $\mathbb{Z}, +$ be the group integers, $\mathbb{Z}/n\mathbb{Z}, \times$ the multiplicative group of integers modulo $n$, and $\varphi(n)$ its order. Then $\varphi(n)\mathbb{Z}, +$, the additive group of multiples of $\varphi(n)$ is a subgroup of $\mathbb{Z}$. The function $f : \mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z} : x \mapsto a^x \mod n$ for fixed $a \in \mathbb{Z}/n\mathbb{Z}$ satisfies the description of the HSP oracle for the subgroup $H=\varphi(n)\mathbb{Z}$ of $\mathbb{Z}$ because

$\phantom{\Leftrightarrow} \forall \, x, y \in \mathbb{Z} \, . \, f(x) = f(y) \\
\Leftrightarrow x = y \mod \varphi(n) \\
\Leftrightarrow x = y + k\varphi(n) \quad \mathit{for \, some} \quad k \in \mathbb{Z} \\
\Leftrightarrow x = y + H$

Consequently, the formulation of the factorization problem is to find a generator of the group $\varphi(n)\mathbb{Z} \subset \mathbb{Z}$ given access to the function $f$ that computes exponentiation modulo $n$. Once you have this generator, $\varphi(n)$, computing the factorization of $n$ is easy using some straightforward (classical) number theory.


GCM: use the same key:IV pair to encrypt file and filename Using Java, I wrote a piece of code that encrypts a given file with AES in GCM mode of operation. So far nothing uncommon.

Now I would also like to encrypt the filename, in the following way:

encrypted filename <- AES(key, IV, original filename).

In order to avoid having multiple key:IV pairs, I also encrypt data with the same key and nonce, like so:

encrypted file <- AES(key, IV, original file)

I know that reusing a key:IV pair is strictly forbidden when dealing with stream ciphers, but since the filename and the file are both in the same set of data, my guess is that it should be fine. However, I am not sure.

Anyone can confirm this ?

tl;dr is it OK to encrypt both a file and the filename with the same key:IV pair with GCM ?

This is terrible. In GCM, if you use the same nonce, then the authenticator is completely broken (for all messages in the future). You should never assume that the attacker doesn't know the filename either. You MUST use different IVs.


Reduction from signatures to encryption? Is it possible to construct an (asymmetric) encryption scheme from a signature scheme?

If the signature scheme is deterministic and allows existential forgery (e.g. RSA), then the answer is yes (create a forgery (m, sig); encrypt plaintexts using AES with sig as the key; send m in clear to the signer along with ciphertexts, who can then compute sig and decrypt these ciphertexts) .

I am interested in similar reductions for probabilistic signature schemes.

What should the properties of a probabilistic signature scheme be so that it can be used for encryption?

Let's first define a few things. Precise definitions are needed because your question is a bit ill-defined, and it seems that you are somewhat cheating.

Some definitions

Traditionally, we define a signature system as the combination of three algorithms:

G: key generation; given a "security parameter" t (e.g. the intended key size), yields a key pair (x, y) (x is the private key, y is the public key).
S: signature generation: given a message m (from a given space of messages M) and x, outputs a signature s.
V: signature verification: given m, y and s, outputs true or false.

It is supposedly infeasible to do forgeries, i.e., given y but not x, find (m, s) such that V(m, y, s) = true. Existential forgeries are "untargetted" forgeries where the attacker does not get to choose m arbitrarily.

On forgeries and "cheating"

Forgeries are bad, and a signature algorithm which accepts forgeries (existential or not) is considered to be broken. No "standard" signature algorithm accepts existential forgeries. In particular, RSA, as specified by PKCS#1, does not, even when using the "old style" v1.5 padding, which is deterministic: no method is known to generate a number s which, when raised to the public exponent, yields a proper PKCS#1 padding (beginning with 0x00 0x01 followed by eight or more 0xFF bytes). Moreover, the message m is first hashed, and even if you could find a s which produces, when exponentiated, a properly padded hash value, you would still be hard pressed to compute the corresponding m.

So, assuming that you want to apply your method on RSA, you are not talking about "RSA, the signature algorithm"; you need to remove the padding and the hash function, at which point you have the RSA core modular exponentiation, also known as "RSA, the trapdoor permutation". A trapdoor permutation can be used quite immediately for asymmetric encryption. In that sense you are "cheating".

@PulpSpy uses a different cheat, by assuming that he can publish the private key, and keep the public key secret. This may work with RSA, but only if the signature engine (the one which produces the signatures) accepts to work with a "private" key expressed as a raw private exponent and modulus, without knowledge of the modulus factors. "Normal" RSA implementation use the standard private key format, which includes the factors because this speeds up quite a bit private key operations (by a factor of about 4, thanks to the Chinese Remainder Theorem). Also, the "public" key needs to be kept secret, which implies a big exponent, not the usual 3 or 65537; there again, an existing RSA "verifier" implementation may refuse to work.

Rewriting the problem

I suggest the following definition of the problem: let (G, S, V) be a signature system. A key pair is generated; the key holder (Alice) maintains x (the private key) secret, in a box which computes S. The only way to use x is to execute S, which produces a signature on a given message m. The public key y is known by everybody, and Bob has some strong assurance that y is Alice's key through an unspecified mechanism (e.g. a certificate), but there is no other value which is thus unambiguously linked to Alice. Is there a way for Bob to use y in order to convey a confidential message to Alice ?

Note that clause about "no other value". If we allow Alice to publish other data, she could generate a transient key pair for an asymmetric encryption or key exchange algorithm, which Bob would just use (this is how it is actually done in S/MIME when the certificated key of a user is only for signatures). Correspondingly, we are after an asynchronous solution (Bob does all the job in one go, and only then sends the whole to Alice; otherwise, in an interactive protocol, Alice could "cheat" by sending a transient key pair).

For the interest of the exercise, we allow Alice and Bob to input precomputed hash values into S and V: no need to find messages m such that h(m) "works", we accept hand-crafted "hash values" which did not involve a hash computation at all.

With the question stated as above, there is now a good reason why this cannot work with signatures schemes based on a non-interactive zero-knowledge proof. A ZK proof is a protocol in which a prover demonstrates to a verifier knowledge of the solution of a given "problem". The protocol is said to be zero-knowledge because the transcript of the protocol is unconvincing: it is possible, without knowing the actual solution of the problem, to build a fake conversation between a "prover" and a "verifier", and there is no way to distinguish between a fake conversation and a real conversation with the true prover. In that sense, no information about the secret data leaks to the outside. A ZK protocol can be turned into a signature scheme: in a normal ZK protocol, the prover sends one or several commitments, then the verifier sends a challenge, to which the prover can respond in a way which is satisfying with regards to the committed values. It "suffices" to compute the challenge from the commitments using an appropriate one-way function, to make the protocol non-interactive; if a message is also used as additional input to the one-way function, then we have a signature algorithm.

This category of signature algorithm includes all the discrete logarithm-based signature schemes: ElGamal signatures, DSA, ECDSA, Schnorr... (they actually use a slightly weakened variant of ZK dubbed "computational zero-knowledge" because their ZKness is relative to the hardness of some operation, here the discrete logarithm).

The point of the ZK property is that producing the signature leaks no information about the signature key, except that the signing box knows it. For an asymmetric encryption or key exchange scheme, Alice must be able to extract at least one bit of extra information from is signing black box. Here, everybody knows that Alice owns the private key, and any signature generated by S will say nothing more. Therefore, there is nothing that Alice can do with S and what Bob sent her, that will yield any information suitable for a key exchange.

Rewriting this as a properly formal proof looks like hard work. So, right now, what I wrote above is merely "intuition". It means that I find it improbable that one could find a (non-cheating) way of turning an ECDSA-signing-box into a key exchange mechanism.


NTAG 424 - how to diversify the key? I am currently working with the NXP NTAG 424 chips, which feature AES-128 encryption.

In the end, one will be able to read an NDEF message; for example, with a smartphone, the backend server will then verify whether the message was delivered.

However, NXP often implies that the UID should not be communicated in the clear. They even have a setting that disables the communication of the UID in the clear (it is then replaced with a fake UID). NXP also states the following in their application note:
" Therefore
verification side does not have immediate info on UID, which is usually used as input for
key derivation function. In this case, KSDMMetaRead key shall not be UID diversified and
high attention on secure storage on the system level of this key is required.
"

Why is the open communication of the UID such a problem? Can the UID be used to crack the key? How should one diversify the key instead?

Why is the clear communication of the UID such a problem?

Problem is that most RFID tags can be read at a distance, without the holder knowing. Since the UID is readable, and if it is fixed, that can help track the holder. That's why there is a trend¹ in modern RFID tags towards random UIDs (RID), and making it necessary for the tag reader to hold a key in order to be able to read any tag-identifying information. As explained in the question's quote, that key must be non-diversified, except when there is another tag identifier available thru a different channel².

  Can the UID be used to crack the key?

No. The tag's UID is an arbitrary public number: fixed at manufacturing (often sequential or random), or drawn randomly³ at each power-up or reset of the tag (see NFC's AN10927). In a system with non-diversified key³, the UID has no relation to the key. In a system with diversified tag key $K_D$ derived from a master key $K$ (not in the tag), the UID has no relation with  $K$. If the tag key is diversified per the UID, it holds the relation $K_D=\operatorname{KDF}(K,\text{UID})$. However, not knowing $K$, knowing the UID does not allow finding the tag key $K_D$, for proper $\operatorname{KDF}$. And even if $K_D$ is somehow extracted from some tag(s), then for proper $\operatorname{KDF}$ that does not allow finding the master key $K$ (which would allow to find $K_D$ for other tags).

  How should one diversify the key instead?

In some tags, when the tag-identifying information (other than UID) has been read using the first non-diversified key, it can then be used to diversify another key, bringing back the security of diversified tag keys. I have no idea about if this is possible on this particular tag.

As already explained, in some application it could be possible to diversify the key using a different information read thru an other mean, e.g. optical.

¹ That's currently marginal. In France, practice is that legitimate readers are required not to keep identifying information beyond the requirement of the application, and identifying information kept by unrelated applications should be protected against reconciliation (for example, a serial number read from an RFID tag could be be encrypted by an application-unique key before being entered in a database).

² In many modern passports/MRTDs that can be read per ISO/IEC 14443, the design is such that there is no identifying information (personal or not) readable directly by that channel, including a mere serial number/(U)UID/PUPI. Reading such information only becomes possible after reading data on the optically readable strip inside the passport, which (after a public transformation) acts as a key to unlock reading more thru the RF channel. I heard that one of the design rationale was to defeat a device that performs a nefarious action (explosion, toxic spray…) when a specific person approaches. If someone has a reference for the true design rationale, please leave comment.

³ In this case, the (U)UID has no cryptographic role and is only used for addressing purposes when there are several tags in the operating field of a reader.


Affine Cipher over an Affine Cipher I would like to know your view about the title, encrypting a plain text with an affine cipher then encrypting that ciphertext once more using the same cipher, but of course different keys. Would it be more secure?

For me, it won't be since it still can be brute forced.  That's what I think, and I have read about Vigenère over a Vigenère, so practically they would be the same case, right?

If you combine two affine ciphers, you obtain one affine cipher. Say the first cipher is $e_1(x) = a_1x+b_1$ and the second is $e_2(x) = a_2x+b_2$. Then $e_1(e_2(x)) = a_1(a_2x+b_2)+b_1 = (a_1a_2)x+(a_1b_2+b_1)$.

Note that if $a_1$ and $a_2$ are both relatively prime with the modulus, then so is $a_1a_2$, so the new cipher can also be deciphered.


Are there any differences in operation between existing Diffie-Hellman specifications? Are there any differences in operation between existing Diffie-Hellman specifications, especially those within the RSA PKCS#3, ANSI X9.42 and RFC 2631 standards?

PKCS#3 is an older standard which only defines the DH primitive itself. It contains the following information: parameter generation, the Diffie Hellman key agreement algorithm, integer/octet string conversions (as in PKCS#1, RSA) and the specification of an ASN.1 structure for the parameters. The ASN.1 structure is very limited, containing only the necessary $p$ and $g$ parameters and an optional privateValueLength parameter.

ANS X9.42 is a much larger specification, which contains a great number of derivative algorithms, including the MQV2 and MQV1 authenticated Diffie-Hellman schemes. With regard to the Diffie-Hellman calculations itself, it contains a method to validate the parameters as well as the public key of the other party. It contains two Key Derivation Functions (KDFs) that are slightly different from each other: one octet string concatenation while the other uses ASN.1 encoding. Both use hashing to derive keys from the generated secret value. Finally the ASN.1 definitions are much more extensive than PKCS#3. The domain parameter structure has a required $q$ parameter, which makes the domain parameter structure incompatible with that of PKCS#3. The base calculation and integer to octet string functions used for the secret value are however identical to PKCS#3. ANS X9.42 also helpfully provides calculation examples.

RFC 2631 is a strict subset of ANS X9.42. It only defines Diffie-Hellman algorithms without authentication. It limits Diffie-Hellman to the ephemeral-ephemeral, ephemeral-static and static-static schemes also present in X9.42. It defines only the ASN.1 based KDF with a specific hash function: SHA-1. The data in this ASN.1 structure is limited as well, but it has not been made static. It contains all the domain parameter and public key parameter validation algorithms. It does however not define any ASN.1 structures for the domain parameters nor the public key. Note that RFC 2631 may not use the same names and identifiers specified in X9.42; it for instance uses "ephemeral-static Diffie-Hellman" for the "dhOneFlow" scheme in X9.42. It also introduces the term KEK for the key generated by the KDF.

Finally NIST Special Publication 800-58A is a document that is based on ANS X9.42. It shows key agreement based on Finite Field Cryptography (what most persons call DH) as well as key agreement based on Elliptic Curve Cryptography. It defines MQV authenticated schemes, but only for ECC. An additional test has been defined for the shared secret value: if $Z$ has the value 1 then an error should be returned. It also contains a slightly different KDF, where the counter is removed from the OtherInfo. It also contains references to NIST Special Publication 800-58C for using a KDF that uses extract-then-expand. Instead of just algorithms a lot of this standard provides indications on how to properly implement the standard. This document seems to be most up to date and provides clearly more information than the other documents.

This answer is based on PKCS#3 Version 1.4, ANS X9.42–2003, RFC 2631 of June 1999 and NIST SP 800 56A: Revision 2, May 2013. Note that ANS X9.42 is not publicly available.


Long Term Security of Truecrypt's hash function? Does Truecrypt's hash function weaken the security of a chosen cipher cascade?

Considering I want to choose a cipher cascade of 3 ciphers for long term security (50+ years) for my archived data on blu-ray disk. Truecrypt allows me to choose only 1 hash algorithm, but up to 3 cipher algorithms.

Doesn't that make the hash function the ultimate weakest link? If SHA2, Whirlpool and RIPEMD160 were all "broken" - would that result in a broken truecrypt container?

Unlike the ciphers, the hash algorithm is not used directly to protect your data. Its only purpose is to take your ASCII passphrase and mix it up, shrinking or expanding it to the size required by the underlying ciphers. In order to make brute force attacks more infeasible, this process is repeated thousands of times in an algorithm called PBKDF2-HMAC so that each password attempt takes time. Because they are not used to directly protect your data, it would not be a major problem if the hash function were found to be weaker than believed. In fact, if your password was strong, even using the infamously broken MD4 algorithm would be technically acceptable, although it would be a rather nasty cryptography faux pas.


Can Bob prove that Alice have a key which encrypts C into A? Alice has a ciphertext $A$, its AES key $B$, and decrypted plaintext of $A$, let's call it $C$.
Alice sends $A$ and $C$ to Bob.
Bob wants to prove $C$ is just decrypted $A$, and has not been tampered with.

Can Bob achieve this without knowing the key $B$?

You do not really specify what your encryption scheme is. "AES" is a block-cipher, that requires a secure mode of operation to be turned into an actual secure encryption scheme.

But I will assume in the following that you are referring to some encryption scheme based on AES that is at least considered CPA secure. (e.g. AES-CBC or AES-CTR). In that case:

No, being able to do so would break CPA security of the encryption scheme.

To see why, consider the following. We have a symmetric encryption scheme $(\mathsf{Enc},\mathsf{Dec})$. Now assume towards contradiction that there exists some efficient algorithm $\mathcal{P}$ that Bob could use to convince himself that $(c,m)$ is a pair of ciphertext and plaintext such that $m = \mathsf{Dec}(k,c)$ with an unknown but fixed key $k$. I.e., let's say it holds that $$\Pr[\mathcal{P}(m,c) = 1\vert m = \mathsf{Dec}(k,c)] \ge 2/3$$
$$\Pr[\mathcal{P}(m',c) = 1\vert m' \neq \mathsf{Dec}(k,c)] \le 1/3$$

Then this algorithm trivially allows us to break CPA security. The attacker $\mathcal{A}(1^n)$ outputs two random messages $m_0,m_1$ and receives the challenge ciphertext $c^*$. $\mathcal{A}$ then simply outputs $\mathcal{P}(m_1,c^*)$. If $c^*$ is an encryption of $m_0$ then  $\mathcal{A}$ outputs $0$ with probability at least $2/3$. Likewise if $c^*$ is an encryption of $m_1$ then  $\mathcal{A}$ outputs $1$ with probability at least $2/3$.
Therefore overall $\mathcal{A}$ can distinguish ciphertexts of $m_0$ and $m_1$ with probability $2/3$ and thus significantly better than random chance.

What is however possible is for Alice to prove to Bob that she knows a key $k$ such that $m = \mathsf{Dec}(k,c)$ without revealing $k$.


AES-128 (cbc mode), is it possible to deduce the IV if the plaintext, ciphertext and key are known? I have the plain text, key and the ciphertext stored in DB. Can I deduce the IV based on this information?

By the formal modern definition of a cipher, the ciphertext and key should be all that's necessary to decipher, thus the IV of CBC should be in the ciphertext (often it is in the first block of ciphertext).

However the original description of CBC disagree and treat IV as a separate.

For the later situation, and assuming IV is not available (which suggests an exercise rather than a real situation), hint: write down the relation between IV, plaintext, ciphertext, and key by the definition of CBC; apply to the first block of plaintext; and use properties of bitwise exclusive-OR (commutativity, associativity, each element is its own inverse), and the defining property of a block cipher like AES-128 (that for fixed key, it is an easily reversible bijection of the block space).


Need a test suite for my RSA implementation I have an assignment to build a software which can encrypt/decrypt by RSA method. I already did it, but my teacher said that I need to find a test suite (include: modulus, public key, private key) to test if my software runs correctly.

He needs real data which has already been tested by someone else and that data needs to be mentioned in lectures, books, reports, benchmarks, etc...

I tried to find them but I cannot :(. I'm very appreciated if you can help me.
Thank you.


Calculating IHVs from known message and hash output Here is a somewhat silly and atypical problem I am currently facing. Usually, when it comes to hashes, one is bothered with finding collisions and preimages. My problem is, I need to find the IHV used to initialise the word buffers. The message and the hash function output are considered to be known.

Is there a non-bruteforce solution of this problem related to MD5 or SHA-1?

By 'IHV', I assume you mean the Initial Hash Vector; that is, the state of the hash function before you start hashing.

Well, if they aren't using the standard initial values (specified by the hash function definition), well, there isn't much you can do.  The problem is that the compression function used by Merkle-Damgaard hash functions (such as MD5 or SHA-1) is specifically designed to be noninvertable; that is, the problem of "finding the previous state, given the final state and the value being hashed" is a hard problem.  They design things that way because if that wasn't true, the "second preimage problem" is easier than expected.

This hard problem of "running the hash function backwards" is precisely the problem you would need to solve to reconstruct the hash function's starting value.


DHKE Square and Multiply Given is a DHKE algorithm. The modulus  has 1024 bit and  is a generator of a subgroup where ()≈2160.
Assuming the public keys have already been computed, how many number of modular multiplication and modular squaring are there in the session key.
Using the square and multiply algorithm on $2^{160}$ :
160 = 10100000 in Binary
1 First One list Number           2
0 Zero calls for Square          $(2){^2}$
1 One calls for Square + Multiply $((2){^2}){^2}$ * 2
0 Zero calls for Square            $(((2){^2}){^2}$ * 2)${^2}$
0 Zero calls for Square           $((((2){^2}){^2}$ * 2)${^2}$)${^2}$
0 Zero calls for Square       $(((((2){^2}){^2}$ * 2)${^2}$)${^2}$)${^2}$
0 Zero calls for Square $((((((2){^2}){^2}$ * 2)${^2}$)${^2}$)${^2}$)${^2}$
0 Zero calls for Square  $(((((((2){^2}){^2}$ * 2)${^2}$)${^2}$)${^2}$)${^2}$)${^2}$
Thus, there should be a total of 7 squares and 1 multiplication for exponent of 160.
Similarly, if we assume now that α is such a short element (e.g., a 16-bit
integer).
Using the square-and-multiply algorithm we should get that there is a total of 4 squares and 0 multiplications for exponent of 16.
Is this a correct understanding of number of modular multiplication and squaring using square-and-multiply algorithm for the session key?

Standard DHKE
Standard DHKE is defined on the multiplicative groups.  Alice and Bob agree on the cyclic group $G$ of order $n$ and a generator $g$ then the key agreement is performed as follows;
\begin{array}{lcl}
\text{Alice} & \text{Transmit} & \text{Bob}\\ \hline
a \stackrel{R}{\leftarrow} [1,n-1]& & b \stackrel{R}{\leftarrow} [1,n-1]\\
\text{calculates } A = g^a & \xrightarrow{A} & \text{calculates } B = g^b\\
 & \xleftarrow{B} & \text{calculates } s = B^a = (g^a)^b = g^{ab} \\
\text{calculates } s = A^b = (g^b)^a = g^{ab} & &
\end{array}
Therefore both sides have agreed on the $s = g^{ab}$ and
Group Selection
We can use the below 3 prime classes to choose the $p$;

Choose a prime in the form $p = kq+1$ and those are called DSA prime by poncho. They are cheap to generate.

Choose a prime of the form $p = 2qr+1$ and those are called Lim-Lee primes where both $q$ and  $r$  primes around the half size of $p$.

Choose a prime of the form $2q+1$ and those are called sage primes and $q$ is called Sophie Germain prime.

Generation easiness and order of security of these groups are $1<2<3$
If you choose $\mathbb{Z}_p$ then the multiplicative order is $p-1$ which is not a prime and the group may vulnerable to Pohlig-Hellman. With the above methods, we guarantee that we have an element with large order $q$.
Modular Exponentiation
def modular_pow(base, exponent, modulus):
    if modulus == 1:
        return 0
    result = 1
    base = base % modulus

    while exponent > 0:
        if (exponent % 2 == 1):
            result = (result * base) % modulus
        exponent = exponent //2
        base = (base * base) % modulus
    return result

Calculation
Let's take ffdhe2048 from RFC 7919

$p = p = 2^{2048} - 2^{1984} + (\lfloor(2^{1918} \cdot e \rfloor + 560316 ) \cdot 2^{64} - 1$
$g = 2$
$q = 2*p+1$, so we have a safe prime.
$n = q = (p-1)/2$, and
a = 160

Exponent =  0
   Squaring   , base   =  4
Exponent =  0
   Squaring   , base   =  16
Exponent =  0
   Squaring   , base   =  256
Exponent =  0
   Squaring   , base   =  65536
Exponent =  0
   Squaring   , base   =  4294967296
Exponent =  1
   Multiplying, result =  4294967296
   Squaring   , base   =  18446744073709551616
Exponent =  0
   Squaring   , base   =  340282366920938463463374607431768211456
Exponent =  1
   Multiplying, result =  1461501637330902918203684832716283019655932542976
   Squaring   , base   =  115792089237316195423570985008687907853269984665640564039457584007913129639936

Result =  1461501637330902918203684832716283019655932542976

Note on 160
The exponent is too small to be square. When the attackers see the result and compared to the
p=16158503035655503650076756738912581681244028566744537587294217069634903417068105001396028181320082342729278178967665408464414511540286736312636777371230622870513101263958286486431353150162631714106572883465707111827110470555674314995828739134017115276543174525317778856109593945166364784848064871928120870618118612598673201345927898883988411507312698966529007613429365380598766218233737927730357521948422470183065248848906427147979329798783525641926066392234261462752284136439556860049465936979571687087918913000139017486599276030303766617061301627342044060015552953742140501997483478059848478124314516169036419563519
They simply will consider that you used a small number and will search it by brute force. The $a$ must be chosen uniformly random as $a \stackrel{R}{\leftarrow} [1,n-1]$.
Actually, we don't need $a \stackrel{R}{\leftarrow} [1,n-1]$ for the security $a \stackrel{R}{\leftarrow} [1,2^{224}]$ is enough between 2019 and 2030 according to NIST ( see as keylenght.com). As stated poncho on the commends, this is more efficient.
Performance
Now the number of operations is quite countable. We have to square for every bit of the exponent ( $160_{10} = [10100000]_2$) and a multiplication whenever a bit is 1 ( 2 times for 160 sine $160= 128+32$).
The above function is not optimal to calculate modular exponentiation and vulnerable to side-channel since there is a conditional that depends on the exponent bits.
MITM
Standard DHKE is vulnerable to MITM attack and Telegram had a different one too. To mitigate the MITM attack digital signatures are required.


Proof for collision resistance on a block-based hash I am designing an unkeyed hash based on the SIMON cipher.  This is a follow up to “this” question.  A quick summary:  I have an ECC engine and the SIMON cipher in hardware, and it’s in an extremely power constrained environment.  I want a hash generator for two reasons: 1) the ECC shared secret, and 2) if I want to verify a stream.  I cannot use any of the other hash engines due to hardware constraints, which is mainly that they are huge and ruin my power budget, but because I already have a SIMON encryption block, I can modify that any way that I want.

I started by reading “chap9.pdf”, and a bunch of papers; however, I would like to blow holes in what I designed.  I need to justify my use of this to myself because hardware is such and expensive proposition.

I took the SIMON 128/256 architecture that has a key expansion on 4, 64-bit words and then used that to create something that takes 128-bit in and puts 128-bits out.  Just to make the problem tractable for this explanation, I will use SIMON 32/64 from here on as it has 4, 8-bit words.

The basic architecture is here:

I just keep feeding things into the lower two words via an XOR, which follows that Davies-Meyer and the Merkle style architectures.

In order to visualize this, I’ve generated the key expansion for a 64-bit input of all 0s for two runs through the hash engine:

In the image above, the result of feeding a stream of 0s into the hash for two hash rounds results in 0x5753c0fe.  This means that 32-bits eventually results in 32-bits, and in the system I plan to implement 128-bit blocks eventually results in a 128-bit number.

Now, I can say everything that is wrong with this that I know of:

I cannot specify the length because this needs to be used as a stream, and I cannot guarantee how many blocks will go through it.  For 2 blocks through it, I can find collisions. .  This seems to be less of a problem as I make the stream inputs longer, but I could not find a formal proof for this.
I have a counter that exists to run the encryption hardware, and I could XOR against that on either the high or low word, but for 2 blocks, I can still find collisions.

Question:  Is there a formal proof for length of stream input and collisions somewhere for a block-based, unkeyed cipher?

If I understand you correctly, you are using the Simon key expansion process, so that the input to your block is the 256 bit Simon key, and the output is the 256 bit last round key (and you're ignoring the Simon encryption process entirely).

If so, three nits:

I believe that you can find preimages for your hash function in $O(2^{64})$ compression function evaluations.  This happens because the key expansion process is invertible; that is, given a 256 bit output, you can find the corresponding 256 bit input.  So, what an attacker would do is assume a 2 block message; he would:

Generate $2^{64}$ initial blocks, and compute the intermediate states from them.
Generate $2^{64}$ final states consisting of the target hash and $2^{64}$ different $K_i, K_{i+1}$ words, and compute the inverse key expansion
Look for a collision in the $K_{i+2}, K_{i+3}$ words; if you find one, this implies a preimage

This is easy to fix; make the transform noninvertible.
If you want your hash function to be collision resistant, you'll need to add some collision-free padding mechanism.
This architecture is actually closer to a Sponge hash function than a Davies-Meyer type construction (just in case you're wondering)