Is modern encryption needlessly complicated? RSA, DES, AES, etc., all use (relatively) complicated mathematics to encrypt some message with some key. For each of these methods, there have been several documented vulnerabilities found over the years. Some even believe that there is a vulnerability in AES known only to the NSA.

On the other hand, the one-time pad is not only ridiculously simple, but also has been shown to be impossible to crack (if used appropriately).

Say you have some message to be encrypted with length n. Simply generate a random string with length m where m is at least as large as n, and perform modular addition of the random string onto the message.

As long as the random string is generated with a high-enough-quality random number generator, and as long as the same one-time pad isn't reused, it should be impossible to crack.

If this is true, all we would need to perfect are fast, cryptographically secure deterministic random number generators. Use the key as a starting seed for the RNG and you have a powerful uncrackable encryption scheme which is simple to understand and implement.

Blum-Blum-Shub is a fast, cryptographically secure PRNG, and there are others too.

I have written a C++ program which uses two 2048-bit primes (which match the necessary criteria) for Blum-Blum-Shub and uses a password which the user enters - converted into a starting seed - to run byte-wise modular addition. The process is fast, deterministic, and if the literature I have read is correct then it should be very secure.

So why is so much time and effort invested in coming up with convoluted encryption cyphers when mathematics shows that the simplest is often the best?

The main difficulty with the one-time pad is that it requires pre-arrangement. In order for me to use a one-time pad to communicate with you, we must either have arranged ahead of time for a one-time pad that we will use (which must be as large as our communication will be), or else we must have some secure way of communicating that will allow us to agree on a one-time-pad for use.

If we have a secure channel to communicate so we can agree on a one-time-pad, then why bother? Let's just communicate through the secure channel.

If we don't have a secure channel, then we cannot engage in secret communication ex-nihilo, since we will not have a one-time-pad agreed on.

Now, if you are going to generate the one-time-pad via a pseudo-random number generator, how are you going to get that one-time pad to me? You must tell me your seed (so that I can generate the same pseudo-random sequence and I can decode the message), in which case we are back to the problem of how you tell me what your seed is without a secure channel to communicate with. So now we have two points of vulnerability: the channel we use to communicate so you can give me the seed; and the fact that a pseudo-random number generator is not truly a random number generator, and so may be susceptible to attack as well.

There is also the problem of distribution; to use one-time pads effectively, no pad can be used more than once. There were intercepts that the NSA had from back in the 50s; when the Soviets mistakenly used the same one-time-pads to encode some messages in the 80s, this was enough to break the encryption in both cases. That means that each message will need a new seed and a new password; so each time you want to communicate you need a new seed/key and a new password. It is just too easy to lose the information, or to re-use it by mistake and thus make the entire thing a wash.

One time pads are effective for pre-established channels of communication with low bandwidth; they are almost useless for initiating remote secret communication with someone you have never communicated with before, and they require a lot of bandwidth to use correctly.


If I want Integrity and Authentication AND Non-Repudiation, can the Digital Signature be based on the MAC? Let's say I'm making a digital signature like this:

hash = hash(message)
digital signature = encrypt_with_private_key(hash)

where the private key is Alice's private key from a secure public-key cryptosystem.

And I'm making a MAC like this:

MAC = hash(message + some_secret_key)

And I then send both of these to my friend, encrypted using AES or some other cipher.

I feel I'm just creating work for him.

Could I simplify things like this?

MAC = hash(message + some_secret_key)
digital signature = encrypt_with_private_key(MAC)

Please tell me the pros and cons of this.

First of all, in a digital signature scheme that follows the hash-and-sign paradigm $Enc_{sk}(hash(m))$ the hash procedure is essential to "fit" the message $m$ in the public-key scheme domain: you cannot encrypt messages of any size with RSA for example.

The second important point is that a digital signature scheme is a bit closed to public-key encryption: because we consider an untrusted channel to communicate the public-key; another similarity is that the signer wants the signature to be publicly verifiable.

So, when we are using public-key cryptography, everything we do not want is to suppose a private/secure channel to exchange keys; you will need one if you want to use a cryptographic hash like a mac scheme. Furthermore, the signer has to exchange different secret keys with everyone who wants to verify the signature. Thus, creating distinct MAC tags: so, such a signature would no be publicly verifiable, but designated.

Another important point is that care must be taken when a cryptographic hash is chosen: HMAC wasn't designed considering collision attacks M. Bellare, New Proofs for NMAC and HMAC: Security without Collision-Resistance.
So, if you don't have a collision resistant mac scheme, what if a adversary can find another $tag'_i=mac(m_i)$, after consulting a polynomial number of $m_i, tag_i, Enc_{sk}(tag_i = mac(m_i))$, and so forging a signature?

BTW, unforgeability is a cornerstone security property of digital signatures schemes.

Last but not least important. by using only a mac scheme and sharing key, we don't have non-repudiation or authentication. If the singer and verifier share a secret key, how can we prove which one created a tag? So mac isn't enough: you also need a public-key scheme.

Well...the pros... I can't see anyone. Sorry.


Question about lower bound and upper bound key collision I'm reading this article and I have a doubt in the page 7. First I going to describe the required definitions and next I formulate my question.

Let be $$F(n)=\{f_k: \{0,1\}^n\rightarrow \{0,1\}^n| k\in \{0,1\}^n\}$$  a family function.

Definition: The upper bound $\kappa$ is defined as follows: For each pair $(x,k)$, there is at most $\kappa-1$ different keys $k_1,\cdots,k_{\kappa-1}$, which are also different from $k$, such that $f_k(x)=f_{k_i}(x)$ for $i=0\cdots,\kappa-1$. Equivalent we define the lower bound $\kappa '$: For each pair $(x,k)$, there is at most $\kappa  '-1$ different keys $k_1,\cdots,k_{\kappa  '-1}$, which are also different from $k$, such that $f_k(x)=f_{k_i}(x)$ for $i=0\cdots,\kappa '-1$

My question is with this claim:

  The values $\kappa$ and $\kappa ′$ restrict the number of different
  images $y$ some preimage $x$ can be mapped to by functions in $F(n)$, i.e.

  $$\dfrac{2^n}{\kappa}\leq |\{f_k(x): k \in \{0,1\}^n\}|\leq
\dfrac{2^n}{\kappa '}$$

  for all $x \in \{0,1\}^n$

Why $|\{f_k(x): k \in \{0,1\}^n\}|\geq\dfrac{2^n}{\kappa}$, resp. $(\leq \dfrac{2^n}{\kappa '})$?
I make this question because the number maximum of equals images are $\kappa$ and the total number of keys is $2^n$ then for me there are at least $2^n-\kappa$ diffentent preimages.

Remember that the bounds are defined for every key. This means, there will be a first set of keys that contains at least $\kappa'$ and at most $\kappa$ keys that all map $x$ to the same $y$. Now, every key not in this set has to be in another set with the same size bounds that maps within which every key maps $x$ to the same $y$ which is different from all the $y_i$ the other sets map to. And so on.

Hence, there are at least $\frac{2^n}{\kappa}$ such sets of keys. All keys in such a set map $x$ to the same $y$ which is different form the $y_i$'s the other sets map to. Consequently, there are at least $\frac{2^n}{\kappa}$ different $y_i$.

Similarly, there are at most $\frac{2^n}{\kappa'}$ such sets of keys and accordingly no more than $\frac{2^n}{\kappa'}$ different values $y_i$.


ChaCha20Poly1305 with empty AAD Is it safe to use ChaCha20Poly1305 with empty AAD? I tried to implement E2E encryption between two clients in network.

Yes, it is safe.  AAD (Additional Authenticated Data) is optional.  It's available for you to use when you have data you want authenticated (integrity checked) but do no wish to encrypt.  In general, in fact, it's far more common to use AEAD algorithms with only encrypted data and no AAD.


Why inversion and multiplication operations are costly in elliptic curves? There are several algorithms for efficient scalar multiplication of an arbitrary point P(x,y) by some positive integer k in elliptic curves defined over $F_{p}$ or $F_{2^{m}}$.

The scalar multiplication deals with point doubling (adding P(x,y) to itself) and point addition(adding two different points (P(x,y),  Q(X,Y)). These point doubling and additions, fundamentally,  further deal with additions, squaring, multiplications and inversion operations.

My question here is that though there are considerable addition and squaring operations involved in scalar point multiplication, ( for example, a single point addition requires 8 additions, 1 squaring, two multiplications and one inversion ) why is the inversion multiplication ratio (I/M) is of special interest for researchers in performance evaluation of different algorithms for scalar point multiplication ?

I do understand that the inversion and multiplication operations are dominant in elliptic curve arithmetic, but aren't these addition and squaring operations, not dominant enough to be considered ?

I would encourage the readers to go through the table 3.13, page no. 145 in this  book so that you may get a clear idea of my question. Please have a look at the last 2 columns titled "EC operations" and "field operations" in this table.

When we perform, say, a point addition of two elliptic curve points, we need to work with elements of the field that the elliptic curve is defined over.   There are several operations we may need to perform, and the total cost of the point addition is the sum of the cost of all the field operations we need to do (plus some overhead, which is typically pretty small):

We may need to add and subtract field elements.  There two operations have about the same cost, and so we typically don't distinguish them.  They're also quite cheap (compared to the other operations required), so it is quite common to ignore them when coming up with an approximation of the total cost.
We may need to multiply two elements.  The cost of this operation is often the 'unit' where all other costs are measured against.
We may need to square an element.  This can be done by just handing the element to the multiply routine; however there are symmetries that we can take advantage of to make this specific operation cheaper.  For odd-characteristic fields, this squaring operation will be somewhere between 0.5 and 1 times the cost of a multiply.  Different implementations will differ in the precise figure; we try to account for that.
We may need to find the multiplicative inverse of an element; that is, given $x$, find the value $y$ such that $xy = 1$, where $1$ is the multiplicative identity.  This operation is by far the most expensive operation for just about any representation.

This $I/M$ value tries to capture exactly how expensive an inverse operation is; an $I/M$ value of 8 estimates that an inverse operation is about as expensive as the total of 8 multiplication operations.

We need an estimate here to guide us which mix of operations will run quickest in total.  If we have an $I/M$ of 5, then an optimization that replaces one inverse with 6 multiplies is a loss.  However, if we have an $I/M$ value of 8; then it is a win.

Now, in my experience, $I/M$ ratios tend to be quite high; a ratio of 8 would be far smaller than what I've seen.


For a given plaintext-ciphertext pair, how many valid AES keys are there? For $PT\in \mathbb{M}$ and $CT\in \mathbb{C}$, let $\mathbb{F}=\{f|f:\mathbb{M}\rightarrow\mathbb{C}\}$ be the collection of all functions from $\mathbb{M}$ to $\mathbb{C}$. Then AES encryption under key $k$ is one of these functions, say $f_k$, such that $f_k(PT)=CT$. Then,

Is there any key $k'$ such that $k\neq k'$, but $f_k(PT)=f_{k'}(PT)$?
If so then is there any fixed cardinality of such sets of keys?

If $f_k$ is AES the block cipher, then there are $2^{128}$ possible output values for a given plaintext and $2^{|k|}$ possible AES keys, where $|k|$ is either 128, 192 or 256, depending on which AES key size you use.

Assuming AES chooses a random permutation, $g_{PT}(k) = f_k(PT)$ behaves like a pseudorandom function*, so you expect something like $2^{127}$ pairs with AES-128 for a given plaintext, but it is possible that there are none. With AES-192 and AES-256 there are always some colliding keys for every plaintext. You expect every key to have (many) other keys that produce the same ciphertext. Roughly, you expect $2^{255}$ and $2^{383}$ pairs, with multicollisions handled as in the above linked question.

If $f_k$ is AES in some mode of operation, then the answer depends on the length of the message. When message length is close to the key length, you expect a lot of collisions, while if it is higher than twice the key length you expect none  due to the birthday bound.

(The previous ignores IV and possible authentication, which depending on mode may make collisions unlikely even for short messages.)

As for whether the cardinality is "fixed", no, it varies with the plaintext. Without exhaustive search or some kind of break in AES, you can only give the expected value.

* Technically not true, since there are related key attacks on AES. You should not rely on $g$ being PRF, but for the purposes of the math here it is probably close enough.


AES with shuffleBytes instead of shiftRows I was examining how AES provides diffusion and noticed that indices of the shiftRows transposition step can be modeled as inputs/outputs of a 4x4 table:

`0123 4567 89AB CDEF -> 0123 5674 AB89 4567`

Where the input is the index of each byte of the 4x4 state, and the output is the destination index that the byte will be transposed to.

I was curious about the effect of changing the above mapping to one with strong cryptographic properties, like those found in this paper.

I have seen this question and this answer which discuss what purposes the shiftRows operation fulfills.

There is the requirement that each column should be spread evenly across the state, so as to ensure diffusion. I found that only certain S-Boxes in the above paper fulfill this property.

The first S-Box I found that does fit that criteria was the third S-Box from the second variation of the Hummingbird cipher (found in the appendix of the paper above). It looks like this:

0123 4567 89AB CDEF -> F458 9721 A30E 6CDB

If I understood the paper correctly, this mapping is among those that offer ideal differential, linear, and branch count properties. We can refer to this operation as shuffleBytes, as it's a generalization of shifting rows.

How would I go about calculating the branch count and active S-Boxes with AES using the proposed shuffleBytes operation in place of the shiftRows operation, with all the operations otherwise the same?

Is there some (obvious) reason this would be bad, assuming the transposition + mixColumns operations still ensures diffusion at least the same rate?

Addendum

After further testing, the complete diffusion over two rounds is only realized with certain configurations of bytes, and not in all cases. Maybe stacking a combination of multiple ideal S-Boxes over multiple rounds might be applied. But with just the one S-Box, diffusion does take longer then two rounds in some cases, so it probably won't be considered an improvement.

AES ShiftRows operations ensures that each new column contains one byte from one of the 4 old columns. Thus it achieves Full diffusion in 2 rounds.

You are right that there could have been other arrangement / shuffle of bytes to meet this criteria too. But if we analyze AES design, we will find that speed and memory requirement on all types of platforms were also given due attention in designing AES components. For example

MixColumn Matrix values are kept to minimum possible, like 01,02 and 03, which are fastest to implement as 01 is element itself, 02 is just left shift by One 03 is Exclusive OR of 02 and 01
Only one Sbox was used for substituting all state bytes
RCons in key schedule were kept minimum possible with simple in values.
The Shift Rows in 32 bit processor is just (i*8) left rotations of ith row where i=0,1,2,3. In case of 8bit processor, the first row elements remain unmoved and others are shifted based on index.

so if you try to do random permutation or some fixes shuffle bytes, you will end up needing more resources/time on some or all platforms.

But if you dont plan to run you AES variation on all platforms, then you can introduce your own platform specific operation (offcourse security of which still needs to be vetted by experts)


What do people mean when they talk about forward secrecy in ciphers? I've heard several people and websites talk about ciphers that have forward secrecy. I know about forward secrecy in key agreement protocols, e.g. RLWE, (EC/SI)DH, QKD, etc. This could be what they're talking about and it's a simple case of misused terminology (I've mostly heard it in articles about cipher suites), but I've also heard this used in the context of hash based signature algorithms so I'm wondering if people are using a special variation of a stream cipher or some other method.

What does 'forward secrecy' mean in the context of hash based signatures?

Well, what that term means is that we have a hash based signature scheme with an evolving key, that is, the private key is constantly being updated, and on a state compromise (at state $N$), you cannot get the private keys used prior to state $N$.

I personally don't see that as a good use of the term (it's feels like 'perfect reverse security' would be more apt terminology, as it's discussing the security of the system prior to compromise).  However, that's what people mean by that terminology.


Can a digital signature scheme also be an encryption scheme? Using Schnorr signatures, one could devise a system where a single public key can represent multiple signers. Do signature schemes like that represent crypto systems usable for encryption?

In that case, could you say that a signature scheme and an encryption scheme represent the same thing?

In that case, could you say that a signature scheme and an encryption scheme represent the same thing?

I don't see how.  With a signature scheme, the public operation can return just a single bit (either "the signature verified" or "it didn't").  It's not at all clear how you could efficiently use a function that returns a single bit as a part of an encryption operation.

Now, there are certainly cryptographical primitives - such as modular exponentiation within RSA - that can be used as a primitive within either a public key encryption or a signature scheme; however there are also signature schemes that cannot be used to do encryption, and so generically, the two classes of schemes cannot be identical.


RSA assumption and relationship given by generating elemts of a Cayley graph I have read a very interesting description of computation related to the RSA group as follows.

"By the Chinese remainder theorem, we have that:
$$(\mathbb{Z}/pq\mathbb{Z})^* \cong (\mathbb{Z}/p\mathbb{Z})^*\times (\mathbb{Z}/q\mathbb{Z})^* \cong (\mathbb{Z}/(p-1)\mathbb{Z})\times (\mathbb{Z}/(q-1)\mathbb{Z})$$
From this, we should be able to write:
$$(\mathbb{Z}/pq\mathbb{Z})^* \cong \langle g_q, g_p\mid [g_q, g_p] = e, g_q^{q-1} = e, g_p^{p-1} = e\rangle$$
Where $e$ is the identity element of the group, $[g_q, g_p]$ is the commutator, etc. Essentially, this is the free abelian group on two generators, subject to the relations on the order of the generators that come from the CRT representation.

We can then write all the quantities you talk about in terms of the generators $g_q, g_p$.
Say that $z = g_q^{z_q}g_p^{z_p}$, and $y = g_q^{y_q}g_p^{y_p}$.
Then your equation:
$$y^r = z\implies g_q^{ry_q}g_p^{ry_p} = g_q^{z_q}g_p^{z_p}\implies g_q^{ry_q - z_q}g_p^{ry_p - z_p} = e$$
Gives us the "cycle". In particular, if you view the Cayley graph as being on vertices of the form $g_q^{x}g_p^{y}$ (so we can sort of visualize it as being some subset of $\mathbb{Z}^2$), this reduces the problem of finding cycles to finding points $(y_q, y_p)$ such that $(ry_q \equiv z_q \bmod (q-1))$ and $(ry_p\equiv z_p\bmod (p-1))$.
You may want to enforce some non-triviality condition (such as $ry_q\neq z_q$ and $ry_p\neq z_p$), I'm not sure.
If you want to find the minimum/maximimum length cycle, you could then find the minimum/maximum non-trivial $(y_q, y_p)$ such that $ry_q \equiv z_q\bmod (q-1)$ and $ry_p\equiv z_p\bmod(p-1)$. Note that if you know the factorization of $N = pq$, you can compute $y_q \equiv r^{-1}z_q\bmod(q-1)$ and $y_p\equiv r^{-1}z_p\bmod(p-1)$ easily (assuming $r$ is invertible in both rings), and then find particular representatives $(y_p, y_q)$ with properties you want by searching through the cosets $r^{-1}z_q + (q-1)\mathbb{Z}$."

(source:Relationship between generating elements given by cycles in Cayley graph)

I have quoted it only because I was very interested in it and please don't misunderstand.

I would like to ask a few questions regarding it.

For finding the maximum length cycle, it is taken as finding the maximum solution to the two congruence relations. But since these are congruent relations how can we justify that the maximum will give the answer relevant to the longest cycle?

As an example, if we consider $a \equiv 0 (modp)$ where $p$ is a prime and the solutions can take only the values $\{0,1,2,...,p\}$, then $a$ can take only the values $0$ or $p$ only. Then $ry_q$ will always be $z_q$?

a) I tried the above idea (just to check with real values easily) for a Cayley graph (undirected) of the group $\mathbb{Z}_3 \times \mathbb{Z}_5$, where the generating elements are $g_1=(0,1)$ and $g_2=(1,0)$, $|g_1|=5, |g_2|=3$. Then for a Hamiltonian cycle $g_1^{m} g_2^{n}=e$, can I write $m \equiv 0 (mod5)$ and $n \equiv 0 (mod3)$?

b) There are several Hamiltonian cycles in this graph, so when I tested it manually for one cycle it was $m=0, n=3$ and for another, it was $m=5,n=0$. Then it seems like if we solve for solutions as the maximum solution to the above equations I get several solution pairs for the combinations of $m=0,5$ and $n=0,3$. Am I right?

Can we write other groups such as $(\mathbb{Z}_p \times \mathbb{Z}_p) \rtimes (\mathbb{Z}_q \times \mathbb{Z}_q)$, where $p,q$ are odd distinct primes, in terms of a free group as above? I am very glad if some guidance/steps to do so can be explained.

For finding the maximum length cycle, it is taken as finding the maximum solution to the two congruence relations. But since these are congruent relations how can we justify that the maximum will give the answer relevant to the longest cycle?

It looks like it shouldn't. I'm pretty sure I was visualizing cycles in the Cayley Graph as being paths in the lattice $\mathbb{Z}^2$. This corresponds to viewing points in the RSA group as tuples $(g_p^{r_p}, g_q^{r_q})$ (where $(r_p, r_q)\in\mathbb{Z}^2$). One could hope to make some statement about maximum elements in this representation relating to maximum length cycles, but this is different than the congruences mentioned.
One could maybe hope to prove some statement about maximal elements in the above representation $(r_p, r_q)$, and then transfer (via exponentiation) to the "standard representation" and hope that they are "close to maximal". I would strongly expect this to be false though --- this property would be akin to being something like Lipschitz normally, which is much more regularity than I'd expect from these functions.

Can we write other groups such as $(\mathbb{Z}_p\times\mathbb{Z}_p)\rtimes_\varphi(\mathbb{Z}_q\times\mathbb{Z}_q)$, where $p, q$ are odd distinct primes, in terms of a free group as above? I am very glad if some guidance/steps to do so can be explained.

For $G\rtimes_\varphi H$ I explicitly include the homomorphism $\varphi : H \to \mathsf{Aut}(G)$ that the semi-direct product is defined with respect to.
The concept you're looking for is that of a group presentation.
This is a way of writing a group $G$ as a set of generators $R$ and relations $S$ the generators satisfy (denoted $\langle R | S\rangle$).
Equivalently, this is a way of writing a group $G$ as a free group on the generators $R$, quotiented by the normal subgroup generated by the relations $S$.
In this terminology, your question becomes "What is a group presentation of $(\mathbb{Z}_p\times\mathbb{Z}_p)\rtimes_\varphi(\mathbb{Z}_q\times\mathbb{Z}_q)$?"
It will be useful to know how group presentations behave under direct products and semi-direct products.

Let $G_1 = \langle R_1 | S_1\rangle$ and $G_2 = \langle R_2 | S_2\rangle$. Then:

$G_1 \times G_2 = \langle R_1, R_2 | S_1, S_2, [R_1, R_2]\rangle$

$G_1\rtimes_\varphi G_2 =\langle R_1, R_2 | S_1 , S_2, \forall (r_1, r_2)\in R_1\times R_2 : r_2 r_1^{-1}r_2 = \varphi(r_2)(r_1)\rangle$

Here $[A, B]$ is the commutator subgroup.
One should be able to use the above "transformation rules" (along with the presentation $\mathbb{Z}_p = \langle g | g^p = e\rangle$ for prime $p$) to compute a group presentation for the group you're interested in (or any other group built from direct and semi-direct products of cyclic groups).


HMAC-SHA256 on large data files I currently need to encrypt large files (video, over 6 Gbytes) for our customers.
To ensure authenticity and integrity, we chose HMAC-256 as we already use it in our internal messaging system.

But working in embedded systems, we are limitted by the memory.
If the message is the whole data file, we could not stored 6Gb in memory to compute the HMAC.

Is there a dedicated protocol that breaks up the message into smaller blocks and create iterative HMAC ? Or any other way to achieve it ?

A SHA-256 implementation usable on several blocks can be turned it into an HMAC-SHA-256 implementation usable on several blocks, as follows:

If the key is larger than 64 bytes, replace it by its 32-byte SHA-256 hash; now the key is at most 64-byte long.
Start a SHA-256 hash.
Set a 64-bytes buffer to all 0x36; XOR the key into that buffer (leaving unchanged any byte past the key length); hash that buffer.
Hash the blocks of data to authenticate (as several blocks if necessary).
Finalize the hash of steps 2/3/4, giving the 32-byte T.
Start another SHA-256 hash.
Set a 64-bytes buffer to all 0x5c; XOR the key into that buffer (leaving unchanged any byte past the key length); hash that buffer.
Hash the 32-byte T.
Finalize the hash of steps 6/7/8, giving the desired 32-byte result.

That simply applies the definition of HMAC.


Has a SHA256 output ever been found consisting entirely of the same character? Is it possible to have an output consisting purely of one character and does this change the entropy of that output? (If that's even possible to ascertain.)

As an example, the Bitcoin cryptocurrency is slowly and inadvertently compiling a list of inputs which produce outputs with successively larger numbers of trailing zeros in its blockchain. Will these ever be used to study the SHA-256 algorithm?

If any filtering criterion on the output of SHA-256 (with its definition independent of SHA-256 internals) leaves $n$ possible values out of $2^{256}$, then as far as we know,

the best method to exhibit an input to SHA-256 matching that criterion involves trying distinct inputs;
the expected number of hashes (compressions) required for this is $2^{256}/n$;
the $n$ outputs are equiprobable, thus the entropy of the process generating SHA-256 hashes passing that criterion from random input is $\log_2(n)$ bit/output, or $n\log_2(n)2^{-256}$ bit/input.

An output consisting purely of one character is such a criterion, with $n=16$ if we read character as hexadecimal digit. It is expected that $2^{252}$ hashes would be necessary to achieve that. Based on blockchain statistics (currently $7\cdot10^{18}$ SHA-256d per second), I guestimate that less than $2^{95}$ SHA-256 hashes have been performed by mankind; thus, with overwhelming odds, nothing giving a hash passing said criteria was ever hashed. Our best estimate of the theoretical entropy rate of this process is $4$ bit/output, or $2^{-250}$ bit/input.

I do not see how the input values found by bitcoin mining could be of any use in the study of SHA-256.


Threshold Secret sharing - How to create a shared secret from pre existing secret parts? In usual $(t, n)$ secret sharing schemes, a secret $S$ is split into $n$ parts so that any $t$ out of $n$ parts reconstruct the original secret. So, suppose that there is a group of $n$ participants each one has a secret $x_i$ ($x_i$ may be its private key). My question is, is it possible to create a secret $S$ using the prexisting secrets $x_i$ ($i=1...n$) so that with any $t$ out of $n$ from these secrets ($x_i$) we can find the secret $S$?

I'd like to suggest a potentially interesting reformulation (or variant) of the problem as a form of secure multi-party computation:

  Given $k$, $n$ and $m$, is there a protocol by which $n$ participants $i \in \lbrace 1, \dotsc, n \rbrace$ may, without the help of a trusted external party, each compute a share $s_i$ such that

  there exists a secret $S \in \mathbb Z / m \mathbb Z$ that is uniquely determined by any subset of $k$ shares (and can be efficiently calculated from them), and
  during the course of the protocol, no group of $k-1$ colluding participants can learn sufficient information to allow them to guess $S$ with probability higher than $1/m$?

  Further, if such a protocol does exist, does it require assumptions about the computational capacity of the participants, or can it be made information-theoretically secure like conventional secret sharing schemes?

As Thomas Pornin's answer shows, such a protocol does exist when $k = n$: each participant simply selects $s_i$ independently and uniformly from $\mathbb Z / m \mathbb Z$, with $S \equiv s_1 + \dotsb + s_n \mod m$.  Thomas's answer also shows that, for $1 < k < n$, at least some communication between the participants must be necessary to establish the shares.

Addendum:

There's actually a very simple way to do this.
Each participant $i$ chooses a random element $x_i$ of a finite field $\mathbf F_m$, generates $n$ subshares $y_{i,1}$ to $y_{i,n}$ of it using Shamir's scheme of order $k$, and sends each subshare $y_{i,j}$ to participant $j$.  Each participant $j$ then adds the subshares they receive together to obtain their share $s_j = y_{1,j} + \dotsb + y_{n,j}$.  By the linearity of Shamir's secret sharing, interpolating any $k$ of the shares $s_j$ then yields the secret $S = x_1 + \dotsb + x_n$.

(Edited to incorporate PulpSpy's space-saving suggestion; see comments.)


How to compare security between S-Box and Addition in the block ciphers? I'm studying a block cipher based on ARX(Addition, Rotation, XOR).

In a block cipher, nonlinearity comes from S-box or modular addition($Z=X\boxplus Y$ mod $2^n$).

As far as I know, in the case of S-Box, its security can be explained in the algebraic aspect.

How to explain the modular addition($\boxplus$ mod $2^n$) in the algebraic aspect?

So you have addition with carry bitwise if the sum is smaller than $2^n-1$
as well as the subtraction of $2^n$ if the sum is greater than $2^n-1.$

Helger Lipmaa has analysis that is relevant in
"Efficient Algorithms for Computing Differential Properties of Addition" available at

http://kodu.ut.ee/~lipmaa/papers/lm01/

You can use that work as a starting point.


Does watching Youtube generate entrophy Does watching videos (either online videos such as off youtube or saved locally) generate enough (if any) entropy to create secure encryption keys? I understand that some activities such as memory usage, disk access, network utilization, using the mouse and keyboard, etc... generate entropy under Linux. What I don't know is if using the CPU and GPU also generates entropy? I also don't know if this is the same under Windows.

It does, but it's practically impossible to evaluate how much: just a tiny little bit, or enough for security?
A PC is an extremely complex thing, and it's practically impossible to know its exact state at a precise moment in time, even having observed its external behavior (user actions, network packets…) very precisely. Even knowing the exact state of the CPU alone is very difficult: it's very difficult to build a cycle-accurate simulator for the CPU of a modern PC or smartphone, much more difficult than building a simulator that implements all the operations but not their precise timing. Furthermore such complex chips have multiple clocks, and there is some unavoidable manufacturing imprecision that causes a drift between those clocks (CPU jitter), which is the basis of HAVEGE.
The problem with relying solely on the entropy from jitter (within the CPU and between peripherals) is that it's unreliable. Depending on the system configuration, on how much activity there is, on the ambient temperature, there may be more or less jitter. The entropy from user input is unreliable because the user may be somewhat predictable and may be observable. The entropy from network input is suspect because an adversary may be able to obtain it (e.g. if they control your Internet access because you're in a cybercafé or because they breached your router's 5-year old unpatched firmware).
All of these methods have the problem that shortly after boot, no or little entropy has had time to accumulate; a way to counter this is to save entropy from past runs in a file, and load that at boot time. This way, there may be a lack of entropy during the system installation, but as soon as the system has accumulated enough entropy for security, it keeps that entropy forever.
Operating systems like Linux and Windows mix all the entropy sources inside the kernel and expose it through system calls or similar methods (modern interfaces: getrandom(), BCryptGenRandom(); deprecated interfaces: /dev/urandom, CryptGenRandom()). The entropy you get from those system interfaces is more reliable than anything you could cobble up on your own, and is at least as trustworthy since it's coming from the operating system kernel which you have to trust anyway.
Fortunately modern systems, at least in the PC/smartphone range, have a built-in hardware random generator that is actually designed to produce entropy. The system mixes in all the entropy from various sources, which (barring bugs in the entropy mixing) gives you entropy that's at least as strong as the strongest source. While sources such as user activity and disk jitter are mixed in, it doesn't matter if they don't provide enough entropy, since the hardware RNG is sufficient on its own.


Is it possible to exactly reverse engineer an unknown cipher inside a black box? Consider the following arrangement:-

There is an unknown cipher algorithm operating inside the black box. You can enter infinite key /plain text pairs, and observe   all of the outputs. The box might just as well be protecting a short friend/foe challenge as an entire 4K UHD movie. Any counter modes, streams, IVs, nonces or padding is handled inside the box. All you need to do is input any size of plain text. The cipher is a world class modern type with strength equivalent to *fish, Rijndael or ChaCha, but not one of those.  It may have come from outer space, or perhaps in a vision. The point is that no one has ever seen it. It might even be a totally unknown NSA Suite A algorithm.

Given unlimited input output tuples, is it possible to reverse engineer the algorithm exactly so that it could be  used reliably for future encryptions?

Note: Hypothetical unknown cipher - security in obscurity? came up, but honestly I can't understand   the question.

Judging by your comments, you are imagining a box that accepts inputs of arbitrary length. Hence it is a function $f:\{0,1\}^*\to\{0,1\}^*$. There are uncountably many such functions but only countably many programs you could propose as the "reverse engineered" result. This makes your problem fundamentally impossible.


Is iterative sha256 adequate for local password manager? I'm fairly entry-level crypto; not a cryptographer by any stretch... I am at the level of ability to implement most of the traditional packages in python; the hashlib hashes and EAS, ECDSA implementations, etc. And generally logically grasp what they're doing under the hood and when they're appropriate. I've come here to learn a bit more about this new breed of PHC 2015 candidates.

I'm working on a "password manager" to manage my logins to social media, email accts and the like.   I tend not to like GUI's, nor did I like any of the implementations I found... so I thought I'd have a go at it myself.  Of course, as I get down the rabbit hole I gain a clearer picture of my own naivety.  Initially... I was just thinking very simplistically... hash the master password w/ sha256... AES-CBC for each site pass... copy to clipboard, ctrl+v and auto remove from the clipboard.  Then I was like... no, we need stronger master pass!  so:

key = sha256(blake(pbkdf(key)))

I was proud for a moment of my implementation... that faded quickly.

I got to thinking about the whole "hash the master password" concept and I realized that it was really meant for server/client situations, with brute being restricted by websocket communications response time and API limits.  With enough time by some malware running in the background and near-unlimited speed on my beast desktop this was still plausibly brute prone?  Not sure to be honest; concerned enough to ponder on...  At this point, I was unaware of "password hacking competition" and the likes of argon2 and friends.  But I saw a problem and of course headed down the ill-advised path of "roll my own".

Two things immediately came to mind.

1) increase ram requirement
2) increase time requirement.

My first attempt was to up the iteration count of pbdfk, which did indeed increase the cost by about 1 second before the python implementation denied me any further iterations.  But I wanted more...

So I devised two simple solutions:

# 1) make the key really big
key *= int(10 ** 8.5 / len(key))

# 2) sha256 it millions of times
for i in range (10 ** 7):
    key = sha256(key)

First gives me about a gig of ram requirement and second slows the response down to 8 seconds.   The ram gives multicore resistance, the time... increases brute time, surely the iterative sha256 makes rainbow tables less likely.  And of course, I could still do something more salty on the way into my iterative big sha256...  ala:

blake(pbkdf()).

I did a little happy dance, but it was at this point that I delved deeper into the rabbit hole and "read the docs" eventually stumbling upon blake2.net:

  You shouldn't use any general-purpose hash function for user
  passwords. Instead you should use a password hashing function such as
  the PHC winner Argon2 with appropriate time and memory cost
  parameters, to mitigate the risk of bruteforce attacks.

At first, I was vilified! I was right!

Then... the "don't roll your own" came over me... and the fact that I was 4 years behind the times in my own awareness. I've since learned argon2 is using blake under the hood.

So I have come here to ask:

Is my method as strong as I expect?
What does argon2 achieve beyond what I'm doing?

I will skip the usual don't roll your own speech.
For a local password manager you typically need encryption   not only password based key derivation.
You want to encrypt your various passwords with a key derived from your master password.
There are many methods for doing so, argon2 is one of the best. However iteratively applying a general purpose hash function is also acceptable. An example of how to use a general purpose hash function is: https://en.m.wikipedia.org/wiki/PBKDF2

Note it mixes the password again in it's iteration and xors the results these ensure the space of possible outcomes doesn't shrink with iteration count as it would with naive chaining. Also note the use of a Salt which prevents attacking multiple passwords together or use precomputed dictionaries/rainbow tables.

Argon2 is also memory hard and argon2i is also side channel resistant not sure these are a must.

With such a key derived from your master password you can encrypt the individual passwords with a symmetric cipher of your choice.

Note there are other things to watch out for when building your own password manager. For instance, be sure to ask lock the sensitive memory to never be swapped to disk. Or your master password and key may find themselves on disk  so that anyone can read them.


Why should the input value on a DPA attack be non-constant? I actually was wondering if anyone could help me out with the following problem:

Let's assume we are attacking the first SubBytes() operation on AES with the help of a differential power analysis attack, for a DPA attack we need to know the plaintext in order to create the hypothesis and to apply the used power model (in this case Hamming weights) later on. The relationship between the simulation and the real power traces is calculated with the correlation coefficient. This is totally understandable from my side.
However, it is always stated that the known input value must not be constant because it will not yield in any result.

This is actually the thing I was wondering about. I came up with the idea that – in case that the values are constant – I will have the same Hamming weights for all my hypotheses. However, the real traces will still slightly vary in power consumption. Applying the correlation coefficient now will eventually lead in no correlation at all, hence yielding $0$ as the result.

Is this assumption correct, or am I thinking in the wrong direction here?

I already did some research on this subject, but was not able to find the right answer to my solution.

The Pearson product-moment correlation coefficient is what you evaluate, in general, when you perform DPA (CPA would be a better name for this, but DPA is used also in this context).

It is defined as:
$\rho(X,Y) = \frac{cov(X,Y)}{\sigma_X\sigma_Y}$

Where $X,Y$ are your vectors, $cov$ is the covariance and $\sigma_X$ is the standard deviation of X.

In your case, one of the vectors should be a vector of power values at the same time instant for all traces and the other vector should be the hamming weight of your hypothesis.

In your case the second vector is made by the same value. Therefore its standard deviation is 0 and then the correlation is not defined (denominator is zero).

Note that DPA is much better than SPA because by using multiple traces it somehow average out other factors (i.e. noise), but for this you also need different input values (I would say the more the better).


Key exchange protocol and digital signatures I am a beginner to coding and encryption standards... I have this task assigned in a course I am following:

Design and implement a key exchange protocol. Include digital signatures in the protocol for authentication.

Does implementing the Diffie-Hellman algorithm covers both parts as in key exchange and digital signature or only the key exchange part? If so what should I do?

Is there any other approach on covering both parts?

No, the Diffie-Hellman key exchange protocol by itself does not include any use of digital signatures.

However, Diffie-Hellman is also insecure against man-in-the-middle attacks, because the messages are not authenticated. This should give you a pointer what to do with the digital signatures.


Why would anyone choose 3DES over AES in software? I'm well aware of what NIST and PCI say about the usage of 3DES and its deprecation/disallowance and I also know that AES is the actual recommended standard for software and hardware encryptions.

I'm seeing many companies still choosing 3DES when they could simply go with the most obvious choice: AES. Why do you think that is? Is there any technical reason why someone could choose 3DES over AES?

In my opinion, there are no reason to choose 3DES over AES, ever.

Especially if it is in software, since 3DES performances have always been terrible. Furthermore, most CPUs ship with AES accelerators nowadays, which means that AES is even faster.

But, sadly, change management is hard, certain smart card or hardware module do not support AES, but support 3DES... so if you can avoid changing your hardware, you might just keep going with 3DES, as it is not practically broken.

Also, most software development team do not have a cryptography enthusiast / a cryptographer and might just be continuing to use the good old algorithm they are used to, or that their system is based on. Not necessarily a good reason, but change is hard, especially when it comes to software, so most of the time, people prefer to avoid any change that would prevent backwards compatibility or any other such things.

Notice that nowadays, you can still find two-key 3DES out there, for these exact same reasons!

On the theoretical side, 3DES features 64 bits blocks, thus it is not suited for today high throughput data transfer protocols, since it could lead to block collisions, while AES is safe on that side with its 128 bits blocks.

On that topic, I refer you to one of my answers for more details on whether or not 3DES is safe.


Recovery public key from secp256k1 signature and message Regarding this article about a signature recovery

  However, with the signature and the message that was signed, and the knowledge of the curve, it is possible to generate two public keys

So we can derive 2 public keys for each signature and message

I try work with python library https://github.com/ludbb/secp256k1-py.
This library is a wrapper for C++ implementation of secp256k1. As I understand from this library we have special function sign_recoverable that returned signature with included information for recovery unique public keys. And regarding this https://github.com/ludbb/secp256k1-py/blob/f5e455227bf1e833128adf80de8ee0ebcebf218c/secp256k1/init.py#L135

   def ecdsa_recoverable_deserialize(self, ser_sig, rec_id):
      if not HAS_RECOVERABLE:
        raise Exception("secp256k1_recovery not enabled")
      if rec_id < 0 or rec_id > 3:
        raise Exception("invalid rec_id")
      if len(ser_sig) != 64:
        raise Exception("invalid signature length")
      recover_sig = ffi.new('secp256k1_ecdsa_recoverable_signature *')
      parsed = lib.secp256k1_ecdsa_recoverable_signature_parse_compact(

We have 4 variant of a possible public key from 1 signature.

In my code and attempts receive Public keys for  signature in DER format (i want to iterate all available)

def public_key_recovery(signature, messsage, rec_id, compressed=True, hex=True):
if isinstance(signature, str):
    signature = unhexlify(signature)
if isinstance(messsage, str):
    messsage = unhexlify(messsage)
raw_sig = ffi.new('secp256k1_ecdsa_signature *')
r = secp256k1.secp256k1_ecdsa_signature_parse_der(ECDSA_CONTEXT_VERIFY,
                                                  raw_sig,
                                                  signature,
                                                  len(signature))
if not r:
    raise RuntimeError("secp256k1 error")
compact_sig = ffi.new('unsigned char[%d]' % 64)
r = secp256k1.secp256k1_ecdsa_signature_serialize_compact(ECDSA_CONTEXT_VERIFY,
                                                          compact_sig,
                                                          raw_sig)
if not r:
    raise RuntimeError("secp256k1 error")

recover_sig = ffi.new('secp256k1_ecdsa_recoverable_signature *')
t = secp256k1.secp256k1_ecdsa_recoverable_signature_parse_compact(
                                        ECDSA_CONTEXT_ALL, recover_sig, compact_sig, rec_id)
if not r:
    raise RuntimeError("secp256k1 error")

pubkey_ptr = ffi.new('secp256k1_pubkey *')
t = secp256k1.secp256k1_ecdsa_recover(
             ECDSA_CONTEXT_ALL, pubkey_ptr, recover_sig, messsage)
len_key = 33 if compressed else 65
pubkey = ffi.new('char [%d]' % len_key)
outlen = ffi.new('size_t *', len_key)
compflag = EC_COMPRESSED if compressed else EC_UNCOMPRESSED
if bytes(ffi.buffer(pubkey_ptr.data, 64)) == b"\x00" * 64:
    return None
r = secp256k1.secp256k1_ec_pubkey_serialize(ECDSA_CONTEXT_VERIFY, pubkey, outlen, pubkey_ptr, compflag)
if not r:
    raise RuntimeError("secp256k1 error")
pub = bytes(ffi.buffer(pubkey, len_key))
return hexlify(pub).decode() if hex else pub

I got correct result for first 2 variants (0,1), and for last 2 always 64 zeros byte string

What is real count 2 or 4  public keys posible  derive  from signature?

You can usually derive two public keys. However, sometimes (very rarely), you can get four public keys.

With some details:

There is an elliptic curve. In Bitcoin, this is secp256k1. Each curve point has two coordinates $(X,Y)$; the coordinates are integers modulo a given prime integer $p$ (precisely, $p = 2^{256} - 4294968273$).
The curve order (number of points on the curve) is an integer $n$, which happens to be prime, and to be very slightly lower than $p$.
Private key is $x$, a non-zero integer modulo $n$. Public key is $Q = xG$, i.e. multiplication of a conventional generator point $G$ by the private key $x$.
To sign a message $m$, things go the following way:

A random (non-zero) integer $k$ modulo $n$ is generated.
The point $kG$ is computed, and its $X$ coordinate (an integer modulo $p$, hence in the $0$ to $p-1$ range) is reduced modulo $n$, thus yielding a value between $0$ and $n-1$. The result is called $r$.
The value $s = (h(m)+xr)/k \bmod n$ is computed. $h(m)$ is the hash of the message to sign, with some hash function that yields a sequence of bytes which is interpreted as an integer.
The signature is $(r,s)$.

Now suppose that you have a message $m$ and a signature $(r,s)$, and you want to recompute the corresponding public key $Q$. If you somehow obtain the point $P = kG$, then you can compute:
$$ Q = r^{-1} (sP - h(m)G) $$

Thus, if you can get the point $P$, then you can have the public key $Q$. However, you do not have the point $P$. Instead, you have $r$, the $X$ coordinate of the point $P$, reduced modulo $n$.

Since $n$ is very slightly lower than $p$, there can be two values $X$ that match $r$. In general there will be only one, but if $r < p-n$, then there will be two.

For each possible coordinate $X$, there can be two corresponding points. Indeed, points on the curve follow the curve equation:
$$ Y^2 = X^3+7 $$
Thus, if $(X,Y)$ is a point on the curve, then $(X,-Y)$ is also a point on the curve, and has the same coordinate $X$.

Putting all together: from the value $r$ (in the signature), you can have up to two candidates for the $X$ coordinate of $P$, and from each such candidate, you can have up to two matching points. In total, there can be up to four curve points $P$ that match the $r$ value from the signature. For each of them, you can compute the corresponding public key $Q$. But note that the case of two possible $X$ coordinates for a single $r$ is very rare; indeed, this will happen randomly with probably about $2^{-128}$, i.e. never in practice (although you might be able to force it with specially crafted data). Thus, you can normally expect to recover two public keys, but (at least theoretically) you might get four.


Attack on Double Encryption Scheme In this protocol:

A → B : { <[A, {K}pk(B)]> }pk(B)
B → A : { <[B, {K}pk(A)]> }pk(A)

I'd like to determine why this is insecure.  How can the attacker learn the key K if A and B are both honest agents?

This is what I have started with:

A → B : { <[A, {K}pk(B)]> }pk(B)

An attacker M can intercept this, however M cannot decrypt this.  M sends it to B so B thinks the message is coming from M:

M → B : { <[A, {K}pk(B)]> }pk(B)

Then I run into the problem that A's identity is still in the message.  When B decrypts, he will realize that D and A do not match, and end the session.

Any help, hints, or advice would be appreciated! Thanks!

EDIT: I think what I do is provide a little more than a hint so don't read further if that is an issue.

   This problem is very much like the NSL protocol in that it allows an intermediary due to neither party declaring their own identity:

That is:

   A -> E : { <[A, {K}pk(E)]> }pk(E) }  E -> B : { <[A, {K}pk(B)]> }pk(B) }  B -> E : { <[B, {K}pk(A)]> }pk(A) }  E -> A the above

Resulting in:

   Now B believes it has a shared channel with A but E is involved.  You can even simplify and omit A entirely since its existence was never proven to party B:

Alternatively:

   E -> B : { <[A, {K}pk(B)]> }pk(B) } B -> anyone : { <[B, {K}pk(A)]>}pk(A) }

and

   Now 'B' presumably believes key $K$ is shared with party $A$ when in fact party $E$ holds a copy.


How secure is a 40 bytes hexadecimal string AES256 encrypted with 50 bytes random password Problem

Assume I have a 40 bytes hexadecimal ASCII string and a 50 bytes random password.

data: a7cd8558a341e3525d060e90fb37975efa8dd519
key:  ]*Úf"¢^¨¥GJþPÒYÅ9ÝÁ´!½OïæñÝ{/§@·]%¾âðNQn@:U2çþÇ<uÓ

The data will be AES256 encrypted with the password. The encrypted data will be stored as a key-value pair and that key and the usage of it predicts the decrypted data represents a lower case 40 bytes hex value.

Question

What can I assume how secure the encrypted data will be?

Use case scenario

I'm using Ansible to provision my VM. One of the Ansible scripts uses my GitHub API token. The token is stored as an variable encrypted with AES256 by the Ansible Vault.

Now I'd like to store my Ansible scripts in my GitHub repository. But I'm not sure how much does it cost to decrypt the GitHub API token.

For reference, this is the Ansible Vault format. In short:

It derives an AES key, HMAC key and IV from the password using a 32-byte random salt
It encrypts the data using AES-CTR with the derived key and IV
It MACs the ciphertext (but not the IV) with HMAC-SHA256. Not including the IV is usually bad, but since the IV is derived from the password and salt and it's not stored with encrypted data, it seems OK.

As far as I know, this looks safe if the password is strong enough. In your case, what you call "key" seems to be the password, and is certainly long enough.


S-box basic question I'm trying to understand DES and a bunch of other cryptographic systems using S-Boxes.

I have now a quite basic question about how Sboxes work in general. For DES, Sboxes are substituting a 6-bits input for 4-bits output. It is clear for me how this works using the suitable substitution table. What I don't understand though is how the cryptosystem deals with the "loss of information" (at least it seems for me to be a loss of information, but I might be wrong).

If you map 6 bits on 4 you lose information. So there might be more than one 6-bit combination which is mapped on the identical 4-bit combination. As a consequence, after the S-box operation it seems for me that it is not possible to get the original 6 bits again out of your 4-bit result. How is it possible then to decrypt your ciphertext again?

Good question and yes, it would appear that data is lost.  And technically, something clearly must disappear as 6 don't go into 4. But consider the overall architecture of DES:

Trace the flow of the left and right halves of an individual block of data.  You'll see that the 2 full 32 bit words flow unimpeded down though the Feistel network. No information is lost there, it's only XORed with, maintaining the width. So 64 bits go into the block, and 64 bits emerge.

You're actually referring to the internals of the DES cipher function which looks like:-

and you can identify the s boxes.  They indeed accept 6 bits and output 4, so something is lost due to the pigeon principle. But look at the expansion box above the s boxes.  Additional bits are created due the permutation, P. So what is lost, never really existed but was created within (and localised to) the cipher function. So similarly for the cipher function, 32 bits go in and 32 bits come out.

The reason this works can be considered by analogy, but don't take it too far.  Consider a single round.  DES's cipher function operates as a small pseudo random number generator keyed off a sub-key (round key) and the other half of the block's 32 bit data.  That is then XORed with the original data to encipher it. The streams then swap and the round functions repeat.  So as a (kind of) pseudo random number generator, the cipher function doesn't have to be invertible.

You could actually re-engineer DES using off the shelf hash functions like MD5 or SHA1 (both truncated to 32 bits) to see that transcoding is still possible. It's a common theme in cryptography to consider hash functions as the basis of ciphers, and some more insight can be found with the questions Construct an encryption algorithm using hash function. (I don't know how to handle the 3 way duplicates.)

Designers of these things tend to reflect the key schedule with the main algorithm. Whirlpool is similarly symmetric. I suspect that this was the only way the designers could think to easily expand a 64 bit key using a similar geometry to the main part, and still XOR with 32 bit half blocks. Hence they invented 48 bit sub keys. There's no specific reason on Earth to have 48 bit round keys. They could have been 32 bits and that would have made asymmetric 6 to 4 bit s boxes unnecessary.


Now that quantum computers have been out for a while, has RSA been cracked? D-wave systems has released a commercially viable quantum computer. This means in theory, that all asymmetric encryption algorithms — such as RSA — are now useless due to the speed at which quantum computers can factor.

Has RSA been cracked yet? If not, why hasn't it?

The reason for our company's concern is an upcoming product that relies heavily on cryptography, and a significantly large number of hackers may attempt to break it. If the code was found to be insecure, it would be a huge problem for our company, our users, and anyone on the Internet if RSA was found to be insecure.

Update: article on D-Wave recent announcement here

RSA has not been cracked.  No one has demonstrated practically viable computing that's anywhere in the realm of breaking RSA.  There is no reason to change any of your practices.

The first thing to understand is that D-Wave has a long history of
repeatedly making bogus claims to the popular press.  Experts in quantum computing have been criticizing and debunking D-Wave's claims for years.  (Try clicking each of the last seven words, for examples.)  So, this is not a company with a lot of credibility.

The latest news is that D-Wave has published a paper in Nature that describes very limited progress towards quantum computing.  It is not a full-fledged quantum computer.  It can't do general-purpose computation; it can only solve one algorithm.  In particular, it can't be used to factor numbers or break RSA.  It can't handle realistic problem sizes; it only has 8 qubits, so it can only solve toy-sized problems (problems that you could have solved with pencil-and-paper anyway).  There is no evidence that it is faster than classical algorithms.  It's not faster than existing classical computers.  It does represent a step forward, but it's a limited step.

Researchers have been studying quantum computing intensely over the past decade or so.  There has been some progress, but it has been slow, and building a working quantum computer will require us to surmount some fundamental challenges (e.g., decoherence) that today no one knows how to deal with.  D-Wave gets a lot of press (mostly because they make irresponsible statements to the press to hype their work beyond its true importance), but others have made more significant contributions.

You use the phrase "commercially viable quantum computer".  That's not a useful phrase.  Please understand that D-Wave has not demonstrated a viable quantum computer.  D-Wave may have sold something to one or two customers, but that doesn't mean they have licked the quantum computing problem or that their claims therefore necessarily have any validity.  Snake oil salesman managed to sell their stuff to plenty of customers, too, but their claims were invariably bogus.

If someone did build a working quantum computing that scaled to an unlimited number of qubits, and solved the decoherence problem, that'd be different: in that case, we'd have to move away from RSA, pronto.  But we're a long ways away from that.  Right now, it's an open question whether we'll see such a quantum computer in our lifetimes (or even if it will ever be possible to build one) -- quantum computing experts like to debate questions like those over drinks.  I suspect, if general-purpose quantum computing is possible, we'll have plenty of warning before quantum computers that can threaten RSA become readily available.

So, in short, no, you don't need to change your strategy or drop RSA.  I wouldn't.  Continuing to use RSA is perfectly reasonable and in line with industry practices.


Did a certain cryptography method get abandoned due to security flaws in the past? I am researching how quantum computers affect current encryption methods (RSA and more).

However, I remember learning in a course that there used to be a particular encryption method which was popular but suddenly had a very bad vulnerability in the past (like quantum computers and Shor's algorithm would be for RSA) and everybody had to move on (is that right?).

I cannot find anything about this in the past, does anybody have any idea which cryptosystem I am talking about?

You could be thinking about the Merkle-Hellman knapsack cryptosystem. It was invented in 1978 and everything seemed well and good until it was completely broken six years later in 1984 by Shamir - it was a complete and total break, i.e. the cryptosystem became unusable overnight.

That said I don't know if the knapsack cryptosystem was ever "popular" in the modern sense (it was 1978 after all) but it was certainly an early public key cryptosystem that met an unfortunate end.

On the other hand, for an example of a progressively worn-down algorithm (as opposed to one being broken immediately) there is of course MD5's collision resistance.


When is the Random Oracle model (not) necessary? Hash functions are often used in cryptographic schemes and protocols, and that doesn't necessarily mean that their proofs are on the Random Oracle model. That leads to the following question: What is the "turning point" in which the use of a hash function requires a proof on the Random Oracle model?

Is it when the proofs require observability and/or programmability
of the random oracle?
Is it when it is essential to guarantee a random output?
Is it related to the usual characteristics of cryptographic hash functions (i.e., pre-image resistance, second pre-image resistance, collision resistance)? If so, how?

A hash's security in the Random Oracle Model implies its collision-resistance, first-preimage resistance, and second-preimage resistance. In addition, security in the ROM implies that the hash's output is indistinguishable from random for an adversary without knowledge of the input, and that the hash is resistant to length-extension attack, neither of which is implied by collision-resistance, first-preimage resistance, or second-preimage resistance. So when randomness or length-extension matters, a hash secure in the ROM is useful in practice, and therefore in formal proofs.

Rigorous formal proofs of protocols often are easier with a hash secure in the ROM than with some weaker hypothesis. I pass at characterizing exactly when the ROM is indispensable, and if that's related to observability and/or programmability of the random oracle.


Is a larger block size less secure against a brute-force known cipertext attack? Suppose a ciphertext $c$ was encrypted from plaintext $m$, and we know something about the form of $m$; say, for example, that $m$ is English text.
We can attempt to brute-force $m$ from $c$ by computing $E^{-1}(c)$ for all possible encryption functions $E$ and discarding the values of $E^{-1}(c)$ which are not English text.
However, the probability of $E^{-1}(c)$ consisting entirely of English text (assuming $E$ behaves ''randomly'') decreases as a function of the block size. Hence, it seems that a larger block size results in fewer false positives.

Am I correct in saying that large block sizes are more susceptible to this kind of attack? Do we have to keep this in mind when designing encryption techniques, or are other factors (e.g. key length) more likely to be security bottlenecks?

The answer depends on the size of the plaintext you are attacking and the number of ciphertext blocks you have.

Assume that you have a 64-bit block-sized cipher named C64 and 128-bit block cipher named C128.

If you know that the $m$ is smaller than 64-bit than you will have only one ciphertext for C64 and C128. There is a need for padding at the end of the plaintext. This padding can be removed and more importantly it can also be used to detect the correct plaintext like in the DES challanges. There is no difference here.

If the $m$ between 64 and 128 bit than the question, do you have the second block for C64? If not then C128 is better here. Otherwise, the are the same.

Similar comments can be made to other cases. But, in short, if you have the all necessary ciphertexts they are the same. If you have all, the only difference is that you need to run almost C64 double times of C128. But this is not counting the actual running times of the ciphers. C128 is expected to be slower than C64.

Not that: a 64-bit block size is not secure; see sweet32. I've used to demonstrate and historical reasons. We don't have a common 256-bit clock cipher also. Also, brute force is not applicable to block ciphers who have a key size larger than 128. We can see this from the collective power of the bitcoin miners that can reach $2^{94}$ double SHA-256 hashes. Some of the nodes are ASIC that boost the attack. One still needs $2^{34}$ year to break with the enormous collective power.


RSA keys finding when messages are known I have this situation, where, in a game, people send messages to each other (game moves etc...) These messages need to be encrypted, and should only be readable by the destination person. I am using RSA for this, but, recently I got a doubt. Is it possible that, if the message is one of n possible messages, can somebody with access to the encrypted one, guess the keys used? (Both public and private).

We use keys to ensure the source and destination. So, we encrypt twice, every message. Once with sender's private key, and with receiver's public key on top of it. So, it is doubly secure, and repudiation is avoided. We use RSA only, for both. Is this bad, if the attacker knows the message to be 1 out of n.

NOTE: If this is a problem, using a random number as a field in the message, and xoring the message first with it, and sending, would that solve the problem. This makes, encrypted message essentially random, for the attacker. But for person with keys, it still allows nicely to be decrypted.

Another question about encryption, does ElGamal encryption have similar issues? I plan to use both in the game app.

I confirm that "encrypt with the private key" in an asymmetric encryption scheme generally does not make sense. It seems that the only reasonable interpretation of "encrypting with the sender's private key" in your setting is that the sender actually signs the message.

Now the attack scenario you describe is not "chosen plaintext attack" but rather known plaintext attack: the attacker knows that the message is one out of n possible, known, messages. For a deterministic encryption, this would allow the attacker to find out what the message actually was, provided the list of n messages is not too big (since the encryption function is public, one can encrypt each of the n messages exhaustively and see which ciphertext matches). However, this is not possible with a standardised version of RSA such as RSAES-OAEP in PKCS #1 where the encryption is made probabilist by the use of an appropriate padding.

Using a standard implementation of RSA would not allow an attacker to recover the keys.
The ElGamal scheme is also probabilistic so the same applies.


Can I use Pollard'-Rho even when the order is not a Prime? I am now solving the ECDL problem.

I want to use [discrete_log_rho] in SageMath, but I can not use it because ORDER is not a prime number.

Can I change it to a decimal number close to ORDER at my disposal?

I tried to use another method, but the size of F was 100bit, so I could not use BSGS because of memory problem.

If I can not use Pollard's-Rho and BSGS, what else is there?

If the order is not prime, you first use Pohlig-Hellman to reduce it to several instances where the order is prime, and use rho to solve those.


TLS Finished message: is it MAC or HMAC In several academic literature, the term Finished MACs is used frequently. I wonder, is it really a MAC or HMAC? I am looking at literature in TLS 1.2 vs. TLS 1.2 specs. The specs of TLS 1.2 Finished messages Here says:
   Structure of this message:

  struct {
      opaque verify_data[verify_data_length];
  } Finished;

  verify_data
     PRF(master_secret, finished_label, Hash(handshake_messages))
        [0..verify_data_length-1];

  finished_label
     For Finished messages sent by the client, the string
     "client finished".  For Finished messages sent by the server,
     the string "server finished".

As far as I know, if PFR are used, then it is HMAC not a MAC. Can you clarify to me please:

1) In TLS, is it Finished MACs or Finished HMACs? when some literature uses Finished MACs, is it correct (i.e. is it acceptable abbreviaton)?

2) Is it correct to use MAC instead of HMAc for short?

Is it correct to use MAC instead of HMAC for short?

In general, no.
MAC is a much more general concept than HMAC and thus such an equivalence in saying is clearly inacceptable. However, if you are talking about a specific protocol which authenticates its payload, saying "the MAC" to designate the MAC algorithm or the tag for messages, even if they use HMAC, is fully acceptable, because you are referring to the use of the more general concept with the concrete instantiation here.

Now to answer the question in the title (which will also catch question #1):

  TLS Finished message: is it MAC or HMAC?

The answer is both.
Yes, HMAC is always used here to compute the (correct) PRF value, which is only possible if the same transcript was seen and the same master_secret was generated. Thus the authentication is built-in.

However, prior to this message, the ChangeCipherSpec message was sent for the record-layer protocol, enabling the use of the negotiated cipher suite. So the Finished message is actually send using the (now) encrypted and authenticated record-layer protocol, which does use the MAC specified in the cipher suite (e.g. GMAC or Poly1305).

The relevant quote from the RFC is:

  The ChangeCipherSpec message is sent during the handshake after the
  security parameters have been agreed upon, but before the verifying
  Finished message is sent.


Transforming Gaussian random $[0,1] $ numbers to uniform $[0,255] $ I am not exactly sure if this is for math stackexchange or crypto:

A TRNG outputs numbers in $[0,1]$ in a Gaussian distribution. I would like to convert them into uniform random bytes ($[0,255] $) to perform byte operations. What is s cryptographically secure method of doing this?

Here is an example distribution from my generator before normalized between $[0,1]$:

Edit:

Output from my original methodology: Normalize values to to be within $[0,1]$, remove first and second decimal place via $x*100-floor(x*100)$, then put between value discrete values in $[0,255]$ via $floor(x*255)$. The resulting distribution is as follows:

There is no such thing like a Gaussian distribution over [0,1]; this doesn't make any sense. So it is not clear what you have to begin with.

However, if you have independent random values, you can generate a random bit by taking two values A and B and comparing them. E.g., if $A<B$ you set the bit to 0, otherwise you set the bit to 1. A sequence of 8 such bits is then a (uniformly distributed) random byte.

PS: As correctly mentionned by Ilmari Karonen, if you have a non-negligible probability to have A=B, you have to check for this and if it happens you have to discard A and B.


State of the art techniques for Anonymous Authentication? What are the state of the art techniques for Anonymous Authentication? What are the most popular ones? The problem domain I am considering is with respect to different users accessing cloud content; lets say watching movies in Netflix. I am looking for schemes that prevents linkability, and also schemes that allows linkability.

Please let me know if it is too vague to answer, and I would try to narrow it down.

Take a look at the ECDAA protocols. They are implemented in the Trusted Platform Module (TPM 2.0). ECDAA is based on pairings over elliptic curves. In contrast to Idemix, they have the benefit of being far more efficient. In contrast to U-Prove, they have the benefit to be multi-show unlinkable.


Security of Keccak/SHA3 against birthday attacks If I understand it correctly the security of $\operatorname{Keccak}$ depends on the capacity $c$, which means that I get a security level of $2^{128}$ for $c=128$ (I omitted the value $r$ here because I think that it is irrelevant to my question...but correct me if I'm wrong).

But in every publication I found (and even on the $\operatorname{Keccak}$ website), it is said that the security does not depend on the output length. I don't understand how the value of $c$ is relevant to birthday attacks. For every single hash function, I can just run a birthday attack regardless of the inner construction of the hash function, right? Which means that for a $\operatorname{Keccak}$ implementation with $c=128$ but an output length of let's say $64$ bits, I can find a collision after $2^{32}$ steps using the birthday paradox, regardless of the value of $c$, right?

Let's even take it one step further. How is Keccak with $c=128$ and an output length of 1 bit still secure? For practical applications, it simply just can't be...

Let us correct some of your numbers. The size of the capacity is twice the size of the expected security margin (against a birthday attack). This is the idea of flat sponge clain etc

  When using a random sponge as a security reference, one considers the success of a particular attack. Such a success probability depends not only on the nature of the attack considered but also on the chosen parameters of the random sponge, i.e., its capacity, bitrate and whether it calls a random permutation or a random transformation. The flat sponge claim is a simplification in the sense that we consider only the worst-case success probability, determined by the upper bound on the random oracle differentiating advantage [Bertoni et al., Eurocrypt'08], which depends solely on the capacity of the random sponge. Hence, it flattens the claimed success probabilities of all attacks using a single parameter: the claimed capacity $c_{\mathit{claim}}$. [source]

Thus if you aim for a security margin of $128$ bits, you need to have a capacity of $256$ bits.

  In this approach, one designs a permutation $f$ on $b=r+c$ bits and uses it in the sponge construction to build the sponge function $F$. In addition, one makes a flat sponge claim on $F$ with a claimed capacity equal to the capacity used in the sponge construction, namely $c_{\mathit{claim}}=c$. In other words, the claim states that the best attacks on $F$ must be generic attacks. Hence, $c_{\mathit{claim}}=c$ means that any attack on $F$ with expected complexity below $2^{c/2}$ implies a structural distinguisher on $f$, and the design of the permutation therefore attempts to avoid such distinguishers. Note that the existence of a structural distinguisher for $f$ does not necessarily imply an attack or weakness in $F$. For example, any distinguisher for $f$ that has success probability zero below $2^{c/2}$ forms no threat, as the flat sponge claim expresses no security against adversaries that may send more that $2^{c/2}$ queries. [source]

TL;DR: the security margin is half the capacity. If you aim for 128 bits, you need a capacity of 256 bits.

That being said, we can move to your misunderstanding. You are right to say that if you take an output length of $1$ bit, you won't have the $64$ bits security claim... because you are looking for a collision in the output.

When you use $\operatorname{Keccak}$, you can retrieve the full size of the bit rate ($r$). You can also extend this output and because these outputs are related  (as you basically always know the content of the bit rate part). Thus the only part that you don't know is the capacity. If you are able to guess or have a collision on this part, then the output is compromised.

The capacity is the only part of the state that you don't know.

When you want a collision, you look either to have a collision on the capacity part or on the bitrate part which is usually bigger than the capacity...

Let $a,b$ be two inputs and $c,c_1,c_2$ the capacity part. You have a collision when :
$$f(a) \to [\theta \mathbin\| c_1]\\f(b) \to [\theta \mathbin\| c_2]$$
where $[\theta \mathbin\| c]$ is full state and $\theta$ is the resulting output (here your output length is important).

The other way to find a collision is to manage to get:
$$f(a) \to [\alpha \mathbin\| c]\\f(b) \to [\beta \mathbin\| c]$$
(collision in the capacity), because then you can have (due to the simplified sponge construction):
$$\begin{align}
f(a \mathbin\| 0) & \to [\alpha \mathbin\| c] &\Rightarrow&&& f([\alpha \oplus 0 \mathbin\| c]) \to \theta \\
f(b \mathbin\| \beta \oplus \alpha) & \to [\beta \mathbin\| c] &\Rightarrow&&& f([\beta \oplus \beta \oplus \alpha \mathbin\| c] ) = f([\alpha \mathbin\| c]) \to \theta
\end{align}$$

TL;DR 2: as @CodeInChaos said Collision resistance is $\min(c/2,n/2)$ and preimage resistance $\min(c/2,n)$ where n is the output size.. But most papers search collisions on $\operatorname{Keccak}[1600]$ thus why they usually state this more generic security margin ($2^{\mathit{capacity}/2}$).


I do many searches but can't find any explanation about "AES analysis using entropy" I found this scenario in CRYPTOOL2 templates but there is no explanation how entropy is used. There is just a short description "This template shows how to use a brute-force search to attack an AES-encrypted text. The Keysearcher component searches a subspace of the AES keyspace and uses the entropy of the decrypted plaintexts to find the correct one.
The plaintext with the lowest entropy will rank first in the bestlist.
As input, the Keysearcher receives a ciphertext, which was entered hex-encoded."
What does "and uses the entropy of the decrypted plaintexts to find the correct one." mean here?

Natural language has a nonuniform distribution. If a character $x$ appears $N_x$ times in a candidate decryption with $N$ characters, the sample entropy estimate will be
$$
\sum_{x \in X} (N_x/N) \log (N/N_x)
$$
by Shannon’s formula, where $X$ is the set of characters.
If the decryption is incorrect (wrong key guess) this value will be high, nearly equal to the maximum of $N \log |X|$ due to the fact that a wrong decryption results in random nearly uniform characters.
If $N$ is large enough and the message is in a natural language, it is very likely that the decryption with the lowest entropy is the one with the right key guess.
The cryptool site points to a help functionality but it seems that you need to download the package, the entropy reference does not appear in the online version.
Edit: So, this approach would only work in ECB (Electronic Codebook) mode for AES since it fails Ind-CPA. This basically means that the plaintext is divided into blocks 128 bits long, with no padding or randomized padding. Therefore the plaintext characters are distributed according to, say English, and have low entropy.


Choice of ECC curve on USB token I would like to get a USB token to secure my keys. My use case is protection of 3 GnuPG keys that I will be using 10 times per day at least. I plan to create a new key ring from scratch. Because ECC seems more future-oriented than RSA, this is what I chose to use. I'm wondering which USB token to choose as well as which curve.

On the GnuPG FAQ, it is said that many people think curves recommended by the NIST or defined by Brainpool have a doubtful origin; therefore, they recommend the non-standardized Bernstein’s Curve 25519. On the NitroKey forum, one poster says that

He is not aware of any profound criticism of Brainpool curves, and
Bernstein’s Curve 25519 is hard to protect against side-channel attacks when implemented in embedded devices.

As a result, I'm a bit lost as to which key/curve to choose.

How NIST's ECC curves (P256 alias secp256r1 and friends) have been generated is public: that's in SEC2v1 (with reference to the "verifiably random" method of ANSI X9.62-1998, a draft of which is here), including the seed of the SHA-1-based PRNG used; however, how that seed was chosen is not public, and it's anyone's guess if that's just lost or if something nefarious was done (yet notably: we know no method to do something nefarious).

How Brainpool's ECC curves have been generated is public, and based on a nothing-up-my-sleeve number. All the details where formerly online there (pages 8 to 10), with copy at the Web Archive.

Disclaimer: I do not know who actually checked that the numbers match the methods listed above.

Bernstein's Curve25519 matches more security criteria (see there) and is designed to be easier to protect against side channel attacks, all things equal. But on the other hand:

It is not known any practical attack taking advantage of characteristics of Brainpool (or NIST) curves for ECDSA signature, and as far as I know for proper implementation of ECIES encryption.
Single-chip tamper-proof devices (including all those with a Common Criteria certification that I am aware of) currently tend to have a hardware accelerator that does not directly support Curve25519; thus secure implementations of Curve25519 on said devices would be slow, or at least not security evaluated. That's the argument given by nitrokey's support:

  Curve 25519 isn’t supported by the smart card chip we are using

The question echoes a common opinion:

  ECC seems more future-oriented than RSA

to which there are several counterarguments:

With key sizes giving comparable security against today's attacks, ECC might well turn out to be what gives the worst protection against hypothetical future quantum computers usable for cryptanalysis, because the current guess is that the larger keys would require quantum computers with about proportionally more coherent qubit, and scalability of that currently is the major hurdle in quantum computing.
For tasks using a securely generated private key (signing in particular), ECC is typically much more vulnerable than RSA is to failure of the random number generator, and that's a very practical line of attack.
For tasks performed with the public key (verification and encryption), RSA is faster, and simpler (thus safer) than ECC is.

Thus if we stick to what's available on secure hardware, target longer term security, do not dismiss quantum computers usable for cryptanalysis within a lifetime as pipedream, and RSA-4096 gives acceptable signature generation and decryption speed, it might be a good choice. See this for applications where RSA makes a lot sense.

Personally I'm far from paranoid on key size or imminent cryptopocalyse by quantum computers (on the grounds that practical attacks tend to be far more mundane, like penetration of the machine where the Smart Card stands, which might not allows private key extraction but allows rogue signature/decryption; side channel attacks; fault attacks), and I'd be happy with 256-bit ECC (or better) if RSA is unacceptably slow, as happens a lot on Smart Card CPUs at 3072-bit level or more: work for secret-key operation increases about with the cube of the key size for both RSA and ECC, and the smaller multiplicative constant for RSA far from offsets it all.


how many blocks are encrypted at a time in DES Algorithm? I know that block ciphers encrypts data in the shape of specified blocks and DES also belong to block cipher family. I totally understand the procedure of DES, but I am confused that is DES take all the blocks of 64 bits of any plaint text and apply the process to all of blocks at a time or it encrypts first blocks then 2nd and 3rd and so on.. can anyone explain it Please??

Guess what: in counter mode DES doesn't encrypt blocks of plaintext at all. In counter (CTR) mode DES encrypts a counter which is XOR-ed with the plaintext.

DES itself doesn't do anything with multiple blocks. DES is an algorithm called a block cipher which handles one block of input and permutes it to a block of output. The chosen permutation depends on the key.

To encrypt anything that is not precisely a block with DES (or any other block cipher) you need a block cipher mode of operation . There are many modes of operation in which a block cipher can be configured as underlying primitive.

How many bytes are actually encrypted by the mode of operation depends on the mode and implementation. One instance of DES - the block cipher - will only handle one 64 bit / 8 byte block at a time.


Chaum undeniable signature - justification for probability of misleading the verifier? Can anyone explain me in details why does the following statement hold true in Chaum and van Antwerpen scheme for undeniable signature?

  The probability that a dishonest signer is able to successfully
  mislead the verifier in either verification or disavowal is 1/q where
  q is the prime number in the signer's private key

Chaum and van Antwerpen scheme:

1) Initialization

Select two big primes $p$ and $q$ such that $p - 1 = 2q$
Select a generator $g$ of the cyclic subgroup $G$ with order $q$ inside of $Z_p^*$

which means an element $g$ such that $1 = g^q \bmod p$ and $1 \ne g^a \bmod p$ for all $0 < a < q$
Choose a private key $k \in \{1, 2, \dotsc, q-1\}$
Send to the Trusted Authority (PKI) the public scheme key $(y, g, p)$ where $y = g^k \bmod p$

2) Signature of a message $m \in G$

Compute the signature $s = m^k \bmod p$

3) Verification of a signature $s$

The verification phase is characterised by a challenge / response procedure between the verifier (Victor) and the author of the signature (Sally):

Challenge:

Victor chooses two random numbers $a,b \in \{1, 2, \dotsc, q-1\}$
Victor computes the quantity $c = s^a y^b = s^a g^{kb} \bmod p$ and sends it to Sally

Response:

Sally computes the response $r = c^{k^{-1}}$ where $k^{-1}$ is the number such that $kk^{-1} = 1 \bmod q$ and sends it back to Victor

Final verification:

Victor checks if $r = m^a g^b \bmod p$ holds true, if it does then the signature is authentic, otherwise or the signature was forged, or Sally is trying to deny her signature.

Which of the two possibilities holds true may be checked with an disavowal procedure that I'm not explaining cause it should not be of interest for the question.

For any further details about the scheme read the following chapter of Handbook of Applied Cryptography at page 476

OK, let me try to expand on Chaum and van Antwerpen's proofs a bit.  Please let me know if there's still something that doesn't convince you.

I'll start by rephrasing Chaum and van Antwerpen's theorem 1 using your notation:

  Theorem 1: Even with infinite computing power, the probability that Sally can verify an invalid signature $s \ne m^k \bmod p$ is at most $1/q$.

To verify $s$, Victor chooses two random numbers $a$ and $b$ from $\mathbb Z_q = \{0, 1, \dotsc, q-1\}$ (see note below).  However, the important bit is that Sally doesn't know $a$ and $b$; she only sees $c = s^a y^b \in G$.

Now, it's not hard to see that every value of $c$ seen by Sally corresponds to $q$ possible $(a,b)$ pairs: in particular, for any $a$ and $c$, we may solve for $b$ as follows:

$$\begin{aligned}
s^a y^b &= c \\
y^b &= s^{-a} c \\
b &= \operatorname{dlog}_y(s^{-a} c)\\
\end{aligned}$$

(This works because, in a cyclic group of prime order, the discrete logarithm is unique for any base not equal to 1; equivalently, $b \mapsto y^b$ is a bijection, and in fact a group homomorphism, from $\mathbb Z_q^+$ to $G$ for any $y \in G$, $y \ne 1$.  The case $y = 1$ cannot occur, since $k \ne 0$ and $g \ne 1$ by construction.)

Now, assume that $s \in G$ and $m \ne 1$ (which Chaum and van Antwerpen's paper mandates).  Then there exists some $x \in \mathbb Z_q$ such that $s = m^x$.  If $x = k$, then the signature is valid, so an invalid signature must have $x \ne k$.

I'll now show that, if $x \ne k$, then for each of the $q$ different $(a,b)$ pairs corresponding to the $c$ sent by Victor, Sally would have to reply with a different $r$ to have it accepted.  Like Chaum and van Antwerpen, I will do so using proof by contradiction.  Specifically, assume that there exist two pairs $(a,b)$ and $(a^*,b^*)$ corresponding to the same $c$ and the same $r$.  Then:

$$\begin{aligned}
m^{xa} g^{kb} =& c = m^{xa^*} g^{kb^*} &&&
m^{a} g^{b} =& r = m^{a^*} g^{b^*} \\
m^{xa} m^{-xa^*} =& g^{kb^*} g^{-kb} & \text{and} &&
m^{a} m^{-a^*} =& g^{b^*} g^{-b} \\
m^{x(a-a^*)} =& g^{k(b^*-b)} &&&
m^{a-a^*} =& g^{b^*-b} \\
\end{aligned}$$

Taking the base-$g$ discrete logarithm and letting $\mu = \operatorname{dlog}_g(m)$, we get $\mu x(a-a^*) = k(b^*-b)$ and $\mu (a-a^*) = b^*-b$.  Substituting the latter into the former, we get $\mu x(a-a^*) = k \mu (a-a^*)$, and thus $x = k$.  But this is only possible if the signature is, in fact, valid!

Thus, we've shown that, if $s \ne m^k$, any value of $r$ that Sally returns can only be valid for one $(a,b)$ pair.  But since there are $q$ possible such pairs, each of which is equally likely, Sally has only a $1/q$ chance of guessing the correct one.

Note: This proof involves a few corner cases in which the version of the Chaum–van Antwerpen scheme given in the Handbook of Applied Cryptography differs from that in Chaum and van Antwerpen's original paper.

First, Chaum and van Antwerpen explicitly require that $m \ne 1$.  This makes sense, since if $m = 1$, $s = m^k = 1$ regardless of $k$!  I assume this is most likely just an oversight in the Handbook, but it may be important if the message $m$ might be chosen by an adversary.

Second, the Handbook says that $a$ and $b$ should be chosen at random from $\{1,2, \dotsc, q-1\}$, whereas Chaum and van Antwerpen also allow $a = 0$ and $b = 0$.  Admittedly, these are somewhat peculiar cases — in particular, $a = 0$ implies that $c$ (and thus $r$, if Sally is honest) is independent of $s$ (and thus $m$)!  Even so, these cases don't actually present a weakness, since they each occur only with probability $1/q$, and, importantly, Sally can't tell when they occur.

In fact, excluding $a = 0$ and $b = 0$ means that, at least in principle, Sally can exclude two of the possible $(a,b)$ pairs (or one, if $c=1$).  Thus, the maximum probability of verifying an invalid signature may actually be as high as $1/(q-2)$.  Of course, for practical values of $q$, that makes no real difference.

Also note that, in practice, one would usually use the compact representation recommended by Chaum and van Antwerpen, in which $G$ is mapped to $\{1, 2, \dotsc, q\} \subset \mathbb Z_p^*$ by the map $f(x) = \min(x, p-x)$, and the map $f$ is reapplied after any sequence of arithmetic operations in $\mathbb Z_p^*$.  (This works because $p-1 \equiv -1 \bmod p$ is the generator of the order-2 subgroup of $\mathbb Z_p^*$.)  Not only is this representation more compact than naively storing elements of $G$, but it makes it easy to map arbitrary messages to elements of $G \setminus \{1\}$ and avoids issues with bogus signatures outside $G$.


Difference between SHVZK and HVZK? What is the difference between Special Honest Verifier Zero-Knowledge (SHVZK) and Honest Verifier Zero-Knowledge (HVZK)? Sometimes I see one term being used, other times the other. Do they mean the same thing?

Special Honest Verifier Zero-Knowledge is a particular case of Honest Verifier Zero-Knowledge; that is, if a protocol satisfies SHVZK, it satisfies HVZK. SHVZK has been introduced to simplify discussions about $\Sigma$-protocols. In $\Sigma$-protocols, HVZK is typically proven as follows: fix an arbitrary challenge $e$, and show that it is possible to efficiently generate a random transcript $(c, e', a)$ for a $\Sigma$-protocol, conditioned on $e = e'$. If such a simulator can be exhibited, then the $\Sigma$-protocol is clearly HVZK. The term SHVZK refers to $\Sigma$-protocols where this particular condition holds.
Note that similarly, the term special soundness is generally used to refer to a sufficient property for the soundness of a $\Sigma$-protocol (typically, that given two transcripts $(c,e,a)$ and $(c,e',a')$ for the same $c$, it is possible to extract a witness efficiently), which is typically satisfies by most $\Sigma$-protocols. Each time, "special XXX" simply means "a specific notion which is sufficient for XXX".


MAC size 128 bits or more? Just a quick question:
I've seen implemented BouncyCastle's class AeadParameters with MAC length of 128 bits, which was allegedly recommended.
Though when I looked up HMac to implement my own MAC in CBCBlockCipher, I found people using HMac with only SHA256, which results in MAC's length of only 32 bytes.

So what route should I take? Should I implement something like SHA512 to gain some MAC length?

It seems that this is just a misunderstanding between bits and bytes.  32 bytes is 256 bits, so 32 bytes is more than enough.

The security of HMAC is very strong; the security is directly related to the minimum of the key size and HMAC output size. So using 32 bytes / 256 bits as output size is fine. You could use fewer bytes for the authentication tag (using the leftmost bytes is the default), but it is recommended to keep to the default. Using SHA-512/256 might be a good idea for larger messages on 64 bit machines. SHA-224 could also be an option if you require a smaller authentication tag. For a newer protocol you could go with KMAC / SHA-3.

AEAD ciphers almost exclusively use the block cipher for the final calculation to produce the authentication tag. If AES or an AES finalist is used then the block size will be 128 bits - which means that 128 bit is the maximum authentication tag supported. You could go for a smaller authentication tag than 128 for real time protocols or protocols for embedded devices. In that case GCM is not recommended as there are security concerns if smaller tag sizes are used for that mode. CCM or EAX mode would make more sense for smaller authentication tags. These modes use CBC-MAC and CMAC respectively.

Note that the verification of an authentication tag should be performed using a constant time compare.