RSA p and q size to encipher a block I have a plaintext about 18 bit size.
I have to encipher it using RSA.
How large have to be p and q?
So M (message to encipher) = 2**18 bit
I tried, using a Python coded RSA alghoritm, different sizes for p and q, and my results are these:

p=61, q=31 not working
p=61, q=127 not working
p=997, q=4253 OK working

I tried them randomly but I think there's a way to decide the size.
Thank you for attention. I hope you can help me.

I have a plaintext about 18 bit size. I have to encipher it using RSA. How large have to be $p$ and $q$?

For security, the recommendation is: very large, like each at least 700 bits and the sum of their bit size at least 2000, so that their product is hard to factor. But maybe that's not the answer thought, for it does not consider plaintext size. Also, there are other conditions for security.
In textbook RSA, the public and private keys are $(N,e)$ and $(N,d)$, with $N=p\,q$, $e\,d\bmod(p-1)\;=\;1\;=\;e\,d\bmod(q-1)$, where $p$ and $q$ are primes. Encryption of a plaintext (integer representative of a) message $m$ is per $c=m^e\bmod N$, and decryption is per $e=x^d\bmod N$.
From the later equation and the definition¹ of $\bmod$ it follows that decryption can return the original message only if $0\le m<N$. This condition is sufficient when primes $p$ and $q$ are distinct (see this question), which we'll assume.
Thus $p$ and $q$ should be large enough that the largest possible $m$ verifies $m<p\,q$. If $m$ is 18-bit, by the definition² of bit size, it is sufficient that $p\,q\ge2^{18}$.
In term of bit size of $p\,q$: at least 19 is sufficient.
In term of sum of the bit sizes of $p$ and $q$: at least 20 is sufficient. This follows from $\|p\|+\|q\|-1\le\|p\,q\|\le\|p\|+\|q\|$.

p=61, q=127 not working

Correct. One way to prove this is that $2^5=32\le p=61<64=2^6$ and $64=2^6\le q=127<128=2^7$, therefore $p$ is 6-bit and $q$ is 7-bit, therefore $p\,q$ is no more than 13-bit, thus all 18-bit $m$ are such that $m\not<p\,q$, thus such $m$ does not belong to the plaintexts that can be enciphered and deciphered back to the original.

p=997, q=4253 OK working

Correct. One way to prove this is that $2^9=512\le p=997<1024=2^{10}$ and $4096=2^{12}\le q=4253<8183=2^{13}$, therefore $p$ is 10-bit and $q$ is 13-bit, therefore $p\,q$ is no less than 22-bit, thus all 18-bit $m$ are such that $m<p\,q$, thus such $m$ belongs to the plaintexts that can be enciphered and deciphered back to the original.
By computing $p\,q=4240241$, we can find that $p\,q$ is 23-bit (rather than the minimum of 22 established above), thus $p=997$, $q=4253$ allows decryption of all messages up to and including 22-bit, and some 23-bit messages.

¹ For integer $i$ and strictly positive integer $k$, the quantity $i\bmod k$ is uniquely defined as the integer $j$ with $k$ dividing $i-j$ and $0\le j<k$. It is written $j=i\bmod k$ without an opening parenthesis immediately on the left of $\bmod$.Contrast with $j\equiv i\pmod k$, which means that $k$ divides $i-j$, but leaves the range of $j$ unspecified.
² The bit size of a strictly positive integer $a$ is the uniquely defined integer $b$ with $2^{b-1}\le a<2^b$. It holds $b=\left\lceil\log_2(a+1)\right\rceil=\left\lfloor\log_2(a)\right\rfloor+1$. In a cryptographic context, it can be written $b=\|a\|$.


Moni Noar One Way Function: What does input is partioned mean? I am trying to understand An Implementation of Efficient Pseudo-Random Functions.

There, the following hash function is defined:

  We define $\hat{h}=\hat{h}_{r}: {\{0,1\}}^* \rightarrow {\bf Z}_R$
  as follows:
  $$ \hat{h}_r(m) = ({\sum_{i=1}^{k} m_i \cdot r^{i-1}}) \bmod R $$
  where $R$ is a 161-bit prime, $r$ (the key of $\hat{h}$) is a uniformly distributed
  element in ${\bf Z}_{R}^*$ and the input $m$ is partitioned into a sequence,
  $\langle m_1 \dots m_k\rangle$, of elements in ${\bf Z}_{R}$.

I am having trouble understanding what "$m$ is partioned into a sequence,  of elements in $\textbf{Z}_R$ means. Does this mean we understand $m$ as a bitstring, iterate through it from left to right as long as the resulting number is $<R$ and repeat this process until we covered the whole $m$ bitstring?

I am having trouble understanding what "$m$ is partioned into a sequence $\langle m_1, ..., m_k\rangle$ of elements in $\textbf{Z}_R$ means.

This is essentially what you said. Consider $n$ such that $\{0,1\}^n$, seen as integers, is a subset of $\textbf{Z}_R$ (e.g. $n = \lfloor\log_2R\rfloor$). Then regard $m$ as a long string $m = m_1\|\cdots\|m_N$ where each $m_i$ is in $\{0,1\}^n$ (if $n$ does not divide the bit-length of $m$ then apply a "good" padding to $m$, i.e. one that is prefix-free).

Just take into account that, as noticed by @poncho in the comments, this is not a PRF. This is a 2-universal hash function, and as shown in the post you cite, it is an ingredient for the construction of an actual PRF.


Which block cipher modes of operation allow a predictable IV? Recently I found out that in the modes CBC and PCBC the IV may be passed in cleartext but never must be predictable. However for this part of my app I rather have the IV be predictable and unique (i.e. generated from other data known to the "receiver" and also the adversary, and not stored/transmitted with the ciphertext) rather than random.

What options do I have as a cipher mode? How do I choose between them? Which is the main difference between OFB and CFB?

The short answer for the mode: use EAX.

There are several reasons why EAX is Good, but, in particular:

It includes integrity check, which is a must have (yes, really; defense against active attackers is often overlooked, and this is equally often deadly).
It needs a unique IV (a nonce) but tolerates predictable nonces.

As for OFB and CFB, see the Wikipedia page which has nice schematics. However, since neither does any kind of integrity checks, you would have to add some kind of HMAC, so choosing a nice integrated mode like EAX is simpler (and simplicity is good for security).

If for some reason you really cannot use EAX (or another similar mode), you can survive CBC by generating unpredictable IV the following way: use your source of "unique, predictable IV" to generate block-sized values, and encrypt each value with the block cipher, using a distinct secret key (which you do not have to share with anybody else). This is like using the block cipher as a PRNG. You still need a bit of randomness at some point (when you generate that extra key) but not as much as previously.


Do any one-key-of-many cryptographic schemes exist? I'm pretty sure I understand how public/private key cryptography works. Anybody can encrypt a message using a well-known public key, but only the person who holds the private key can decrypt it.

My question concerns securely sending a message to multiple people. Say there are n public/private key pairs. Is there a way to encrypt a message using the n public keys such that any one of the private key holders can decrypt the message in its entirety, but nobody else can?

Further, unrelated to public/private key cryptography, is there any scheme where there are n shared keys such that anybody who knows the n keys can encrypt a message such that any one of the shared keys can decrypt the message in its entirety, but nobody else can?

Yes, absolutely.  Here is the standard construction to address this problem.  Let $pk_1,\dots,pk_n$ be the public keys of the $n$ recipients.  We pick a random symmetric key $k$, encrypt the message $m$ (using authenticated encryption) under key $k$ to get $c=AE_k(m)$, and then encrypt $k$ under each of the public keys. Finally, we form the whole ciphertext as

$$E_{pk_1}(k),E_{pk_2}(k),\dots,E_{pk_n}(k),c.$$

That's what we treat as our ciphertext.  Now any of the $n$ recipients can decrypt (they can recover $k$ using their private key, and then use that to decrypt $c$), but no one else can.

The same method works in the shared-key (symmetric-key) setting as well.

This standard construction is standardized in more detail in "RFC 4880: OpenPGP Message Format" and in PKCS#7 (enveloped-data).  (Thanks, David Cary and DrLecter!)

You might also enjoy looking into broadcast encryption, which solves a related problem.  It basically allows you to transmit a message to millions of receives, without having a huge blowup in the size of the ciphertext (so it achieves much shorter ciphertexts than the simple scheme above), though there are some details and a little bit of additional coordination required.

For digital signatures, you might enjoy looking at ring signatures and group signatures.


Can I use SHA1 as license key? I have recently started looking into creating secure, while not validating against an external server, software product keys.

The idea I have had is to create a key consisting of two parts firstly a section that contains some (but not all) details of the user; for example name, customer ID and maybe a salt this would then be ecoded one way or another, say a simple base64 just to obfuscate it. The second part would be an SHA1 signature for a hash of all the user data this would be mostly the same as above but would contain the entitled software version (i.e. 1.0) and maybe something else related to the program.

The deployment of this would work by the user entering the key and the software extracting the user details from the key, appending its own credentials (version number etc.) the generating a hash a verifying the signature using this hash.

If the user key has not been tampered and the user is entitled to user that version of the software all will pass and we can proceed. If this it not the case (say the version entitlement is wrong) the signature will not match the hash. Obviously the public key has to be contained within the software to verify the signature but at no point does the user have the entire hash.

I was discussing this with a friend who said they thought this would be inherently poor as the user could poke through the program find out how the key system works and then, given the structure and the public key generate any number of license keys that would appear valid, as they would control the signature to match the software generated hash of 'fake' credentials.

Is this really that easy to crack surely even if the user did create a hash of some fake details and ID number they could not generate a valid signature to match this? Sorry the question has ended up being much longer than I intended; i wasn't sure how to be clear shorter. I hope this all makes sense.

You're somewhat on the right track.  A standard way to do this would be using an RSA sign/verify scheme.

On the server, user-specific and license-specific data is concatenated into a string and signed with the private key.

In the software, the signature is verified with the public key.  The public key can not be used to create valid signatures, it can only verify them (this is the beauty of asymmetric cryptography).

Of course, as pointed out by Thomas, there's nothing to stop someone decompiling your software and modifying the source code, but that can't be avoided.

If you're going to use RSA, be sure to use a secure padding scheme like RSA-PSS.


Can multiple public keys lead to the same shared secret in X25519? I have no mathematical knowledge about this, but I just read in RFC 7748 the following:

  Designers using these curves should be aware that for each public key,
  there are several publicly computable public keys that are equivalent
  to it, i.e., they produce the same shared secrets.  Thus using a
  public key as an identifier and knowledge of a shared secret as proof
  of ownership (without including the public keys in the key derivation)
  might lead to subtle vulnerabilities

Does that mean that multiple Curve25519 public keys can produce the same shared key produced by X25519? I just don't understand.

Does this mean that key servers (let's say that such key servers even verify the ownership of these public key using sending an encrypted challenge to the claimant) using Curve25519 are not a good idea?

There are two independent sources of equivalent public keys for the X25519 function.

The first is rather simple: A public key is an integer u between $0$ and $2^{255}-1$ that represents an element of the finite field $\mathrm{GF}(2^{255}-19)$. Hence, for all $i\in\{0,\dots,18\}$, the integer $2^{255}-19+i$ represents the same field element as the integer $i$.

The second source of equivalence is a bit more specific.
In a nutshell, the X25519(k,u) function is defined as follows:

Clamp the secret key k, forcing bits $\{0,1,2,255\}$ to zero and bit $254$ to one.

In particular, note that this means the clamped scalar $k'$ is a multiple of $8$.
Compute the scalar product $[k']P$, where $P$ is a Curve25519 point with $x$‑coordinate u.
Return the $x$-coordinate of $[k']$P.

Now Curve25519 has cofactor $8$, hence there exist nonzero points $Q$ of order dividing $8$. For any such point, the public key $P+Q$ is equivalent to the public key $P$: Since $k'$ is a multiple of $8$, we have
$$ [k']Q = [k'/8][8]Q = [k'/8]\infty = \infty $$
and therefore (using the distributive law)
$$ [k'](P+Q) = [k']P + [k']Q = [k']P+\infty = [k']P \text. $$

For a concrete example, the two public keys

629fb7d4a50e0339edfdfae1464fedb848dd35f25c5fecd3d3f5af61654a691d
b53677c430779b050cd6db7e1f4ca6735e07b30a61711f45a88e710790af772a

will, for every secret key, give identical shared secrets using X25519.


Hash Function - Pre-image resistance and Strong collision Resistance Why does pre-image resistance not guarantee strong collision resistance?

Logically I can make sense of this, but I am wondering if there's any general theorem that proves this?

With the definitions that a function $F$ is

(strongly) collision-resistant when a [computationally bounded] adversary can't [with sizable odds] exhibit any $(a,b)$ with $a\ne b$ and $F(a)=F(b)$;
first-preimage-resistant when, given $f$ determined as $F(a)$ for an unknown random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $F(b)=f$;
second-preimage-resistant when, given a random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $a\ne b$ and $F(a)=F(b)$;

neither form of pre-image resistance guarantees (strong) collision resistance. As to why: there's no argument that such guarantee should hold; and we have counterexamples, both practical (e.g. MD5), and theoretical.

Consider an hypothetical random function $H$ from bitstrings to $k$-bit bitstrings; or a good practical cryptographic hash with $k$-bit output (assuming that exists). This $H$ has all three properties, for large enough $k$. Define another function $F$, as
$$F(x)=\begin{cases}H(\mathtt{“b”})&\text{if }x\text{ is the string }\mathtt{“a”}\\H(x)&\text{otherwise}\\\end{cases}$$
$F$ is not collision-resistant since the strings $\mathtt{“a”}$ and $\mathtt{“b”}$ collide; but is preimage-resistant (in both senses) for large enough $k$.

The above counterexample still works if we use quantitative definitions of the three properties, requiring effort $O(2^{k/2})$ to break collision-resistance, and effort $O(2^k)$ to break preimage-resistance.


DES anti-fixed points for semi-weak keys I am looking for some "real examples" of anti-fixed points for DES semi-weak keys. As I know, there are $2^{32}$ anti-fixed points for 4 of the 12 semi-weak keys each. One or two examples of these points may help.

Anti-fixed points: For 4 of the (known) DES semi-weak keys, there exist $2^{32}$ plaintexts such that $E_k(x)=\overline{x}$

More info about DES weak keys, semi-weak keys, fixed points and anti-fixed points in the Handbook of Applied Cryptography, fact 7.90 (alternate link)

K = 01FE01FE01FE01FE   P = 771DF32699DF2F2A   C = 88E20CD96620D0D5
K = 01FE01FE01FE01FE   P = 668493768A3D5786   C = 997B6C8975C2A879
K = 01FE01FE01FE01FE   P = 6F52785BC50C62BE   C = 90AD87A43AF39D41
K = 01FE01FE01FE01FE   P = DFFE8B7E72E5CFED   C = 200174818D1A3012

will do. I found that by a randomized search after about $2^{34}$ DES operations, which tends to confirm the order of magnitude of the $2^{32}$ stated in the question.

Explanation:

For $i\in[1,16]$, note $L_{i-1}$ and $R_{i-1}$ the 32-bit contents of the $L$ and $R$ registers before encryption round $i$; note $R_{16}$ and $L_{16}$ the output of the last round after a swap (even if that swap is undone by an extra final swap, or equivalently is not done); note $K_i$ the 48-bit sub-key for round $i$. We have $L_i=R_{i-1}$ and $R_i=L_{i-1}\oplus F(E(R_{i-1})\oplus K_i)$, where $E$ is the expansion, and $F$ represents the S-boxes and permutation $P$ combined.

For the four keys $K$ 01FE01FE01FE01FE, FE01FE01FE01FE01, 1FE01FE00EF10EF1, E01FE01FF10EF10E, it holds that $K_i=\overline{K_{17-i}}$.

If it happens that $L_{8}=\overline{R_{8}}$, using that $E(\overline X)\oplus \overline{K_i}=\overline{E(X)}\oplus \overline{K_i}=E(X)\oplus K_i$, it follows that the input of function $F$ (S-boxes and permutation $P$) at rounds 8 and 9 are the same, thus their output are the same. By induction we get that the input of $F$ at round $i$ and $17-i$ are the same, and $L_i=\overline{R_{16-i}}$. Thus $L_{16}=\overline{R_0}$ and $R_{16}=\overline{L_0}$, thus $E_K(P)=\overline P$ for the $P$ corresponding to $L_0$ and $R_0$.

We could efficiently construct $2^{32}$ plaintexts $P$ with that property by performing the last 8 rounds of decryption and final permutation of DES, starting from the $2^{32}$ values of $L_{8}=\overline{R_{8}}$.

Unsettled: does there exist a DES key $K$ with more than $2^{32}$ anti-fixed points?


Using bad generator in ElGamal Encryption Suppose Alice chooses a random Prime $p$ and a random private Key $a \in \mathbb{Z}^*_p$. By accident, she also chooses a random number $g \in \mathbb{Z}^*_p$, which is not a generator of $\mathbb{Z}^*_p$ and therefore

$$\langle g\rangle \subset \mathbb{Z}^*_p$$

as opposed to $\langle g\rangle = \mathbb{Z}^*_p$, which would yield a valid key. Alice then computes $A \equiv g^a \pmod{p} $ and publishes the Tuple $(p,g,A)$ as her public key.

Bob now encrypts a message $M$ using Alices public key by computing

$$C_1 = g^b \pmod{p}$$
$$C_2 = M \cdot A^b \pmod{p}$$

Is it possible for an attacker (Eve) to distinguish a “real” ciphertext $(C_1,C_2)$ from a random ciphertext $(Z_1,Z_2) \stackrel{$}{\longleftarrow} \mathbb{Z}^*_p$ with significant advantage (say $Adv \geq \frac12$)?

Edit: I guess it should be enough to show, that the ciphertext cannot be random, if

$$\langle g \rangle \neq \langle C_1 \rangle \quad(\text{or $Z_1$, respectively})$$

But how can Eve check for this property efficiently? Can someone point me in the right direction here?

Edit: A real-world situation where this flaw occurred was recently found in the PyCrypto Library

The attacker can distinguish $\langle C_1, C_2 \rangle$ from a random pair if the attacker knows a value $q < p-1$ such that $g^q = 1 \mod p$.

Here's how the distinguisher would work: he simply computes $C_1 ^ q$ and checks to see if that value is 1.  If this $C_1$ corresponds to a valid ciphertext, then that value will always be 1.  If this $C_1$ is part of a random pair, then the value will be 1 with probability $q/(p-1) \le 1/2$ (remember, $q$ will always be a divisor of $p-1$).

On the other hand, just because we show distinguishability against a particular random source doesn't mean that we have shown that it is insecure.  In this case, that would depend on what is the order of $g$ (and whether it is "smooth", that is, has no large prime factors).  If the order of $g$ is smooth, then solving the discrete log problem is easy, and hence the system is insecure.  On the other hand, if the order of $g$ has a large prime factor $q$, I believe that it is still safe.


Which QKD schemes don’t utilize an authenticated classical channel? This Wikipedia article discusses one drawback of quantum key-distribution:

The main drawback of Quantum Key Distribution is that it usually relies on having an authenticated classical channel of communications. In modern cryptography, having an authenticated classical channel means that one has either already exchanged a symmetric key of sufficient length or public keys of sufficient security level. With such information already available, one can achieve authenticated and secure communications without using QKD, such as by using the Galois/Counter Mode of the Advanced Encryption Standard. Thus QKD does the work of a Stream Cipher at many times the cost. Noted security expert Bruce Schneier remarked that quantum key distribution is "as useless as it is expensive".

My question is, how universal is this drawback?  Wikipedia says “usually”, so are there some quantum key distribution schemes which do not rely on an authenticated classical channel of communication?
And if so has any such scheme been practically implemented?

Which QKD schemes don’t utilize an authenticated classical channel?

None that can be trusted. All secure Key Distribution systems, quantum or not, require an authenticated channel at setup, before the distributed key can be trusted. This is typically a classical channel, like a person carrying (before the Key Distribution occurs) a paper with some secret scribbled on it in an opaque envelope, or (after the fact) a telephone line to compare a public value, with the tone of the voice expected to provide proof of origin.
A Key Distribution system not using an authenticated channel would allow Alice and Bob, who never met, to agree on a secret key. Alice would be using a gismoA, Bob a gismoB, both of public design. And when gizmoA and gizmoB are connected in some way (perhaps an optical fiber) not under scrutiny by Alice, Bob, or their delegates, the gismos would do their thing and output a secret key identical on both sides.
That can't be: the "public design" requirement allows an adversary to build gismoA2 and gismoB2 functionally identical¹ to the originals. The "connected in some way not under scrutiny" requirement allows the adversary to connect gismoB2 to gismoA and gismoA2 to gismoB. From the standpoint of Alice and Bob, nothing has changed: their gismoA and gismoB output a key. However gismoB2 outputs the same as gismoA, and gismoA2 outputs the same as gismoB, and the adversary knows these outputs. Thus the "secret" requirement is not met.
As Charles H. Bennett and Gilles Brassard put it in their "BB84" paper Quantum cryptography: Public key distribution and coin tossing generally regarded as foundational to KQD:

(QKD) achieves one of the main advantages of public key cryptography by permitting secure distribution of random key information between parties who share no secret information initially, provided the parties have access, besides the quantum channel, to an ordinary channel susceptible to passive but not active eavesdropping.

Accordingly, all serious articles on QKD, and companies selling QKD gismos, acknowledge they rely on an authenticated classical channel of communication. Many additionally require that channel to provide secrecy (that's a security requirement if that channel is used before QKD takes place). However, that channel needs only be used once at setup, or perhaps when the gismos get out of sync due to errors or attacks. For example, ID Quantique's 2020 whitepaper states that it is made

use of a pre-established secret key in the emitter and the receiver, which is used to authenticate the communications on the classical channel. This initial secret key serves only to authenticate the first quantum cryptography session. After each session, part of the key produced is used to replace the previous authentication key.

This is universal. All serious attempts replace the authenticated classical channel by another authenticated channel of some sort. One line of research DHL a Physicaly Unclonable Function, Fedex entangled photons, or UPS trapped smurfs. Another literally aims a single-photon/laser source towards a satellite, reasons that no other satellite can realistically get in there and play satellite-in-the-middle (per laws of physics unchanged since Kepler), discount the possibility of drone-in-the-middle² as too far-fetched, and hopes there's no fog.

¹ "Functionally identical" is not the same as indiscernible. There may be (e.g. quantum) PUFs that insure gizmos are discernible, but "public design" implies that how to make discernible gizmos functional and interroperable is public.
² That reportedly works against printers, but admittedly few use QKD.


Converting a 5-bit s-box to its bit-sliced format I'm currently trying to convert a 5-bit sbox (the one from this cipher: http://primates.ae/wp-content/uploads/primatesv1.02.pdf) to its bit-sliced format (i.e. to a boolean network).

Most papers only address techniques for converting up to 4-bit s-boxes into their bitsliced format.

I have done some work trying to brute-force my way to the results, as a 5-bit s-box does not seem as much, this however still proved tricky, as their is in the end an infinite possibility og AND, NOT, OR and XOR that you can do on the 5 input bits... Is there any accepted/known way of doing this, or does it come down to trying to bruteforce different combinations till a matching one is found? (I hope not, as I have no guarantee on it being the optimal then).

I have considered trying to make truth tables and synthesize the logic network from them. I'm not sure this is the way to go though.

A recent paper presented at FSE'2016 [1] addresses this exact question. In fact, it even provides a bitsliced implementation for the S-Box you are interested in Section 4.

In summary: you first encode the existence of a bitsliced implementation as a SAT problem, use an off-th-shelf SAT-solver to solve it and finally retrieve the bitsliced encoding from the output of the SAT-solver.

[1]: http://eprint.iacr.org/2016/198.pdf "Optimizing S-box Implementations for Several Criteria using SAT Solvers", Ko Stoffelen, Proceedings of Fast Software Encryption 2016


How hard is the following q-Strong Diffie-Hellman problem? From On the $q$-Strong Diffie-Hellman Problem, the following problem is well-known to be hard.

  For an randomly chosen element $x \in \mathbb{Z}_p$ and a random generator $g \in \mathbb{G}$, the exponent $q$-strong Diffie-Hellman Problem is, given $(g, g^x, g^{x^2}, \dots, g^{x^{q-1}}) \in \mathbb{G}^{q}$ to compute an element $g^{x^q} \in \mathbb{G}$.

Here, I want to ask how hard is the following problem:

For an randomly chosen element $x \in \mathbb{Z}_p$ and a random generator $g \in \mathbb{G}$, given $(g, g^x, g^{x^2}, \dots, g^{x^{q-1}}, g^{x^{q+1}}, g^{x^{q+2}}, \dots, g^{x^{2q-2}}) \in \mathbb{G}^{2q-2}$ to compute an element $g^{x^q} \in \mathbb{G}$.

Can it be reduced to other well-known Diffie-Hellman problem?

So I found that [1][2] shows that the hard assumption of the following problem holds in generic bilinear groups.

  $\ell$-BDHE problem: given $(h, g, g^{\alpha}, g^{(\alpha^2)}, \dots, g^{(\alpha^\ell)}, g^{(\alpha^{\ell+2})}, \dots, g^{(\alpha^{2\ell})}) \in \mathbb{G}^{2\ell+1}$, output $e(g,h)^{(\alpha^{\ell+1})} \in \mathbb{G}_T$.

And it is trivial to see that $\ell$-BDHE can be reduced to the problem described in the question.

However, I am still wonder whether there is a better reduction without introducing bilinear pairing.

Update: It seems that [3] uses the same technique as the one in the above to prove the hardness.

[1] Hierarchical Identity Based Encryption with Constant Size Ciphertext

[2] Collusion Resistant Broadcast Encryption With Short Ciphertexts and Private Keys

[3] An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials


How does recovering the public key from an ECDSA signature work? It is possible to recover the public key from an ECDSA signature values $(r,s)$?

Please explain how this works.

Actually, it is not possible to uniquely recover the public key from an ECDSA signature $(r,s)$.  This remains true even if we also assume you know the curve, the hash function used, and you also have the message that was signed.

However, with the signature and the message that was signed, and the knowledge of the curve, it is possible to generate two public keys; one of which will be the public key corresponding to the private key used.

Here's how that works:

First, you find the two points $R$, $R'$ which have the value $r$ as the x-coordinate $r$.
You also compute $r^{-1}$, which is the multiplicative inverse of the value $r$ from the signature (modulo the order of the generator of the curve).
Then, you compute $z$ which is the lowest $n$ bits of the hash of the message (where $n$ is the bit size of the curve).

Then, the two public keys are $r^{-1}(sR - zG)$ and $r^{-1}(sR' - zG)$

It is easy to verify that if you plug either of these values in the ECDSA signature routines as the public keys, the signature validates.


Public key encryption schemes and security of an uncommon use Suppose that we use a public key encryption scheme by keeping the public key secret. Can we consider a public key encryption scheme at least as secure in this private-key setting, when compared to the normal use?

Assuming that you're using the same definition of "secure" for both schemes1, then yes, it is indeed trivially true that modifying a public key encryption scheme by restricting the distribution of the public key will yield a scheme that is "at least as secure" as the original.

Specifically, consider an attacker who wants to break the modified scheme.  We don't really care what the attacker wants to do (although, usually, someone attacking an encryption scheme would want to extract some information from an encrypted message), just that it's something that the modified (and the original) scheme is designed to prevent.  There are two possible cases:

Either the attacker knows the public key, or can somehow determine it from other information that they have.  In this case the two schemes are, from the attacker's viewpoint, equivalent, and therefore equally secure.
Alternatively, the attacker may not know the public key.  In this case, if they were given the public key, that would make the two schemes equivalent from their viewpoint.  Since giving the attacker extra information cannot make the scheme harder to break, that means that the modified scheme cannot be easier to break than the original.

Therefore, in neither case can the modified scheme be easier to attack than the original.

It is, however, quite possible for the two schemes to be equally secure.  For many real world public-key encryption schemes that is indeed likely to be the case, if only because such schemes are usually not designed to hide the public key in any way, and thus may allow attackers to easily learn it.

In general, public-key crypto is designed with the assumption that the public key is public, and trying to make it otherwise rarely if ever yields any significant benefit.  While it may be possible to repurpose some crypto algorithms originally intended for public-key encryption for other uses, in some of which the "public key" might in fact need to be kept secret (as e.g. in this question I asked before), that generally invalidates much of their original security proofs and requires reanalyzing the whole algorithm from the ground up with the new assumptions on what's public and what isn't.

1) Specifically, the definition of what would constitute a successful attack should be the same for both schemes, and should not make reference to anything that would differ between the schemes.  In particular, for the purposes of this argument I'm excluding "the attacker learns something that isn't already public" as an admissible definition of a successful attack, since the two schemes differ in what they consider to be public information.


Independently choose lanes and threads param on Argon2 I'm researching on using Argon2 on a JavaEE server-side application.

I'm a bit reluctant to set the parallelism parameter larger than 1 on a JavaEE environment where threads are supposed to be managed by the application server etc, etc.

One idea is to use the low-level API and set lanes to -lets say- 4 and threads to 1.

In the future, I could set threads to 4 to speed things up or revert back to 1 thread if things don't work out well.

I've done some basic examples with the reference implementation and I've seen setting lanes/threads independently to be working as expected.

Is there any scenario where this would produce incorrect results?

Is there something conceptually "wrong" or "insecure" on setting a high value on lanes but not utilising it with multiple threads? Like giving some advantage to an attacker?

Thanks in advance.

There is nothing fundamentally wrong about using fewer threads. It does mean you may not be able to make use of all the memory bandwidth you have, resulting in memory being filled a bit more slowly, but it will not damage the memory-hardness of Argon2. This is not ideal for you as the defender because parallelism is not meant to increase the number of operations you can perform in any given timeslice, but to increase the memory fill rate. A single hardware thread on an x86 CPU even at its maximum clock rate cannot saturate the memory bus. It takes multiple cores to do that. In fact, because it's the fill rate that matters, using more than a few threads on most x86 hardware will actually not speed things up!

The attacker is bound not by the computation rate (in fact, the compression function in Argon2 is very simple), but by the total amount of memory required to calculate the hash. Forcing them to use more execution units would not increase the total cost of the attack nearly as much as a bit more memory.

Benchmarks of single-pass Argon2d using an Intel i7-4500U processor from the paper:

Threads  Cycles/byte  Bandwidth (GB/s)
1        1.3          2.5
2        0.9          3.8
4        0.6          5.4
8        0.6          5.4


OTP same message encrypted twice (with different keys) Lets say we have a message $m$ that we encrypt with two keys $k_1, k_2$ such that $k_1 \ne k_2$. This will produce two ciphertexts $c_1, c_2$ such that $c_1 = m \oplus k_1, c_2 = m \oplus k_2$.

The attacker managed to get the two ciphertexts and also has the knowledge that both ciphertexts $c_1, c_2$ represent the same message. Does this knowledge lower the OTP security in any way?

The most an attacker can find out is that $c_1 \oplus c_2 = m \oplus k_1 \oplus m \oplus k_2 = k_1 \oplus k_2$. But since both $k_1$ and $k_2$ are fully random and not reused it won't help the attacker to find either $k_1$ or $k_2$. Basically each key stream is still encrypted with the other key stream.

Note that for OTP $k_1 \ne k_2$ is an invalid constraint; the keys should be fully independent of each other. For instance, if you have $k_1 = C | 0$ and $k_1 = C | 1$ where $C$ is a constant then $k_1 \ne k_2$. Those keys do however not represent valid OTP key streams; those must be fully random. Fully random also means that $k_1 = k_2$ is a possibility. If you know that the message is always identical then $k_1 \ne k_2$ means that if you get $c_1 = c_2$ that the messages differ.

So given the invalid constraint that $k_1 \ne k_2$ is true, then the answer of the question is yes - the security is lowered. If the keys are truly random then the answer is no.


Which gives better deterministic encryption SIV or Plain ECB mode? Lets say , if we encrypt a plain text message $msg$ with key $key$ in below two ways. Which is the below would give better deterministic encryption and why ?

AES-ECB($key$ , $msg$)
SIV($key$, NIL , $msg$) where associated data is NIL.

I could not make out much from Rogaway and Shrimpton's paper on "Deterministic Authenticated Encryption" which introduces Synthentic IV (SIV) mode.

Edit: Here $msg$ is same as single block .

Both:

Secure deterministic encryption for one-block messages.

ECB:

No expansion for block-sized messages.
Faster.

SIV:

Authentication.
Works for messages of any size.


Advantages of Montgomery Ladder-based Scalar Multiplication I do not quite understand what the greatest advantages are of using the Montgomery ladder algorithm for scalar multiplication?

Can someone help me out?

Synthetically, the advantages of the Montgomery ladder are that it is simple and fast.

If you look at X25519, the Diffie-Hellman algorithm applied to Curve25519 and described in RFC 7748, you will see that for an n-bit Montgomery curve, multiplying a point with an n-bit scalar, you will need to compute about 10n multiplications of field elements. In more details, there are n iterations of a loop, each of them implying:

4 multiplications with two varying field element values
4 squarings
1 multiplication with a fixed and usually small constant (called a24 in the RFC)
1 multiplication with the base point "u" coordinate (fixed throughout the algorithm, but may vary between invocations)

To that, a final field inversion must be added, which is normally done with a modular exponentiation. If the field modulus is well chosen, that inversion will add a bit more than n squarings. So the value of "10" given above is an estimate that depends on how squarings and multiplications by constants can be optimised; in practice, overall cost will be between 8n and 12n.

Now, with "classic" curves with Weierstraß equation y2 = x3 - 3x + b (for some constant b), the usual implementation method is to use Jacobian coordinates, in which a point (x, y) is represented by the triplet (X, Y, Z), with:

x = X / Z2
y = Y / Z3

With that representation, a point doubling costs 8 multiplications (4 of them are squarings), while a point addition which is not a doubling uses 16 multiplications (4 of which being squarings). A basic double-and-add algorithm would then need an average of 16 multiplications per multiplier bit, but in fact 24 if you want a constant-time implementation (which is recommended), therefore not leaking information about which scalar bits are 0 and which are 1. An extra n multiplications in total are to be added, for the final inversion of Z to get back to affine coordinates (there again, classically with a modular exponentiation).

Things can be sped up with a window optimisation in which, for base point P, you precompute small multiples of P; for instance, with a 5-bit window, you compute kP for all k from 0 to 31 (which involves 15 doublings and 15 point additions), and then you only make one point addition every five doublings. This requires some extra implementation care (for instance doing a constant-time lookup in the window, if constant-time execution is sought) but can bring down overall cost to about 13n field multiplications, i.e. 30% more than for a Montgomery curve. Some further speedups are possible when the base point is known in advance, as is the case for the first half of Diffie-Hellman (using the conventional base curve), because the addition formulas in projective coordinates when one of the point has Z = 1 (called "mixed additions") are a bit simpler (11 multiplications instead of 16).

So, in practice, Montgomery curves get a speed advantage, but not really because they are Montgomery curves:

As shown above, the advantage is slight (about 30%). It must be said, though, that implementation of Montgomery curves is much easier and it shows up as smaller code and less room for tricky bugs.
A much bigger speedup of Curve25519 over NIST curve P-256 comes from the definition of the base field. NIST P-256 uses integers modulo p = 2256 - 2224 + 2192 + 296 - 1. Curve25519 uses p = 2255 - 19. Both are integers chosen because they allow for faster modular reduction; however, NIST's choice is optimised for computer hardware of the late 1980s, while Curve25519 shoots at mid-2000s hardware, with much cheaper multiplication opcodes, and superscalar architectures. On modern hardware (and this includes modern "small" embedded CPU), the latter choice seems to be roughly twice faster than NIST's modulus.
An extra interesting feature of Curve25519 is that it is not one curve, but two curves. Every possible source value for the "u" coordinate will define either a point on the curve, or on the "twisted" curve, which is also cryptographically good (its order is a big prime multiplied by a very small cofactor). This allows X25519 to be safe without performing any validation of the incoming point, which again makes for simpler and shorter code. There again, that feature is not intrinsic to Montgomery curves; classic curves in short Weierstraß form can exhibit the same property, but the NIST curve does not.
Conversely, there is a complication that comes from Montgomery curves, which is that their order is necessarily a multiple of 8; hence, it cannot be prime. This means that a valid curve point is not necessarily a point on the prime-order subgroup on which we perform most operations. The X25519 specification accommodates that issue by forcing scalars to be multiple of 8. When Curve25519 (or its derivative edwards25519) is used in other, more complex cryptographic protocols, this property can be problematic and must be side-stepped appropriately (usually by the same methods of multiplying things by 8 or forcing multipliers to be multiple of 8). In a way, this is a trade-off: implementation is more simple, but at the expense of a bit of extra complexity in the protocols.

To summarise: the Montgomery ladder makes for a somewhat faster algorithm which is easier to implement, especially if you aim for constant-time code. But modern standard curves, that are Montgomery curves, also come with a few extra features that are quite nice to have, and yield even greater speedups; these extra features are not reserved to Montgomery curves, but NIST curves don't offer them because they had not been invented or at least noticed at that time.

As an historical note: Montgomery curves were first invented and used for the elliptic curve factorization method in which raw speed is of paramount importance, but the curves themselves don't have any actual cryptographic relevance.


EC equivalent for RSA-OAEP I have some questions regarding aforementioned subject:

Is there a EC equivalent of RSA-OAEP key transport/encryption algorithm ?
Is ECIES-KEM sufficient ?

Short answer,
 - yes
 - yes
To be honest I don't really know how to give a longer answer.
He are some pointers
http://www.secg.org/download/aid-780/sec1-v2.pdf
http://digital.csic.es/bitstream/10261/32674/1/Gayoso_A%20Comparison%20of%20the%20Standardized%20Versions%20of%20ECIES.pdf


What is the difference between SHA-3(Keccak) and previous generation SHA algorithms? SHA-1 and SHA-2 share the same structure and mathematical operation as their predecessors - SHA-0 and MD5.  Both SHA-0 and MD5 have been broken. This is one of the main reasons why SHA-1 is considered insecure and is being phased out for SHA-2.

NIST announced in 2007 a competition to produce the next generation NIST hash function: SHA-3.

What is the major difference in structure and mathematical operation between the previous SHA-1 and SHA-2 functions and SHA-3?

They are all hash functions. Apart from that, they are structurally quite different. The SHA family (SHA-0, SHA-1, and the SHA-2 functions such as SHA-256 and SHA-512) use the Merkle-Damgård construction, around an internal permutation which happens to be an extended Feistel network. Low-level primitives include boolean bitwise operations, and addition over 32-bit or 64-bit integers.

In SHA3, the structure is that of a sponge function, which is quite different. Moreover, the inner permutation is not a Feistel network; low-level primitives are boolean bitwise operations over 64-bit words, but not additions. This avoidance of operations that involve carry propagation helps a lot with performance on hardware implementations (FPGA, ASIC).


Finding RSA private exponent with a chosen ciphertext attack? Let's say there's this blackbox app that has a known modulus $N$, private exponent $e$, and takes ciphertext $C$ encrypted against $N$ and $e$ input and outputs plaintext $M$.

The encryption is done via textbook RSA (i.e. $C=M^e\bmod N$ and $M = C^d\bmod N$). Is there any way, using some form of CCA or whatever the sort, to recover the primes/private exponent of the RSA key? I know CCA is traditionally used to find the plaintext rather than the key, but since the app, in this case, decrypts the message for  us, there is no need. Is it even cryptographically possible?

Is there any way, using some form of CCA or whatever the sort, to recover the primes/private exponent of the RSA key?

TLDR: No, save for a breakthrough or a leak.

Whether $N$ can be factored (in time polynomial to $\ln N$ with non-vanishing probability) given $(N,e)$ and an RSA decryption blackbox (assumed free of side-channel leakage) is one of the most thought at open problem in cryptography, and to a lesser degree in number theory.

Proving either yes or no would make the news, even if restricted to an heuristic algorithm, plausible mathematical hypothesis, a polynomial of degree so high that the method is impractical, and a particular choice of $e$. I'm thinking of $e=3$, or $e=N$ (the Clifford Cock's cryptosystem, which predates RSA), or on the contrary random odd $e\in[0,N])$.

A proven fact is that extracting any working private exponent $d$ of size upper-bounded by a polynomial in $\ln N$ allows to extract a factor of $N$, at least heuristically and in heuristic polynomial time, and in practice allows to factor $N$.

Another experimental fact is that if we probe a physical implementation  of such a black box, that has a public design, long enough, with sensitive-enough sensors, and pour enough brainpower and a little CPU power on the thing, we manage to extract $N$. This is one of several understandable reasons why such black boxes are not made of public design.

BTW: experimental cryptanalysis with quantum sensors is the one unobstructed way for experimental cryptanalysis to go quantum.


Does TLS have to provide both confidentiality and authenticity? I'm working on a project that uses OAuth. In the OAuth RFC it says many times that communication between the authentication server and the client should be with the use of TLS. However, in the project I'm looking at that uses OAuth, they say that the channels they use are only authenticated, not confidential. When looking at the TLS tag here, it says that TLS is both confidential and authenticated. But when looking at wiki, it looks like it can be either or? Can someone maybe clear up whether TLS can provide authenticity without providing confidentiality?

TLS can provide only authenticity without confidentiality.
To do this you need to use the *_WITH_NULL_* cipher suites. They're disabled by default in most libraries.

However, I strongly recommend against using them.
You've really nothing to lose when using encryption and if you don't there may be privacy concerns.


Using multiple secret keys I have two secret keys. One is a secret key generated by OpenSSL (primary secret key). Second key is generated by performing one way hash operation to GPS co ordinates and time parameters (geo secret key). Now I want to combine this two keys to be used for an AES encryption. I have two options.

Encrypt twice by using two keys.
XOR the two keys derive a single key and use it for encryption.

The first option will be bit expensive since there will be two encryption operations. Although the second option will be less expensive I am not sure whether it is secure or not. Will the second option make the finale encryption key vulnerable? Will it severely affect the randomness of the finale key in a way that it is not usable?

More details about my requirement: I want to decrypt a message successfully only when the device is in a specific location. So I am deriving a second key based on the GPS data. But location and time cannot be kept secret. So I need to know whether will it reduce the randomness of my finale key due to the XOR operation done between Primary secret key and Geo secret key.

You elaborated that your goal is to make it possible to decrypt a message successfully "only when the device is in a specific location".

Great goal, but yeah, well, the particular scheme you describe in your question ain't gonna work. Someone who is not physically at the specific location, but who knows where the specific location is, can still infer the key and decrypt the ciphertext.  This is a fundamental flaw, and it's not something you can fix by sprinkling on a KDF or multiple keys.  It doesn't matter how many keys you have or how you combine them.  Sorry to break it to you, but your scheme is not secure, and it cannot be easily repaired.  You're asking the wrong question: your whole approach is flawed.

There's been academic work on this sort of problem (e.g., by Dorothy Denning), but it's a much harder problem than you seem to realize, and the resulting schemes look very different.  One has to find some source of unpredictable entropy that is visible to anyone who is at the specified location at the specified time, but that is not known or predictable to anyone else.  That's very challenging.

For the state of the art in this area, see the following papers:

Location-Based Authentication: Grounding Cyberspace for Better Security.  Dorothy Denning.  Computer Fraud & Security, Feb. 1996.
On location-restricted services. Eran Gabber and Avishai Wool. IEEE Networks, 13(6):44-52, November/December 1999.

There may be more other work; I recommend that you do a literature search to check.


Practical Threshold Signatures In Practical Threshold Signature it says that there is a requirement in which the RSA public exponent $e$ must be more than $l$. $l$ in this case is the number of players in the threshold group.
My question is: Why is there a constraint that the public exponent must be larger  than the number of players?
In my case, my public exponent must be 3 (due to limitation on another component), hence the number of player can only be 2.
Thanks.

I am not too familiar with this paper, but there is (at least) the following reason. They define $\Delta = l!$, then require (right after equation 6) that $1 = \mathsf{gcd}(e', e) = \mathsf{gcd}(4\Delta^2, e) = \mathsf{gcd}(4(l!)^2, e)$.
This is not possible if $e \leq l$ (as then the GCD is $e\neq 1$).


Bitwise operation question with shifting involved I am trying to find a value of X (32 bits) such that ((X XOR a)+b)<<3 = (X+c) XOR d. <<3 means shift left 3 bits. a,b,c and d are all constants which have been determined elsewhere.

However, I don't want to brute force the full 2^32 combinations. I was told solving it 3 bits by 3 bits from the MSB on the left hand side would help however this feels off to me.

Say I fix the first 3 MSB. This with the left shift that means that the 3 LSB will be fixed, leading to the next 3 bits and so on. It seems to me that fixing any 3 straight bits will end up with all of X being solved. Are 8 tries really all I need to solve this equation?

There's also the possibility that the values of a,b,c and d at the time might create an unsolvable equation too. If I don't find it within the 8 (or more tries if my above paragraph is wrong) it's safe to ditch this and try new values of a,b,c,d right?

Actually, you want to solve it from the LSB side.

First, solve for the 3 LSBs of X; we can see that the 3 LSBits of the left hand side of ((X XOR a)+b)<<3 = (X+c) XOR d doesn't actually depend on X (and there's no propogation anywhere from the higher order bits of X, so they can be ignored for now), so it's effectively a simple equation, easily solved.

Then, solve for the next 3 LSBs of X; again the 6 LSBits left hand side doesn't depend on those bits (it does depend on the 3 LSBits of X, but we already know those); again, that portion of X is easily solved.

So, just keep on iteration until we have all the bits of X.

One thing we can see from this process is that there is always exactly one solution for X for any (a, b, c, d) values.


Should RSA primes p and q differ in length by "a few digits"? When generating RSA keys in the original RSA paper it is stated:

  to gain additional protection against sophisticated factoring algorithms, p and q should differ in length by a few digits

Why is this? How many is "a few digits"? And how important is this?

The quoted recommendation is generally considered obsolete in the context of RSA with secure parameters, and is either disregarded, or replaced by asking that $\left|p–q\right|>2^{(n/2)–100}$ where $n$ is the number of binary digits for $N=pq$. This modern rule was in ANSI X9.31 (1998), and is still in FIPS 186-4 (2013), appendix B.3, criteria 2(d).

This quoted recommendation, and its modern counterpart, are intended to make $p$ and $q$ different enough to guard against Fermat factorization, and improvements thereof. The basic Fermat factorization technique enumerates integers $b$ from $0$ onward, stopping when $N+b^2$ is a square $a^2$, revealing $p$ and $q$ as $(a+b)/2$ and $(a-b)/2$ (within order). Numerous improvements exist allowing to skip some $b$, and reducing the cost of the squareness test.

However, with $p$ and $q$ of equal size and $n\ge512$, but $p$ and $q$ otherwise mostly random, all known improvements of Fermat factoring have fully negligible odds to succeed (because the number of $b$ to enumerate by the basic Fermat factoring method is $\left|p–q\right|/2$, which is higher than $2^{212}$ with odds better than $1-2^{-40}$, and none of the known improvements lowers the $2^{212}$ steps to something workable). Notice that $n=512$ is so small that it provides only very limited security (see this), and that the pointlessness of trying Fermat factorization (compared to other factorization techniques) grows when $n$ grows.

The quoted recommendation only makes sense for toy examples of RSA, say when $p$ and $q$ both are about 9-10 decimal digits (thus $n\approx64$). And then a few digits can safely be taken as 2 digits; or even (in decimal) reduced to a single digit, as long as the leading digit of the largest prime is not 1.

Rules in ANSI X9.31 and FIPS 186 prescribe (in the interest of interoperability of devices using RSA private keys they did not generate) that $p$ and $q$ are primes in range $[2^{(n-1)/2}\dots2^{n/2}]$, implying that they have the same number $n/2$ of binary digits (and that their number of decimal digits differs by at most one, if at all). This goes straight against the wording of the quoted recommendation. According to my memories of Robert Silverman's account: the requirement that $\left|p–q\right|>2^{(n/2)–100}$ (for $n\ge1024$) was introduced (although technically not needed) to please the ANSI X9.31 standard's committee, sponsored by bankers, who wanted a simple rebuttal to a court argument on the tune of: "I claim that my client did not produce that signature! One simple explanation is that the modulus has been factored. An expert has testified that Fermat factoring, known since the 17th century, potentially could do that, and allow such forged signature. No precaution against it was taken! Whoever carelessly specified that signature system must bear the consequences!".


"Double Encryption" using the same cipher? When it comes to the words "double encryption", I cringe.  What I see is the following scenario play out.

Someone has plain text and they encrypt it with the AES cipher using the 14 round variant, so AES256.  Then they run that encrypted information, through again another 14 rounds thinking it is double encrypted.

In my mind, I think of it differently.  When I think of encryption and doubling it, I believe the strength of encryption, in the case of AES, as being tied to the number of rounds through the algorithm. So in this scenario, I think of double encryption as 28 rounds through the AES cipher.

In short - AES(28 round) > AES(14 round) + AES(14 round)

I have read some whitepapers on cascading encryption, but they referred to using two different ciphers, not the same cipher twice.

Is there anyone able to shed some light on this for me?

When I think of encryption and doubling it, I believe the strength of encryption, in the case of AES, as being tied to the number of rounds through the algorithm.

I don't believe that's the best way to think of things.
The strength of the encryption really is 'how much work does an attacker need to do to perform the attack'.
For a cipher, there are two strategies:

We can just go through all possible key values, and see which one 'works'

We can rely on cryptographical weaknesses within the cipher itself

Increasing the number of rounds can plausibly (not always, but in practice, appears to) make the cryptographical weaknesses within the cipher harder to exploit, but (unless increasing the number of rounds also increases the number of key bits), doesn't do anything to slow down brute force attacks (apart from a constant factor).
As far as we know, there are no known cryptographical weaknesses in
AES-256 (apart from some related key attacks, typically not applicable), and so adding more rounds doesn't increase security in any meaningful sense.
Now, it would look like running the text through two separately keyed AES-256 would double the number of key bits, and so significantly increase security.  However, it turns out that there is a better-than-bruce force attack; this involves encrypting the plaintext with all possible AES-256 keys, decrypting the ciphertext with all possible AES-256 keys, and then searching for a match.
Of course, the amount of work involved is ridiculous; it will never be the case that anything involving $2^{256}$ operations will be feasible; this can be shown by thermodynamics and the minimal amount of energy needed to perform any operation.
This implies that, barring a cryptographical advance that allows us to break AES-256 with significantly less than $2^{256}$ operations, it'll be safe.
Which leads us directly to the next topic:

I have read some whitepapers on cascading encryption, but they referred to using two different ciphers, not the same cipher twice.

This potential cryptographical weakness is precisely why people use distinct ciphers.  There might be a weakness in AES-256 that makes the cipher significantly weaker than our current understanding; however, if we perform AES-256 encryption, and then (say) Camellia-256 encryption, then the resulting cipher is strong unless both AES-256 and Camellia-256 are weak.  It is possible that there is a weakness in one of the two ciphers; it is considered far less likely that both contain weaknesses.


Why ElGamal signature is insecure with nonrandom k? In ElGamal signature scheme like:

Keygen:
$\beta:=\alpha^a\bmod p$ where $\alpha$ and $p$ are large prime numbers. Public key is $(p,\alpha,\beta)$ and secret key is $a$.

Sign:
Choosing random $k$ such that $\gcd(k,p-1)=1$, calculating $r:=a^k\bmod p$ and $s:=k^{-1}\cdot(m-a\,r)\bmod(p-1)$; then we send $(m,r,s)$

Verify:
Calculating $v_1:=\beta^r\cdot r^s\bmod p$ and $v_2:=\alpha^m\bmod p$; then if $v_1$ and $v_2$ are equal the signature verifies.

In the booklet I'm reading for cryptography course it is said that if $k$ is non-random this signature scheme is insecure. What's the reason?

If we use constant $k$ in this scheme we can find the secret key like this:

We know $(m_1,r_1,s_1)$ and $(m_2,r_2,s_2)$ for two different plaintext, as k is constant $r_1=r_2=r$ so we have this equivalence:
$$s_1k-m_1\equiv-ar\equiv s_1k-m_1\ mod\ p-1 \Rightarrow (s_1-s_2)k \equiv m_1-m_2\ mod\ p-1$$

This equivalence has $d$ answer where $d=gcd(s_1-s_2,p-1)$, $d$ is usually small so we can find $k$ using brute force on $r\equiv \alpha^k\ mod\ p$.

Now we know $k$ we can caluculate $a$ using $a.r\equiv m_1-k.s_1$ equivalence. Number of answer for this equivalence is $gcd(r,p-1)$ by comparing $\beta$ and $\alpha^a$ we can find $a$.

Now we know secret key and sign every plain text we want and that's insecure.


On discrete logarithm problem The classic discrete logarithm problem is to find $x\in\Bbb Z_p$ such that we know generator $g$ of $Z_p$ and $p$ is a prime with $\frac{p-1}2$ a Sophie Germain prime and we are given $h\in\Bbb Z_p$ such that $g^x\equiv h\bmod p$ holds.

Suppose given $g^x\equiv h\bmod p$ we know how to generate $g^{x^{2^i}}\bmod p$ at every $i\in\Bbb N$ in $O((\log ip)^c)$ time at a fixed $c>0$ does it help to solve finding $x\in\Bbb Z_p$?

Also is it known how to generate $g^{x^{2^i}}\bmod p$ at every $i\in\Bbb N$ in $O((\log ip)^c)$ time at a fixed $c>0$?

Also is it known how to generate $g^{x^{2^i}} \bmod p$ at every $i \in \mathbb{N}$ in $O((\log ip)^c)$ time at a fixed $c>0$?

No, it is not known; that would immediately imply a polynomial-time method to solve the computational Diffie-Hellman problem, and that's better than what's currently known.

This problem is: given $p, g, g^x \bmod p, g^y \bmod p$, compute $g^{xy} \bmod p$.

Given such an Oracle, here is how we would solve it (and from here on in, everything is done $\bmod p$): first, we can compute $g^x \cdot g^y = g^{x + y}$

Then, we ask our Oracle to compute $g^{x^2}$, $g^{y^2}$, $g^{(x+y)^2}$ in $O((\log p)^c)$ time.

We then compute $g^{(x+y)^2} \cdot ( g^{x^2} \cdot g^{y^2} )^{-1} = g^{2xy}$

Then, we take the modular squareroot of $g^{2xy}$, that gives us $g^{xy}$

Every step above takes polynomial time.


Why doesn't the GCM spec use a more efficient multiplication algorithm? NIST SP 800-38D § 6.3 Multiplication Operation on Blocks describes a multiplication algorithm that, in my testing, appears to be a good amount slower then algorithm 2.40 (arbitrary reduction polynomials) in the Guide to Elliptic Curve Cryptography.

My question is...why? Does the algorithm described in NIST SP 800-38D provide better protection against timing attacks?

My question is... why?

There are a number of different algorithms that perform $GF(2^{128})$ multiplication, all with different trade-offs (speed on specific platforms, program size, memory usage, complexity, side channel resistance, etc).  NIST doesn't care which one you use, as long as you get the expected result at the end.

As for why NIST decided to put that specific algorithm as an example in the spec, well, I didn't write the spec, so I can't be certain.  My guess is that they decided on the goals of simplicity and clarity, and that algorithm was the best they could find that would meet those goals (whether it is actually simpler or clearer than algorithm 2.40 is, of course, debatable...)


If TDP exist then CCA-secure PKES exist? My cryptography slides describe several relations between cryptographic problems. I don't still have a good justification on the following:

  If trapdoor permutations exist then CCA-secure public key encryption schemes exist.

How is this justified?

The slides cite this article. I was wondering if there is a short explanation for this.

For the context of this answer I will assume that that the author meant to say doubly enhanced TDP, since that's the only path I can currently think of. (See Definition 7)

Constructing CCA secure encryption

The relevant construction is due to Dolev, Dwork, and Naor. It is based on a CPA secure public key encryption scheme, a one-time signature scheme and a non-interactive zero knowledge argument. We'll show how those are instantiated below.

The basic idea of the encryption scheme is that we have $2\ell$ public keys $(\mathsf{pk}_1^0,\dots,\mathsf{pk}_\ell^0)$ and $(\mathsf{pk}_1^1,\dots,\mathsf{pk}_\ell^1)$ of the CPA secure PKE, where $\ell$ is the length of the verification key of the one-time signature scheme. To encrypt a message, we then encrypt the message seperately under $\ell$ public keys, where at position $i$ whether $\mathsf{pk}_\ell^0$ or $\mathsf{pk}_\ell^1$ is used, is determined by the $i$th bit of a fresh verification key of the one-time signature scheme. We then prove using the NIZK that all ciphertexts are encryptions of the same message and finally sign everything with the one-time signature scheme.

The main ideas of the security proof are:

Since we have many encryptions of the same message (something enforced by the soundness of the NIZK), we can reduce to CPA security, while still being able to decrypt, because we can use one of the other keys.
Any new ciphertext queried to the decryption oracle either uses the same verification key, in which case the adversary would need to forge a signature. Or it uses a different verification key, in which case at least one ciphertext uses a different encryption key from the challenge ciphertext and we are able to use the corresponding decryption key for decryption.

It of course remains to instantiate all those building blocks.

The building blocks.

CPA secure PKE

If a family of trapdoor permutations $\mathcal{F}$ exists then, due to the Goldreich-Levin Theorem there also exists a family of trapdoor permutations with a hardcore predicate. Given a TDP with a hardcore predicate, a simple construction of CPA secure PKE for bits exists, where a a keypair consists of a description of an $f_i\in\mathcal{F}$ for the public key and the corresponding trapdoor for the secret key. A ciphertext is then simply $(f_i(r),\mathsf{hc}_i(r)\oplus m)$ where $r$ is a uniformly chosen element from $f_i$'s domain, $\mathsf{hc}_i$ denotes the hardcore predicate of $f_i$ and $m\in\{0,1\}$.

If necessary, this encryption scheme can be used to construct CPA secure encryption for longer messages by encrypting each bit seperately. The security follows via a standard hybrid argument.

One-Time Signatures

The construction of Lamport gives us an existentially unforgeable one-time signature scheme for fixed length messages from any one-way function. In particular the construction can be therefore be instantiated from a family of trapdoor permuations.

Noninteractive Zero-Knowledge Proofs

NIZK for $\mathsf{NP}$ can be constructed from doubly-enhanced trapdoor permuations. The construction essentially works by performing an $\mathsf{NP}$-reduction to the Hamiltonian Cycle problem and constructing an NIZK for Hamiltonian Cycle. In the original construction in Goldreich's Foundations of Cryptography: Volume 1, Basic Tools it is incorrectly claimed that the construction is instantiable from any TDP, this was corrected in the paper linked above.


Signature over MAC value for a random key Would it be possible to create a signature scheme like this:
$
\DeclareMathOperator{Gen}{Gen_{\Mac}}
\DeclareMathOperator{Mac}{Mac}
\DeclareMathOperator{Sign}{Sign}
\DeclareMathOperator{F}{F}
\DeclareMathOperator{H}{H}
$

$$k_d = \Gen$$
$$m_d = \Mac(k_d, M)$$
$$S = \big(k_d, \Sign(K_{priv}, m_d)\big)$$

So instead of a hash, you'd use a random key.

I know that $$H = \big(k_d, \Mac(k_d, M)\big)$$ is not necessarily secure as you'd give the adversary the ability to choose any key. However, in this case the result is signed as well.

If it isn't secure, are there ways to make it secure? For instance, I could imagine RSA that contains the $k_d$ and recovers it using message recovery. Or ECDSA where an additional hash is calculated over $k_d$ and $m_d$.

Primary goal is to make a faster signature generation by replacing a slower hash with a possible faster MAC such as GMAC.

Would it be possible to create a signature scheme like this:

As I understand it, your proposal is that the signature consists of the MAC key, along with the signed MAC value of the message.

In general, this would not be secure, for two reasons:

For many MACs, it is not difficult, if you know the key, to find a second message with the same MAC as an existing one.
It is not part of the MAC assumptions that it is difficult to find a second key and message pair that MACs to a specific value.

MACs that would not be secure due to these properties include CMAC and GMAC.

  If it isn't secure, are there ways to make it secure?

Well, if you limited yourself to, say, HMAC or KMAC, it would be secure (as long as you didn't truncate the MAC excessively); however that's largely because these two MACs are largely hashes (with some key bits sprinkled in), and signing a hash is safe.  These two MACs are, in fact, collision resistant, even if you select the key (which is a rather stronger assumption than is assumed by the standard MAC security properties).

On the other hand, if the goal is to use a faster MAC rather than a slower hash, this suggestion would help you a great deal.  The problem, in this case, with GMAC, is that if you know the key, GMAC doesn't actually give you any cryptographical properties; creating first preimages (for example) is actually quite easy...


Why does the verifier have to send a challenge in Shnorr protocol? In the Shnorr protocol where the prover wants to prove he has a witness $w$ for $g^w$ the following interactions happen:

the prover chooses a random $r$, calculates $y=g^r$ and sends $y$
the verifier sends a challenge $x$
the prover calculates $t=xw+r$ and sends it to the verifier
the verifier tests if $g^t=(g^w)^x.y$

My question is why the verifier sends a challenge. Would he be convinced if the prover just sends $t=r+x$ and the verifier tests if $g^t=g^w.y$? Plus $t$ won't reveal the witness.

my question is why the verifier sends a challenge, would he be convinced if the prover just sends $t=r+x$ and the verifier tests if $g^t=g^w \cdot y$  ?

That is, why doesn't the prover just send $t$ and $y$?  Well, anyone can pick a random $t$ and compute $y = g^t \cdot (g^w)^{-1}$.  Because $g^w$ is public, this can be computed by anyone, and so wouldn't serve as a proof of knowledge.

And, it is easy to find a solution to $g^t=(g^w)^x \cdot y$ (without knowing $w$), if you know the $x$ value before selecting the $y$ (and you suggested a constant $x=1$, hence the prover knows it up-front).  However, if you can find a solution for $g^t=(g^w)^x \cdot y$ for two different $x$'s, that's different; it's easy to show that with solutions to two different $x$'s (and the same $y$), we can recover $w$ (and hence someone who can do that must know $w$).  On the other hand, we can't just give out two solutions (as that means the verifier would then be able to deduce $x$).

So, what we do is get the prover to give a solution for an $x$ he cannot predict in advance; either he got extremely lucky (and he guessed the correct $x$ value when he generated $y$), or he does in fact know multiple solutions (and hence knows $w$).


Vulnerabilities in specifying the hash algorithm used for signature verification on a per-message basis Let's say that I have a 4096-bit RSA key and when I sign data, I typically use SHA-512. As far as I understand it, the hash algorithm used to sign/verify a message is specified in the message. If a hash algorithm is susceptible to collisions, then it doesn't matter how large my RSA key is, and signatures can be forged.

So what is to prevent someone from forging a signature by selecting MD5 as the hash algorithm used to "sign" a message?

To forge a message using a hash collision, you need to generate a signature (using that hash function to sign a "good" message); then that signature is also a valid signature for the "bad" message.

So, to prevent this from being a concern, you just never sign a message using MD5 as your hash function.  Yes, the attacker can generate a "good" and a "bad" message with the same MD5 hash, but unless he can convince you to sign the "good" message using MD5, that doesn't help him.  If you always use SHA-512 when you sign messages, that means that the attacker must find a collision in the SHA-512 hash function; we believe that's infeasible.


Can we use BLS as a VRF? Intuitively, it seems that the hash of a BLS signature could be used as a VRF as well. In a nutshell, BLS-Signature is the VRF output and the verification first checks the signature is valid, and then compute the hash over it to provide the VRF output. (Or similarly, one can provide H(BLS-Signature) as the VRF output and BLS-Signature as the VRF proof.)

Is this scheme a VRF ? Given a collision resistant hash function of course.
How would one would go about proving it ?

Yes, in the random oracle model, the hash of a BLS signature makes a VRF essentially as secure as the BLS signature scheme (provided the verifier accepts only the unique canonical encoding of each signature).

This works because BLS signatures are unique.  Fix a pairing $e\colon G_1 \times G_2 \to G_T$ on groups $G_1$ and $G_2$ of prime order.  For any fixed $A \in G_2$, the homomorphism $\phi_A\colon \sigma \to e(\sigma, A)$ is an injection (or the system is trivially insecure) because $G_1$ has prime order.  Let $B \in G_2$ be the standard base point.  A putative signature $\sigma \in G_1$ under public key $P \in G_2$ on a message $m$ satisfies the signature equation $$e(H(m),P) = e(\sigma,B) = \phi_B(\sigma).$$  Since $\phi_B$ is an injection, there is at most one possible signature $\sigma$ for any public key $P$ and any message $m$.


key recovery in the ideal cipher model I'm reading up on the ideal cipher model and can't wrap my head around some basic calculation.

Let $E$ is an ideal cipher with $n$-bit key and $n$-bit block. For each key $K$, $E_K$ is random permutation chosen uniformly random from the $2^n!$ of them. My question is, given an ideal cipher, and $q$-queries to it: $(m_i, E_K(m_i))$ for $i\in[q]$, what does it leak about $K$?

For any given $q$ mappings $\{ m_i \to E_K(m_i) \}$, there are $2^{n-q}!$ permutations that respect the mappings. So $E_K$ could be any one of them. Does this mean those $q$ queries leak nothing about the key?

In the ideal cipher model, $E_K$ and $K$ are independent, so no amount of information about $E_K$ will tell you anything about $K$ itself.


Does key-length recommendation provided by NIST consider quantum computer? Here we can see the suggested key-length by NIST in a few decades:
https://www.keylength.com/en/4/#Biblio10

Does this consider quantum-computer?

Does this consider quantum-computer?

No, it does not.  It is generally believed that, because of Shor's algorithm, a Quantum Computer will be able to factor and compute discrete logs (including within an elliptic curve group) in polynomial time, hence algorithms depending on those will be insecure.

As for the symmetric algorithms, the conventional wisdom is that you will need twice the key size to obtain the same level of security.


Cipher Block Chain continued Initialization Vector Assume a communication session between Alice and Bob (being client and server, in my case). Alice uses a secure random generator to generate both a key and an IV for use with AES in CBC mode.

Alice transmits both the key (and IV) over a "secure channel" (RSA is being used), together with a message that has been encrypted using these parameters, to Bob.

Bob decrypts the message, and wants to send a message back, obviously using the same received session key. As I am working using a bandwidth constrained channel, every byte saved is a win.

Is it okay for Bob to use the last AES ciphertext block as initialization vector for his transmission, given that this is the way CBC works?

If not, why not? If so, can I keep on chaining using this method, assuming a perfect lossless channel?

Bonus question: if it works, is it possible to apply this to other block modes?

Is it okay for Bob to use the last AES ciphertext block as initialization vector for his transmission, given that this is the way CBC works?

There is a known vulnerability with this; if the attacker can convince Bob (or Alice, on her next message) to start the reply message with an attacker-chosen block, then the attacker can use this to form an encryption oracle (and can then use that encryption oracle to decrypt low-entropy plaintext blocks).

This isn't a problem for CBC itself; it assumes that Alice (or Bob) selects the message up front, and then gives it to the CBC-mode encryption engine.  The plaintext block that the attacker needs to submit for this vulnerability to apply depends on the immediately previous ciphertext block; as the intermediate chaining values are unknown when the block is selected, this doesn't apply.  However, in your case, the attacker may be able to see the entire previous encrypted block, hence reusing the last ciphertext block as the next IV can cause this problem.

Depending on how Alice and Bob form their messages, this might not be applicable to your use case; however it would seem prudent to avoid this possibility anyways.

There are a couple ways to get around this problem:

Generate the next IV in a way that depends on a secret key that both Alice and Bob know (but not the attacker, obviously); for example, the IV for message $n$ might by $\text{AES}_k(n)$
Use the last ciphertext block, but process it somehow (in a key-dependent fashion); for example, set $IV = \text{AES}_k( \text{LastCiphertextBlock} )$

As for how other block cipher modes would work, well, that'd depend on the actual mode.


Key iteration count while using random keyfile larger than master key If I were to have a 4096-bit file of random data (/dev/random) used as a keyfile for LUKS, would there be any benefit to having a key iteration count higher than 1?

My reasoning is that the attacker could choose to guess the contents of the 4096-bit file (very very hard), the 256-bit master key (still hard, but easier than the 4096-bit file), or the potentially key-stretched 256-bit key derived from the keyfile that would decrypt the master key (equivalent in difficulty to the master key).

Am I correct in believing that an iteration count of 1 is no less secure than a count of 100000 for the keyfile?

Key stretching is only used to make small-entropy keys less vulnerable to brute force attacks. If it is (nearly) impossible to break the original key, than there's little sense in using a iteration count of more than 1.

If the input to the function is as big (in sense of entropy in bit) as the output, then an attacker could just attack the algorithm which did use the output and not the key derivation function itself.


why Niederreiter cryptosystem is not a candidate in NIST PQC competition? Seemingly, Niederreiter cryptosystem is faster than McEliece, and it can also be used to implement digital signature. Why isn't this scheme appear in NIST post quantum competition?

Classic McEliece is using the Niederreiter T-OWF:

The KEM is built conservatively from a PKE designed for OW-CPA security, namely Niederreiter’s  dual  version  of  McEliece’s  PKE  using  binary  Goppa  codes.

https://classic.mceliece.org/nist/mceliece-20201010.pdf


Outsourcing arbitrary computations securely Consider the following scheme. Alice wants Bob to make some computations for her, but she doesn't want to reveal the data on which he's going to do it. So, she encrypts the data, sends them to Bob, he makes some (Turing-complete) computations on them, and sends an encrypted answer. For example (C++-like pseudocode)

// Alice: range of numbers (ideally, 2^32 for int's)
const int max = 117
// Alice: ready some inputs
int a = 3, b = 5;
// Alice: ready some random keys
int ra = rand() % max, rb = rand() % max;
// Alice: encrypt inputs
int ea = (a + ra) % max, eb = (b + rb) % max;
// Bob: compute sum of inputs
int er = (ea + eb) % max;
// Alice: decrypt result
int r = (er - ra - rb + 2 * max) % max;
// Alice: yeah, it was 8!
cout << r << endl;

Mention that neither Bob has access to inputs and outputs, nor there are some unencrypted data used in process. Though, such a scheme has several drawbacks:

Obviously, we shouldn't use modulo of rand that simply, because in current implementation it prefers some results over others.
The data are not that much encrypted, because their distribution didn't change.
To compute some arbitrary function Alice and Bob should send the data for each operation, while ideally there should be only two: Alice sends inputs, Bob responds with outputs. Possibly, this could be solved by sending a seed for PRNG, generating "salt" for single steps of computation.

Such kind of computations must have already been studied somewhere, though I don't know, how they're called. Could you suggest some good keywords and sources to start with?

What you are seeking for is a special case of secure multiparty computation, namely secure function evaluation or also called secure 2 party computation.

However, general solutions to this problem require interaction, meaning that the parties performing the computation need to exchange more than two messages. You write:

  To compute some arbitrary function Alice and Bob should send the data for each operation, while ideally there should be only two: Alice sends inputs, Bob responds with outputs.

Within recent years, two solutions to this problem have attracted much research interest, namely:

Garbled circuits (GCs)

Have initially have been proposed by Yao back in 1982 as a general idea to perform secure two party computation, i.e., to evaluate $f(a,b)$ between two parties with $A$ having input $a$ and $B$ having input $b$ without neither learning the other's input but the result.

One can generalise this to receiving $A$ and $B$ possibly different outputs for two possible different functions $f_A$ and $f_B$. We can also emulate this by a function $f$ to be evaluated as $f((a,r_A),(b,r_B))=(f_A(a,b)\oplus r_A\|f_B(a,b)\oplus r_B)$ for $r_A$ and $r_B$ being uniform random strings. Lets say that $A$ holds the input $a$ and setting the input $b$ of $B$ (the one computing the evaluation) to be simply nothing, allows $B$ to obtain the evaluation $f$ without learning $a$ and only learning $f(a)\oplus r_A$ but not learning $f(a)$. Sending this back to $A$, $A$ can retrieve $f(a)$.

Having this scenario it can be realised with GCs by letting $A$ build the GC and give it to $B$ along with the garbled input, $B$ evaluates the GC and learns only the garbled output, which is sent back to $A$ and $A$ receives the output.

Garbled circuits can be built using symmetric encryption and oblivious transfer.

You may look at the Might Be Evil project for an implementation of GC and further pointers.

Fully Homomorphic Encryption (FHE)

A first FHE construction has been proposed by Gentry back in 2009 and there has been much progress since then. Loosely speaking, FHE represents an (public key) encryption scheme which allows you to evaluate any function $f$ which can be represented as a circuit on encrypted data such that the input is a ciphertext $c$ for message $x$ and the output is a ciphertext $c_f$ containing $f(x)$. Consequently, $A$ can encrypt some $x$ to obtain $c$, give it to $B$ and $B$ can evaluate $f$ on $c$ without learning neither $x$ nor $f(x)$ but only $c_f$. Giving $c_f$ back to $A$, $A$ can decrypt to obtain $f(x)$.

Simple Operations

If you only want $B$ to add or multiply encrypted values you can use additively homomorphic or multiplicatively homomorphic encryption schemes which are entire practical, but leave you with very limited computations.

Some remarks

The practicality of GC and FHE largely depends on your setting and the circuit to be evaluated and is unfortunately not that nice as one would desire.

FHE is impractical at the moment, but since FHE schemes are typically constructed via a bootstrapping approach from certain somewhat homomorphic encryption (SHE) schemes (which allow to evaluate a certain class of circuits homomorphically), using a "customised" SHE scheme may be practical for some approaches, see e.g., here.

This is a very active field of research and one could write a lot about that. However, I hope this gives you some pointers to look at for further reading.


Floyd's cycle finding algorithm on SHA256 I'm trying to implement Floyd's cycle finding algorithm on SHA256 function. I think I understood the method used to find cycles but what bothers me is how to properly feed the repeated hashing function.
Let's say I hash string "abc".
What I will get as a result is :
"ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad"
As I understood this is a 256-bit (32-byte) output so it could be chunked as:
ba 78 16 bf 8f 01 cf ea 41 41 40 de 5d ae 22 23 b0 03 61 a3 96 17 7a 9c b4 10 ff 61 f2 00 15 ad where each chunk could be represented as individual character.

So my question is should I feed the next Hash function with the raw result with 32-byte or with the string:
"ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad"
which I suppose has 64-byte.

Additionally, if I were only to check first 4-bytes for the collision, what should be fed to the hashing function in this case?

We usually use raw bytes, because this doesn't require extra step (convert hex to string). But technically speaking any representation will allow you to find a cycle (just a different one).

When talking about shortened-hash cycles, same rules apply: we usually use raw bytes just cut to desired length or we fill rest of hash with zeros, because that requires least steps to complete. But you can use anything that will cut entropy to desired value.


Checking if discrete logarithm is $\geq\frac{\varphi(p)}2$ in polynomial time? Given $p$ a prime, $g$ generator of $\Bbb Z_p^*$, and $h\in\Bbb Z_p^*$, that uniquely defines some $z\in[0,\varphi(p)[$ such that $g^z\equiv h\pmod p$.

Is it possible to determine in polynomial time if $\displaystyle z\geq\frac{\varphi(p)}2$ ?

Given an oracle that tells you for any $h\in\mathbb{Z}_{p-1}^\times$ if the discrete logarithm $\log_g(h)$ is $\ge\frac{p}2$ or not, allows you to find $x := \log_g(h_0)$ for fixed $h_0$ with about $\log_2 p$ queries:

The query $\log_g(h_0)\stackrel{?}\ge\frac {p-1}2$ gives you one bit of information $z_0 := \lfloor\frac{2x}{p-1}\rfloor\in\{0, 1\}$, and you know that $h_1 := h_0\cdot g^{-z_0\cdot\frac{p-1}2}$ has a discrete logarithm $\log_g(h_1) \in \{0, 1, \dots, \frac{p-3}2\}$.

So if you multiply $h_1$ with $g^{\lfloor\frac{p-1}4\rfloor}$ you get an element $h_1'$ with discrete logarithm $\log_g(h_1')\in\{\lfloor\frac{p-1}4\rfloor, \dots, \lfloor\frac{3p-7}4\rfloor\}$, and querying $\log_g(h_1')\stackrel{?}\ge\frac {p-1}2$ gives you (roughly) another bit of information by cutting the interval in half.

You can repeat this step of multiplying an adaptively chosen power of $g$ to query the oracle, halving the intervals in every step until you find a single value from which then you can calculate the discrete logarithm $x$.


Cryptography vs Security This may sound a little bit of basic but here it goes…

Which of the following is correct?

“Cryptography is under the security field”, or
“Security is under the cryptography field?”

Cryptography is all about encryption and decryption. Encryption/Decryption requires a key. Isn't security the same? Security also depends on key/password, to keep data secure. I can feel that they are co-related but I'm not clear about the differences. Can anyone clear this out?

EDIT: With the word "under" I meant pure dependency, and "Security" hints at Information Security.

The correct answer would be:

  1 . “Cryptography is under the security field”.

Let me try to explain it a bit…

Cryptography

Modern cryptography concerns itself with 4 objectives:

Confidentiality: the information cannot be understood by anyone for whom it was unintended.
Integrity: the information cannot be altered in storage or transit between sender and intended receiver without the alteration being detected.
Non-repudiation: the creator/sender of the information cannot deny at a later stage his or her intentions in the creation or transmission of the information.
Authentication: the sender and receiver can confirm each other’s identity and the origin/destination of the information.

Information Security

Now, if you look at information security (what you simply call “security”), you’ll notice that – besides the four points mentioned above – there’s a whole universe of other security-related things that information security handles. To name just a few examples of what information security  additionally covers (besides cryptography):

risk management,
access control,
security classification of information,
business continuity,
disaster recovery planning,
laws and regulations,
etc.

Nota Bene

In the end, this might also help you understand why StackExchange has a Security.SE – which  covers information security in general, and a Crypto.SE – which explicitly focuses on cryptographic details like algorithm design, protocol analysis, etc.

EDIT:
More of an aside, but it may help understand things even better… I just noticed that Wikipedia has a nice Contents-listing in their InfoSec article, from which you can see how Cryptography fits into Information Security as a sub-category (6.5).


What are the requirements of a key schedule? In the first block cipher I designed I used a CSPRNG to generate the round keys.  The purpose was to at least have a chance of creating a (hopefully!) secure cipher on the first try (but please don't use it in production).

One criticism I got was that the key schedule was too expensive.  This made me wonder: what are the actual requirements of a key schedule?  Clearly a CSPRNG is overkill.  I want to know what the actual requirements are.  What is required of a key schedule?

I know:

Every bit of the key should ideally effect each round key.
As always, speed and simplicity are desirable.

Desirable Properties

There are a few papers and resources related to key schedule design out there.

From this paper from 2012  we can highlight some of the following points:

Key bits should be uniformly used
All subkeys should be "equally good"
It is "hard" to find any remaining key bits from any known key bits.
Hard to invert
If possible  every  key  bit  should  affect  nearly  every  round  in  different  ways
No equivalent keys
Collision-freedom (standard hash function properties)
No dead spots
Equally powerful effect of every key bit on the subkeys.
Low implementation cost
Minimal mutual information between  all  subkey  bits  and  master  key  bits

Which the paper then basically summarizes with:

  First, key schedules should have no bit leakage in the level
  of "round", or of the whole key schedule. The former means they only consider
  leakage between different rounds of subkeys, or between some rounds of subkeys
  and master keys. When an recursive key schedule is invertible or when subkeys
  are  direct  transformation  from  master  key,  above  leakage  cannot  be  avoided.
  The latter means that no subkey bits can be derived easily whatever key knowledge is obtained

They then go on to define terms and techniques which are more in depth in relation to cryptanalysis of key schedules.

This paper appears to build on the work of the previous one, but I cannot access it.[1]

This paper concludes mostly the same things:

Maximize  avalanche  in  the  subkeys  and  avoid  linear
key  schedules.

Though the authors note: "As an open question, we note that the DES key schedule is linear,
and wonder why it appears to resist related-key attacks"

Every key bit should affect nearly every round, if possible, but
not in exactly the same way
The key schedule should be designed to resist
differential  attacks.

Key Schedule Classification

This last paper had some different material that is also interesting. They classify the key schedules of algorithms into two types, with subclasses of those types. The types are defined by whether or not knowledge of round key bits reveals knowledge of any other round key bits, or the master key.

A Type 1 key schedule allows recovery of other round key/master key information if some round key information is known
A type 2 key schedule does not allow recovery of other round key/master key information if some round key information is known

They further go on to define sub types, A, B, and C.

A Category 1, Type A cipher (1A) is one in which all bits of the master key are used in each round, and hence knowledge of a round subkey yields all bits of the master key and all other round subkeys. The cipher NDS [3] is such an example.
A 1B cipher is one where knowledge of a round subkey gives some, but not all bits of the master key or other round subkeys. DES is an example.
A 1C cipher is one in which knowledge of a round subkey yields bits of other round subkeys or the master key after some simple arithmetic operations or function inversions. SAFER K-64 [6 ] is an example.
A 2A cipher is one in which not all bits of the master key are used to create each round subkey . In these ciphers, certain master keys are guaranteed to produce at least two identical round keys. A cipher such as CAST-128 [7] is an example. In other words, the entropy of the round subkeys is not maximised.
A 2B cipher is one in which all master key bits are used in the determination of all round subkeys, thus maximising the entropy of the subkeys. An example is Blowfish [8].
The most secure schedule classification is 2C. However, this may lead to unmanageably large master keys for ciphers whose security cannot hope to match what is naively suggested by the key length. Further, export restrictions on cryptographic materials often limit the size of the key. For these reasons, the best we can hope for is to mimic 2C schedules as closely as possible, with the next strongest classification, 2B.

Efficiency with embedded devices

While one way functions are recommended as part of a key schedule, there is a downside if they are used a certain way. If only noninvertible functions are used in deriving round keys, then decryption will require the algorithm to generate all its key material at the beginning. On a general purpose computer this is not really a concern, however, on embedded devices with limited gate counts/surface areas, the excess storage can become problematic. The storage requirement will increase by the round key size per round. This will lead to a higher unit cost.

The best solution I am aware of is to split the key schedule into two parts, an invertible part, and an uninvertible part. The invertible part is used to generate round key material in a way that is friendly to on the fly processing, while the uninvertible part of applied just before usage of the round key. This maintains the best of both worlds, in that embedded devices can decrypt with an on-the-fly key schedule and the cipher can have the protection a non invertible key schedule offers. This is potentially a small change that will improve the applicability of the cipher towards smartcards and the like.

[1] Free version added.


Encryption for IOT devices with minimal overhead I have several IOT devices that transmits nearly 200 bytes of data every 10 seconds. I want to make the data secured but i also want to keep the data size nearly same. Ofcourse for IOT devices computations should be lightweight. I have been considering AES 128 for this job and RSA for key exchange. I am wondering if i am on the right track or there are better options.

i saw NIST have called for lightweight encryption algorithm for IOT devices. until that is standardized which encryption should i use.

in summary, i want to get the overview of different encryption scheme with minimal overheads and computations. I looked around but there seems to be no this type of comparisons.

I am very much new in this field so forgive me if i have done any silly mistake.

For passively powered RFID tags, I settled on 160-bit ECC (Curve25519) to exchange the keys and SPECK for the actual encryption on a software platform.  If I make my own hardware, I use SIMON instead of SPECK.  For an IoT application, I see no reason not to do something similar.

If you are looking for comparisons of symmetric ciphers regarding throughput and power, I would suggest the SIMON and SPECK paper and the paper on PRESENT as both have good power tables and comparisons.


Indistinguishability in the presence of an eavesdropper attack scenario The property of Indistinguishability in the presence of an eavesdropper
as described in the following experiment:

(tract from: Introduction to Modern Cryptography)

It must be interpreted as a scenario of  Ciphertext-only attack or Known-plaintext attack?
Thanks

It's CTO, you are trying to figure out the plaintext given two ciphertexts. M1 and M0 are just bits of either 1 or 0.


What does "with all but negligible probability" mean? I have met the sentence that something will happen "with all but negligible probability" in the paper "Homomorphic Signatures for Polynomial Functions". However, I cannot quite figure out what exactly they mean by this. I know the definition of something happening with negligible probability, it is the "all but" that throws me off. In the paper they are referencing, it is described that it happens with probability $1-2^{-\Omega(n)}$, so I figure this must be the definition of it happening with all but negligible probability? However, I do not know what they mean by $\Omega(n)$, and I cannot seem to find the definition in the paper. Can someone perhaps clean things up for me?

$\Omega(n)$ is a mathematical notation from the same family that the notation $O(n)$ comes from.

To review, $O(n)$ is bounded from above; that is, if we say that $f(n) = O(g(n))$, what we're actually saying is that, for all sufficiently large $n$, there exists a constant $c > 0$ such that $f(n) < c \cdot g(n)$, that is, $f(n)$ grows no faster than $g(n)$.

$\Omega(n)$ is the same, except that it is bounded from below; that is, if we say that $f(n) = \Omega(g(n))$, then (for all sufficiently large $n$) there exists a constant $c > 0$ such that $f(n) > c \cdot g(n)$, that is, $f(n)$ grows at least as fast as $g(n)$.

Hence, what they mean when they say $1 - 2^{-\Omega(n)}$, there's a constant $c$ such that the probability of success is always $> 1 - 2^{-cn}$ (except for possibly small $n$); hence, for large $n$, the probability is quite high (however, that doesn't say what "large" means in this context :-)

In case you're wondering, from the same family, we also have "little-oh" notation $f(n) = o(g(n))$ ("f grows strictly slower than g"), little-omega notation $f(n) = \omega(g(n))$ ("f grows strictly faster than g") and theta notation $f(n) = \Theta(g(n)))$ ("f grows as fast as g, within multiplicative upper and lower bounds")


Sylow theorems in (Z/pZ)* This might sound as a silly question but does the Sylow theorem III apply to (Z/pZ)*?

For Example for (Z/11Z)* we have the order of the group being 10 = 2 * 5.

I would expect to have only 1 Sylow 5-subgroup. Or am I wrong?

Although not really a question regarding cryptography, Sylow's theorems are quite boring for cyclic groups (or any commutative group):

$(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic and has order $p-1$
Theorem 1 gives you the existance of subgroups with order of every prime power divisor of $p-1$, where every element has a power of that prime as its order.
Theorem 2 on its own isn't all that useful, because conjugation of subgroups doesn't give you a different group in commutative groups: $g^{-1}Hg=g^{-1}gH=H$

Now the part you are asking about: The number of Sylow p-subgroups is fixed - it is $1$. Let's say we want a Sylow p-subgroup for prime $q$ (not to cause confusion with the group order $p-1$, and $q$ divides $p-1$). Theorem 2 states that Sylow groups are conjugate to each other, however conjugation always gives you the same subgroup. Assuming there are two Sylow p-subgroups, then theorem 2 would require them to be conjugate. However, that means those two subgroups are actually equivalent.