What is the difference between PKCS#5 padding and PKCS#7 padding One runtime platform provides an API that supplies PKCS#5 padding for block cipher modes such as ECB and CBC. These modes have been defined for the triple DES, AES and Blowfish block ciphers. The other platform API only provides PKCS#7 padding.

Are PKCS#5 padding and PKCS#7 padding compatible?

The difference between the PKCS#5 and PKCS#7 padding mechanisms is the block size; PKCS#5 padding is defined for 8-byte block sizes, PKCS#7 padding would work for any block size from 1 to 255 bytes.

This is the definition of PKCS#5 padding (6.2) as defined in the RFC:

  The padding string PS shall consist of 8 - (||M|| mod 8) octets all
  having value 8 - (||M|| mod 8).

The RFC that contains the PKCS#7 standard is the same except that it allows block sizes up to 255 bytes in size (10.3 note 2):

  For such algorithms, the method shall be to pad the input at the
  trailing end with k - (l mod k) octets all having value k -
  (l mod k), where l is the length of the input.

So fundamentally PKCS#5 padding is a subset of PKCS#7 padding for 8 byte block sizes. Hence, PKCS#5 padding can not be used for AES. PKCS#5 padding was only defined with RC2/RC5 and (triple) DES operation in mind.

Many cryptographic libraries use an identifier indicating PKCS#5 or PKCS#7 to define the same padding mechanism. The identifier should indicate PKCS#7 if block sizes other than 8 are used within the calculation. Some cryptographic libraries such as the SUN provider in Java indicate PKCS#5 where PKCS#7 should be used - "PKCS5Padding" should have been "PKCS7Padding". This is - with high probability - a legacy from the time that only 8 byte block ciphers such as (triple) DES symmetric cipher were available.

Note that neither PKCS#5 nor PKCS#7 is a standard created to describe a padding mechanism. The padding part is only a small subset of the defined functionality. PKCS#5 is a standard for Password Based Encryption or PBE, and PKCS#7 defines the Cryptographic Message Syntax or CMS. In that sense you could say that ECB and CBC mode can use PKCS#5 or PKCS#7 compatible padding. Later PKCS#5 standards simply refer to successors of the PKCS#7 CMS standard for 16 byte block ciphers such as AES.


Offline Complexity of the garbling scheme The offline complexity of the garbling scheme means the time complexity of the circuit encoding algorithm, that is, $\textrm{GC.Circ}(1^\lambda, C)$, where $C$ is the circuit to be garbled. It's straightforward to see that the offline complexity is $\textrm{poly}(\lambda, C)$.

My question is that whether there exists any optimal offline complexity of circuit encoding algorithm? for example, is it possible that the offline complexity is "sublinear" in the circuit size?

From The Foundation of Garbled Circuits

  A garbling scheme is a five-tuple of algorithms $G=(Gb,En,De,Ev,ev)$.
  The first of these is probabilistic; the remaining algorithms are
  deterministic. A string $f$, the original function, describes the
  function ev$(f,\cdot): \{0, 1\}^n\rightarrow \{0, 1\}^m$ that we want
  to garble where $n$ and $m$ are the input and output size resp.  On
  input $f$ and a security parameter $k\in \mathbb{N}$, algorithm $Gb$
  returns a triple of strings $(F, e, d)\rightarrow Gb(1^k, f)$. String
  $e$ describes an encoding function, $En(e,\cdot)$, that maps an
  initial input $x\in\{0, 1\}^n$ to a garbled input $X=En(e, x)$. String
  $F$ describes a garbled function, $Ev(F,\cdot)$, that maps each
  garbled input $X$ to a garbled output $Y = Ev(F, X)$.  String $d$
  describes a decoding function, $De(d,\cdot)$, that maps a garbled
  output $Y$ to a final output $y = De(d, Y )$.

Thus, taking an FHE $(Gen,Enc,Dec)$ scheme (see this)which takes an encoded input $X=Enc(x)$, applies the function $C$ to it to get $Y=C(X)$ and then decode the output by $y=Dec(Y)$ we get that $y=C(x)=Dec(C(Enc(x))$ (since the scheme is fully homomorphic. In this example the garbling algorithm, the one you denote by $CC.Circ$ just do nothing and its complexity is $O(1)$, which is optimal.

This example shows that you must restrict your arguments when you refer to the optimality considerations of a garbling scheme. This topic is currently under an intensive research.


Hard random lattices The content I ask in this question is in the following picture in [GPV08][1]. I do not understand the proof of the first claim in $\bf Lemma$ 5.2.  In the proof, which reprensents the uniform distribution over $\mathbb{Z}_{q}^{n}$ and which represents $\bf{u=Ae} \mod q$.

Could someone explain it to me? Thanks!

[GPV08] Craig Gentry, Chris Peikert, Vinod Vaikuntanathan, [How to use a short basis: trapdoors for hard lattices and new cryptographic constructions][1], August 25, 2008.

The first claim has three steps to it:

Assumption of Primitivity: We want to make sure that the matrix $A$ isn't such that the function $x\mapsto Ax\bmod q$ (equivalently, $A$ viewed as a linear operator $\mathbb{Z}_q^m\to\mathbb{Z}_q^n$) "misses" most of its codomain. Imagine that $A$ is the all zero's matrix --- then the claim can't possibly be true!

If $q$ were prime we could assume that $A$ is "full rank" and this issue would disappear. We often don't like to restrict to the case that $q$ is prime though (for example, $q = 2^k$ is common in practice), so our matrices become defined over rings-that-aren't-fields, and "rank" can be a slightly problematic construct to work with (In particular, consider the lattice with basis matrix $\mathsf{diag}(2,1,1,\dots,1)$. If $q$ is not prime, this may not be equivalent to the identity matrix, so despite being "full rank" it will not surject).

Instead, we assume that $A$ is surjective as a map. This can be described several different ways in the literature (here it is "the columns generate the codomain", other places the term "is a primitive matrix" is used. When $A$ is a vector one can specify "the GCD of its entries is one"). This ends up being the right analogue of "$A$ is full rank" to use when working over rings-that-aren't-fields like $\mathbb{Z}/2^k\mathbb{Z}$. I believe this notion still works over number fields (so in the RLWE case) as everything can be viewed as an integer lattice still, but am less familiar with this area.
Near-uniformity of Discrete Gaussians mod the lattice: Lemma 2.8 states the following:

  Let $\Lambda, \Lambda'$ be $n$-dimensional lattices with $\Lambda'\subseteq\Lambda$. Then, for any $\epsilon\in(0,1/2)$, any $s\geq \eta_\epsilon(\Lambda')$, and any $c\in\mathbb{R}^n$, the distribution of $(D_{\Lambda, s, c}\bmod \Lambda')$ is within statistical distance of at most $2\epsilon$ over $(\Lambda\bmod\Lambda')$

A useful simplification here is to set $\Lambda  =\mathbb{Z}^n$. Then, this states that for any $n$-dimensional integer lattice $\Lambda'$, that for "large enough $s$" that $(D_{\mathbb{Z}^n, s, c}\bmod \Lambda')$ is within $2\epsilon$ being uniformly distributed over $\mathbb{Z}^n\bmod\Lambda'$, the fundamental domain of $\Lambda'$.

This is "what the smoothing parameter is defined for". The smoothing parameter specifies the "phase transition" between the Discrete Gaussian being non-uniformly distributed over the fundamental domain of $\Lambda'$ (when working mod the lattice of course), and it being very close to uniformly distributed (for a graphical demonstration of this, look at this other question). As long as we take $s$ larger than the smoothing parameter of the relevant lattice, the uniformity follows easily as a consequence.
The quotient group:
It's worth mentioning explicitly what we should "expect $\mathbb{Z}^m/\Lambda^\perp$ to look like". Let $q$ be prime so everything is simpler. Recall that:

  $$\Lambda_q^\perp(A)  = \{x\in\mathbb{Z}^m \mid Ax \equiv 0 \bmod q\}$$

When $q$ is prime, this is just the kernel of the linear map $A : \mathbb{F}_q^m\to\mathbb{F}_q^n$. Then the group $\mathbb{Z}_q^m/\ker(A)\cong \mathsf{im}(A)$ by the first isomorphism theorem (for abelian groups). Of course we're dealing with $\mathbb{Z}^m/\ker(A)$ (no $\bmod q$ upstairs), but this doesn't actually matter --- as $\Lambda_q^\perp(A)$ is always $q$-ary (contains the sublattice $q\mathbb{Z}^m$), we have that all points in $\mathbb{Z}^m$ which differ by a point in $q\mathbb{Z}^m$ will be identified anyway, so we may as well pick representatives for these points and call them $\mathbb{Z}_q^m$, and "continue evaluating the quotient".

I'm under the impression this argument extends to the case of composite $q$ if one makes the appropriate substitutions of "linear algebraic arguments" to "module-theoretic arguments" along the way, but I haven't made the substitutions myself before, and don't feel like going through with it here. If someone has a reference I'd be interested.

Putting it together:

From here everything is fairly mechanical.
We want to analyze the distribution of $(D_{\mathbb{Z}^m, s, c}\bmod\Lambda_q^\perp(A))$.
By the second point this is within $2\epsilon$ (in statistical distance) of $\mathsf{Unif}(\mathbb{Z}^m/\Lambda_q^\perp(A))$. By the third point the underlying set of this is (assuming $q$ prime for simplicity) isomorphic to $\mathsf{im}(A)$, so the uniform distribution on the first set is identical to $\mathsf{Unif}(\mathsf{im}(A))$. Then, by the first point we have that $\mathsf{im}(A)\cong \mathbb{Z}_q^n$, so this distribution is simply $\mathsf{Unif}(\mathbb{Z}_q^n)$. In total, we end up with $(D_{\mathbb{Z}^m, s, c}\bmod\Lambda_q^\perp(A))$ being within $2\epsilon$ in statistical distance of $\mathsf{Unif}(\mathbb{Z}_q^n)$, which is the first claim.


Automatic csr sending In our project we have grpc server and clients which should satisfy mutual tls. So, there is CA and clients generate csr to sent to CA to signing it. Now I need to send csr manually to CA to sign it and also manually back to clients. If there are many clients, it becomes inconvenient.
Of course, I can add an additional server that will receive requests and send back, but I think that this is a complication and I am trying to find a generally accepted scheme.
I am new in this theme. How to organize it correctly? Or use a simple ready-made solution.

The ACME protocol was designed by the Internet Security Research Group, and is used by Let's Encrypt to sign domain-validation TLS certificates. Since the transport of GRPC is HTTP/2, which uses TLS for encryption and authentication (when enabled) that should be what you want.


What is the time complexity of the basic components of a symmetric cipher? I have a very basic knowledge on time complexity and even less on programming, so please bear with me. I am interested to know the time complexity in big-O notation of some of the basic operations in symmetric ciphers. In particular:

matrix multiplication (including permutation matrices)
XOR of bit strings
expansions, for instance expanding 64 bits to 128 bits
bit shifts
permutations using a P-box (say the one in PRESENT)
substitutions using an S-box (again, say the one in PRESENT)
combining the operations (as above or other operations)

Related to item 1: If I multiply (say) $vP$ where $v$ is a $1 \times n$ vector and $P$ is an $n \times n$ permutation matrix I see $1 \times n \times n$ multiplications and $n \times n$ XORs (assuming bits). So am I right to sat $O(vP) = n^2 + n \approx n^2$ ?

Related to item 2: a linear operation so I assume $O(1)$ for each XOR and therefore $O(n) = n$ for $n$-bit string XOR another $n$-bit-string.

Related to item 3: If expanding $64$ bits to $128$ bits then it seems there are $128$ operations so $O(n) = n$

Related to item 4: intuitively I should say $O(1)$ for each bit shift and therefore for $n$ bit-shifts $O(n)=n$.

Related to items 5 and 6: I really have little idea. But if it is the $PRESENT$ P-box then I suppose $64$ operations and therefore $O(n=64)=n$. As for the S-box, I think $O(n = 16) = n$, assuming the $PRESENT$ S-box.

Related to item 7: I think we add the time complexities of each component but can approximate the answer as the most time consuming of all terms.

I have looked at a few videos and books on time complexity but most speak in programming languages, and I cannot find anything simple on time complexity for cryptographic components (functions?) as describable above.

One final question:

I assume a cipher has a total time complexity. Where can I find the time complexities of a given cipher, especially DES, PRESENT and AES? And is there available time complexities per round of these ciphers?

I cannot find anything simple on time complexity for cryptographic components (functions?) as describable above

You wont really find anything because those components are generally not described that way. There are simply too many ways of implementing each component in hardware and software on multiple platforms, and they do not always obey the rules of big-O notation, a 1-bit XOR and a 64-bit XOR may take the exact same amount of time, but transform a 64X difference in data. Shifting by 1-bit usually takes the same amount of time as shifting by several bits. In hardware, a permutation may be done by arranging wires in a specific pattern, and take 0 additional time to complete, whereas in software a complex series of operations may be required to rearrange the data (like the DES initial permutation for example).

Things like matrix multiplication can be implemented as table lookups or as a series of more simple operations, sometimes bitsliced to improve performance. Increasing the size of the matrix can have wildly different outcomes in terms of time requirements based on the implementation method, since generating a table is only needed once.

Simply put, it is more common to describe the performance of those operations in cpu cycles on a specific platform, individually and as a group of operations, and as the entire algorithm. Then a given implementation/platform combination can be compared, and the best or most common used as a benchmark.


Do I need to use null bytes and \x80 in hash length extension attack? Say I want to perform a hash length extension attack. All the tools I have used use \x00 and \x80 to pad hashes (hlextend and hashpump). But is it necessary to use these bytes? Based on my understanding of padding (and this question: Computing the padding of MD5), it seems that I can use any byte I want. If so, how would I compute the new hash? Would it be the same with using some arbitrary character, like "5", as padding as if I had used null bytes?

But is it necessary to use these bytes?

Yes, it is, at least for most messages that you'll see in practice.  MD5 works by taking the message, and applying a fixed padding to it. This fixed padding involves, for messages which are a number of bytes (as opposed to, say, a message of 119 bits) an 0x80 byte, and for not huge messages, 0x00 bytes (in the length field if nowhere else).  Then, it runs an iterated compression function over the padded message, and the end result is the MD5 hash.

What the length extension attack does is artificially appends that exact padding pattern to the message; so when the MD5 processes that message, it performs the exact same operation, and so comes up with an intermediate state that is exactly what the MD5 hash output is (which we know).  After that, we can append anything else we want (and we can predict how MD5 will handle that, because we now know the MD5 state).

For this to work, we have to do precisely the same padding to the message that MD5 does; because it uses an 0x80 and some 0x00 bytes (for any reasonable message), you do too.


Security of Carter-Wegman polynomial authenticators, and their concatenation? Carter-Wegman polynomial authenticators

For a given finite field $(\mathbb F,+,\times)$ of $f$ elements, define a Carter-Wegman polynomial authenticator for a message $M=m_1\|m_2\|\dots\|m_l$ of $l$ symbols in $\mathbb F$ as $$H_{(r,s)}(M)=s+\sum_{i=1}^l m_{(l+1-i)}\cdot r^i$$ where $r$ and $s$ are uniformly random independent secrets over $\mathbb F$  (I'm restricting to neither $r$ nor $s$ reused, even though $r$ could).

Common fields $(\mathbb F,+,\times)$ are $GF(2^b)$ (equivalently: field $(\{0,1\}^b,\oplus,\times)$ where $\times$ is binary polynomial multiplication followed by reduction modulo a public irreducible polynomial of degree $b$ ), and $(\mathbb Z_f,+,\times)$ for prime $f$. AES-GCM uses $GF(2^{128})$ with polynomial $x^{128}+x^7+x^2+x+1$. Poly1305 uses $\mathbb Z_f$ with prime $f=2^{130}-5$ (and some restriction of the domain of $r$, and of the $m_i$'s).

Questions

Tight security bound for elementary attack model: for fixed public $l$ and $(\mathbb F,+,\times)$ of $f\gg l$ elements, an adversary chooses a message $M$ of $l$ symbols, obtains $H_{(r,s)}(M)$ for fresh uniformly random secrets $r$ and $s$, and makes one attempt to produce $H_{(r,s)}(M')$ for $M'\ne M$ of his/her choice (also of $l$ symbols). What's a tight upper bound of probability $\epsilon$ of success (undetected forgery) as a function of $f$ and $l$? Do we reduce $\epsilon$ by excluding some $r$, e.g. requiring $r\ne 0$ ? Are some fields better than others ?
Concatenation of authenticators using the same field: we consider $H_{(r,s,r',s')}(M)=H_{(r,s)}(M)\;\|\;H_{(r',s')}(M)$, with the $r$, $s$, $r'$, $s'$ uniformly random independent one-time secrets in $\mathbb F$. What's a new tight upper bound for probability $\epsilon$ of undetected forgery as a function of $f$ and $l$?
Concatenation of authenticators using different fields: we consider  $H_{(r,s,r',s')}(M)=H_{(r,s)}(M)\;\|\;H'_{(r',s')}(M)$, with $H$ (resp. $H'$) using field $\mathbb F$ of $f$ elements (resp. $\mathbb F'$ of $f'$ elements), with $f'\gtrsim f$ and some public way to plunge $m_i$ into $\mathbb F'$ , $r$ and $s$ uniformly random independent one-time secrets in $\mathbb F$, $r'$ and $s'$ uniformly random independent one-time secrets in $\mathbb F'$. What's a tight upper bound for probability $\epsilon$ of undetected forgery as a function of $f$, $f'$ and $l$? Is this lower than in 2. ?

Motivation

Wide Carter-Wegman polynomial authenticators are non-trivial to implement both efficiently and portably: portable C has no semantic for carry-less multiplication, and no type wider than 64 bits. A generic Poly1305 uses 25 integer multiplications plus significant additions and shifts for 128 bits of message processed (or double arithmetic which a lot of low-end platforms do not have in hardware). It is thus tempting to concatenate narrower authenticators, which are easy and usually efficient to implement: C99 provides arithmetic in $\mathbb Z_f$ for $f<2^{32}$, using the w = ( (uint64_t)u * v ) % f; semantic, and many hardware+compilers have good support for that (or perhaps w = ( (int64_t)u * v ) % f; for $f<2^{31}$ ).

Tight security bound for elementary attack model:

Well, here's the general theory; suppose the attacker had a valid message, MAC pair $(m_{1,...,l}, H)$ with

$$H=s+\sum_{i=1}^l m_{(l+1-i)}\cdot {r}^i$$

and he selects a different pair $(m'_{1, ..., l}, H')$.  His pair would authenticate if:

$$H'=s+\sum_{i=1}^l m'_{(l+1-i)}\cdot {r}^i$$

or, if $r$ happens to be a root of

$$0 = H-H' + \sum_{i=1}^l (m_{(l+1-i)} - m'_{(l+1-i)})\cdot {r}^i$$

This is an $l$-degree polynomial over a field, and hence has at most $l$ roots.  And, as $s$ is chosen randomly, the attacker gets no other information about what $r$ can be, and hence he has to guess blindly; the bottom line is that the probability of success for any chosen ciphertext is bounded by $l/f$ (or, more generally, the probability of success after $z$ queries is bounded by $lz/f$.  And, if we consider an attacker that selects $l$ values $a_{1..l}$, and uses $(x-a_1)(x-a_2)...(x-a_l)$ as the different polynomial, we can see this will succeed iff $r = a_i$ for some $i$, and hence this probability is tight.  (for $lz/f \le 1$).

  Do we reduce $\epsilon$ by excluding some $r$, e.g. requiring $r \ne 0$?

Actually, we increase it somewhat.  If the attacker knows that some of the potential values of $r$ are impossible, that is, there are actually only $f'$ possible $r$ values, he can use this knowledge to increase his success probability to $l/f'$.  As you can see, this doesn't harm security much if we just exclude a handful of values; however we probably don't want to eliminate a large majority of them.

  Are some fields better than others ?

Actually, no (other than the size of $f$); the above logic used no property of the field (other than that it was a field), and hence it applies equally to all fields.

  Concatenation of authenticators using the same field

The attacker gets to play the same game, he gets to pick $l$ values $a_{1..l}$, and he'll succeed only if both $r, r'$ are within the $a_{1..i}$ values (actually, he can pick different values for the different authenticators, as they do not share the constant term; that doesn't appear to change the conclusion).

Hence, we get a probability bound of $(l/f)^2 = l^2 / f^2$ (or, more generally, of $k$ authenticators, $l^k / f^k$)

At first glance, this looks better; however remember that, in this case, $f$ is smaller; if $f$ is $1/k$ the size of the field size of the original approach (that is, the same total tag size), then the success probability we allow an attacker increases by a factor of $l^{k-1}$.

This may be a reasonable approach, if $l$ isn't too large.  On the other hand, if we allow quite long messages, this just doesn't work.

  Concatenation of authenticators using different fields

Same reasoning applies, $l^2 / (f \cdot f')$.  Now, I don't know how feasible the attacker will find it to a common message that generates difference polynomials in the different fields all with lots of roots; I'm guessing that it may be possible, and so I wouldn't want to make a security assumption based on it.


Can I perform a division of two integers homomorphically using ElGamal? How can I perform a division of two integers homomorphically?
(Simplifying assumptions can be made if needed, that is, I am fine with dividing numbers that are whole and the result will be whole as well, e.g., simple divisions such as 4 divided by 2 are fine)

Given two ElGamal ciphertexts:
$$ C_1 = (C^{1}_{1}, C^2_1) $$
$$ C_2 = (C^{1}_{2}, C^2_2) $$

I can multiply them homomorphically as follows:
$$ C_r = (C^{1}_{1} \cdot C^{1}_{2} ,C^2_1 \cdot C^2_2) $$

The following does not seem to work to achieve division though:
$$ C_r = (C^{1}_{1} \div C^{1}_{2} ,C^2_1 \div C^2_2) $$

Let $G$ is a cyclic group with order $q$ and generator $g$.

Let $x$ be Alice's private key. The two messages $c_1$ and $c_2$ are encrypted with the public key of Alice;

$$c_1 = (g^{y_1}, m_1 \cdot g^{x y_1})$$

$$c_2 = (g^{y_2}, m_2 \cdot g^{x y_2})$$

Now to calculate $m_1/m_2$ in the encrypted values, calculate the inverse of $g^{y_2}$ and $m_2 \cdot g^{x y_2}$ in the group

$$ c_2'=\Big((g^{y_2})^{-1},(m_2 \cdot g^{x y_2} )^{-1}\Big) = (g^{-y_2},m_2^{-1} \cdot g^{-x y_2})$$

then multiply,

$$c_1  c_2' = (g^{y_1}  g^{-y_2}, \;\; m_1 m_2^{-1} \cdot g^{x y_1} g^{- x y_2})$$

Now, check the decryption.

$$s = (g^{y_1} g^{-y_2})^x = g^{x y_1 }  g^{-x y_2 } $$

$$s^{-1} =  g^{-x y_1 } \cdot g^{x y_2 } $$

$$ s^{-1} \cdot m_1 m_2^{-1} \cdot g^{x y_1} g^{- x y_2} =  m_1  m_2^{-1}  \cdot g^{-x y_1 }g^{x y_1}\cdot  g^{x y_2 } g^{- x y_2} = m_1  m_2^{-1}$$

Note: based on comments of Geoffroy and Mikeazo.


It doesn't. The mod operation does not have to be performed after exponentiation. Modular exponentiation can be implemented using modular multiplication (and modular addition). Modular multiplication in turn can be implemented relatively efficiently, for instance using a Montgomery multiplier.

Here's an example using decimals instead of binary; you know that $323 \times 323$ ends with a $9$ even without doing the full computation. This is a $\bmod 10$ operation. In the same way, you know that $323^3$ ends with a $7$ because $323 \times 323 \times 323$ ends with a $7$.


PublicKey Unknown Encoding I have a public key:

MIGJAoGBAKv4OKlpYBAQEFAAOCADqTnisSvdLP+mTswZJdbtk1J+4+qAySJuENCe
+1rcnERjdNa2LTS2y//REwXWo8Jd3mU42GfZJrJhSLFOgYnX3efuMBVebWlqUNGt
sMedxuVaFBL3SoqU7e5RELIsuArCJJIgz86BQDX0x63VpXAgMBAAE=

which, if you use any online base64 decoder, will say it’s invalid Base64 encoding – which is why decoding fails. But I can get it to decode using the Apache Commons Base64.decodeBase64() function.

My current implementation in Java is:

String PUB_KEY = "MIGJAoGBAKv4OKlpYBAQEFAAOCADqTnisSvdLP+mTswZJdbtk1J+4+qAySJuENCe+1rcnERjdNa2LTS2y//REwXWo8Jd3mU42GfZJrJhSLFOgYnX3efuMBVebWlqUNGtsMedxuVaFBL3SoqU7e5RELIsuArCJJIgz86BQDX0x63VpXAgMBAAE=";

byte[] keyBytes = Base64.decodeBase64(PUB_KEY);
X509EncodedKeySpec spec = new X509EncodedKeySpec(keyBytes);
try {
    KeyFactory factory = KeyFactory.getInstance("RSA");
    PublicKey key = factory.generatePublic(spec);

    Cipher cipher = Cipher.getInstance("RSA");
    cipher.init(Cipher.DECRYPT_MODE, key);
    byte[] decrypted = cipher.doFinal(Base64.decodeBase64("Zm/qR/FrkzawabBZYk7WfQJNMVZoZrwWTvfQwIhPMzAuqEO+y+sb/x9+TZwTbqmu45/GV4yhKv0bbDL8F6rif7RJap7iQUFQBDEIAraY42IGZ8pB6A0Q0RSnJWW+tLTLJg5cTrgZQ8sLoO+U03T6DE1wy73FU5h6XhXxZERo0tQ="));
    String tada = new String(decrypted, StandardCharsets.UTF_8);
    tada.length();
} catch (Exception e) {
    e.getMessage();
}

There already exists a C++ implementation of this – which works – but the moment I get to factory.generatePublic(spec) I get an InvalidKeySpec error.

I can tell you that with this public key and with the encrypted text I should get this unencrypted text: 2ABB43E83F7EC33D0D33F64BA5782E42.

What is wrong with the public key where I am getting an error about it being the wrong key spec?

MIGJAoGBAKv4...................3VpXAgMBAAE=
30818902818100 ABF8... ...DD5A57 0203010001
        7                             5

Overhead & public exponent are 7 + 5 = 12 bytes. You have a 1024 bit modulus = 128 bytes.
So a correct encoding would be 12 + 128 = 140 bytes, requiring ceil(140 / 3) = 47 * 4 = 188 base 64 characters.

You however seem to have 182 characters, so there are 6 characters missing in action. These characters are part of the modulus (because they cannot be anywhere else, you clearly have the head and tail of the public key). That means you have to find 6 * 6 bits that can have basically any value, for a total of 36 bits or 2^36 = ~69 billion possible values. The 6 bit values may be at any location as well. That would multiply the number of options with over 8 billion if I'm not mistaken or 33 bits. Unfortunately 69 bits is out of range for brute force efforts.

The best thing you can do is guess that you are missing very specific bytes.
Prime suspects are + and / signs, but it would be a long shot inserting 6 of these characters at every possible place, testing the modulus using whatever valid public key operation you are able to perform.

But in general, this is not an operation that is likely to succeed.


Dice rolls as entropy source? I would like to generate a 128 bit random number with dices, but I have heard that dices are pretty biased, especially low quality (non casino dices).

Would it make sense to generate a higher bit number, like a 1000 bit number? Would that "absorb" the flaws and biases exhibited in the dices. In the sense that the overall bias diminishes, the more bits you add to it?
What is the best method to make the bias go away?

Concatenating the individual numbers thrown into a  128 bit string
Multiplying the individual numbers thrown
A combination of both, for example with 2 dices: (R1+R2)x(R3+R4)x(R5+R6)…

…
  What is the best method to make the bias go away?
  …

No matter if we’re talking about the bias coming from manufacturing flaws, or the bias we know from casino-quality dice, you can use the Von Neumann skew-correction algorithm to generate uniformly random data from skewed input.

The Von Neumann skew-correction algorithm was published in “Various techniques used in connection with random digits.” (NIST journal, Applied Math Series, 12:36-38, 1951). Since the paper is hard to find online due to its age and publication date, I‘ve put a copy in my Google Drive account (PDF) for reference purposes.

The general idea behind Von Neumann’s skew correction is to consider sequences of rolls/coin-tosses/whatever instead of isolate ones while picking a sequence length long enough that an even number of possible outcomes has equal probabilities.

Explaining the Von Neumann skew-correction algorithm:

For dice, pick a sequence length where $n>2$. The reason for picking a sequence length of $n>2$ is that no subset of possible outcomes of equal probability for $n=1$ or $n=2$ has a cardinal divisible by $6$.

So, for this example, let’s simply take $n=3$. Doing so, the outcomes of any dice can be partitioned into 6 categories of equal probability according to the relative ordering of the successive numbers rolled – provided these numbers are all different.

We need this, so that sequences can be grouped according to whether the second number is greater – 1 – or smaller – 0 – than the first, and whether the 3rd number is greater 111,011 or smaller 100,000 than both the first and the second, or between them 110,001.

All 6 possible orderings will occur with equal probability because each of the sequences belonging to any of these orderings matches exactly one sequence of equal probability in every other ordering. Meaning: 1,2,4,1,2,4 matches the ordering 111, while 2,1,4,2,1,4 (which is equally likely to be rolled) matches 011.

EDIT

@fgrieu describes a different, yet equally practical implementation in his comment below.


How to select $g$ in Paillier Cryptosystem For my cryptography class project in university I have selected Paillier Cryptosystem as a course project http://en.wikipedia.org/wiki/Paillier_cryptosystem#Key_generation

In key generation it says

  Choose two large prime numbers $p$ and $q$

I have selected $p$ = 11 and $q$ = 17, it also satisfies the condition

  $gcd(pq, (p-1)(q-1))=1$

which makes my $n$ = 187 and ${\lambda}$ = 80

and now in 3rd point it says

  Select random integer $g$ where $g \in (\mathbb{Z}_n^∗)^2$

now what does it mean $g \in (\mathbb{Z}_n^∗)^2$?

there is a question What does $(\mathbb{Z}_n^*)^2$ mean? but it doesn't make any sense to me

so the first question is how can I select the random integer g?

In 4th point it says

  Ensure $n$ divides the order of $g$ by checking the existence of the following modular multiplicative inverse: $\mu\ = (L(g^{\lambda}\mod n^{2}))^{-1} \mod n$

it further says

  where function $L$ is defined as $L(u) = \frac{u-1}{n}$ .

can some one please help me to find out $g$ and $\mu$?

The public (encryption) key is $(n, g)$.
The private (decryption) key is $(\lambda, \mu)$.

with any example or link that can guide me to a correct path.

Thanks

The requirement is that your element $g$ is in $\mathbb{Z}_{n^2}^*$ and not in $(\mathbb{Z}_{n}^*)^2$.

The set $\mathbb{Z}_{n^2}^*$ is the set of integers smaller than $n^2$ that are relatively prime to $n^2$, i.e., you require an element $g$ from $\mathbb{Z}_{n^2}$ such that $\gcd(g,n^2)=1$.

$(\mathbb{Z}_{n}^*)^2$ on the other hand is the set of pairs $(a,b)$ such that $a$ and $b$ are from $\mathbb{Z}_n^*$.

You compute $\lambda=lcm(p-1,q-1)$ where $lcm$ is the least common multiple. Then for your chosen $g$ you have to check whether $a=L(g^\lambda \bmod n^2)$ (where $L(u)=\frac{u-1}{n}$ ) has a multiplicative inverse modulo $n$ (is an element in $\mathbb{Z}_n^*$), i.e., you have to check whether $\gcd(a,n)=1$. If this is the case, then compute $\mu$ as $a^{-1} \bmod n$. Otherwise, try with another $g$ until this condition is satisfied.


Data I/O operations for encrypted files I need to implement a simple approach on a Linux system to encrypt/decrypt data and I would appreciate any feedback from you. Basically, I need to change a bit the behavior of the functions read/write.

I've checked some options such as EncFS, but they only perform encryption/decryption at file level (decrypt/encrypt the entire file at once). However, I need some solution at a fine-grained level, such as at block level. To make things easier, we only append data at the end of the file and we don't change existing data of the file.

Consider the following use case, as an example:

File foo.txt is empty
Write 10 bytes to file foo.txt

Encrypt the input (10 bytes) and write it to the file foo.txt. Depending on the encryption algorithm, the plaintext and ciphertext sizes might differ.

Read 6 bytes from file foo.txt

How should you handle this situation? Should you decrypt everything you have and extract only 6 bytes?

What I have seen is that you most likely have to keep also metadata about the encrypted files as well (number of blocks, etc.). Thanks in advance!

Ad hoc…

What you’re describing is not much different from the encryption in storage systems… only that your “storage system” is a file (foo.txt) instead of a hard drive. Now, in a perfect world you would encrypt every block of data (that you store in foo.txt) with its own key, but that would be pretty impractical in your situation. From my point of view, the most obvious solution would be to use a “tweakable cipher” or a “tweakable narrow-block encryption mode”. They were designed to avoid (read: work around the problem) the “need separate key per stored data block”.

Therefore, and relying on your description, I’ld most probably opt-in for a “tweakable narrow-block encryption mode” like LRW (paper), XEX (paper), or XTS. An example representing one of the more frequently used implementations would be AES-XTS. Depending on your coding skills, it shouldn’t be all too hard to incorporate such a solution into the CRUD functionalities of your application.

But, it depends on the details…

For the sake of completeness, let me mention that there are other options out there, which might also lead to a valuable solution. I merely mentioned what I personally would tend to use, based on the information you provided. But choosing a fitting solution will strongly depend on things like the kind of data you want to store, how it’s formatted, what security level you expect, what specific scenario is to be assumed, etc. (Always check for potential attack vectors!) You will have to assess and verify all the little details to be able to choose a most optimal solution that perfectly fits your individual situation and needs.

One of many examples: If the filesize and available hardware capabilities permit it, you might be better off handling encryption/decryption on the whole file (using AES-CBC or something like that) instead of crypting the individual data-blocks you plan to create, read, update and delete. On the other hand, if we’re talking about a file that is bound to hold hundreds of thousands of individual data blocks/entries, and which therefore is bound to grow up to and beyond several gigabytes in filesize, loading that beast into system memory to wrangle with contained data will tend to be a bit… (let’s just call it) “non-optimal”.


Is ciphertext stealing important in relation to Blowfish? I am writing a simple messenger (as a proof of concept  not for production), and I came across Blowfish as being as being an interesting alternative to AES.

As it is not meant to be an actual product, I am not entirely concerned with something like E2E encryption, nor do I want to deal with certificates, so my goal is to use just a mid-speed block cipher for encryption.

During my development, I noticed that there were options for ciphertext stealing. How big is the security benefit from using it, and what are the costs?

Ciphertext stealing doesn't bring you any security benefits, although – if you're hell-bound on using CBC mode – it could avoid padding oracle attacks. Otherwise it is just a way to avoid padding the plaintext and therefore increasing the ciphertext size in CBC mode.

Ciphertext stealing is independent of the block cipher used. So you could use it with 3DES, Blowfish or indeed AES in CBC mode. It's also available in ECB mode but ECB mode itself is not considered secure.

Blowfish is not an interesting alternative to AES. Even Bruce Schneider, the principal engineer of the cipher, recommends against using Blowfish. Although it hasn't been broken its 64 bit block size makes it an uncomfortable fit to most modern modes of operation, especially those that use CTR underneath.

When using messaging you should probably have a look at AES/GCM or another mode of authenticated encryption. Ciphertext stealing is not that interesting, just use something based on counter mode such as GCM. CTR and most other modes of operation do not require padding nor ciphertext stealing.

Choice of the block cipher isn't that important; creating a secure protocol is much harder. Then you can drop in any modern, secure block cipher you want. To play it safe, just use AES.


Will elliptic curve cryptography be weakened? Today this post is going around on the internet and there someone wrote that it could perhaps mean that elliptic curve crypto will be weakened.

Here's the link: https://plus.google.com/+DavidRoberts/posts/KcjNn99tYaa

Can someone perhaps clarify this?

From: https://plus.google.com/+DavidRoberts/posts/KcjNn99tYaa

  David Hansen

  The result announced by Taylor has absolutely nothing to
  do with elliptic curve cryptography, and no effect thereon.


What does the mask generation function in PKCS#1 output if the generated mask is shorter than the specified mask length? I am implementing RSA-OAEP with the mask generation function as specified in PKCS #1. It says after producing the variable T to "output the leading maskLen octets of T as the octet string mask". However, in one part of RSA-OAEP, where the mask generation function is used on a random seed, maskLen is greater than T. I don't believe I put in the wrong maskLen. RSA-OAEP does not work unless the output of the function is of the specified maskLen. Should I copy T to a byte array of length maskLen?

In MFG1, the size of $T$ in octets of the provisionally generated mask is never smaller than the specified $maskLen$ at the point where we want to

  Output the leading $maskLen$ octets of $T$ as the octet string $mask$.

That follows from the fact that $T$ was built as the concatenation of $\lceil maskLen/hLen\rceil$ hashes, each of $hLen$ octets.

See the algorithm given in PKCS #1 V2.2, section B.2.1. Notice that the notation $\lceil maskLen/hLen\rceil$ means that the division is with the rounding upwards. In C and Java, if maskLen > 0, that is obtained as (maskLen - 1)/hLen + 1. This can not cause overflow, and the final + 1 nicely cancels with the prescribed - 1 in $\lceil maskLen/hLen\rceil-1$.


Is it possible to verify a clearsigned message with a short public key (fingerprints)? For practical reasons, I'd like people to be able to post clearsigned messages with their public key fingerprints (8E570D9F7F70256595769E49F9BC5BCAD7E18635) for the system to check. However, the libraries I see all seem to require a full public key certificate to do verification. Is there a way to do it with just fingerprints?

No, it isn't possible to use a fingerprint as a key to verify signatures.

The PGP fingerprint is a hash of the public key material, see RFC 4880 section 12.2; it doesn't actually contain the public key, and as such it is not correct to speak of a fingerprint as a “short public key” as you did in your question—it is more like a unique key identifier.

A hash function maps an arbitrary-length input to a fixed-length output. One of the requirements for a cryptographic hash function is preimage resistance, i.e. given an output hash, it is difficult to find the input value to the hash. In this case, the input value to the hash would be the public key that was put into the hash. More to the point, the hash function that is used to generate the fingerprint effectively “loses” the public key information that you need to verify signatures.

Considering the size of the public key data, just trying potential public keys by brute force until you re-create a fingerprint to re-discover the public key information at runtime will also not work because it is too computationally expensive.


Malleability of ElGamal and Hashed ElGamal Question: Suppose A encrypts a number $x$ which indicates her bid on a contract, using ElGamal encryption. Say that the encryption of $x$ produces a ciphertext $c$. Explain how E can modify $c$ to make it an encryption of $100 \cdot x$.

Answer: E is exploiting the malleability of ElGamal.  She can take the ciphertext pair $(c_1,c_2)$ Where $c_1$ is $g^y$ and $c_2$ is $m * h^y$  and multiply $c_2$ by $100$ to get the desired results.  A can protect herself from this by used a hashed version of ElGamal

Is this correct?

There are different crypto-systems that have been called Hash-Elgamal. The one your exam refers to is likely whatever was included in your course. Without knowing that, we can't necessarily answer your question.

The most common is the Elgamal variant defined with encryption function: $c=\mathsf{Enc}(m,r)=\langle g^r, \mathcal{H}(y^r)\oplus m \rangle$

This is still a malleable encryption function, except that the adversary must xor in the amount they want to change the encrypted message by. So strictly speaking, it may protect against the exact attack of multiplying in constants, but it does not prevent the broader attack of being able to manipulate a message under encryption (without knowing the message).

Hash Elgamal could also refer to the Fujisaki-Okamoto heuristic applied to Elgamal. This prevents malleability but can also lose the CPA-security of Elgamal. Other Elgamal variants that use a hash function are Cramer-Shoup (mentioned by @jalaj) and DHIES. These are both secure against any malleability (they are CCA-secure) however they aren't typically referred to as hash Elgamal.


SHA1 Partial Collision I'm working on a little python script that reads in two fairly similar English sentences (they're in text files - reading them in) and I'm trying to force a SHA1 partial collision (e.g. first 32 bits of each hash are equivalent).

Currently, my logic of thinking is as follows:

Concatenate empty space to the end of string 1.
Hash string 1.
Concatenate empty space to the end of string 2.
Hash string 2.
Check if hash_of_string_01[:32] exists in the dict, if not, move on - else exit program.
Check if hash_of_string_02[:32] exists in the dict, if not, move on - else exit program.
Add both new hashes to the dict.
Loop...

However, this isn't anywhere near efficient, nor entirely correct. I'm trying to wrap my head around how I can approach this solution...

Any guidance you can provide me would be valuable! Thank you. :)

It is wanted a partial collision (over $b=32$ bits) between hashes of strings starting in distinct strings 1 and 2. I won't directly answer homework, but my hints outgrew a comment.

The solution presented should work, though details allowing to output the colliding strings are left out, and there are inefficiencies. Towards guiding optimization, I suggest estimating (perhaps, in big-$\mathcal O$ notation)

the expected number of steps in the algorithm,
the expected cumulated size of the hashed strings;
the expected number of insertions (and searches);
required memory size (which depends on the aforementioned details).

If 4 becomes outrageous, be smarter: minimize what's in the dictionarie(s), and make a second hash pass to detect the other colliding string; or store a value allowing to reconstruct that string, rather than the string itself.

You'll find that 2 suggests that (at least when $b$ grows), the naive method of obtaining the hash of a string by hashing it from the start dominates the cost of the calculation. That can be fixed in at least two ways: hashing shorter strings (hint: as suffix, combine space and some other character with similar rendering, such as non-breaking space); or if that's not allowed, being smarter at computing the hash of long strings with the same start (hint: keep appropriate hash states).

After these tweaks, if insertions and searches in the dictionaries become a serious bottleneck, or if one is tight on memory, or otherwise want to get rid of dictionaries, one can use Floyd's cycle finding algorithm with an appropriately defined function (hint: craft a function $f$ over $\{0,1\}^b$ such that finding a collision for $f$ solves the problem with odds about 50%). This is a great way to solve the problem, although it requires somewhat more hashes than techniques using a dictionary.

If $b$ grows to the point that the hashing needs to be distributed, see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website).


Termonology help: What is using AEAD without encrypting data called? I'm using ChaCha20-Poly1305 in a "full AEAD" mode, where a payload of data is encrypted and a block of unencrypted "additional data" is secured as well.

However, I'd like to also occasionally use the same algorithm without encrypting, just appending the payload of data that would normally get encrypted to the additional data, using an encrypt length of zero.

The tag is to best I can tell, a tag. It's not really a signature, it's not a hash, it's pretty close to a mac. Is tag in this case colloquially synonymous with anything else?
Is it right to say ChaCha20 in AEAD-mode? I know GCM has GHASH and GMAC, but I think those are the Galois part. Would be it be fair-enough to say I'm using ChaCha20 in HMAC mode? What would be the right way to phrase this?

The tag is to best I can tell, a tag. It's not really a signature, it's not a hash, it's pretty close to a mac. Is tag in this case colloquially synonymous with anything else?

It is not just close to a MAC—it is a MAC.  Various synonyms:

message authentication code / MAC
MAC tag
authenticator
authenticator tag
authentication tag

  Is it right to say ChaCha20 in AEAD-mode? I know GCM has GHASH and GMAC, but I think those are the Galois part. Would be it be fair-enough to say I'm using ChaCha20 in HMAC mode? What would be the right way to phrase this?

ChaCha/Poly1305, as used in, e.g., is a specific authenticated cipher (or AEAD).  So is AES-GCM.  You shouldn't worry about the method by which they are constructed—what is important is the security contract of the whole thing.  You should generally forget the archaic ‘mode of operation’ way of thinking that requires a user to choose a block cipher and a mode of operation from two different cauldrons of unintelligible acronym soup and then mix them.

If you use ChaCha/Poly1305 with an empty ciphertext, there's no specific name for it, but it would be like AES-GMAC, which is AES-GCM with an empty ciphertext.  You could say you are using ChaCha/Poly1305 as a (nonce-based) message authentication code, I guess.

If you're really interested in the acronym soup (which is not useful in isolation outside the cryptography literature):

GHASH is a universal hash family based on polynomial evaluation in $\operatorname{GF}(2^{128})$.  Cheap in hardware, slow and often leaky through side channels in software.
GCM is a method of constructing a nonce-based authenticated cipher out of a 128-bit block cipher and GHASH.
GMAC is GCM with an empty ciphertext (but usually nonempty additional data) which serves as a nonce-based message authentication code.

None of these are ever used much if at all outside AES-GCM.  And:

HMAC is a method of constructing a pseudorandom function family out of a fixed hash function like SHA-256.  It is not related to GMAC, GCM, GHASH, Poly1305, ChaCha, or AES, except insofar as (a) it can also be used as a message authentication code like AES-GMAC or ChaCha/Poly1305 with empty ciphertext, and (b) it can also be used as a PRF, including as a stream cipher, like ChaCha.


Challenges of Fiat-Shamir Transformation of ZK Proof / Sigma Protocol Let $\Sigma$ be a sigma protocol whose commitment, challenge and response phases are $\Sigma_1, \Sigma_2, \Sigma_3$, respectively.

In Fiat-Shamir Transformation, the challenges are $H(\Sigma_1)$ where $H$ is some hash function.

However, in some literature, instead of having $H(\Sigma_1)$ it is $H(x \parallel \Sigma_1)$, where $\parallel$ denotes concatenation and $x$ is the common input. For example, if $\Sigma$ is the graph 3-coloring protocol, $x$ would be the corresponding graph.

Why consider the concatenation with $x$? Is $x$ there in order to prevent malleable attacks?
Consider a language $L \in$ NP and suppose that a prover P wants to prove to a verifier V that $x \in L$. We use the classical reductions of $x$ to a SAT instance and then to a G3C instance. Call this reduction $t$. In this way, $x \in L$ iff $t(x)$ is a 3-colorable graph. Now we can apply the Fiat-Shamir Transformation, and the challenges become $H(t(x) \parallel \Sigma_1)$.
Is it possible to make the challenges $H(x \parallel \Sigma_1)$ instead of $H(t(x) \parallel \Sigma_1)$, thus avoiding increase of the input of $H$?

Thanks in advance.

If the challenge is calculated as $H(\Sigma_1)$ the transform is called the weak Fiat-Shamir (wFS) transform. On the other hand, when the challenge is computed as $H(x\mathbin\Vert \Sigma_1)$ the transform is called the strong Fiath-Shamir (sFS) transform.

In scenarios where the attacker can choose adaptively the statement she would like to prove, the proof system is not secure anymore, ie. it is not a proof-of-knowledge anymore. For instance, this leads to many practical attacks against the Helios voting system. Let's consider the Schnorr identification as an example where the wFS transform is not secure.

In a group $\mathbb{G}$ of order $q$ generated by $G$, it proves knowledge of an exponent $x$ satisfying the equation $X = G^{x}$ for a known $X$. Viewing $(x, X)$ as a signing/verification key pair and including a message in the hash input yields a signature of knowledge. To create a proof, the prover picks a random $a\leftarrow \mathbb{Z}_q$ and computes $A = G^a$. She then hashes $A$ to create a challenge $c=H(A)$. Finally she computes $f=a+cx$;
the proof is the pair $(c, f)$ and the verification procedure consists in checking
the equation $c
= H\Big(\frac{G^f}
{X^c}\Big)$.

However, if the goal of the adversary is to build a valid triple $(X, c, f)$ for any $X$ of her choice, then this protocol is not a proof of knowledge anymore unless the discrete logarithm problem is easy in $\mathbb{G}$. Suppose indeed that there is an extractor $K$ that, by interacting with any prover $P$ that provides a valid triple $(X, c, f)$, extracts $x = \log_G(X)$. This extractor can be used to solve an instance $Y$ of the discrete logarithm problem with respect to $(\mathbb{G}, G)$ as follows: use $Y$ as the proof commitment, compute $c = H(Y )$, choose $f\leftarrow \mathbb{Z}_q$ and set $X = \Big(\frac{G^f}{Y}\Big)^{1/c}
$. Since the proof $(Y, c, f)$ passes the verification procedure for statement $X$, the extractor $K$ should be able to compute $x = \log_G(X)$ by interacting with our prover. We now observe that, by taking the discrete logarithm in base $G$ on both sides of the definition of $X$, we obtain the solution $\log_G(Y ) = f − cx$ to the discrete logarithm challenge.

A nice paper describing the pitfalls of the wFS transform can be found here.

Since this is an instance of the sFS transform, your proposed change yields a secure ZKP, for proof see Section 4. in the above linked paper.

However, I'm not aware of any practical deployment of ZKPs which would use such reduction techniques. Generic ZKPs for NP-complete languages are overkill and inefficient in most application scenarios. In my opinion, those results are mostly considered as theoretical results to show that there exists ZKPs for all NP languages.


Encryption-Decryption-Encryption I have learned from Applied Cryptography that triple encryption with three independent keys in encryption-decryption-encryption (EDE) process gives security not higher then $2^{2n}$ when it comes to meet-in-the-middle attack, where $n$ is keysize. If the triple encryption is done in encryption-encryption-encryption (EEE) process instead, is the security still the same as in EDE process or less?

I'm just curious to know how and how much security does this middle decryption provide?

EEE and EDE are effectively the same in terms of security.  EDE is used because it is "backwards compatible:" by setting all three keys to be the same, it becomes equivalent to just single encryption (E) with that key.


perfectly secret with key chosen uniformly Prove or refute: Every encryption scheme for which the size of the keyspace equals the size of the message space, and for which the key is chosen uniformly from the keyspace, is perfectly secret.
My attempt:
I think the statement is false because I made a counterexample:
$M = \{a, b\}, K = \{k_1, k_2\}, C = \{0, 1\}$. Let $\operatorname{Enc} (k, a) = 0$ and $\operatorname{Enc}(k, b) = 1$ for $k\in\{k_1, k_2\}$. The algorithm will return $a$ in the input ciphertext $0$ and $b$ in the input ciphertext $1$. Clearly, the schema is correct. But if we compare with the rule: $$\Pr [C = c | M = m_0] = \Pr [C = c | M = m_1]$$ We have to : $$\Pr [C = 1∣M = a] = 1 \neq 0 = \Pr [C = 1∣M = b]$$

What now follows "My attempt" (added by kelalaka from here) is IMHO a good refutation of the proposition.
The king of proofs is a well-justified counterexample.


ECDSA non random k - Retrieve private key At the moment I'm playing around with ECDSA. I know that I can retrieve the private key if the same K is used to sign two messages.

I tried to use this script: Ruby Script to crack the private key. But I'm always getting an error:

  signature_der_string.rb:14:in `decode': null is wrong length (OpenSSL::ASN1::ASN1Error)

My signatures start with a leading 0. If I leave out the 0 I get a different error

  `decode': too long (OpenSSL::ASN1::ASN1Error)

Can you help me what I'm doing wrong?

msghash1_hex = '4992c90022d12b85555493d3dcca55671b4047c1'

msghash2_hex = 'fced62bb70b5af004e8720342d036da02009e5e8'

sig1_hex = '436c79af2252b161af0b74e3eeb4064af334c483e8708fe709c46b1aa480fa49b017fb020fbc9717c6bf50ada23a820'

sig2_hex = '436c79af2252b161af0b74e3eeb4064af334c483e8708fe734065fe380b95c601f118c047976b3007831690806e10f4'

I have modified this Ruby script to not require public keys and to allow direct (r,s) input. Funnily enough, I stumbled on this thread (created two hours ago as of writing) on Google searching for the exact same problem. Note that I am using Secp192r1 (due to a CTF challenge), so feel free to modify that to your likings:

require 'ecdsa'

msghash1_hex = '000000000000000000000000000000000000000000000000'
msghash2_hex = '000000000000000000000000000000000000000000000000'

sig1 = ECDSA::Signature.new(0x000000000000000000000000000000000000000000000000, 0x222222222222222222222222222222222222222222222222)
sig2 = ECDSA::Signature.new(0x000000000000000000000000000000000000000000000000, 0x333333333333333333333333333333333333333333333333)

group = ECDSA::Group::Secp192r1

def hex_to_binary(str)
  str.scan(/../).map(&:hex).pack('C*')
end

msghash1 = hex_to_binary(msghash1_hex)
msghash2 = hex_to_binary(msghash2_hex)

r = sig1.r
puts 'sig r: %#x' % r
puts 'sig1 s: %#x' % sig1.s
puts 'sig2 s: %#x' % sig2.s

# Step 1: k = (z1 - z2)/(s1 - s2)
field = ECDSA::PrimeField.new(group.order)
z1 = ECDSA::Format::IntegerOctetString.decode(msghash1)
z2 = ECDSA::Format::IntegerOctetString.decode(msghash2)

k_candidates = [
  field.mod((z1 - z2) * field.inverse(sig1.s - sig2.s)),
  field.mod((z1 - z2) * field.inverse(sig1.s + sig2.s)),
  field.mod((z1 - z2) * field.inverse(-sig1.s - sig2.s)),
  field.mod((z1 - z2) * field.inverse(-sig1.s + sig2.s)),
]

private_key = nil
k_candidates.each do |k|
  private_key_maybe = field.mod(field.mod(sig1.s * k - z1) * field.inverse(r))
  puts 'Private key maybe: %#x' % private_key_maybe
  next
end

Signature.new(r,s) are the parameters above. msghash_hex is basically the hex version of your HASH(message) without 0x and with quotation marks around it to make it into a string to be processed later.


AES and GOST 28147-89 "Magma" Comparison I am trying to understand how AES is comparable to GOST 28147-89 "Magma". Like for parameters such as bit shifting and addition of the subkey to the input, which are a part of Magma, what is their replacement in AES? Also, how is S-box application in AES different from that of Magma?

Why is swapping of halves not required in AES?

I am trying to understand how AES is comparable to GOST

Except for them both being block ciphers, and relying on similar components (e.g. sboxes), there is actually very little similar to how they work internally.

GOST (Magma, as Squeamish points out, GOST is a fairly generic term) is a fairly straight forward Feistel cipher internally, where the block being operated on is split into two halves, and then one half is modified (based on the other half and the key); this is done 32 times.  Decryption is done by performing the cipher, but with an inverted key schedule.

AES, in contrast, is a Substitution/Permutation cipher; each round (except the last, which is slightly different) can be viewed as the concatenation of four operations, each of which operates on the entire block.  Decryption can be viewed as performing each of these suboperations in reverse (as each one is invertible).

  Like for parameters such as Bit shifting

AES doesn't have any explicit 'bit shifts'.  Now, one of the suboperations is called MixCollumns; in the forward direction, it involves a Galois multiply of the elements by 1, 2 and 3; I suppose you could look at multiplying by 2 and 3 as 'kind of' bit shifting, but that's a strained comparison IMHO.

  addition of the subkey to the input

Magma stirs in the subkey by xoring the input to the sbox (which affects the other side).  In contrast, AES xor's the subkey into the entire block.

  how S-BOX application in AES is different than GOST?

Magma uses the sboxes (8 different 4 bit to 4 bit sboxes) as a part of the Feistel function (to select the value that affects the other side).  In constrast, as one of the suboperations, AES applies the (single 8 bit to 8 bit sbox) sbox individually to each byte of the block (which implies that the AES sbox must be invertible).

  Why swapping of halves is not required in AES?

Because AES is not a feistel network.  Magma swaps halves, to make decryption easier (so that the decryption operation is precisely the same as the encryption operation, except that the key schedule is reversed).  AES uses a different method for doing decryption, and so it has no reason to swap halves.


Can data over a very low bandwidth channel still be encrypted? If you have a very low bandwidth channel, can encryption still be used?

Another way of putting this might be, does encrypting well increase the size of the data significantly?

Are there good encryption techniques that keep the block size the same?

If the sender and recipient can agree on the nonce of every message from existing context, so that the nonce either doesn't need to be transmitted or can be derived from metadata that must be transmitted anyway, then a stream cipher can be used to encrypt with no length expansion.

But the problem here is that you likely don't want just plain encryption, but authenticated encryption (AE), and AE algorithms generally require an authentication tag to be transmitted along with messages, which is an overhead that expands message size.

There do exist however AE algorithms that under limited circumstances could be used to encrypt and authenticate with no length expansion.  One example is the still experimental CAESAR competition candidate AEZ, which claims the following property (from the v5 spec, p. 10):

  Exploitation of domain-specific redundancy. In many contexts, plaintexts have a certain expected structure. This might arise because the message was produced by or for a particular protocol. We intend that if the user checks for the anticipated structure and regards messages as inauthentic if they don’t comply, then this check augments authenticity and correspondingly lessens the need for the nominal redundancy that is inserted by AEZ before enciphering (that is, the extra ABYTES zero bytes).

The following guideline is given for when a very low ABYTES (authentication tag length) value may be safely used (p. 13):

  Applications should not reduce ABYTES to zero or some other small value without ensuring that, combining the ABYTES zero bytes with
  any decryption-verified redundancy, there remain enough total bits $r$ of redundancy that forging each message with probability $2^{−r}$ is alright.

AEZ however is still very much at an experimental, cryptographic competition phase, so if you need a solution today you're just going to have to use a well-established AE scheme, and that will require length expansion.


Malleable encryption What I would like to achieve is the following:

Alice sends to Bob the encryption of a datagram that has the following format:

| 256-bit number | SomeLongArrayOfZeroes |

Bob knows the decryption key.

But before the datagram reaches Bob, there are some intermediaries which I would like to be able to add some additional 256-bit numbers. These third parties should not be able to read the first 256-bit number which was included by Alice. Let's also assume that these third parties know which portions of the ciphertext they have to modify in order to not modify data inserted by other parties.

I was researching homomorphic encryption but it looks like an overkill for this purpose. There's no need for two ciphertexts to interact with each other. I just need to be able to add additional data to already encrypted ciphertext which already contains some information without imposing damage to it. Assuming the other parties will follow some rules so as not to damage the prefix. A third party should not be able to decrypt information added by the other third party.

In the end, Bob should be able to decrypt the message using the key provided by Alice.

Any suggestions? I was thinking about some kind of a stream cipher. What are the possible solutions?

Several cryptosystems possess this partially homomorphic property. Notable examples include Benaloh, and Naccache-Stern which generalizes it, as well as Damgård–Jurik which generalizes the Paillier cryptosystem.

A worked example of the latter scheme:

The encryption primitive is defined as $E(m)=g^m\cdot r^n \mod n^2$ for a random element $r \in \mathbb{Z}$. From this we can see that given two ciphertexts we have:
$$E(m_0)\cdot E(m_1) = (g^{m_0}\cdot {r_0}^n) \cdot (g^{m_1}\cdot {r_1}^n) \mod n^2$$
$$E(m_0)\cdot E(m_1) = g^{m_0 + m_1}\cdot {(r_0 \cdot r_1)}^n \mod n^2$$
$$E(m_0)\cdot E(m_1) = E(m_0 + m_1) \mod n^2$$

So we can compute the encryption of the addition of two plaintexts from only the ciphertexts, without revealing them, by simply multiplying the ciphertexts.

Additionally, if we know the value of $m_1$ then we can avoid using the encryption primitive and directly compute as follows:
$$E(m_0)\cdot g^{m_1} = (g^{m_0}\cdot {r_0}^n) \cdot g^{m_1} \mod n^2$$
$$E(m_0)\cdot g^{m_1} = g^{m_0 + m_1}\cdot {r_0}^n \mod n^2$$
$$E(m_0)\cdot g^{m_1} = E(m_0 + m_1) \mod n^2$$

Now, by viewing multiplication as repeated addition, we can extend the homomorphic property to multiply by a constant, by implementing repeated ciphertext multiplication using exponentiation:
$$E(m_0)^{m_1} = (g^{m_0}\cdot {r_0}^n)^{m_1} \mod n^2$$
$$E(m_0)^{m_1} = g^{m_0 \cdot m_1}\cdot {({r_0}^{m_1})}^n \mod n^2$$
$$E(m_0)^{m_1} = E(m_0 \cdot m_1) \mod n^2$$

EDIT: Thanks tylo for specific examples


Is SHA-256 safe and difficult to crack? I am trying to crack a SHA-256 hash but I am not sure how to approach this in an efficient way. The following is known of the original non-hashed content:

64 characters long
only consists 0-9 and a-z (no capital letters)
the original content does not consist dictionary words
the hash is not salted

I have done some reading on the subject of cracking hashes and some information I have read is conflicting. For example, one said on a public forum that SHA-256 is virtually impossible to crack while the other said that it's a rather poor method for password storage as it could be cracked easily.

Is SHA-256 a safe method to hash passwords with (if not, what are the alternatives) and how do I crack a given hash in an efficient way (assuming the given criteria above).

Thanks in advance!

SHA-256 is a relatively poor way to store passwords but it is considered to be pretty much impossible to "crack". That is, retrieve the original plaintext from the hash.

The reason it is poor to use for passwords, especially without a salt, is due to the fact that it is inexpensive to compute, thus more vulnerable to brute force and rainbow tables etc.

You won't be able to crack the hash you have been provided with.

If your question is about how to securely hash passwords, consider something like PBKDF2 if you still want to use SHA256 underneath.


Can a message and one time pad each encrypted with separate ciphers be weaker than the stronger of either cipher? Assume you have:

A truly random one time pad, $P$
A plain text message, $M$
Two symmetric ciphers, $C_S$ and $C_W$, where $C_S$ is always more secure than $C_W$

Assume the keys have already been securely exchanged and the attacker intercepts everything Alice transmits.

In theory, can $C_S(P \space \oplus \space M)$ and $C_W(P)$ taken together be less secure $C_S(M)$?

Also, is $C_S(P \space \oplus \space M)$ and $C_W(P)$ always more secure than $C_S(M)$.

In longer form, if I XOR a message with a one time pad and encrypt that with one cipher and encrypt the one time pad with a different cipher, can that be less secure than just using the stronger of the two ciphers? Is it the case that it would always be stronger?

No, it can cannot be less secure. The proof is simple: if P is ever found out then the security of the strong cipher still protects $P \oplus M$ and thus $M$.

However if the one-time-pad $P$ ever leaks then it can be used to break the weak cipher, and in that case the result is just as secure as the strong cipher. It is generally not a good idea to rely on data to be kept secret forever. And it is certainly not a good idea to rely on security that may or may not be present.

Outside of theoretical security, the weak cipher may also have issues with e.g. padding oracle attacks that could leak $P$, in which case only the strong cipher will be left.

All in all, without additional details, I would rate this about as secure as the strong cipher, so the one time pad doesn't seem to have much benefit (certainly compared to, for instance, frequently using fresh keys).


Looking for cryptographic secure hash algorithm(s) that produces identical root hash for differently sliced hash list I have a scenario similar to the one described in Wikipedia: hash list, but with a twist. I'm looking for a cryptographically secure hash function that would create the same root hash for the same file, no matter how the the file is chopped up for the individual hashes in the list.

E.g. case 1: File is divided into 3 parts; the hash list consists of the hashes for the 3 parts; the root-hash is computed from the 3 hashes. case 2: Same file is divided into 2 parts; the hash list consists of the hashes computed for the 2 parts, the root hash is computed from the 2 hashes. Since it is the same file I want the root hash to be the same.

Is this doable (maybe with some restrictions on number and size of file parts)?

[Edit]
Specific use case:
My system stores files for users. Large files are usually sent / stored in smaller chunks (currently I don't control in which way the files are split up into chunks). Each chunk is encrypted beforehand by the client, but accompanied by a hash of the unencrypted content. I now would like to know if two users upload the same file (as this allows me to do some optimization) without having to know the content of the file. So if I could compute a "hash" of the whole file by using the individual chunk hashes I could easily achieve this.

A Hash Tree is meant for that. A binary tree seems fit. I'll restrict the description to something directly derived from SHA-256 (256-bits output, 512-bit hashed per round).

A parameter n>0 is selected, defining a "superblock" size of n*512 bits. Say 8192 bits (1kB, for n=16); n=1 works, but a higher value improves computing efficiency markedly.
The file is padded as in SHA-256, and conceptually organized into m superblocks of that size (the last superblock's size might be shorter, but is mutiple of 512 bits; the padding might be in the last superblock, or span the last two superblocks).
The file is chopped in segments of consecutive superblocks, with the limit of segments on superblock boundaries. Each computation point is assigned a segment which it receives (or generates and pads).
Each computation point separately hash each superblock in its assigned segment, using SHA-256 less padding. Each superblock requires n hash rounds (except the last which may require less). Most of the rounds are performed here (exactly as many as for SHA-256 of the whole file), in a distributed manner.

All the hashes obtained at step 4 form the m leaves on top of a single overall binary tree with a 256-bit hash at each node, and structure independent of how the file was chopped. Each of the m-1 non-leaf node of the tree will be the hash, obtained with one round, of the 512 bits in the two nodes linked on its top-left and top-right. The bottom node of the tree will be the final hash. It will be independent on how the file was chopped at step 3, because the computation will be performed according to the same tree regardless of the chopping.

[drawing of tree needed]

All branches in the tree join adjacent levels, except on the right where the j+1th level from the top is skipped when the jth lower-order bit of m-1 is 0.
The computation point responsible for a segment computes the hashes for nodes which have all their leaves assigned to that segment, and must keep the others. This needs precise organization [and is left as an exercise to the reader; my earlier description was flawed].
Each computation point returns its partial result. That will include Ceil(Log2(k+1)) 256-bit hashes at most, for the partial hash of k superblocks. If the communication is centralized, the central point finishes the calculation, re-hashing according to the same binary tree as necessary. With decentralized communication, it is advantageous to aggregate partial results with a peer handling a segment of the file just before or after, which might allow to perform slightly more of the work.

Note: Computations can be interleaved to reduce storage requirements. There is a total of m-1 extra rounds in steps 5 and 6, an overhead of about 1/n, distributed in part.


Combination of two stream ciphers Recently, I've been wondering what happens when I combine two stream ciphers $f_1$ and $f_2$ by xoring the keystream, so the final cipher would be:

$C = P \oplus f_1(K_1) \oplus f_2(K_2)$

$P = C \oplus f_1(K_1) \oplus f_2(K_2)$

Obviously, the keystreams shouldn't be the same because they would negotiate each other, so a few scenarios shouldn't apply:

$f_1 = f_2$ and $K_1 = K_2$ because they obviosly would create the same keystream.
$f_1 = f_2$ and $K_1 \neq K_2$ but there $f$ is insecure and $K_1$ and $K_2$ are part of a related-key attack so $f$ produces the same keystream.
Really bad luck?

Another thought was that the combination could be used to double the key length, as long as there are not related keys. Also given that $f_1 \neq f_2$ and an attacker is able to compute the keystream of only one of both,  he would be left with $C \oplus f_\mathit{other}(K)$ making the combination as secure as the most secure cipher used.

Finally, one last thought I had is that such patterns are already used in stream ciphers (e.g. A5/1) when LFSRs are combined so they might be secure?

This sort of combination is vulnerable to a meet-in-the-middle attack.  Let's start from one of your equations:

$$
C = P \oplus f_1(K_1) \oplus f_2(K_2)
$$

If we XOR $f_1(K_1)$ to both sides, we get:

$$
C \oplus f_1(K_1) = P \oplus f_2(K_2)
$$

Now if I have one known plaintext/ciphertext pair $P, C$, to attack the cipher, I can carry out the meet-in-the-middle attack:

I build a table of the values of $C \oplus f_1(K_1), K_1$ for all possible values of $K_1$.  This takes time and memory proportional to $2^{|K_1|}$.
For each possible value of $K_2$ I compute the corresponding $P \oplus f_2(K_2)$, and look it up in the table from step #1.  If I find a match I record that $K_1, K_2$ combination as a candidate key.

Now the key must be one of the candidate keys, and it only took me $2^{|K_1|} + 2^{|K_2|}$ time to find this out, not $2^{|K_1| + |K_2|}$—the combined cipher is much weaker than a cipher with the sum of the key lengths.

(Note that there can be more than one candidate key.  Any $K'_1, K'_2$ such that:

$$
f_1(K'_1) \oplus f_2(K'_2) = f_1(K_1) \oplus f_2(K_2)
$$

...is a candidate key as well.  But you can bet the number of candidate keys will be much, much smaller than the number of keys.)


Why do we need special key-wrap algorithms? Wikipedia says:

  Key Wrap constructions are a class of symmetric encryption algorithms designed to
  encapsulate (encrypt) cryptographic key material.

We are using these algorithms to encrypt (and authenticate) a key, using a symmetric algorithm (and symmetric key, named key encryption key).

Some of these algorithms are quite complicated, like the AES-keywrapping algorithm AESKW defined by NIST originally in 2001, with a new draft 800-38F available now. In the following image, each red box is one invocation of the AES block cipher, to encrypt in total only 256 bits (i.e. 2 blocks) of plaintext (including a constant part as integrity check/authentication):

(Image from Figure 7 of Deterministic Authenticated-Encryption - A Provable-Security Treatment of the Key-Wrap Problem, by Rogaway/Shrimpton, 2007.)

Why do we need such complicated algorithms, when a simple combination of CBC or CTR mode with a MAC, or an authenticated encryption mode like AEX would give us the same security result?

The paper you cite (Deterministic Authenticated-Encryption...) gives quite a bit of useful information (but I'm assuming you already knew that). It looks like a pretty good read (I'll let you know if that assumption holds after I finish it).

For why simpler constructions (CBC/CTR with a MAC or even AEX mode) don't satisfy (emphasis added):

  A key-wrap scheme is a kind of shared-key encryption scheme. It aims to provide “privacy and integrity protection for specialized data such as cryptographic keys, . . . without the use of nonces” (meaning counters or random bits). So key-wrap’s raison d’etre is to remove AE’s reliance on a nonce or random bits.

The reason for removing the nonce/IV/random bits, at least according to the paper, is to make the protocol "more resilient to IV misuse."

I also found the following paragraph useful (emphasis added):

  That said, in many contexts where one would think to use key wrap, one can use a conventional AE scheme, instead. This does not make studying the key-wrap problem pointless. First, it clariﬁes the relationship between key wrap and conventional AE. Second, DAE leads to misuse-resistant AE, and methods that achieve this aim make practical alternatives to conventional (not misuse-resistant) two-pass AE methods. Finally, practitioners have already “voted” for key-wrap by way of protocol-design and standardization efforts, and it is simply not productive to say “use a conventional AE scheme” after this option has been rejected.

Another potential reason for key-wrap algorithms is their analyzability. I'm not completely sure about this, but it could be that under the key-wrap algorithms, security is provable, but that might not be possible under a more simplistic approach.

On a side note, when reading through the intro to that paper, it made me wonder how the notion of Entropic Security plays into key-wrap algorithms. In the paper, they briefly mention it as a related work, but that is all.


Contrasting Key Rotation Requirements : Asymmetric vs. Symmetric Ciphers I'm trying to contrast key rotation requirements for asymmetric and symmetric ciphers.

In the case of symmetric ciphers, we have the results such as the so called "CBC Theorem" (stated on pg. 24 of https://crypto.stanford.edu/~dabo/cs255/lectures/PRP-PRF.pdf)
The CBC Theorem states that for a "q - query" CPA attacker attempting to break semantic security of AES-128-CBC, the attacker's advantage is less than $1/2^{32}$ only if $q^{2}L^{2} / \left\lVert X \right\rVert$, the "error" term in the CBC theorem, is less than $1/2^{32}$, i.e. given that $\left\lVert X \right\rVert = 2^{128}$ for AES-128, we can encrypt $2^{48}$ AES-128 blocks after which we need to switch the key in order to keep the attacker’s advantage below $1/2^{32}$

I have not seen a proof of theorem, but I'm guessing such results arise from basing the security of block cipher modes purely on their behavior as pseudo random functions.

Probabilistic asymmetric encryption schemes such as RSAES-OAEP, ECIES etc., on the other hand, employ the assumption of pseudo randomness in addition to an assumption around (computational) hardness of some number theoretic or algebraic problem, such as hardness of EC/DLP, factoring or short vector problems etc.

Does the fact that asymmetric schemes are based on such dual assumptions (pseudo randomness + factoring etc.) mitigate or extend the horizon for key rotation in such schemes after a certain number of encryptions under the same key, beyond what is implied by relying purely on pseudorandomness as is the case for AES-128-CBC under the CBC theorem? Is there an asymmetric analog for the CBC theorem that quantifies the advantage conferred to an adversary  after some number of encryptions under the same key?

I have not seen a proof of theorem, but I'm guessing such results arise from basing the security of block cipher modes purely on their behavior as pseudo random functions.

Another factor is that block ciphers are not pseudorandom functions (PRF), but pseudorandom permutations (PRP). That means that as you get close to the birthday bound you do not see the collisions that you would expect from a PRF. This is significant with some modes of encryption.

However, yes, even with a PRF if you have collisions in the input to the function you start to lose security, so that puts a bound on things.

In the case of CBC mode the theorem concerns the probability that two ciphertext blocks are equal (and thus the inputs). This happens with significant probability as you get to the birthday bound. From such a collision the attacker finds that $p_i \oplus p_j = c_{i-1} \oplus c_{j-1}$, the right side of which they know.

  Or is there an analog for the CBC theorem that necessitates rotation of asymmetric encryption keys after some critical number of encryptions under the same key?

Yes, there are analogs.

If you are talking about pure asymmetric encryption like padded RSA, there is a chance that the random padding collides with an earlier one and you leak plaintext equality. E.g. if you encrypt the same plaintext twice with RSA-OAEP and have parameters such that there is $x$ bits of randomness, the probability of the randomness colliding and getting two equal ciphertexts is $2^{-x}$, in which case an attacker knows they must be the same plaintext.

If you use hybrid encryption, there is similarly a probability that the random symmetric keys used are equal, which would encrypt the same plaintext to the same symmetric ciphertext, again leaking equality.

(These are not the best attacks on RSA, just an example that bounds exist.)

Does that mean that you must rotate keys? Not really. The actual bounds for secure RSA sizes and padding algorithms are large enough that you will not hit them. A limited signing key lifetime may be a good idea for other reasons - in case you lose the key and in case better attacks come along - but you are not practically limited in the data you can encrypt or sign.


What threat do quantum simulators pose? I recently saw an article at phys org that did some sort of "quantum simulation" on a conventional computer to calculate prime probabilities, the article (and paper associated) does mention shor's as well.

What threat does this model pose to current cryptography?

https://phys.org/news/2018-04-quantum-simulator-faster-route-prime.html

https://arxiv.org/abs/1704.03174

What threat does this model pose to current cryptography?

Do you mean "what threat does their algorithm run on a quantum simulator pose to cryptography"?

If so, the answer is "none".  Yes, there exist Quantum Simulators (which run on classical computers), that can run Quantum Algorithms. However simulating $n$ entangled states requires $O(2^n)$ memory and time, and so a Quantum Algorithm that runs in polynomial time on a real Quantum Computer would make the simulator take exponential time; we already can factor faster than that on a classical computer.

These simulators are useful in studying what a real (that is, reliable) Quantum Computer could do, once it is built; they are not particularly useful in actually solving problems.

On the other hand, if the question is "they have a new Quantum Algorithm for factoring; what threat does that pose, once we have a real Quantum Computer?"

The answer to that is "not much more than what is known now".  We already have Shor's algorithm, which can factor in polynomial time.  Their algorithm might run faster (or with less qubits or other resources), and hence be somewhat more practical. However with Shor's algorithm, anything that relies on the difficulty of factoring is assumed to be already broken - this algorithm would (at best) make it a bit more broken.

As an aside, of the commonly used public key cryptosystems, only RSA and Pallier rely on the difficulty of factorization.  Shor's algorithm also addresses the discrete log problems (and so also covers DH and ECC); they don't mention whether their new algorithm can be used to attack those problems.


Security implications of using constant string to verify AES key? I know that you can use for example CBC-MAC to verify data integrity and thus the password upon decryption.

But would there be security implications of just adding a constant string to the plaintext and if the first block is identical upon decryption we know the key was correct?

It likely depends on the encryption algorithm you use, but the answer is likely NO, this method does not ensure the integrity of ciphertexts.

For example, suppose you're using CBC mode encryption. The value you get for the first plaintext block when decrypting depends only on the first ciphertext block and the IV. Hence, I could intercept a message and change the ciphertext in any way I wanted as long as I kept these two values the same. The resulting, tampered-with ciphertext would pass your proposed integrity check.

However, if you really are only trying to make sure the key is correct (so a user can be informed if they entered a password incorrectly, for example), rather than trying to provide a secure MAC, then this method should work. Just be aware that it's not secure in the MAC sense.

Your scheme will not adversely affect the privacy of the encryption algorithm, as long as the encryption algorithm is secure against chosen-plaintext attacks. All standard encryption algorithms, such as CBC, meet this requirement (as long as they're used with a secure blockcipher, such as AES).

In summary, your scheme (1) will not alert you if a third party tampers with a ciphertext (whereas CBC-MAC would); (2) will almost certainly succeed in letting users know if they're using the correct key; (3) will not compromise the security of the encryption algorithm.


How much would it cost in U.S. dollars to brute force a 256 bit key in a year? I am often told that any key can be broken and that it is only a matter of time and resources for any key to be broken. I know that this is technically true. However, I think that there is probably a point where it makes sense to say a key is uncrackable (for example, if it would cost 100 times the world GDP to crack it, it is essentially uncrackable without the help of an advanced alien civilization, etc.).

How much would it cost in U.S. dollars to brute force a 256-bit key using a strong algorithm such as AES or Twofish in a year?

I would also be curious to know what it would cost to crack a 128 bit key in a year.

I am asking this mostly out of curiosity. I do not know very much about cryptography, so please feel free to pick the algorithm of your choice if that matters. I am interested in how one would project the cost (assume you have to buy the hardware but you get to choose what hardware you buy).

The average cost of electricity in the US is $\$0.12$ per kWh. For a single server, I'll use 3741 kWh annually as an estimate. That would be about $\$450$ per year for one machine.

Let's say you can do $10^{14}$ decryptions per second. That is $3.15\times 10^{21}$ decrypts per year for one machine. You need to do (on average) $2^{255}$ decryptions in a year, so you would need $\frac{2^{255}}{3.15\times 10^{21}} \approx 1.84\times 10^{55}$ machines. To figure your cost you would multiply that by $\$450$ and get about $\$8\times 10^{57}$ or 8 octodecillion dollars. Gross world product, or GWP, is about $63\times 10^{12}$, so brute-forcing a 256-bit key would cost about $10^{44}$ times the GWP.

You can follow similar math to get the cost of brute forcing a 128-bit key.

Note:

I am completely ignoring hardware costs, maintenance, etc. The estimate above is for electricity only. We can take a hint from the NSA on this. You'd be a lot better off hiring a few thousand mathematicians and have them work on breaking the cipher as opposed to trying to brute-force it.


Finding collisions for XOR of many hashes There's a collision-resistant hash function $H$.

Given $x$, how  hard would it be to find a set $a[i]$ such that:

$H(a[1]) \oplus H(a[1]) \oplus \cdots \oplus H(a[N]) = H(x)$

whereas none of $a[i]$ equals to $x$?

This question is studied extensively in the paper

A New Paradigm for Collision-free Hashing: Incrementality at Reduced Cost by Bellare & Micciancio

In appendix A, they describe how to break the one-wayness of the function $H(x_1,\ldots, x_n) = h(x_1) \oplus h(x_2) \oplus \cdots \oplus h(x_n)$. The idea is as @SEJPM suggests in the comments above: XOR is the operation of a vector space over $\{0,1\}^\ell$ (where $\ell$ is the output length of $h$). Sufficienctly many $h(x_i)$'s form a basis for this vector space. Once you have a basis, you can easily solve for a subset of basis vectors that XOR to any desired value.


why doesn't quadratic residue attack work with Elgamal encryption with decisional diffie Hellman assumption? I was reading this notes http://www.cs.umd.edu/~jkatz/gradcrypto2/NOTES/lecture4.pdf

It's given that discrete log assumption is not enough for semantic security, I'm assuming there maybe chance of getting quadratic residue even if we choose x and r so that both are not even.

But what about decisional diffie Hellman assumption? Isn't it just same? Can't the adversary similarly select one message which is quadratic residue and do the same attack?

The difference is to which groups we think the assumption applies.

The discrete logarithm assumption is thought to apply to groups of the form $\mathbb{Z}_p^*$ with $p$ prime, amongst others. As explained in the linked lecture notes, there exist polynomial time algorithms that determine whether $m_b$ is a quadratic residue. This is sufficient to rule out half of the possible plaintexts, because in groups modulo a prime, exactly half of the elements are quadratic residues. Given this counterexample, the discrete logarithm assumption is consequently not sufficient to achieve semantic security.

The Decisional Diffie-Hellman assumption does not apply to groups $\mathbb{Z}_p^*$ with $p$ prime, but it is thought to apply to other groups -- the ones typically use for ElGamel. The DDH assumption is a stronger assumption that applies to some of the groups where the discrete logarithm assumption holds.

In particular, if the DDH assumption holds, we can prove that there cannot exist a polynomial time algorithm that determines whether an element is a quadratic residue. This necessarily disproves the DDH assumption for groups $\mathbb{Z}_p^*$ with $p$ prime.

So long story short, if the DDH assumption holds, then the attacker cannot perform the attack using quadratic residues in polynomial time, or in fact even distinguish chosen plaintexts in polynomial time. However, the DDH assumption does not hold for all groups where the discrete logarithm assumption holds, and for some of those groups where the DDH assumption does not hold, an attacker can perform the attack in polynomial time.


Can a PRF distiguisher invoke the function's algorithm? The definition of a function $F:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ being a Pseudo Random Function Family (PRF) is that it's implementable by a P.P.T. algorithm $\mathcal F$, and there is no P.P.T. algorithm $\mathcal A$ able to distinguish $x\mapsto F(k,x)$ from a random function for unknown random $k$ and non-vanishing probability.
Is the algorithm $\mathcal A$ allowed to invoke the algorithm $\mathcal F$ implementing $(k,x)\mapsto F(k,x)$? Or even more generally, part of it?

That seems necessary to decide if the following $G$ is a PRF or not.

Let $H:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ be a PRF.
Let $P_c:\ \{0,1\}^n\to\{0,1\}^n$ be a PRP with key fixed to arbitrary constant $c$, with both $P$ and ${P_c}^{-1}$ computable by a P.P.T. algorithm.
Define $G:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ by (assimilating bitstrings to integers per big-endian convention)
$$G(k,x)\underset{\text{def}}=\begin{cases}
{P_c}(k\bmod2^{\lfloor n/2\rfloor})&\text{if }x=0^n\\
1^n&\text{if }x=1^n\text{ and }P_c^{-1}(k)<2^{\lfloor n/2\rfloor}\\
H(k,x)&\text{otherwise}
\end{cases}$$

Essentially, $G$ is the PRF $H$, except it has a set of weak keys $k$ of size $2^{\lfloor n/2\rfloor}$, such that whatever $k$, $G(k,0^n)$ is a weak key; and when $k$ is a weak key, $G(k,1^n)$ is $1^n$.
We can build a distinguisher for $G$ that

submits $x=0^n$, gets $y$
applies the algorithm for $G$ to input $(y,1^n)$
tests if the outcome is $1^n$, which will always be the case for $G$, and only with vanishing  probability for a random function.

However there seems to be no distinguisher if we can neither apply the algorithm for $G$, nor analyze it to extract $c$.

Motivation is this question, which asks if $F_2(k,x)\underset{\text{def}}=F(F(k,0^n),x)$ is a PRF, assuming $F$ is a PRF. If the above $G$ was a PRF, $F=G$ would be a counterexample.

The adversary $\mathcal{A}$ is allowed to invoke the algorithm $\mathcal{F}$ (if it is P.P.T.) in any PRF definiton known to me.
We are generally interested in security against every possible P.P.T. algorithm $\mathcal{A}$ and require that for every such algorithm $\mathcal{A}$ it holds that $\mathcal{A}$ can only distinguish from a random function with non-negligible probability.
If $\mathcal{F}$ is a P.P.T. algorithm, there exists an adversary $\mathcal{A}$ that includes the $\mathcal{F}$ functionality. This adversary is able to invoke $\mathcal{F}$ and we require from our PRF, that it is secure against that adversary too.
The same argument holds for parts of the algorithm $\mathcal{F}$.

As far as I understood it, for your example the important question is the following:
Does the adversary $\mathcal{A}$ know $c$?
Again, we need indistinguishability against all adversaries from a PRF, which means that we need indistinguishability even against an adversary that knows this fixed $c$.


Dilithium signature scheme and timing attacks – Does the running time actually depend on the secret key? The paper “CRYSTALS – Dilithium: Digital Signatures from Module Lattices”  (by Léo Ducas, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé) introduces a digital signature scheme based on lattices.

However, it worries me for two reasons:

There is no proof of post-quantum security.
There is no proof that the running time does not depend on the secret key.

The first appears to be a technical limitation of the proof technique and unlikely to lead to a practical attack, but the second one is definitely exploitable if my fear is real.

Does the running time actually depend on the secret key?

The running time does not depend on the secret key. All multiplications, additions, and modular reductions can be implemented to be constant-time.

Diving in to the details:

The probability of the goto in line 11 of the signing algorithm is independent of $s_1$, $s_2$ (the probability is in equation (4)).
The goto in line 13 is also independent of $s_1$, $s_2$ because the use of $s_2$ in line 12 can be replaced with an expression that does not use $s_2$ (as in equation (1) ) in which all variables have distributions independent of $s_1$, $s_2$.


Initializing PGP keys by one side I am using a PGP method to encrypt and decrypt messages shared between users A and B.

Upon the start of a message exchange is the initialization of the public and secret keys by both Users.

Lets say that User A downloads the message exhange app and he adds his friend (through phone number). He then wants to initialize a conversation. At this point User B has still not downloaded the app.

How are the keys to be safely generated if it is User A initializing the conversation? Technically, the request of creating the secret key for both parties would then have to be done by User A as well, which makes it not safe.

Without the public key of User B (thus also the creation of the secret key for User B), User A will not be able to start sending encrypted messages.

The obvious solution is that he will need to wait before the friends accepts the friend request, thus creating and sharing the keys.

Is there a way to solve this issue without this restriction? That is, how can User A already start sending encrypted messages to User B, who has not signed up and accepted the request?

You could use message specific keys, which encrypt the messages themselves. Once a secret key has been established you can encrypt the message specific keys with it and send them over in a new message (with meta-data) to user B. You should of course have some method of storing the encrypted messages somewhere for this to work.


Why should $a,b < N$ for Montgomery Reduction? In Montgomery reduction, when calculating $a \times b \mod N$, it is required that $a \lt N$ and $b \lt N$.
I think $0 \le T \lt N \times R$ is enough for the Montgomery Reduction.

Rationale:

Let $a' = a \times R \mod N$,
let $b' = b \times R \mod N$, and
let $T = a' \times b'$.

Then $T \times R^{-1} = ((T + ((T \times (-N^{-1}) \mod R) \times N) / R) \mod N$.

$T \lt N^{2} \lt N \times R$ as $R \gt N$. Also remainder of $\mod R \lt R$, so $(T + ((T \times (-N^{-1}) \mod R) \times N)/ R \lt (N \times R + R \times N)/R = 2 \times N$.

As such, $a$ and $b$ can be greater than $N$. Is that correct? If it isn´t, what´s wrong with my rationale?

Looks like misunderstanding to me: you are asking about Montgomery reduction but your example is about Montgomery multiplication.

Montgomery reduction inputs a number in range $[0..NR-1]$ and outputs a number in range $[0..N-1]$, where $R$ - auxiliary Montgomery modulus.

Montgomery multiplication inputs two numbers $A$ and $B$ in range $[0..N-1]$ and outputs a number in range $[0..N-1]$

Internally, Montgomery multiplication is standard integer multiplication followed by Montgomery reduction; so, formally it is possible to apply Montgomery multiplication to any numbers $A \ge 0$ and $B \ge 0$ such that $AB \le NR-1$. Since $R \gt N$, this is weaker requirement than $0 \le A \le N-1$ and $0 \le B \le N-1$, but I doubt this possibility makes practical sense.


In public key cryptography, how many keys are required for secure communication between n parties? In public key cryptography, how many keys are required for secure communication between n parties?

In my view the answer should be $n^2$.

Reason: There are ‘$n$’ Parties. Every Party has One (1) Public Key (for Encryption). Also, every party has $(n-1)$ private keys (paired) (for Decryption). So every party has $$ 1 + (n-1) = n\,keys,$$ and there are $n$ parties communicating. Number of Keys required is therefore equal to $$ n * n = n^2$$

Now, am I correct? (Please be specific & also show the full logic & give proper explanations).

Asymmetric keys come in pairs. The public key of a pair can be used to encrypt data so that only the holder of the private key can decrypt it. If you had one private key, you'd also have exactly one public key that corresponds to it, so your answer of one public key and $n-1$ private keys per person cannot be entirely correct.

The question is somewhat ambiguous, but the answer that is probably expected is $n$ key-pairs, so $2n$ keys altogether. Each person has a single key-pair and knows all the public keys of others' key-pairs. They can encrypt data using any public key to be decrypted using that person's (single) private key.

The number of keys each person knows is about $n$ (one private key and $n-1$ public keys, plus their own public key if you want to count that). However, the total number is not $n*n$, because the public keys are all the same $n$ keys.

However, in the real world you would use hybrid encryption. In addition to the long term key-pairs there would also be a symmetric key for either every message sent or every session (in an interactive protocol like chat). Further, depending on the symmetric primitives used, you could need a second short term key for message authentication/integrity.