If I send a signed email, how does the end user get the public key? I am sending a signed email using Python and smtplib. I have successfully signed the email using this example: http://proj.badc.rl.ac.uk/svn/ndg-security/branches/Dependencies/m2crypto/doc/howto.smime.html

My question is how does the end user get the public key to check the signature? I have not seen any examples of attaching the public key to the same email. Thanks.

You can send the public key certificate as an attachment with the email or you can send the public key certificate in a separate email.

The main point is the end-user should receive the public key for verification.

A certificate can be a file e.g. *.cer . The end user needs to have a program to verify the document.

UPDATE:
Chances of an MIM attack or other attacks always exist. But having more than one form independent communication can help the situation along. E.g. send the key in soft form (usb/CD) with a courier service. Or talk to the person you send your public key to and ask them to open the key in a text editor and tally first and the last line of the key. Or use public key database/storage providers like PGP does.


Security of zero knowledge proof protocols When designing a protocol based on zero knowledge proofs, be it based on the discrete log problem, or on a Hamiltonian cycle in a graph, or something else, I assume there are security considerations, like there are security considerations in the use of conventional ciphers.

For example, when using AES (or any block cipher for that matter), one has to make sure that the IV is random, and a good block cipher mode is chosen.
When using RSA, one has to use a secure padding scheme, pick a high, but not too high exponent (0x10001, for example).

I wonder whether there exist this kind of considerations for several ZKP systems too; e.g., on how to generate a "good" graph for the Hamiltonian path problem.
I.e. I wonder how to make sure that Victor cannot gain Peggy's knowledge, using side channels, timing attacks, statistical attacks, or something alike? Has there been interesting publications to read upon this topic?

I will try to answer your question in three parts. Before I start, let me introduce a somewhat more formal notation to ease the explanation. In particular, let $L = \{x ~|~ \exists~w : (x,w) \in R\}$ be the NP language with associated witness relation $R$ and we will always assume that we have a proof system for that language.

Informally speaking, one proves that a particular proof system satisfies the zero-knowledge property by showing that when setting up the proof system in a special way (indistinguishable from the original setup) one can build an efficient simulator $\cal S$ which can produce proofs for statements in the language which are indistinguishable from real proofs output by the actual prover - but $\cal S$ runs without knowing a corresponding witness. Very roughly, this then shows that - under the assumption which was used to prove zero-knowledge - no information about the witness is contained in the proof.
It is important to note that a zero-knowledge proof only guarantees that the proof itself does not contain information about the witness. However, if $L$ is so that finding witnesses for statements in $L$ is easy, one can always directly compute the witness without looking at the proof at all. More precisely, the problem under which the zero-knowledge property of the used proof system is proven is not necessarily connected to the problem associated to finding a witness for some element in $L$. Speaking in terms of your example: "generating a good graph for the Hamiltonian graph problem" is something which is independent of the zero-knowledge proof system and only depends on your application.
To your question regarding other attacks: of course, the zero-knowledge property does not rule out attacks on the implementation level. For example, if the prover leaks something about the witness upon proof computation via some side channel, one might be able to find out something about the witness. For further reading, I would just recommend standard literature on side channel attacks (e.g., [1]). Alternatively you may also have a look at [2], who explicitly mention how they address implementation-level issues in the context of zero-knowledge proofs.

References

[1] Stefan Mangard, Elisabeth Oswald, Thomas Popp: Power analysis attacks - revealing the secrets of smart cards. Springer 2007, ISBN 978-0-387-30857-9, pp. I-XXIII, 1-337

[2] Endre Bangerter, Stefania Barzan, Stephan Krenn, Ahmad-Reza Sadeghi, Thomas Schneider, Joe-Kai Tsay: Bringing Zero-Knowledge Proofs of Knowledge to Practice. Security Protocols Workshop 2009: 51-62


Why SM2 ECC parameters does not specify cofactor h? Recently I've been studying the ECC with the Chinese SM2 standard. One question is on standard part 5, parameters definition, it only defines $p, a, b, n, XG,$ and $YG$, but not cofactor $h$.

I found some useful discussion introducing all the parameters mathematics behind: What is the relationship between p, n, and h.It doesn't answer my question: Why SM2 does not specify h, while Key Exchange Agreement Protocol introduce in SM2 part 3 has used it.

On the standard part 1, section 5.2.2, it provides a method to verify Elliptic Curve Parameters. One option process uses to verify $h$ is:

(optional) Calculate $h'=\lfloor((p^{1/2} + 1) ^ 2)/n\rfloor$, and verify $h=h'$

This also means h can be calculated by the equation above. I calculate with an online big number calculator, the result is slightly greater than 1 (not fully equal).

Or have I misunderstood this cofactor? It is calculated instead. Elliptic curve can be perfectly defined only with $p, a, b, n, XG$, and $YG$.

Elliptic curve can be perfectly defined only with $p, a, b, n, XG$, and $YG$.

Yes, indeed even though it's not the nicest / most convenient set of parameters, this is sufficient to recover the curve order (using Schoof's algorithm) and with that the co-factor.

Of course Schoof's algorithm, while efficient, isn't exactly fast nor widely implemented and therefore usually the curve order and co-factor are supplied.

  Why SM2 does not specify h, while Key Exchange Agreement Protocol
  introduce in SM2 part 3 has used it.

Well, the quality of the linked IETF draft isn't the best, so maybe it was just an oversight.

To answer your question: $h=1$.
This can be verified using the following sage-math instructions:

F=GF(0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF)
a=0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC
b=0x28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93
n=0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
E=EllipticCurve(F,[a,b])
h=E.cardinality_pari()/n;h

where the last one should return the co-factor $h$ as being $1$.

  I calculate with an online big number calculator, the result is
  slightly greater than 1 (not fully equal).

This formula comes from the Hasse-bound (with $q$ being the curve and $p$ being the field order) $$\left|q-(p+1)\right|\leq 2\sqrt p$$ which assuming $q\geq p+1$ is
\begin{align}
&&q-(p+1)&\leq 2\sqrt p\\
\iff&& q&\leq p+2\sqrt p +1=(\sqrt p +1)^2\\
\iff&& h=q/n&\leq (\sqrt p +1)^2/n
\end{align}
If the last value is barely over $1$, this means that $h$ can only be $1$.


Why GCM operation mode with AES-128 is recomended and can we use AES-192 and AES-256 with GCM? It happens that on the internet I often find that AES encryption should use a 128-bit key only if it is used in conjunction with the GCM mode of operation.

Why only with 128-bit keys?

What happens if I use one of 192 or 256?

Can it be? Why is this recommendation made?

AES can be used with 128,192, and 256-bit key sizes and always with 128-bit block size †.

In NIST 800-38d, GCM is defined for 128-bit block size, since it is operating on block size and doesn't mandate about the key size.

  This Recommendation specifies an algorithm called Galois/Counter Mode (GCM) for
  authenticated encryption with associated data. GCM is constructed from an approved symmetric key block cipher with a block size of 128 bits, such as the Advanced Encryption Standard (AES) algorithm that is specified in Federal Information Processing Standard (FIPS) Pub. 197

In rfc5288 these modes are defined for TLS 1.2

  The following cipher suites use the new authenticated encryption
     modes defined in TLS 1.2 with AES in Galois Counter Mode (GCM)

CipherSuite TLS_RSA_WITH_AES_128_GCM_SHA256 = {0x00,0x9C}
CipherSuite TLS_RSA_WITH_AES_256_GCM_SHA384 = {0x00,0x9D}
CipherSuite TLS_DHE_RSA_WITH_AES_128_GCM_SHA256 = {0x00,0x9E}
CipherSuite TLS_DHE_RSA_WITH_AES_256_GCM_SHA384 = {0x00,0x9F}
CipherSuite TLS_DH_RSA_WITH_AES_128_GCM_SHA256 = {0x00,0xA0}
CipherSuite TLS_DH_RSA_WITH_AES_256_GCM_SHA384 = {0x00,0xA1}
CipherSuite TLS_DHE_DSS_WITH_AES_128_GCM_SHA256 = {0x00,0xA2}
CipherSuite TLS_DHE_DSS_WITH_AES_256_GCM_SHA384 = {0x00,0xA3}
CipherSuite TLS_DH_DSS_WITH_AES_128_GCM_SHA256 = {0x00,0xA4}
CipherSuite TLS_DH_DSS_WITH_AES_256_GCM_SHA384 = {0x00,0xA5}
CipherSuite TLS_DH_anon_WITH_AES_128_GCM_SHA256 = {0x00,0xA6}
CipherSuite TLS_DH_anon_WITH_AES_256_GCM_SHA384 = {0x00,0xA7}

and for TLS 1.3

TLS_AES_256_GCM_SHA384
TLS_CHACHA20_POLY1305_SHA256
TLS_AES_128_GCM_SHA256
TLS_AES_128_CCM_8_SHA256
TLS_AES_128_CCM_SHA256

  Can it be?

Yes, see above.

  although AES-256-GCM is available, it is costly from the computational point of view at this time and should be used with other practices and methods to ensure greater security and privacy.

AES-256 is only 40% slower compared to AES-128. New CPU's from INTEL also includes instructions for GCM mode. If you are targetting post-quantum cryptography or fear of multi-target attacks on any 128-bit key sized block cipher you should use 256 bit key. Otherwise, 128 bit is fine [1],[2].

  Why is this recommendation made?

Anybody can make recommendations. It is up to you to listen to them. Some already migrated to 256.

As commented by Swashbuckler, Department of Homeland Security, in section 5.1 of DHS Sensitive Systems Policy Directive 4300A Version 13.1
July 27, 2017 mandates 256-bit key size for block ciphers.

  Systems requiring encryption comply with the following methods:

  Products using FIPS 197 Advanced Encryption Standard (AES)
  algorithms with at least 256 bit encryption that has been validated
  under FIPS 140-2
  National Security Agency (NSA) Type 2 or Type 1 encryption

If you want to sell a product that contains AES to them you need to use 256-bit.

† Don't confuse AES with the Rijndael. From Wikipedia's footnotes;

Key sizes of 128, 160, 192, 224, and 256 bits are supported by the Rijndael algorithm, but only the 128, 192, and 256-bit key sizes are specified in the AES standard.
Block sizes of 128, 160, 192, 224, and 256 bits are supported by the Rijndael algorithm for each key size, but only the 128-bit block size is specified in the AES standard.


Which crytographic libraries to use for Elliptic Curve Cryptography and Bilinear Pairing? I'm currently trying to implement a solution for Vehicular ad hoc networks based on cryptography. I choose to use python to implement the solution, but I don't know which libraries I have to use to implement the cryptographic functions (methods and modules). I searched about it but I didn't find good ones most of the libraries I've found where about implementing Cipher algorithms and hash functions. I need libraries for Elliptic curve cryptography and Bilinear pairing. Please, suggest me good libraries that have good methods.
PS: I'm using Python3.8 and Ubuntu os and these are the solutions that I'm working on https://www.cs.nmsu.edu/~misra/papers/T-ITS-2011.pdf and https://www.mdpi.com/2073-8994/12/10/1687/htm

you can use pbc library (The Pairing-Based Cryptography Library).
https://crypto.stanford.edu/pbc/


Digital Signature Scheme Count My question is How I will be able to count digital signature Scheme that can sign many documents with one private key. There are signature scheme as long as exists private keys in the keys spaces? or There are signature scheme as long as exists methods than RSA, DSA, ECDSA, Hash-Based signature schemes, etc? I am doing this question because I want understand

this paragraph of my lecture

  Hash-based digital signature schemes which are presented in this
  chapter oﬀer a very interesting alternative. Like any other digital
  signature scheme, hash-based digital signature schemes use a
  cryptographic hash function. Their security relies on the collision
  resistance of that hash function. In fact, we will present hash-based
  digital signature schemes that are secure if and only if the
  underlying hash function is collision resistant. The existence of
  collision resistant hash functions can be viewed as a minimum
  requirement for the existence of a digital signature scheme that can
  sign many documents with one private key. That signature scheme maps
  documents (arbitrarily long bit strings) to digital signatures (bit
  strings of ﬁxed length). This shows that digital signature algorithms
  are in fact hash functions. Those hash functions must be collision
  resistant: if it were possible to construct two documents with the
  same digital signature, the signature scheme could no longer be
  considered secure. This argument shows that there exist hash-based
  digital signature schemes as long as there exists any digital
  signature scheme that can sign multiple documents using one private
  key

I suppose this is a terminology question. "A digital signature scheme which can sign many documents with one private key" means something like this:

There are some sets $M$ (the "message space", often the set of bitstrings of any length, or some useful subset thereof), $K_{pub}$, $K_{priv}$ (the public and private "key spaces") and $S$ (the signature space).
There is a tuple of (probabilistic and efficiently computable) functions $(g, s, v)$.
$g : \varnothing \to K_{pub} \times K_{priv}$ ($g$ generates a random key pair).
$s : M \times K_{priv} \to S$ ($s$ signs a message, i.e. generates a signature from the private key and message)
$v : M \times K_{pub} \times S \to \{\mathsf{true}, \mathsf{false}\}$ ($v$ verifies a signature)
If $(y, x) = g()$ and $m \in M$, then $v(m, y, s(m, x)) = \mathsf{true}$ (or at least with overwhelming probability).

Normally we also want that the scheme is secure, which then adds some more properties:

Given $y$ (the public key) and a message $m$, without knowledge of $x$ it is hard to create a $\sigma \in S$ such that $v(m, y, \sigma) = \mathsf{true}$, even if some (or even many) other $(m', \sigma')$ are known, or even signatures to other messages can be requested. (This is known as "universal forgery".)
It should even be hard to create any message $m \in M$ and $\sigma \in S$ such that $v(m, y, \sigma) = \mathsf{true}$ (other than the $m'$s which were given/queried as examples). (This is known as "existential forgery".)

(There are also variants of this definition where the number of documents which can be signed with each key before the security gets lost is limited, but these obviously are not "signature schemes which can sign many documents with one key".)

Usually there also is some formalization of "hard", often with a security parameter.

Similarly, we have the term of "hash function", something like that:

There is a message space $M$ (usually the set of bitstrings of any length, or some useful subset thereof) and a hash space $H$ (usually the set of bitstrings of some fixed length).
There is a function $h : M \to H$.

The "collision resistance" property then is something like

It is hard to find $m_1, m_2 \in M$ with $h(m_1) = h(m_2)$.

The "there exists a digital signature scheme which ..." in the quoted lecture extract supposedly means as much as "there exists a secure signature scheme which ...".

We already know that there are signature schemes (RSA, DSA, ECDSA, ...), but it is not proven if they are actually secure. (We sure hope so, and nobody did break them publicly yet, but it might not actually be possible to prove anything, or it might be that there is no secure signature scheme at all.)

We also don't know if there exist any actually collision-resistant hash function. We have some candidates (like SHA-2), and some previous candidates which proved to actually be not collision resistant (MD4, MD5).

The argument then is:

If there is any secure signature scheme (for multiple documents with each key), then there has to be a collision-resistant hash function.

(The idea is that you actually can use the signature scheme as a hash function by using a fixed key, and the signature scheme is not secure if you can find two messages with the same signature (i.e. a hash collision). I think this doesn't actually follow from my security properties mentioned above, so maybe your lecture used some other security definition.)
Also there will be shown (in the following paragraphs/pages of your text) that from any collision-resistant hash function you can build a secure hash-based signature scheme.
So it follows: If there is any secure signature scheme (which can sign many messages) at all, then there is a secure hash based signature scheme.


When was hash chain first used? Hash linking is used to prove the integrity of a blockchain, or similar systems. When was that technique first used? I would guess it was early, maybe 1950s/1960s?

Lamport suggested the use of hash chaining in 1981 in Password Authentication with Insecure Communication, Communications of the ACM 24.11 (November 1981), pp 770-772.

He cites 3 prior papers:

Diffie, W., and Hellman, M.E. New directions in cryptography.
IEEE Trans. Inform. Theory 1T-22 (Nov. 1976), 644-654.
Evans, A., Kantrowitz, W., and Weiss, E. A user authentication
scheme not requiring secrecy in the computer. Comm. A CM 17, 8
(Aug. 1974), 437-442.
Wilkes, M.V. Time-Sharing Computer Systems. American
Elsevier, New York, 1972.

[1] is the paper which essentially invented Public Key Cryptography in the open literature. Lamport refers to the use of a one way function F, as described there, as hash functions in his chain.

[2] and [3] are cited for "the widespread use of such a function", e.g., storing $y=F(x)$ instead of $x$.

So it seems to me Lamport may well be the first to suggest the use hash chaining.

Edit: Thanks to @Gilles for pointing out Merkle patented hash trees in 1979.


Is prime order group used in ECDSA unique? In ECDSA, we use a prime order group $\langle G\rangle$ for cryptographical use. Assume $\#\langle G\rangle = p$. Is there another subgroup in the curve used for ECDSA whose order is also $p$?

This question has two faces;

The number of rational points of the used curve is prime like secp256r1, i.e. $\#C(K) = p$ where $K$ is the field where curve $C$ is defined;
In the group theory, let $G$ be a finite group and $H$ be a subgroup of $G$.
Then the order of $H$ must divide the order of $G$. This the Lagrange's Theorem in group theory. More formally;

Lagrange's theorem - If $H$ is a subgroup of a group $G$, then ${\displaystyle \left|G\right|=\left[G:H\right]\cdot \left|H\right|.}$

Below a corollary to the Lagrange theorem;

If the order of the group is prime then there are no subgroups other than the trivial subgroups.

Therefore, an order $p$ group has no subgroups other than the trivial subgroups which are the identity group and the group itself.

The number of the rational points of the used curve is not a prime,  $\#C(K) = n$;
This really depends on the group. The Lagrange theorem doesn't guarantee the existence of the subgroups if an integer divides the order of the group.
Consider the Curve25519 which has a prime order subgroup $n$ and the co-factor is $h=8$ ( $h = \#E(\mathbb{F}_p)/n$) then we have the subgroup of order $2,4,8,n,2n,4n,8n$, i.e. we have all possible subgroups.
You can find a group that has two prime subgroups of order $p$ the if there are no other subgroups the curve group will be isomorphic to $\mathbb{Z}_p \oplus \mathbb{Z}_p$. Is this possible in Elliptic Curves?
I haven't seen an example in secure elliptic curves. The reason is simple; we want a large prime subgroup order that is close to the curve order in order to effectively use the curve. If there are two different subgroups of order $p$ then the curve order will be $\geq p^2$. This means you are wasting your computations.

More into theory (4.1 is in the second edition of Washington's Book);

Theorem 4.1: Let $E$ ben elliptic curve group over the finite field $\mathbb{F_q}$. Then $$E(\mathbb{F_q}) \simeq \mathbb{Z_n}
> \text{ or } \mathbb{Z_{n_1}} \oplus \mathbb{Z_{n_2}}$$ for some
integer $n \geq 1$, or for some integers $n_1,n_2 \geq 1$ with
$n_1|n_2$.

If the $E(\mathbb{F_q})$ falls into the first case implies that the subgroup order $r$ must divide $r|n$. But the subgroups of $\mathbb{Z})_n$ are unique. Therefore there cannot be two subgroups that have the same order.
The second case is more interesting [1] [2] [3] since it is a direct product of groups. Since $n_1\mid n_2$ there is a subgroup of $H$ of  $\mathbb{Z_{n_2}}$ such that it is isomorphic to $\mathbb{Z_{n_1}}$. Now we have two subgroups of the same order $\Bbb Z_{n_1} \oplus \{0 \}$ and $\{0\} \oplus H$.
As said before we don't prefer curves that can have two different subgroups of order large prime.


How to measure ECC key size? I have implemented a ECC key generation scheme successfully. Now I need to find ECC key sizes of each generating key pairs. I assumed that ECC key size is the size of the ECC private Key.

So I would like to to know whether this is correct?

The size we speak of with regard to elliptic curves is the size of the field over which the elliptic curve is defined. This is not necessarily exactly the size of the private key.

For example: Curve25519 is a 255-bit elliptic curve and has, effectively, 252-bit private keys, though they are usually encoded as 256-bit values with four fixed bits. Public keys are 256-bit values, but only contain 255 bits of information since the last bit is always 0.


A doubt about Diffie-Hellman Key Exchange I have a doubt about the Diffie-Hellman problem:

Is it possible to send a message to someone using only the Diffie–Hellman key exchange?

Since it's called a key exchange can you only make a key?

What exactly do you doubt about the CDH or DDH problems?

  Is it possible to send a message to someone using only the Diffie–Hellman key exchange?

You cannot "send" a message using DHKE but you may use its resulting shared secret as a one-time-pad (by multiplication; not XOR) to "encrypt" a message encoded as a group element. When the sender uses a unique key per message, this is called ElGamal.

To encrypt a larger message we'll step back to Diffie-Hellman and use the hash of its shared secret as our key for a symmetric stream cipher. This is called hybrid encryption.

However neither scheme above authenticates our messages, thus an active adversary may tamper with our messages and depending on our application may recover our messages. Along the symmetric route we just need to replace encryption with authenticated encryption.

Instead of reinventing the wheel, this function is known to libsodium as crypto_seal_box. If you want to send many messages, you may prefer one handshake per session and use streams.

You probably don't want to use a single DHKE, but perhaps two or three. Two if you need forward secrecy and three if you want forward secrecy and mutual authentication. The Noise protocol elaborates on many variations and Signal uses an extension of triple-DH. All of these options require the receiver to send the sender at least one message per handshake.


Struggling to understand CFB mode (with DES) I'm really struggling to understand CFB mode (with DES if that matters). I realise after searching around here that these modes are now obsolete but I need to understand them for class. From wikipedia, I see that for encryption:
$$C_i = P_i[:s] \oplus E_k(S_i)[:s]$$
$$S_0 = IV$$
$$S_i = (S_{i-1} << s) | C_i$$
(I'm using a python like notation so [:s] means first $s$ bits).

I'm already having trouble understanding this encryption scheme and how error propagates through. Wikipedia says that if an $C_i$ becomes corrupted then the encryption will eventually recover. I tried reading discussions about this here but I'm failing to see this (I am hoping for a more elaborate explanation).

Let's say $s=4$ bits, $IV$ is 64 bits and that $C_2$ becomes corrupted such that we correctly computed $C_1$ and $C_2$ from $P_1$ and $P_2$ but we can not correctly calculate $C_3'$ since $$C_3 = P_3[:4]\oplus E_k((IV << 8) | C_1 | C_2')[:4]$$
and so $E_k((IV << 8) | C_1 | C_2')$ gives an incorrect encryption and therefore an incorrect $C_3$ which I denoted as $C_3'$. If I continue this pattern, it seems that I always get an incorrect $C_i$ since the shift register will always be wrong. e.g consider

$$C_{17}' =^{?} P_{17}[:4]\oplus E_k((IV << 64)|C_1|C_2'|C_3'|...|C_{16'})$$

$$ = P_{17}[:4]\oplus E_k(C_1|C_2'|C_3'|...|C_{16}')[:4]$$

but this still gives the wrong value so I'm not sure why the system recovers. What am I misunderstanding?

and so $E_k((IV << 8) | C_1 | C_2')$ gives an incorrect encryption

That's your issue; CFB isn't designed to correct for errors in the plaintext - after all, if the ciphertext is not modified, then the decryptor will get precisely what the encryptor encrypted and so if the original plaintext had an error, and then was correct, what the decryptor will get will have that exact same error, and then be correct.

Instead, what CFB is concerned about is if the ciphertext is modified.  As long as $C_3'$ remains in the shift register, yes, the decryptor will get gibberish.  However, after 16 shifts (8 bytes), $C_3'$ will fall out of the shift register.  Then, the 8 bytes will be precisely what the encryptor had intended, and so it will start to decrypt properly (and it will stay so as long as long as no further errors in the ciphertext occur).

Of course, CFB's claim to fame is not that it can adjust to bit flips in the ciphertext (after all, CBC has that same property, and OFB is even better); what CFB does in addition is handle it if segments aren't received at all.  For example, suppose if $C_3$ wasn't received in error, but not received at all; that is, the decryptor received $C_1, C_2, C_4, C_5, C_6,...$.  With CFB, the next 8 bytes will be decrypted incorrectly, however after that, the shift register will resync, and everything later will be decrypted normally.  This is in contrast to CBC, where if a 4 bit chunk was dropped, it would never resync (because everything is processed in 64 bit chunks, and those chunks wouldn't line up anymore).

If you're wondering what could cause such an error, well, way back in the day, there really were communication channels (RS-232, for example) where you could add or drop individual bytes.  Doing CFB over such a line would give a usable encrypted channel, even when that happened.

Of course, nowadays, we're not concerned about recovering about such add/drop errors, and considerably more concerned about attackers who can intentionally cause such errors (and try to gain an advantage for doing so); hence the fashion today is to place sequences of plaintext bytes into records, and perform an authenticated encryption of those records.  Hence, the advantages of CFB aren't seen as an advantage today...


Send a message to an entire group of recipients I'm attempting to send a message to a group of recipients, through an untrusted intermediary.

Each of the recipients will have been invited to the group by someone who already has a trusted public key from them.

The best solution I've come up with so far is that a shared secret is created by the first member of the group, and that is sent encrypted to each of the future recipients by whoever invited them. All messages addressed to the group will be encrypted with the shared secret.

Are there any major flaws with this approach? Is there a better, more well known approach?

One of the major flaw in this approach is that you wont have the option to remove a member from the group. If you want to you will have to send a new shared secret to each of the other members which is not very scalable if the group is large or the number of people leaving the group is large.

There are a lot of ways to accomplish broadcast key distribution,
One of the methods is Logical Key Hierarchy (LKH). The basic idea of this scheme is arrange members at leaves of a key tree, each member receives keys on its path. In this scheme both entry and exit of members has low computation and communication overhead.


"Padless" One-time-Pad encryption I have just read about the perfect security of an OTP encryption and what came to my mind was that what if the Pad used for encryption/decryption did not have to be transported separately from the message, but instead together with it?

And what if it was computed using an algorithm from the message itself (from all the characters in an 1:1 way so that it had the same size) providing a random-looking pad for encrypting the message, and after encrypting the message would be stored in an interwoven way in the message itself, expanding the file size by a factor of 2. The encrypted file itself would have double size of the original one but no-one would be able to find out what is the message and what is the key since it would be interwoven using a secret algorithm, perhaps the same one as was used for generating the pad.

Would this be a good encryption comparable to real OTP with the pad transferred and generated separately? Did I just invent the wheel, or is this a breakthrough thing (I mean storing the pad inside the file in a secret way preventing others to extract it)?

I know calculating the pad from the message itself would perhaps break the real randomness so this could be avoided and the pad simply taken from a real random key number generator.

Your "secret algorithm" is now effectively the key.

If the algorithm stays fixed for all messages, you now no longer have a one-time pad. So let's make your algorithm be tweakable by, say, accepting as input a string that describes its exact operation. Now we have the benefit of being able to publicize the "secret algorithm", since the actual secret details are contained in this input string. Except now that input string is the key, and now you have to find a way to transmit it... which is the problem you were trying to solve in the first place.


Swapping Key and IV in AES? Safe? I have an application where I want to be able to send an encrypted file, and then mete out "keys" that allow the receipient to decrypt the file from a certain point to the end of the file. Actually, it's from a certain point to the beginning, and I'm doing the above by reversing the file.

Looking at AES (and thus Rijandel) and all of the available block modes, it needs the key to decrypt every block, and so releasing this would allow the receipient to decrypt the entire file. Not useable.

However, if I was to make the Key public, much like the IV or a Salt is usually public, and instead mete out the IV necessary to decrypt block N through the end, then that would give me the functionality I need, since theoretically the IV in a mid-stream block does not let you derive the IV for previous blocks, but only subsequent blocks.

So, the question is, how less secure is AES if I switch the Key and IV around as inputs to the block cipher?

For all standard modes, AES isn't secure at all if you reveal the key; even if you keep the IV hidden.

Exactly how this works out varies between modes; for CBC mode, the attacker will be able to decrypt the entire text except for the first block (well, last block because of your reversing the file), even if you didn't give him an IV.  The same goes for CFB mode.

As for OFB and CTR modes, the 'IV update' function is reversible and independent of the message; hence revealing any intermediate IV will allow the attacker to decrypt the entire message.

What you want is unusual (at least, I never heard of the requirement before), and it's not surprising the existing modes can't handle it.

One idea which might work out is a varient of OFB mode using SHA-256 (for example), that is:

$IV_{i} = SHA256(IV_{i-1})$

$C_i = P_i \oplus upper128(IV_i)$

where $P_i$, $C_i$ are the i-th plaintext and ciphertext blocks (128 bits), and $upper128$ extracts 128 bits of its input.

The idea is:

The IV update function is noninvertible, hence the attacker does not have immediate access to previous states
Even if the attacker has a guess for the previous plaintext block, he cannot validate it.  That is, if he is given $IV_i$, knows $C_{i-1}$ and has a guess for $P_{i-1}$, he can't determine if his guess is correct; that guess tells him what 128 bits of $IV_{i-1}$ would be, but $IV_{i-1}$ has 128 bits he isn't given, and that's too much to search over).

Now, this is nonstandard, nonvetted and slow compared to AES-based transforms.  However, it might address the problem you're looking at.


Cipher for Product Registration? I'd like to implement a "Product Registration" scheme into my software where upon initial use, the User must enter a key to unlock it.

The key they enter is compared to their encrypted Username.
They would have to acquire the key from myself if they wished to use the software.
Their encrypted Username must be reasonably short so it's not too difficult for them to enter the key. They would however, only have to enter the key once.
(I'm aware this isn't actually how keys are issued)

What kind of encryption is appropriate for this?
(It needs to encrypt a string into letters and numbers only and be reasonably short).
There's no thought needed over decryption, since I'll only be comparing encrypted strings.

I'm basically looking for a cipher that produces the shortest code possible so that it's not tedious for the User to enter.
(Though still difficult to break)

Any suggestions?
Thanks!

(You needn't worry over the actual security.
I'm a noob programmer and all my software is free anyway)

Since no-one else has mentioned this yet, I guess I should point out that it is possible to use public key signature schemes like (EC)DSA to generate software registration keys.  For example, Microsoft apparently uses this for their product keys.

Basically, you embed the public key in your program and keep the private key, which you'll use to sign whatever information you want to tie the activation code to; this could be just a fixed string, but it could also include things like the name of the user or information about the computer they're using, depending on what kind of registration system you want.

The problem, as you correctly suggest in your post, is choosing a signature length long enough to be reasonably secure while short enough for users to type in.  If you could have your users type in 64 random characters (out of a repertoire of 32 each), you'd be fine with a total signature length of 320 bits — but in practice, even 30 characters is a nuisance to type.  Of course, if you're doing the registration online, you could just give the user a block of text to copy and paste.

Anyway, if your software is free anyway and you don't care about security, much simpler schemes (like woliveirajr's suggestion) will do just as well.  But if that's the case, why make your users go through the nuisance of registration in the first place?


The use of Elliptic Curves as part of a blockchain transaction As I understand it, Elliptic-Curve Cryptography is used in the verification step of a transaction (i.e. when creating a digital signature), but not in the creation and security of a 'block' (when assigning a nonce to a hash value with a set number of zeros). Why do we use ECC when validating the initial transaction request, and not when validating the block? Or to flip that around, why not just use Cryptographic hashing in the validating transaction step (and not use ECC at all)? I know hashing is used on the message component during the validating transaction request, so why not use it again for the whole digital signature?

My understanding of blockchain is limited, so upfront apologies for any unclear language!

If you're asking why don't we use a simple hash to authenticate, well, that doesn't actually provide any authentication (as anyone can compute that hash).

On the other hand, there are signature algorithms based on hash functions (oddly enough, called hashed-based signatures) which rely on the preimage resistance (or collision resistance) of a hash function.  They would appear to be ideal for block chains, except that they do have these drawbacks:

These signatures are significantly larger than ECDSA signatures; we might be talking on the order of 1kbyte rather than 64 bytes for what bitcoin is currently using.
There are practical drawbacks; in the simplest case ("one time hash based signatures") a public key can safely sign only one message.  On the other hand, this might be an acceptable limitation in the bitcoin case; everytime we sign a transaction, we'd generate a fresh public/private key pair, and include the public key in with the transaction we're signing (and use the new private key the next time).  There are other schemes that lessen this restriction (in case this approach turns out not to be feasible).

I suspect reason #1 is the main reason why bitcoin hasn't transitioned to this approach


Self-shrinking generator A self-shrinking generator is a LFSR sequence processed with an algorithm that is different from von Neumann unbiasing. Does this imply that using von Neumann unbiasing instead would lead to an inferior result of security?

[This incomplete answer is a community wiki; fell free to expand/correct it]

The self-shrinking generator, and von Neumann de-biasing applied to the output of an LFSR, both group bits output by the LFSR in pairs, and for each pair output either nothing or a single bit, according to this table:

Pair    SSG    VN
 00      -     -
 01      -     0
 10      0     1
 11      1     -

We hereafter assume the LFSR has $n$ bits and is maximum-length (that is, uses a primitive polynomial and is not initialized to all-zero).

The LFSR has period $2^n-1$, and within that each of the pairs 01, 10, and 11 appears exactly $2^{n-2}$ times, while the pair 00 appears $2^{n-2}-1$ times. If follows that in $2^{n+1}-2$ steps of the LFSR, both the SSG and VN output exactly $2^{n-2}$ times 0 and as many times 1, and cycle.

Thus both the SSG and VN cycle after (at most) $2^{n-1}$ outputs, and have no bias. For $n>3$, the shortest period conjecturally is $2^{n-1}$ (that conjecture was made for the SSG by Willi Meier and Othmar Staffelbach's The self-shrinking generator, in proceedings of Eurocrypt 1994; they give proof that the shortest period is at least $2^{\left\lfloor n/2\right\rfloor}$).

Illustration with 2 periods of 31 steps of the LFSR based on $x^5+x^2+1$: both SSG and VN have period 16, with 8 zeroes and 8 ones.

LFSR 10101110110001111100110100100001010111011000111110011010010000
SSG   0 0 1 0 1     1 1   1     0         1   0   1 1 0   0 0
VN    1 1   1     0         0   1   0 0 0   0 1       1 0 1 1 0


Can a homomorphic encryption scheme be made CCA2 Secure? Is it possible to modify a homomorphic encryption scheme so that it can be CCA2 secure?
From the definition of a homomorphic scheme, it seems that it is malleable, which would result in lack of CCA2 security. So, if we use the regular method to convert a CPA secure scheme to CCA2 secure scheme (using a hash of the message and a random value), will it still preserve its homomorphic property?
Please correct me if my understanding is wrong.

The best you can get for homomorphic encryption schemes is non-adaptive chosen ciphertext security (IND-CCA1 security), see e.g. here for a quite up to date characterization.

As you rightly observe homomorphic encryption schemes are malleable by definition and cannot provide adaptive security against chosen ciphertext attacks (be IND-CCA2 secure).

Since in the IND-CCA2 security game the adversary knows the relationship between both messages for the challenge ciphertext, the adversary can obtain another ciphertext to a chosen plaintext and operate on the challenge ciphertext and the newly obtained ciphertext and then submitting the resulting ciphertext to the decryption oracle. This does not violate the conditions of the IND-CCA2 game (the adversary is only restricted to not submit the challenge ciphertext directly to the decryption oracle). Consequently, the adversary can determine which plaintext is hidden in the challenge ciphertext.

The reason why IND-CCA1 security can however still be achieved for homomorphic encryption schemes is that in the IND-CCA1 game the adversary after having obtained the challenge ciphertext no longer has access to a decryption oracle (and thus eliminating the aforementioned strategy).

Concluding, every compiler/transform (like Fujisaki-Okamoto or Naor-Yung double encryption) that takes a less secure scheme (IND-CPA) and converts it into an IND-CCA2 secure scheme destroys the homomorphic property of the original scheme.


Does the server signs message body after ssl handshake? So after SSL handshake the master secret is used to securely transfer data encrypted using symmetric cryptography. My question is simple: after SSL handshake, when the server (for example my bank) sends to me message encrypted symmetrically, is the message body (when my computer decrypts it) signed by server's public key or not?

SECOND QUESTION: If answer to question 1 is yes, then if I would receive some data (for example my bank statement) from the server, could I present this data signed by trusted server's key (bank's key) to some third party to prove that this data originated from particular company (because it's signed by asymmetric key that this company is using)?

THIRD QUESTION: If answer to question 1 is yes, then does the message (when decrypted symmetrically) received from server (after handshake) contains timestamp which could be used to prove, in the way similar to one presented in QUESTION 2, that this message originated at this-and-this time (for example a week ago)?

..., is the message body (when my computer decrypts it) signed by server's public key or not?

It's not signed. The "message body" (i.e. application data) is only protected by a HMAC. This HMAC relies on a shared secret known both to client and server created together with the encryption key based on the pre-master secret generated during the key exchange. Given that client and server have both the same key for encryption and the sane secret for HMAC the client might create any encrypted application data itself. This means it is impossible for some third party to figure out if the application data in some packet capture originated from the server or was faked by the client.


Equality check in homomorphic encryption Considering that we have a homomorphic encryption server working with integers mod p (a large prime number) with access to multiplication, addition and subtraction, is it possible to design an equality function which receives two encrypted values and returns an encrypted 1 if they are equal and an encrypted 0 if they are different?

This is obviously assuming randomized encryption, so direct comparison of the ciphertexts would be impossible.

Depends on what you mean "returns 1 if there are equal".

If you mean "returns an encrypted 1 if there are equal, and 0 if there are not", then here's one straight-forward way; to compare the values $A$ and $B$, you just compute the encrypted value $1 - (A - B)^{p-1}$; that is an encrypted 1 if $A = B$ (because $A - B = 0$), and an encrypted 0 if $A \ne B$ (Fermat's Little Theorem). This takes $O(\log p)$ homomorphic multiplications, and two homomorphic subtractions.

On the other hand, if you mean "returns the value 1", and so allows someone without the private key whether two values are the same, we hope that's not possible.  That would be a violation of the security of the system; it would allow an adversary to determine the value of encrypted plaintexts, and so if it were possible, the homomorphic system would be insecure.


Exactly how bad is using 'mod' to clamp reduce numbers to a given range? Let's say I'm naive and want to generate a random integer in the range [0, m), so I do the following:

k = cryptographically_secure_rng() % m

where cryptographically_secure_rng returns a random integer in the range [0,n).
Obviously, assume m <= n.
Now in general k isn't distributed uniformly anymore.

It seems to me that for any reasonably nontrivial value of m and n, this can't possibly cut the attacker's time by more than half -- and in general, it would seem to cut it by a much smaller fraction.
Yet my impression from security/crypto is that such a naive RNG would be catastrophic for the security of the system.

So my question is:
How bad is this from the standpoint of an attacker trying to attack a system by exploiting this function?

Could such a bias be abused and amplified (e.g. exponentially) to attack a system?
If so, in what kind of a system might this occur, and how?
If not, then is the problem worth worrying about, and why?

The answer is that it depends on how much larger $n$ is than $m$, and also depends on the application. If $n$ is much larger than $m$ (say 64-128 bits longer) then you are fine, as pointed out by @Ricky Demer. However, otherwise, you will have bits that have a bias.

If you are using this key in HMAC, then it doesn't matter. However, in general, it can matter and can matter a lot. Thus, I strongly recommend against doing this without making $n$ at least 64-128 bits longer than $m$. If you want to see a work where small biases are used to recover plaintext, then Analysing and Exploiting the Mantin Biases in RC4 is a good place to start.


What is the difference between discrete logarithm and natural logarithm? Why we take (base $e$) and (base 2) in natural and discrete logarithm, respectively?
I do not understand the difference between these two concepts.

I will assume you understand modulo operation and the exponentiation.

First let's consider logarithm in $\mathbb{R}$.

You know that if we have $e^x = y$ then $x = \ln y$. The Napierian logarithm return values in $\mathbb{R}$.
You can have the same thing with another base. For example : $2^3 = 8$ and $\log_2 8 = 3$.

The simplified idea of the discrete logarithm is to return only the Integers ($\mathbb{Z}$).

In $\mathbb{R}$, we have $\log_2 5 = 2.321\ldots$. This is not interesting for us. Hard to manipulate... How does this translate into a Integer ?

Lets consider consider the integers where all numbers have to be below a certain prime number $p = 11$.
Lets also consider the only allowed operation is the multiplication : $\times$.

Therefore we have :
$3 \times 4 = 12 \equiv 1 \pmod{11}$
And so on.

This kind of structure is called a group of multiplication modulo the prime p. Its notation is the following $\mathbb{Z}_p^\times$. In this case we have $\mathbb{Z}_{11}^\times$

Let's consider $g=2$ and apply the exponent ($g^n = g \times  \ldots \times g$) :
$2^0 \equiv 1$
$2^1 \equiv 2$
$2^2 \equiv 4$
$2^3 \equiv 8$
$2^4 \equiv 2\times 2^3 \equiv 2 \times 8 \equiv 16 \equiv 5 \pmod{11}$
$2^5 \equiv 2\times 2^4 \equiv 10 \pmod{11}$
$2^6 \equiv 2\times 2^5 \equiv 9 \pmod{11}$
$2^7 \equiv 2\times 2^6 \equiv 7 \pmod{11}$
$2^8 \equiv 2\times 2^7 \equiv 3 \pmod{11}$
$2^9 \equiv 2\times 2^8 \equiv 6 \pmod{11}$
$2^{10} \equiv 1 \pmod{11}$

This is called a cyclic group of generator $g$ (here 2) : after a certain number of exponentiations, we have loop.

Now let's move back to our question : $\log_2 5 = ?$
In $\mathbb{Z}_{11}^\times$ as we have $2^4 \equiv 5 \pmod{11}$, therefore in $\mathbb{Z}_{11}^\times$, $\log_2 5 = 4$.

The discrete in discrete logarithm refer to the aspect that we are working in a discrete group and not any real numbers.


Why can't NORX produce intermediate auth tags like Keyak can? Why can't NORX produce intermediate auth tags like Keyak can?  Keyak appears quite attractive because of this, but seems to be slow in the absence of hardware acceleration.

The NORX documentation does not specify how to use it for intermediate tags, but I agree with Richie Frame that it could easily support them. Using intermediate tags in sponge-based authenticated encryption was considered by Bertoni et al., SAC 2011, see Section 2.1. Since NORX's mode of operation is derived from the same construction, I see no obvious obstacle.

Note that, on the other hand, Keyak explicitly specifies the concept of a session with intermediate tags, its implementation readily supports them and its security analysis takes them into account.

About the second part of your question, i.e., that Keyak "seems to be slow in the absence of hardware acceleration", there is no objective reason to believe so, since Keyak with its 12 rounds and full-state absorbing should be at least twice faster than SHAKE128. For instance, our current benchmarks confirm the comment of Biv, as Ocean Keyak takes about 1.8 cycles/byte on Haswell on a single core.

Disclaimer: I am one of the co-designers of Keyak.


Why weak modes of operations are not banned? If some modes of operations of AES are not secure (like ECB or CBC), which are prone to bit flipping / manipulation attacks, and why they haven't they been banned or advised against by NIST for other bodies and are still recommended?

The last publication that I am aware of is: Recommendation for Block Cipher Modes of Operation.

From the document:

  "This recommendation specifies five confidentiality modes of operation
  for symmetric key block cipher algorithms, such as the algorithm
  specified in FIPS Pub. 197, the Advanced Encryption Standard (AES)
  [2]. The modes may be used in conjunction with any symmetric key block
  cipher algorithm that is approved by a Federal Information Processing
  Standard (FIPS). The five modes—the Electronic Codebook (ECB), Cipher
  Block Chaining (CBC), Cipher Feedback (CFB), Output Feedback (OFB),
  and Counter (CTR) modes—can provide data confidentiality."

All listed modes are vulnerable to manipulation attacks in one way or another. And all modes require specific prerequisites to be secure. This could be a maximum message size or having an unpredictable IV in the case of CBC.

Only authenticated modes can achieve message integrity / authenticity. Others are all vulnerable because changes to the ciphertext cannot be detected. Originally a lot of effort was spend on error propagation due to unreliable transport. This is what is meant when bit flipping attacks are mentioned. However, in modern times, the encryption is commonly performed in a higher layer where error correction has already been performed. So we're mainly interested in protecting against targeted attacks. Mixing confidentiality and error detection is not a big topic anymore.

As indicated, any of these old modes can be used to achieve confidentiality. For a higher level of security for actual messages you would probably want to use newer recommendations such as GCM and CCM though. However, above modes have not been broken so there is no need to retract them; that would involve rewriting many systems that are compliant.

Although ECB mode can be used for small messages (single block encrypt) or as building block, I guess ECB is the most contentious mode of the bunch. Even as building block, you could argue that directly using the block cipher makes more sense. But please do note that many higher level API's do not directly expose the block cipher to the user; you'd need to use ECB mode instead.


Can we use PHE or SWHE instead of bilinear pairings in ZK-SNARKS? In ZK Snarks bilinear pairings are used to do "encrypted computation". I was wondering if we can use Partial Homomorphic Encryption or Somewhat Homomorphic Encryption instead of bilinear pairings. Can you please elaborate on why they should or should not be used?

Yes it is possible, and in fact, it has been done, with partial homomorphic encryption (for example in this paper) and somewhat homomorphic encryption (here and here).

The main difference is that a SNARG which uses these primitives instead of pairings is not publicy verifiable anymore. Indeed, suppose to simplify that you are supposed to perform a "multiplication" and some additions using a pairing, and that the verification should succeed if the exponent in 0 in the end. When doing so with the pairing, the final "zero test" can be publicly checked by everyone. When replacing it by a homomorphic encryption scheme, however, what you end up with is an encryption of zero. Checking that this does encrypt zero requires knowing the secret key of the scheme. For this reason, these SNARGs are restricted to being designated-verifier: they can only be verified by the owner of a specific secret key (and this secret key cannot be made public, since knowing it allows to forge a proof).


Confusing notation in the definition of differential privacy I've started looking into differential privacy from scratch following "The Algorithmic Foundations of Differential Privacy" by Dwork and Roth (freely available online). The mathematical notation is however somewhat confusing. On page 16, they define Probability simplex and Randomized algorithm as:

Is it correct that $\Delta(B)$ is a simple categorical probability distribution over $B$? Or is is something else?

Here's my reasoning:

$B$ is a categorical random variable of cardinality $|B|$ (so having $|B|$ categories) so $\Delta(B)$ is a probability mass function, PMF (which is a discrete probability distribution function) over $B$. Why? It assigns each category from the random variable B a probability value > 0 such that the sum of all values is one.

But the second definition looks somehow under-defined:

  A randomized algorithm $\mathcal{M}$ with domain $A$ and discrete range $B$ is associated with a mapping $M : A \rightarrow \Delta(B)$

What exactly is $A$ here? It is the domain of the algorithm, but is it discrete, continuous, single-dimensional, multi-dimensional, or what? Or it doesn't matter?

  On input $a \in A$, the algorithm $\mathcal{M}$ outputs $\mathcal{M}(a) = b$ with probability $(M (a))_b$ for each $b \in B$.

This notation is confusing: $(M (a))_b$ - why they index with lower-cased $b$ and what does it mean?

  The probability space is over the coin flips of the algorithm $\mathcal{M}$.

Flipping a coin sounds funny in a formal definition (why not simply say "a Bernoulli distribution with $\theta = 0.5$"?). Nevertheless, the last sentence doesn't make much sense to me: what is "the probability space"?

I've looked up several other sources but they use different notation and don't even bother with these "first principles". So any explanation is much welcome.

I had the same problem when I was understanding this because it's not so intuitive. I will answer here in case future people had the same trouble.

Agree with you $\Delta B$ assigns a probability to every element of the set $B$.

$A$ It can be anything I assume from continuos to discrete objects.

$(M(a))_b$ is the probability that the mechanism outputs $b$ when the input is $a$.

The probability space is over the coin flips of the algorithm $\mathcal{M}$. This means you will not know before you apply the mechanism which will be the result. For example, if you toss a coin, you will know what will be the answer? No. What this space is inducing the most important, the randomness. You will see on some papers " The probability space is over the randomness of the algorithm $\mathcal{M}$", which makes more sense.

I made an example to stabilize these definitions:

Let's consider an mechanism $\mathcal{M}$ that will find a $a$ in a list $A=\{(x_0,x_1,x_2,x_3,...,x_n): x_i=\{a,b\},n\geq 2\}$ where the half are a's and the other half are b's. With output $B=1$ if it finds an a and $B=0$ if it doesnt . This is $B=\{0,1\}$. Then the algorithm/mechanism $\mathcal{M}(x_i)=b$ with probability $(M(x_i))_b)$ which is defined by $\{(p_1,p_2)\in \mathbf{R}^2: p_1+p_2 = 1;p_1,p_2 \geq 0\}$ (Probability Simplex) . It means give a value of $p_1$ that $B=1$ happens and $p_2$ that $B=0$ happens . Who define this probabilities ?. The space of randomness, which we will never know for sure will be the result of the mecanism, because in that case wil be deterministic.


Encryption mode with chained algorithms Suppose that I want to encrypt some data using two different algorithm chained (e.g. AES and Serpent) and harnessing the benefits of CBC.

I can do:

SERPENT_CBC( AES_CBC(plaintext) )

or

SERPENT_ECB( AES_CBC(plaintext) )

Of course the second solution is computationally slighter than the first one.
But can it be considered as safe as the first one?

Links to papers or books that discuss this topic are welcome.

Note: This is not (yet) a full answer, but I'm posting this anyway in the hope that I or someone else might be able to complete it later.  Please don't upvote this yet.  If you can fill in the gaps in the vague proof sketch below, please do so; if you post it as a separate answer, you'll have my vote.

It's pretty trivial to show that, if AES-CBC is secure and the keys are independent, then both of your schemes will also be secure.  Of course, that's not a very interesting result, so, to get something more interesting, we'll need to assume that AES-CBC is somehow not secure enough by itself.

Of course, we could hypothesize all kinds of attacks on AES or on your use of the CBC mode, but, to keep things simple, let's just assume that the security of the AES layer is completely lost because the attacker knows your AES key.  (This assumption also has the advantage that, besides being just about the worst-case scenario imaginable, it also seems a lot more plausible in practice than any hypothetical cryptanalytic attack on AES.)

CBC encryption using a secure block cipher normally provides IND-CPA security, assuming that the attacker cannot predict the IV and that the message length is fixed (i.e. not useful to the attacker).  It's easy enough to show that, assuming that Serpent is a secure block cipher, and that you implement CBC correctly, your first scheme is also at least as secure as Serpent-CBC alone, and thus also IND-CPA secure.

The remaining question then is:

  Assuming that the attacker knows the AES key (but not the Serpent key), and that both AES and Serpent are secure block ciphers, does the construction Serpent-ECB( AES-CBC( $m$ ) ) provide IND-CPA security?

Intuitively, provided that the CBC IV is chosen randomly, it seems that the answer might, in fact, be yes, although I have no proof of this yet.

In particular, we have the following lemma:

  Lemma: If no plaintext block is ever encrypted twice, ECB mode instantiated with a secure block cipher is IND-CPA secure.

(Proof omitted, but it's kind of intuitive: a secure block cipher looks like a random permutation, and two outputs of a random permutation are indistinguishable if you've never seen either of them before.)

So the question becomes whether an adversary who:

a) knows the key,
b) can choose the messages, but
c) does not know the IVs in advance

would be able to force the output of CBC encryption to contain the same block more than once with a non-negligible probability.

Of course, this might happen by chance, if the number of encrypted blocks gets close to the birthday bound, although it's not quite clear whether such random collisions actually provide any advantage to the attacker.  Still, even if they do, we may avoid this issue by assuming that the total number of blocks the adversary can ask to be encrypted is much less than $2^{64}$.

We can also show that, even if the attacker knows the CBC mode encryption key and can choose the plaintext to be encrypted, as long as the IV is uniformly randomly chosen and unknown to the attacker when they choose the message, each of the ciphertext blocks, considered individually, will also be uniformly random.

However, that's not quite enough to show that the attacker would not be able to introduce correlations between the ciphertext blocks, possibly causing them to repeat more often than expected.  Intuitively, that should not be possible, if the block cipher used is, in effect, randomly drawn from a secure pseudorandom permutation family, but I'm getting too tired to be able to show this right now.


Key construction in the Full Cramer-Shoup cryptosystem The Full Cramer-Shoup Encryption scheme needs to choose six random numbers from $\mathbb{Z}_q$, which we denote them by $ x_1,x_2,y_1,y_2,z_1,z_2 $. Then the scheme hides these random numbers in the values $c=g_1^{x{1}}g_2^{x{2}}$, $d=g_1^{y{1}}g_2^{y{2}}$, $h=g_1^{z{1}}g_2^{z{2}}$.

It is clear that the proportion of public key to private key is near to 1:2, because we can denote them by binary-tuple, which have two private keys and one public key, such as $((x_1,x_2),c)$, $((y_1,y_2),d)$, $((z_1,z_2),h)$.

Is it possible we use the less private keys to achieve the scheme, because my intuition tells me it have so many private keys?

Yes, if you allow to introduce other primitives into the PKE scheme.
The Kurosawa-Desmedt scheme is an example whose secret key consists of four exponents in $\mathbb{Z}_q$.

Let us fix a group $\mathbb{G}$ of prime order $q$. Let $H$ be a secure hash function (TCR security).

Cramer and Shoup

Let us review the Cramer-Shoup scheme. As you wrote, the scheme is summarized as follows:

$\mathrm{pk} = (c,d,h) = (g_1^{x_1} g_2^{x_2}, g_1^{y_1} g_2^{y_2},g_1^{z_1} g_2^{z_2}) \in \mathbb{G}^3$
$\mathrm{sk} = (x_1,x_2,y_1,y_2,z_1,z_2) \in \mathbb{Z}_q^6$
$\mathrm{ct} = (u_1, u_2, e, v)$,
where $u_1 = g_1^r$, $u_2 = g_2^r$, $K = h^r$,
$e = E_K(m)$, $\alpha = H(u_1,u_2,e) \in \mathbb{Z}_q$,
and $v = c^r d^{r\alpha}$.

I omit the decryption algorithm. The scheme is IND-CCA2 secure if the DDH assumption holds and the SKE scheme ($E_K$) is one-time secure.

Kurosawa and Desmedt (CRYPTO 2004)

Kurosawa and Desmedt proposed a new PKE scheme with more compact secret key, as you wanted.
The scheme is summarized as follows:

$\mathrm{pk} = (c,d) = (g_1^{x_1} g_2^{x_2}, g_1^{y_1} g_2^{y_2}) \in \mathbb{G}^2$
$\mathrm{sk} = (x_1,x_2,y_1,y_2) \in \mathbb{Z}_q^4$
$\mathrm{CT} = (u_1, u_2, e, t)$,
where $u_1 = g_1^r$, $u_2 = g_2^r$, $\alpha = H(u_1, u_2) \in \mathbb{Z}_q$,
$v = c^r d^{r\alpha}$, $(k, K) = KDF(v)$, $e = E_K(m)$, and $t = MAC_k(e)$.

The scheme is IND-CCA2 secure if the DDH assumption holds, the SKE scheme ($E_K$) is one-time secure, and the MAC scheme ($MAC_k$) is secure.
In this scheme, $v$ is used to extract keys for SKE and MAC,
 while in the CS scheme, $v$ is used to serve integrity of $u_1,u_2,e$.
By this change, they successfully removed $h$ from the public key and $z_1,z_2$ from the secret key.

Others

There are tons of PKE/KEM schemes improving the Cramer--Shoup PKE/KEM scheme;
efficient ones based on slightly stronger assumptions, say, GDH, HDH, and GHDH assumptions, and less efficient ones based on weaker assumption. Some researchers try to make schemes compact by employing the random oracles. You can find them by search engines, say, Google Scholar.


what method of transposition does AES 256 encryption use I'm interested in learning how to use AES-256 encryption in C/C++. I'm still a beginner in Cryptography but I'm confident in my abilities to program.

There is still a lot for me to learn about this topic so please don't respond telling me that I shouldn't be implementing the algorithm or that I should be in college. I'm not, and never will be.

My question is just on the method of transposition used after you send the function a message and a key. I don't fully understand how to use the key but I understand enough to know that the message chars go though a function that gets called a minimum of 10 times. I also understand that the function goes through a processes of Substitution -> Transposition -> Substitution -> XOR

My question regards Transposition. I understand two methods(I don't know their name) One where you draw your message bit by bit on a line alternating top and bottom, eventually combining the top half with the bottom half. The other method I understand is where you have say a number and use the number to encrypt ex:

3612
hell
othe
rexy

cipher text: lhxleyhorete

Which methods are used in AES-256? Does it use more than one?

What method of transposition does AES use?

Transposition is a simple movement of data to an alternative location. There are two relevant steps in AES when it comes to transposition: addRoundKey and shiftRows.

addRoundKey

The addRoundKey step incorporates a bitwise rotate left. This is a transposition of bits within a single word.

shiftRows

The shiftRows step is a transposition of bytes in the state. Each of the four rows of the state are shifted by an amount from $0$ to $3$ places. This step is designed to work in tandem with the mixColumns operation to ensure that changes in the state diffuse evenly and completely through the rest of the state.

Conclusion

The addRoundKey function incorporates a bitwise transposition, and the shiftRows step of the main function is a byte-wise transposition.

Note

  I'm interested in learning how to use AES-256 encryption in C/C++

All that being said, if you want to learn how the algorithm works, then implementing it is a good strategy and you should do so. But there is a lot more than functional correctness to consider in a secure crypto library - your code can produce correct input/outputs while still being vulnerable to all kinds of subtle and impressive attacks. After you are done implementing you might see if you can find/use any of these attacks to break your program.

If you intend to use AES to protect users data in the real world, you should strongly consider using a pre-existing library such as libsodium*.

* Note: I am not discouraging you from writing your own code, but using it is a different story. You wouldn't self-study karate for 2 weeks and then start up a mercenary protection service, for reasons that are obvious in the real world but not necessarily so obvious in the information world. Empowering yourself is great, but protecting people is against powerful adversaries who mean business needs to be taken seriously


How to determine the fastest OpenSSL cryptographic algorithm This question does have to do with cryptography, but not necessarily with encrypting meaningful data. This is my first post here, so if I'm going about this question incorrectly please let me know.

Some quick back story:
I have a regular volume of hard drives that I need to wipe. I'm not wiping DoD stuff, and I really don't want to debate which method is the correct one to use. I have a method I use that I'll show here and that's what I'll continue to use for the time being. I'm also running the wipe from a Raspberry Pi because I don't have an extra PC available.

Because I have a regular volume, I tried to find a method of writing psudo-random data to a disk with the highest throughput.

This gives me 8-9MBps throughput:

dd if=/dev/urandom of=/dev/sda

And this gives me 9-10MBps:

dd if=/dev/zero of=/dev/sda

I need this process to move much faster, and I don't have access to any hardware-backed crypto.

I found this a while ago from someone else in the StackExchange network and it gives me 28-35MBps throughput:

openssl enc-aes-128-ctr -pass pass:<128-bytes-of-random-data> -nosalt < /dev/zero > /dev/<disk-to-wipe>

My question is, how can I quickly determine which crypo library will give the the most throughput for my application and still generate sufficiently random data for my use case? Are there additional crypto libraries that aren't installed by default? Is there something faster than openssl for this?

I know I could use an old laptop or some other device for this, but I don't have that now, and even if I did I would still want to optimize the solution for that device.

I hope this makes sense and is relevant to this community, but if this needs to be posted somewhere else please let me know.

It's always best to wipe disks using the ATA SECURE ERASE command directly to the drive. This command lets you wipe data that simply isn't visible to even the Operating System. It is a direct command to the drive to erase itself. Preferably you should send this command over a real SATA or PCI-e (M.2) connection as some (USB) controllers may get in the way. On Linux you can execute it using the hdparm command that is e.g. available on the Parted boot disks or sticks. The good thing is that it doesn't require any CPU or bus speed; the drive just wipes itself at maximum speeds.

The SECURE ERASE command is the only command you should use on an SSD. If you just write to an SSD then - first of all - you won't reach any sectors that have been written before due to wear leveling. Second, by writing data to all sectors, you'd mark all those sectors as in use, and you'd have to SECURE ERASE the disk anyway to be able to (reliably) use it again. Never try to wipe an SSD by just writing to it. Advantage: SECURE ERASE just erases the flash blocks, which is a separate, fast command to each of the blocks; it may literally finish in less than minute, even for larger drives.

Unfortunately, these commands may however be buggy, so some tests afterwards may be in order if you cannot find any information on the drive if SECURE ERASE has been implemented correctly (if unsure, buy Intel SSDs, as they have very rigorous testing of their drives - at least they seem most thorough when it comes to the security / drive encryption).

I don't think you will find anything much faster than AES-CTR on a highly optimized OpenSSL library. You could try a stream cipher as no Raspberry has fast AES support - as far as I know. For just erasing a disk I would assume that RC4 would give you much better results. It won't be as secure, but as it is exceedingly hard to remove data from a wiped disk in the first place, I'd say RC4 is still plenty secure none-the-less. So on actual hard drives - the type with actual disks - RC4 could be a preferred option.

The newer the disk, the more dense the data, the harder it is to restore it. So if you have a rather new disk then writing zeros may already be a good option. There may be some magnetic residue left on the outside of the tracks, but you'd have to reposition the head and be extremely lucky to be able to read it out with any chance of getting significant data. Most disk restoration services will not be able to restore a zeroed disk, at least as far as I've been able to find out so far.

Completely off topic here, but for dd, you'd probably better try a larger block size of e.g. 4 MiB using the -bs command. Otherwise you may get sub-optimal results.

I've got no idea on how to secure erase a USB stick or SD-card. They are pretty small, so if they contain any important data, I'd say destroying the chips physically is the best option. A direct appliance of a sharp object to the center of the chip destroys them with a very high reliability. They are very brittle and don't like torsion - or hammers, for that matter. Buy physically small ones so you don't pollute as much when you bin them for incineration - preferably only the silicon (the flame retardant in the plastic of USB sticks is highly toxic when burned; they are chemical waste).

Hammers also work pretty reliably on the disks of HDD's (with glass disks), for your uber highly secure stuff. Sanding them down is 100% effective. Wear protective glasses and protect yourself from dust and flying objects. I haven't tried this myself yet unfortunately.


Can 64-bit “PRINCEcore” practically be brute forced? There is a cipher called PRINCE proposed in ASIACRYPT two years ago.

See the paper: “PRINCE – A Low-latency Block Cipher for
Pervasive Computing Applications”

The cipher divides the 128-bit key into 64-bit k0 and k1. If I remove the key whitening at the beginning and end. Then the cipher is stripped down to PRINCEcore which only uses 64-bit k1. Is brute forcing the PRINCEcore practical?

Some clarifications:

I dont worry about side channel attacks or fault attacks.
I have seen several attacks on PRINCE (and also PRINCEcore), but they are not significantly better than brute force.

PRINCEcore is a 64-bit block cipher with a 64-bit key $k_1$. PRINCE is a 64-bit block cipher with a 128-bit key $k_0||k_1$ built from PRINCEcore as
$$\operatorname{PRINCE}((k_0||k_1),x)=\operatorname{PRINCEcore}(k_1,(x\oplus k_0))\oplus P(k_0)$$ where $P(k_0)$ is given as $(k_0\ggg1)\oplus(k_0\gg63)$ which I read as: rotate the 64-bit $k_0$ right by one bit, then replace the rightmost bit by its XOR with the second leftmost one; making $P$ a mapping.

That extension from PRINCEcore to PRINCE is reminescent of the extension from DES to DESX, analyzed by Joe Kilian and Phillip Rogaway in How to protect DES against exhaustive key search (an analysis of DESX). At least, that construction greatly improves the resistance to exhaustive key search, and I do not see that PRINCE could be practically brute-forced with work commensurate to brute-force of PRINCEcore (that is, near $2^{63}$ encryptions).

Note: The best motivation I can find for $P$ is that the rotation it contains avoids a cancellation of $k_0$ in some common operating modes, like OFB, CBC, CFB.. However, by rotating the output of PRINCE, we can cancel that rotation. And the single-bit XOR in $P$ does not seem to add much security.


Resources for basics of lattice crypto I'm looking to fill in the gaps of my knowledge of lattices. Can anyone point me towards papers or books that introduce lattice crypto assuming a fairly solid math background?

Mods: Feel free to close this if it's not the proper format. I'm not exactly clear on the literature request policy.

This introduction and this one are well formed . Also have a look at this thesis . Notes from this course may be helpful . Oded Regev has numerous publications to the field.


Is there an additively homomorphic encryption scheme that supports calculating a square root on the ciphertext? I need an additively homomorphic encryption scheme that satisfies: $D(\sqrt{E(m)}) \approx  \sqrt{m}$. It seems that the lifted ElGamal satisfies this, but it is hard to do decryption if the message space is large. Is there any other scheme that satisfies this?

I believe that such a system (with Homomorphic addition and approximate squareroots) is likely to be Fully Homomorphic, and hence it is unlikely that you could find an efficient candidate among existing systems (or, if you did, well, that's a Really Significant result).

Let us assume that:

Subtraction (as well as addition) can be done homomorphically
The approximate squareroot of 2 is 1.

Then, we can compute the "or" of two encrypted values $a$ and $b$ (which are both encrypted versions of either 0 or 1), by computing:

$$\sqrt{\sqrt{a+a+b+b}}$$

It is easy to verify that the result will be an encrypted 0 if both $a$ and $b$ are 0, and 1 if either (or both) are 1.

That, with homomorphic subtraction, is a complete set, and so we have a FHE system on our hands.


Benefit of combining classical substitution ciphers with modern cryptography I know that a simple monoalphabetic substitution cipher is considered extremely weak, on account of linguistic frequency-analysis attacks.  However, assume the following:

cleartext is encrypted (with 256-bit AES, for example), and the resulting cipher is in base64 format
the client has a key of 64 chars (a-z, A-Z, "+/"), where each character is randomly mapped to another character (i.e., 'a' -> 'Y', 'b' -> 'f', 'c' -> '/' etc)
a simple monoalphabetic substitution cipher is applied to the base64 ciphertext

Aside from the practicalities of implementing this approach, would this add much security?  I argue that it would, taking into consideration the following points:

neither base64 encoded text nor the raw encrypted data it represents are subject to frequency-analysis attacks
the 'key space' (to use the word loosely) of the base64 character set, represented as a factorial (64!) = 1.2688693e+89, or roughly 2^296 (if I calculate correctly).

So, in the case of a brute force attack, an attacker would need to try 2^296 key combinations, and for each one of those, they would need to go through the normal process of brute-forcing a 256-bit AES cipher (already unfeasible).

In the case of a break in the underlying algorithm (AES, in this case a break would be highly unlikely) the attacker would still need to search the 2^296 keyspace to find the original ciphertext.

There has been plenty of discussion about double-encryption, and how it adds little more security (in terms of orders of magnitude), but I would like to know people's thoughts about the approach described above.  I DO understand that it's complete overkill, and that 256-bit AES encryption is more than sufficient by itself, but I'm interested to hear opinions at least from a theoretical point of view.  Does this potentially add much security?

The fact that a given cipher has a key length of 296 bits doesn't mean at all that it provides 296 bits of security or even that a brute force attack would take $2^{296}$ steps. The problem of mono-alphabetic substitution cipher is the ridiculously small block size (in this case, barely $\log 64 = 6$ bits).

If absolutely nothing about the plaintext is known, every cipher is unbreakable, as there's no way of knowing if you got the right result.

In practice, you always know something about the plaintext. If that's not enough to launch a known-plaintext attack, your method might add some security form a theoretical point of view, but it's rather pointless in practice, since brute-forcing a 256-bit key is just as feasible as brute-forcing a 552-bit key.

However, if you do know enough plaintext, the mono-alphabetic substitution cipher doesn't add any security at all. After encrypting the known plaintext with an AES key, all you have to do is check if matching characters get mapped into matching characters. If they don't, discard the key; no further tests are required.


Authenticating code securely and generating a certificate I'm working on a product with strong security. Essentially there is an App, downloaded from the iTunes App Store. When the App starts up, it generates a strong RSA keypair and stores it in the Keychain. This key pair is the foundation for a lot of things in the overall system. The next step is for the App to use this keypair to generate a CSR (Certificate Signing Request) and present it to a CA (Certificate Authority) and request an SSL Client Certificate for the App key pair. The CA then records the UUID of the App. This process needs to be secured so that only the validated App can submit the CSR.

My question is how do I authenticate my App to the CA, to prevent something else to request these Client Certificates? I understand that we cannot rely on the certificate alone for security. Its only purpose is to prevent a layer of security between the App and the backend system and a "anchor" for User Security (outside the scope of this question).

Logic dictates that we should "give" the App something that only the App knows (i.e. a secret, encrypted and obfuscated in code). But this can be extracted with enough time and effort, thereby unlocking access to the CA.

Essentially I want to know how I can authenticate a piece of code.

Currently, our thinking is to generate a unique key pair at build time, embed the public key in the code (obfuscated) and use the public key to encrypt the CSR. The private key is in the backend. This ensures that only entities with the public key can submit the CRs.

Note - this process has no user intervention. It is not about the user, only about securely generating an identity unique for an instance of an App and issuing a certificate

My question is how do I authenticate my App to the CA, to prevent something else to request these Client Certificates?

There is generally no way to authenticate the client code. Any secret you embed in the app could be extracted. You must assume an attacker can send requests that an authentic client would.

Instead, what you can do is authenticate the user. You can give each legitimate user a secret license key and only allow a single client certificate to be signed per valid license key. (Probably with the ability to reset for reinstall, etc.)

As an example, such a scheme could look like:

User buys app, downloads client and receives a license key.
App asks user for license key. Sends a certificate-signing request to server that proves the license key.
Server verifies the license key is valid and unused, signs certificate, stores the fact that it is now used.

The certificate signing request could be e.g. licence_key||certificate encrypted with the server's public key (which is embedded in the app). As long as an attacker cannot generate valid license keys on their own, they cannot get extra certificates signed.


Security proof of partially blind signature (schnorr signature based) I read a representative paper about partially blind signature.

Abe and Okamoto - "provably secure partially blind signature".

They suggested a partially blind signature scheme based on Schnorr signature.

In the security proof section, they proved that the scheme is secure against adaptive chosen message attack using ID reduction scheme.

They assume a single-info adversary, $U^{*}$ that violates unforgeability for infinitely many sizes.

And the machine ${M}$ is constructed by a forger ${U^*}$.

Firstly, ${M}$ select $b$ (0 or 1, randomly) and assigns $(y, z)=(g^{x}, z_{0}g^{\gamma})$ if $b=0$, or $(y, z)=(z_{0}g^{\gamma}, g^{w})$ if $b=1$.

$\gamma, x$ (or $w$) is chosend randomly.

Random oracle $F$ is defined so that it returns appropriate value of $z$ according to above selection.

Let's assume that $b=0$.

If $U^{*}$ is successful with probability at least $\eta$, then the author says we can find a random tape string for $U^{*}$ with probability at least 1/2 such that $U^{*}$ succeeds with probability $\eta/2$.

I cannot understand what 'finding a random tape' means.

Does it mean finding $\gamma$ and $x$?

Why is it 1/2 and $\eta/2$ ?

Below is a capture of the paper.

Thanks.

It follows by the probing strategy/heavy-row lemma, which traces back to [Oka,FFS]. Read §6 in this paper for a nicer explanation.

References:
[Oka]: Okamoto. Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes. CRYPTO 1992.
[FFS]: Feige, Fiat and Shamir. Zero-knowledge proofs of identity. JoC 1988.


How to calculate the order of the subgroup? Given a curve with points over GF(p), a subgroup of prime order q and a co-factor h.

How do I calculate the size of q which is also the modulus?

I was thinking q = p/h

Run Schoof's algorithm on the curve parameters to find $qh$, and divide by $h$.

The size $p$ of the coordinate field is only required, by Hasse's theorem, to be near $qh$, within a factor of a square root: $|qh - (p + 1)| \leq 2 \sqrt p$.  Consequently, $p/h$ may be near $q$ but is not equal to $q$ except in anomalous curves in which ECDLP is easily solved by additive transfers as described by Smart (preprint), Araki–Satoh, and Semaev (the ‘Smart-ASS’ attack).

For example, Curve25519's coordinate field is $\operatorname{GF}(2^{255} - 19)$, and its order $2^{255} + 221938542218978828286815502327069187944 = qh$ where $q = 2^{252} + 27742317777372353535851937790883648493$ and $h = 8$.


Diffie-Hellman: difficulty of computing $g^{x^2}$ given $g^x$? Hoepfuly a simple question.
Given a group where the CDH problem is hard, if the adversary sees a public key $g^x$, is it easy or hard for the adversary to compute $g^{x^2}$?
My intuition says it should be hard, but I don't know for sure.

Let's call the problem Square Diffie-Hellman (SDH).
SDH is at least as hard as CDH in groups of known order and the reduction goes as follows.$^*$ Given an adversary $\mathsf{A}$ that breaks SDH, our goal is to construct an adversary $\mathsf{A}'$ that breaks CDH. Given the CDH challenge $(g,g^x,g^y)$, $\mathsf{A}'$ runs $\mathsf{A}$ thrice -- first on $(g,g^x)$, then on $(g,g^y)$ and finally on $(g,g^{x+y}=g^xg^y)$ -- to obtain $X=g^{x^2}$, $Y=g^{y^2}$ and $Z=g^{(x+y)^2}$, respectively. Now $\mathsf{A}'$ can extract the solution to CDH, i.e., $g^{xy}$, by computing $(Z/XY)^{1/2}$. The correctness of the solution can be argued using the identity $(x+y)^2=x^2+y^2+2xy$.
Note that the ability to compute a square root is crucial for the reduction to go through. Therefore the reduction above holds only for prime-order groups or any group of known order. (I am not aware of a reduction from CDH to SDH for groups of unknown order.)
As @poncho points out in the comment, this means that SDH is equivalent to CDH since the reduction in the other direction is straightforward as described next. Given an adversary $\mathsf{A}$ that breaks CDH, we construct an adversary $\mathsf{A}'$ that breaks SDH works. On input the SDH challenge $(g,g^x)$, $\mathsf{A}'$ computes $(g,g^x,(g^x)^r)$ for a random $r$ and sends it to CDH adversary $\mathsf{A}$. The CDH solver returns $g^{x^2r}$ from which it can retrieve $g^{x^2}$ by computing the $r$-th root.
$^*$ This is an example where we know a Turing reduction but not a Karp reduction.


Why is a MAC verification algorithm required when we can simply create a new MAC and compare the received one with the one calculated? The process of verifying integrity through MAC involves two separate algorithms (as mentioned here). On the server side, a signing algorithm runs which calculates the MAC of the message using the shared key, while on the client side, a verification algorithm runs which uses the secret key, the received MAC and the message to verify whether the message was altered in transit or not.
But we can simply dispense with a separate verification algorithm by simply calculating the MAC of the received message using the shared key. If the calculated MAC and received MAC are the same, the message has not been altered.
Is that what actually happens in all MAC verification algorithms?

Signing and signature verification are concepts related to public key cryptography.
In case of message authentication codes, there is a single secret key and one function:
T = MAC ( K, M )

Where:

T - tag
MAC - MAC function
K - secret key
M - message

Messages can be signed by either the client or the server and verified by the other, depending on the case. Both parties calculate MAC the same way, using the same function and secret key, over the same message. There is no separate function for MAC verification. The only extra step on the receiving end is associated with comparing if both received and calculated tags match, and then acting accordingly. But this has nothing to do with a MAC algorithm itself.


Replacing a block cipher's key schedule with a stream cipher Take Rijndael (AES) of block size 128 and reformulate it with a tweakable number of rounds and no key schedule.

Suppose we obtain:

Rijndael128(r, k)

where r is number of rounds and k is key of length r*128 bits (it is the concatenation of all round keys).

k is then made salsa20(x) where x is a 256 bit secret and nonce is constant.

Would this be at least as secure as AES-256 when r >= 14?
Assume no timing or side channels.

The requirements of a key schedule would be easily met by Salsa20, or any PRF for that matter. A key schedule is similar in purpose to a cryptographic hash functions (which Salsa20 is built off of), but the requirements are not as strict. For example, a preimage attack is fatal to a hash function, but being able to calculate the original key given only the round keys is not a huge deal for a key schedule. For this reason, key schedules typically do not involve particularly computationally-intensive operations and instead opt for much simpler and more lightweight algorithms.

From a paper referenced by the answer linked above, there are several classifications of key schedules. A Salsa20-based key schedule would fall under category 2B, the strongest practical category. That is, every bit in the master key influences every bit in every round key. Changing any one bit in the master key will change, on average, 50% of bits in all the expanded round keys.


PGP double encrypt instead of signing? So, maybe this is a dumb question, or maybe it's something someone's already done and it's really common, but whatever, here goes:

Why do we sign a message with our private key and then encrypt it with our contact's public key, instead of encrypting our message with our private key and then encrypting it again with our contact's public key?

Wouldn't the latter be better?

In general, the high-level idea behind the Digital signatures is what you mention (Convincing the verifier about owning the secret key). We have to be careful in the Encryption schemes we care about the confidentiality and the message keeps secure against the malicious users while in the Signature schemes the authenticity matters and the message is public.

Let show what is the difference between the RSA encryption scheme and the RSA signature scheme.

  RSA encryption scheme:

Setup:

Selects two large prime number $p$ and $q$.
Compute $n=pq$ and $\phi=(q-1)(p-1)$.
Selects $1<e<\phi$ such that $\gcd(e,\phi)=1$.
Calculate $d$ such that, $d\cdot e = 1 \mod(\phi)$.
Then the pair of public keys are $(n,e)$ while the secret key is $d$.

Encryption:

For a message $m$ compute $c=m^e \mod(n)$.

Decryption:

For a given ciphertext $c$ a valid receiver who owns secret key $d$ can compute $m=c^d \mod(n)$.

  RSA Signature scheme:

Setup:

Selects two large prime number $p$ and $q$.
Compute $n=pq$ and $\phi=(q-1)(p-1)$.
Selects $1<e<\phi$ such that $\gcd(e,\phi)=1$.
Calculate $d$ such that, $d\cdot e = 1 \mod(\phi)$.
Then the pair of public keys are $(n,e)$ while the secret key is $d$.

Signing:

For a message $m$ compute $sig=m^d \mod(n)$ and issue $(m,sig)$.

Verification:

For a given pair of message and signature, a verifier by taking the pair of public keys can check $sig^e \mod(n)\stackrel{?}{=}m$.

As you can see, both approaches follow the same idea but in signature schemes, we use keys conversely. But we never use the term of Encryption with a secret key for the Digital signatures because the main point for the encryption is confidentiality of the message while in the signature the message has to publish with the signature.

The RSA signature is just an example while we know this scheme is forgeable if the adversary owns two valid signatures and multiplying them to get a third valid signature.


SHA-256 Hashing problem from binary values For a school project we have been given some example hexadecimal numbers to hash like the following:

Len = 2 (in bits)
Msg = c0
SHA 256 - MD = 1e1cea10a23697dc97b423c259842ac12ee679d6b43f088f3c32b26dbbfb0d79

The binary representation of c0 is 11000000, but as the length is 2 units, I assume that the binary number to be hashed is 11, which corresponds to 3 in decimal. Using online hash converters, I cannot get the example hash value back. What am I doing wrong?

You need to hash exactly 2 bits set to 1. Two bits need to be padded, remembering that this is the last block. In that case the result is correct.

Note that representing two bits with hex value C0 is not correct. C0 represents a full byte and there is no reason to use the most significant bits rather than the lowest significant bits. Two bits set to one should simply be represented as 11 in binary.

I calculated the required result by performing a digest of the value E0 (the value with an additional padding bit set to 1, and the rest 0 valued padding bits: 11 1 0 0000), skipping the usual padding byte 80 (or 1000 0000 in binary), padding with zero valued bytes and then finally setting the (internal, encoded) length to 2. A bit messy, but it works.


Secure way to compare two secret numbers without disclosing them? For example, two people want to know who is the older, without disclosing their age. Is there a secure way to do this without a third party involved?

Of course there are ways to do that.

See for example, Secure Integer Comparison with Applications in Economics which is implemented in VIFF.

Also, solutions to the millionaire's problem would probably do the trick too. There are lots of these. Just search around for solutions to that problem.


Why do we need Rekey (Use case of rekey cryptography) I'm new to cryptography, and I'm trying to understand the concept of rekeying. What is the motivation (necessity) behind rekeying? What is the detailed mechanism for generating new session keys for an encrypted established connection?

Clear explanations of basic concepts would be very helpful, as would links to good videos or blogs.  (I have been unable to find such materials online.)

I would say that rekeying is used in cryptography in order to limit the number of messages (talking about encryption and decryption here) that are sent from the same key. This is just a preventive measure to thwart the attacker from getting much information about the same family of messages (encrypted with the same key) by looking at the encryption of messages with the same key.
If you have heard about the standard security definitions of encryption schemes and the standard attacks, like ciphertext only attacks, chosen ciphertext attacks, etc. then you might know that if the adversary gets hold of many many messages encrypted with the same key then in some encryption schemes and in some use case scenarios, the adversary might get some information about the messages which he ideally shouldn't have.
Let me give you a very primitive example.
You might know what a caeser cipher is (if not, then look it up). In case of caeser cipher (or any substitution cipher), if the adversary sees a lot of messages, encrypted with the same key, then they can easily run a frequency analysis attack on the cipher to learn the key and then get the message in plain. Rekeying, very frequent in such cases, in such a case might at least prevent the attacker from getting enough information to run an attack like this or at least make it an attack more difficult to run.
Don't assume that this is how weak the modern ciphers are, they are pretty great at prevent many attacks, even more sophisticated ones like linear and differential cryptanalysis on DES and AES.
But still, if an adversary gets hold of $2^{43}$ known plaintexts then it can successfully cryptanalyse DES encryption (although because of this, DES is not used these days and it is replaced by AES and 3DES) meaning that if the adversary somehow knows the encryptions of $2^{43}$ messages, all encrypted with the same key, then it can find the key and decrypt all of the upcoming messages (if encrypted with the same key) by using Linear Cryptanalysis.
Now in the above case, if one puts a limit on the time for which a key is used, say for only $2^{30}$ messages, then the attacker will never get $2^{43}$ encrypted messages with a single key because the key will be refreshed or rekeyed after just $2^{30}$ messages and this prevents the Linear Cryptanalysis attack on the cipher. Note that this above discussion assumes that adversary somehow gets to know the messages and their encryptions whenever they are sent. This may be true if adversary knows what the other 2 parties are talking about for some time but doesn't know what they will talk about, say a month later, and he wants to get the key somehow so that he can listen to their talk after a month. If he has already seen $2^{43}$ messages in the part where he knew what they were talking about, then he will recover the key and then use that key to listen to their chats after the month. If the 2 communicating parties change their keys, then he won't be able to use that old key to listen to their chats after the month.
In practice, say in the browser, a hybrid type of encryption is usually used where a public key handshake is used to establish a symmteric key and then that key is used to encrypt messages by symmetric encryption (AES) because symmetric encryption is way faster than public key encryption. Then you might ask that why don't we use symmetric key encryption to establish the keys also? This is so because symmetric key encryption doesn't provide a way for 2 parties to negotiate a key over an untrusted channel like internet but public key cryptography does (like Diffie Hellman Key Exchange Protocol).
Once a connection has been established, then across multiple sessions public key cryptography is used to rekey the symmetric encryption through which messages will finally be encrypted.


How to apply a block cipher to (large) packetized communication when packets can get lost/erased? In light of current events (Zoom getting strong headwinds for using AES-128 in ECB mode), I was wondering what the general approach is to packetized data encryption, where the packet length (UDP for video over internet: > 1200 B payload)

Is it really just a block cipher in ECB mode, so that each packet can be decoded without any prior packet⁰?
Is it a block cipher in some non-ECB mode, but it gets reset at the start of a packet?
Is it a block cipher in some non-ECB mode, but we're just using a sufficiently large number of say $N$ different keys, de- and encoder, which we use in interleaved / sequential fashion, so that any erasure of less than $N$ successive packets gives us enough time to let the transmitter know we need to re-initialize the receiver?¹
Would you go the WiFi/WPA route of deriving a key for each packet, leading to the couple of  attacks we know against that TKIP/KDF method?
Am I totally missing everything?

I've tried to look into how KASUMI (3G crypto standard) does this, but I haven't been able to track down the relevant standards document.

⁰ ... and everyone is bashing Zoom for adhering to industry best practice?

¹ wouldn't that lead to feasibility of forcing the encoder to a known state by an attacker with control over which packets get lost?

Is it really just a block cipher in ECB mode, so that each packet can be decoded without any prior packet⁰?

No. ECB is bad and creating a secure real-time channel (that can even handle packet loss) is a solved problem. It has been for years. There's no good excuse for using ECB here.

  Is it a block cipher in some non-ECB mode, but it gets reset at the start of a packet?

The usual approach would be to have some form of initialization vector for the encryption which is sent as cleartext with every packet and is used to re-synchronize the state between both endpoints if packet loss is expected. For some encryption schemes this can simply be the packet counter. Then once you have synchronized state for a packet, you use a stateful encryption scheme, like GCM or CTR + HMAC to encrypt the singular packet.

If you want to have a look at how this works out in practice, the three big secure channel standards are TLS (cannot handle lossy underlying layer), DTLS (adaption of TLS 1.2 for lossy contexts) and SRTP.