Homomorphic properties of Paillier I'm curious about the homomorphic properties of Paillier. So, basically if I have $\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk}, \alpha) \cdot \textsf{Enc}(\textsf{pk}, \alpha^{-1}))$, I will get as result $\alpha + \alpha^{-1}$. But, does it also mean that if I have $\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk}, \alpha)^{\textsf{Enc}(\textsf{pk}, \alpha^{-1})})$, then the result will be $\alpha \cdot \alpha^{-1}$, which will basically cancel each other, and will be left with 1?

No, there is no reason that $\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk},\alpha)^{\textsf{Enc}(\textsf{pk}, \alpha^{-1})})$ would be $\alpha\cdot\alpha^{-1}$, including when we spread $\bmod N$ or $\bmod N^2$ here and there.

What does apply is: for overwhelmingly most $\alpha$ and $k$ in $\Bbb Z$, it holds that $\textsf{Dec}(\textsf{sk},\textsf{Enc}(\textsf{pk}, \alpha)^k\bmod N^2)=k\cdot\alpha\bmod N$. We could take $k=\alpha^{-1}\bmod N$ and get $\textsf{Dec}(\textsf{sk},\textsf{Enc}(\textsf{pk},\alpha)^{(\alpha^{-1}\bmod N)}\bmod N^2)=1$, but that's not useful anyway, since $\alpha^{-1}\bmod N$ reveals $\alpha\bmod N$.

Criticism of the question:

It is not defined in which group it is computed $\alpha^{-1}$, and that matters.
$\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk}, \alpha) \cdot \textsf{Enc}(\textsf{pk}, \alpha^{-1}))$ will be $\alpha+\alpha^{-1}\bmod N$, which may or may not be $\alpha+\alpha^{-1}$.


Diffie-Hellman should size of group be a prime? I have found some contradicting answers regarding finding a safe prime.

  When p is a "safe prime", this means that $(p−1)/2$ is also prime. We then define $q=(p−1)2$. In that situation, the order of any non-zero $g\mod p$ (except 1 and p−1) is either $q$ or $2q$

If it can produce a group of size $2q$ then the groups length is by definition not a prime.

Okay, so following this theory, 83 should be regarded as a safe prime.

$(83-1)/2=41$ and $41$ is a prime.

The length of the subgroup produced by $2 \mod 83$ is $82$. (can you phrase it like that? Even though it refers to a set/group of congruences by $2^{1..p-1} \mod p$?

I can prove it with a little program

const groupSize = (p, g) => {
    const group = new Set()
    for(let i = BigInt(0); i < p-BigInt(1); i++){
        group.add((g**i)%p)
    }
    console.log(group.size)
}
groupSize(BigInt(83), BigInt(2))

output: 82

This contradicts an answer to one of my previous questions regarding choosing a safe prime.

  If h is a factor of the size of the group generated by g, then given $g^x\mod p$, we can compute $h\mod n$ in $O(\sqrt h)$ time. If g generates the entire group, well, its size will be $p−1$, which always has a factor of 2 (assuming $p>2$), and so we'd be giving away $x\mod 2$ for free.

Diffie-Hellman what is the subgroup

This makes me believe that the group cannot be an even number, since it is then a factor of 2?

This contradicts an answer

In what sense do they contradict?

The first one states that, for a safe prime, we have subgroups of size $q$ and $2q$.

The second one states that we typically use a $g$ that generates a subgroup whose size is a prime.

These two statements do not contradict each other; combined, that would mean that (to follow both) we select a $g$ that generates a subgroup of size $q$.  This is always possible (in fact, $g=4$ is always such a generator).

Your computations show that, for $p=83$, then $g=2$ is not such a generator.  What that means is that, to follow the advise of the second statement, you'd pick a different generator (and, in fact, $g=3$ works, that is, generates a subgroup of size $q$, for $p=83$)


Is there a way of sharing a key without anyone knowing what the key is initially? I started learning about key sharing and Shamir secret sharing, I'm wondering whether you need someone who knows the key initially and then distributes it, is this step necessary or not?
In my case I have a group of people that run a permission blockchain (they are the consensus nodes) and I want all incoming transaction to be encrypted but the decryption part should be available only if a majority decides to construct the decryption key, but I don't want this decryption key to be known initially by anyone. Is it possible or not?

You can use MPC in order to generate a key that is distributed amongst a set of users, without anyone knowing the key itself. This is a very standard MPC problem, and many different protocols can be used. For example, if you want to generate a key for ECIES encryption, then you can basically have each party $P_i$ choose a random $x_i\in\mathbb{Z}_q$ and send a commitment to $Q_i = x_i\cdot G$ along with a zero knowledge proof of knowledge of $x_i$. Then, after all commitments are received, all parties decommit and ZK proofs are verified. Finally, you define the public key to be $Q=\sum_{i=1}^n Q_i$. This will give you a plain additive sharing. You can use a similar idea to get a Shamir sharing as well.


Is tagging the hash of a password along with ciphertext secure? Suppose I have a password, in which I use Argon2ID with 1GB memory to derive an encryption key. Then, I encrypt my data using XChaCha20 using that encryption key. The problem with ChaCha is that any encryption key "works". If you use the wrong password to decrypt, you won't get an empty output or error like AES, but instead, you just get corrupted/useless data. I want to be able to validate the password so that I know whether it is correct before decrypting. If I take the SHA3_512 of the Argon2ID-ed password and include it with the ciphertext, is the ciphertext now vulnerable to attacks? I'm using a CSPRNG to generate Argon2ID's salt and ChaCha's nonce, which would put off rainbow tables. Is this scheme secure? Here's a visual example:
plaintext = "sfsdfasdfadfasdfasdfasdfadf"
password = "some_very_strong_password_blah"
salt = csprng(16)
nonce = csprng(24)
key = argon2id(password,salt,t=32,m=1GB,p=4)
ciphertext = XChaCha20.encrypt(plaintext,password,nonce=nonce)
check = sha3_512(key)
ciphertext += check
// Done. To check the password,
// I would derive the key using Argon2ID
// again and compare it with 'check'

Would this be secure? I know about this question, but that scenario is without a KDF and doesn't include any entropy. Thanks.
Update: AES does not give an empty output if the wrong key is used. The crypto library I use does.

You don't get empty output in AES, too. AES is a permutation and will always return a plaintext, correct or not depending on the key.

If I take the SHA3_512 of the Argon2ID-ed password and include it with the ciphertext, is the ciphertext now vulnerable to attacks?

One needs to find a pre-image to the key, and normally the cost of this is around $2^{512}$ for SHA3-512, however, if you are using xChaCha20 then the cost is around $2^{256}$ since the input is the 256-bit key. In any case, it is secure to be bruteforced.
You can also, encrypt the all-zero message block or any random message block you chose to validate the key.
Note that the Veracrypt uses Decryption is considered successful if the first 4 bytes of the decrypted data contain the ASCII string “VERA”

Is this scheme secure?

First of all, your password's strength is important. You should either use dicewire to have strong passwords or use a password manager to generate one, and those still require a master strong password from you.
The missing part is the integrity of the data, you can use Poly1305 together with the xChaCha20 to have the confidentiality, integrity, and authentication, too.
Another issue can be the update of the encrypted data. If you use the same $(Key, nonce)$ pair for the update, the updated parts of the file are vulnerable to crib-dragging and that part may fail the confidentiality. To mitigate this, you need either use a new $nonce$ and encrypt all of the message or use a new key, too.
A side note; you can use this strong password to derive multiple keys directly
with Argon2id or use HKDF's expand part since the derived key from Argon2id is already is a Pseudo-Random Key.


Why does KangarooTwelve only use 12 rounds? The initial Keccak submission used 18 rounds, which was bumped up to 24 rounds for the final version after distinguishers were found for a reduced 16 round variant.  However, the Keccak team has recently released a spate of cryptographic primitives based on a twelve-round variant of Keccak.

I've seen scattered references which give the impression that new bounds were found and that even 18 rounds is overkill.  However, I can't grok the research and I need a canonical answer.

What led them to feel comfortable with 12 rounds for K12?

I. Intuition: collision only on 6 rounds.

KangarooTwelve aims at fast hashing but also claims 128-bits security. This can be seen in the fact that the capacity is set to 256 allowing a rate of 1344 for a faster absorption.

Note that while the base sponge construction uses only the 12 finals rounds of Keccak, it is applied twice on each bit in the case of a message longer than 8129 bytes. You compute first the CVs values and then hash it with the first string (see bellow).

KangarooTwelve(M,C):  S_0 || S_1 || ... || S_n = M || C
  F = Sponge[Keccak-p[1600,nr=12],r=1344,c=256] (or mini Keccak)

                          +------------+
                          |    S_0     |
                          +------------+
                               ||
                          +----------+
                          |  `110*`  |
                          +----------+
                               ||
+-----------------+   F   +----------+
|     S_1  ||`110`|------>|   CV_0   |
+-----------------+       +----------+
                               ||
+-----------------+   F   +----------+
|     S_2  ||`110`|------>|   CV_1   |
+-----------------+       +----------+
                               ||
       ...                    ...
                               ||
+-----------------+   F   +----------+
|     S_n  ||`110`|------>|  CV_n-1  |
+-----------------+       +----------+
                               ||
                          +----------+
                          | r_e(n-1) |
                          +----------+
                               ||
                          +------------------+   F
                          |  0xFFFF  || `01` |------>  output
                          +------------------+

Other reasons that lead to consider K12 safe are the current absence of collisions for more than 6 rounds, implying a security margin of 100%. This same round-reduced approach is also used in Keyak and Ketje.

If you want to have more security, you can use Marsupilami 14, it is Kangaroo 12 but with the last 14 rounds of Keccak instead of 12 and a capacity of 512 bits.

II. The complexity arguments.

Joan pointed this to me: in this note, it is noted that the complexity of the zero-sum distinguisher are

for 18 rounds: $2^{1370}$
for 14 rounds: $2^{257}$
for 12 rounds: $2^{129}$

In the case of KangarooTwelve, the capacity is 256 bits. A generic attack on a sponge with such capacity leads to a complexity of $2^{128}$, thus the complexity of the zero-sum distinguisher for 12 rounds is higher, rendering the efficiency of this attack worse than bruteforce.

As for the 14 rounds of MarsupilamiFourteen and its capacity of 512 bits, the arguments is the same.

Also to generate the zero-sum structure, one need to start in the middle of the iterations. This attack surface is reduced by the way KangarooTweleve operates due to all the fixed constants.


How does redundancy in a file effects performance and security of encryption? Does redundancy in a file or data effect performance and security of encryption? (for example for AES, if not for general case)

Is it easier to encrypt something that has high redundancy or something that has almost no redundancy?

And does redundancy makes security weaker by any means?

Pretty much all modern encryption systems (including AES, in any standard mode) are data-agnostic: they are designed to encrypt any byte (or bit) stream regardless of its content, and their performance does not depend in any way on what the stream contains.

Indeed, if this were not the case, that would open the encryption scheme to timing attacks — if the performance of the encryption system depended on the data being encrypted, an attacker would be able to learn something about the data by timing how long it takes to encrypt it.  Modern encryption systems are designed to avoid such attacks, primarily by ensuring that their performance is constant regardless of the data being encrypted or the key used.

(That said, ensuring that the execution time of an encryption routine remains perfectly constant can be difficult, and it's not at all uncommon for timing attacks to be discovered against insufficiently careful implementations of even standard crypto algorithms.  This is one reason why writing secure low-level crypto code requires a lot of skill and attention to detail.  However, even when such vulnerabilities exist, they're typically a lot more subtle than what you describe.)

As for security, modern encryption schemes are also supposed to be secure regardless of the data being encrypted.  Indeed, the minimum level of security typically expected of a secure encryption scheme is ciphertext indistinguishability under a chosen-plaintext attack (IND-CPA), which requires that, even if the attacker gets to choose the messages being encrypted, he still cannot distinguish the encrypted output from a random bitstring (of equal length).

That said, while encryption systems in current use (such as AES, in any secure mode) are assumed to meet this level of security, and while no-one currently knows (or at least has published) any attacks that would violate that claim, no-one has also ever managed to unconditionally prove that any encryption scheme actually meets that standard, and sometimes new attacks do get discovered against systems previously thought to be secure.  If an encryption system is sufficiently badly broken, it is possible that the nature of the data being encrypted might affect the ability of an attacker to exploit the system's weakness.  That said, any system for which that would be the case would be regarded as hopelessly insecure and unsuitable for use today.


Is Curve P-384 equal to secp384r1? I am a bit confused with different notations of elliptic curves.
Specifically, I am comparing the NIST specification with the SECG specification.

More specifically I want to know if the NIST curve $Curve P-384$ (NIST D.1.2.4) corresponds to $secp384r1$ specified in SECG (2.5.1).

I found a related question here on crypto.SE where it is said that these are the same curves and its just different notation.

This would mean:

Curve-P 384 = secp384r1
Curve-P-256 = secp256r1
...

However, I compared the curve parameters mentioned in both documents and found that there are deviations.

Equation: $a$ is fixed in the NIST case

NIST defines the curve as: $ E: y^{2} \equiv x^{3} - 3x + b (\mod p)$
SECG defines the curve as: $ E: y^{2} \equiv x^3 + a.x + b (\mod p)$

Basepoint G

NIST defines the basepoint as:

$G_{x}$ = aa87ca22 be8b0537 8eb1c71e f320ad74 6e1d3b62 8ba79b98
59f741e0 82542a38 5502f25d bf55296c 3a545e38 72760ab7
$G_{y}$ =  3617de4a 96262c6f 5d9e98bf 9292dc29 f8f41dbd 289a147c
e9da3113 b5f0b8c0 0a60b1ce 1d7e819d 7a431d7c 90ea0e5f

SEC defines the basepoint as:

$G$ = 04 aa87ca22 be8b0537 8eb1c71e f320ad74 6e1d3b62 8ba79b98
59f741e0 82542a38 5502f25d bf55296c 3a545e38 72760ab7 3617de4a
96262c6f 5d9e98bf 9292dc29 f8f41dbd 289a147c e9da3113 b5f0b8c0
0a60b1ce 1d7e819d 7a431d7c 90ea0e5f
which is the NIST versions $G_{x}$, $G_{y}$ concatenated and preceded by 04

I am not an expert on the math behind ECC, so I need help assessing if the mentioned deviations of the two specification mean that they are not equal and if so, what are the differences and why are they different?

Thanks!

Yes, they refer to the same curve. I'm not sure why the equations' different, but I believe that's just a transcription error. The 04 in basepoint is just standard way to encode a point in SECG #1.

EDIT: (Answer extracted from the comments)

In the SECG case:

a = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF 00000000 00000000 FFFFFFFC

and

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF 00000000 00000000 FFFFFFFF

so $a = (p-3) \bmod p$

the Nist version does $x^3 - 3x + b \mod p$, whereas the SECG version does $x^3 + (p-3)x + b \mod p$. Subtracting $3x$ or adding $(p-3)x$ is equal $\bmod p$


Compression in key generation of DES algorithm Does anyone have a pseudo-code or an algorithm or even a diagram of the compression (pc2) of the DES algorithm?

I can't find a relation between the bits that are dropped, even when I do it manually it does not generate the right result. I mean put as the first bit of the output (subkey $K_i$) the 14th bit of $C$, the 2nd of the output is the 17th of $C$.. the 25th bit of the output is the 41th of $D$.

Is the above correct or did I misunderstand?

The PC-2 substitution transforms the 56-bit concatenation of the 28-bit $C$ and $D$ after they have been appropriately rotated, into the 48-bit subkey $K_i$ for round $i$, before that is combined using XOR with the 48-bit output of expansion $E$ and divided into 6-bit entries for each of the 8 S-tables. The table defining PC-2 is correspondingly organized as 8 lines of 6 values in the defining standard.

14  17  11  24   1   5
 3  28  15   6  21  10
23  19  12   4  26   8
16   7  27  20  13   2
41  52  31  37  47  55
30  40  51  45  33  48
44  49  39  56  34  53
46  42  50  36  29  32

The $j^\text{th}$ integer in the table when scanned in reading order is the index of the bit in the input corresponding to the $j^\text{th}$ bit in the output (in DES, the convention is that the bits are numbered from 1 onwards, with 1 being the first or left bit, or the most significant bit in the first or left octet in an octet or quartet string, with octets and quartets expressed in big-endian hexadecimal).

Hence integers 1..28 in the table corresponds to bits from $C$ (and happen to be directed towards the first 4 S-boxes); and the others corresponds to bits from $D$ (going to the other S-boxes).

In other words, we form the first 24 bits of the output by taking the 14th, 17th, 11th .. 13th and 2nd bits of $C$; and the next 24 bits of the output by taking the 13th, 24th, 3rd.. 1st and 4nd bits of $D$ (we subtract 28 from the integers above 28 to get the index in $D$ ).

Integers 9 18 22 25 and 35 38 43 54 are not in the table; they correspond to bits of $C$ and $D$ that are not used in this round (but have or will be in the previous or next round, if any, due to the combination of the shift counts used with PC-2).


Why don't PyCrypto and M2Crypto produce the same result as OpenSSL here (AES-128 ECB) If I run the following, for openSSL:

echo -n "0123456789abcdef0123456789abcdef" | openssl aes-128-ecb -nosalt -nopad | xxd

and enter the key "YELLOW SUBMARINE", I get the following ciphertext:

a2a5 8316 129f c596 8341 c78a 0c36 5d20
a2a5 8316 129f c596 8341 c78a 0c36 5d20

Yet in PyCrypto, the following code:

from Crypto.Cipher import AES
key = b'YELLOW SUBMARINE'
cipher = AES.new(key, AES.MODE_ECB, "")
msg =  cipher.encrypt(b'0123456789abcdef0123456789abcdef')

Outputs:

20 1e 80 2f 7b 6a ce 6f 6c d0 a7 43 ba 78 ae ad
20 1e 80 2f 7b 6a ce 6f 6c d0 a7 43 ba 78 ae ad

(line breaks added for clarity)

What is the cause of this discrepancy? Both are 128-bit AES in ECB
mode. PyCrypto doesn't appear to be salting, and padding should be
unnecessary in any case with this plaintext.

P.S. The same thing happens with M2Crypto:

import M2Crypto
cipher=M2Crypto.EVP.Cipher('aes_128_ecb',b'YELLOW SUBMARINE',"", op=1,
padding=0, salt=None)
out=b''
plaintext=b'0123456789abcdef0123456789abcdef'
out=out+cipher.update(plaintext)
print ' '.join(x.encode('hex') for x in out)

Outputs:

20 1e 80 2f 7b 6a ce 6f 6c d0 a7 43 ba 78 ae ad
20 1e 80 2f 7b 6a ce 6f 6c d0 a7 43 ba 78 ae ad

Commandline openssl enc normally does Password Based Encryption which derives the actual key, and IV (although IV is ignored for ECB), from the password or passphrase you enter, using a variant of PBKDF1. To get "raw" encryption you must specify the key in hex with -K (uppercase), in which case -nosalt is irrelevant (because it applies only to PBKDF). Except for the most recent releases of OpenSSL (and my test system has an older one) with -K you must also specify an -iv in hex even when the cipher/mode used doesn't need it, like ECB.

lin04:~ $ echo -n YELLOW SUBMARINE |od -tx1 |awk '$1="";gsub(/ /,"")'
59454c4c4f57205355424d4152494e45
lin04:~ $ echo -n 0123456789abcdef |openssl aes-128-ecb -nopad \
-K 59454c4c4f57205355424d4152494e45 -iv 00 |od -tx1
0000000 20 1e 80 2f 7b 6a ce 6f 6c d0 a7 43 ba 78 ae ad
0000020

Out of scope of your question, but I hope you know that using ECB is in most cases
a very bad idea. I've seen probably dozens of questions and answers here and
security.SE about that. As the most glaring fairly recent example, see the Adobe
password breach, which allowed many many passwords to be broken due to using ECB.


Cryptographic properties of field multiplication While reading about AES-GCM, I discovered there is a multiplication over $\operatorname{GF}(2^{128}$). My question is about its cryptographic properties, such as:

Take a random element $X$ from $\operatorname{GF}(2^{128}$) (which is not $0$ or $1$). Multiply it with a constant $Y$ (say, the plaintext, which is defined over the same field, $Y\neq 0$). Given the product $XY$, is it possible to recover $Y$ (or some non-trivial information about $Y$)?
If the product $XY$ satifies some regularity condition (such as $XY=1$), is it possible to gain information on $Y$?
If multiple conditions like this are given, is it possible to gain information on $Y$? I mean, say for randomly chosen $X_i$'s, the product $X_iY$'s are given.

If the above problems are hard to solve, probably finite field multiplication can be used as a method for masking countermeasure for side channel (at least theoretically).

You're asking about the multiplication operation over $GF(2^{128})$; it turns out that, if we exclude the element 0, then the multiplication operation over that modified set of $2^{128}-1$ elements is a group operation; for example, inverses exist.
And, for any group operation $\odot$, we have:

For any element $Y$, if we multiply it by a random (and independent) element $X$, the result $X \odot Y$ is random (and revealing it does not reveal anything about $Y$).

This answers your question one (with your question being modified by having $X$ exclude the 0 element only, not the 1 element)
.  Remember, 0 is not a member of the group (even though it is a member of the field; we deliberately excluded it when defining the group); in contrast, 1 is a member of the group, and avoiding it would leak some information, in particular, the value that $Y$ is not (because $Y \ne X \odot Y$
)

If both $X$ and $Y$ are unknown, then revealing $X \odot Y$ does not reveal any information about $Y$

This answers your question two.

Revealing $X_i \odot Y$ for a large number of random $X_i$ values also does not reveal any information about $Y$.

This answers your question three.

If the above problems are hard to solve, probably finite field multiplication can be used as a method for masking countermeasure for side channel (at least theoretically).

Possibly, but it wouldn't be ideal.  For one, we had to deliberately exclude the 0 value; a real implementation that does masking can't ignore such a possible value; in particular, if you had a $Y=0$ value, masking wouldn't work in that case.  On a more practical note, masking would usually involve computing inverses, and while computing multiplicative inverses over $GF(2^{128})$ isn't that hard, it isn't exceptionally trivial either.


Is there any block cipher which is also a pseudo-random-permutation over the key As block ciphers are defined as a pseudo-random-permutation over the data (keyed with the key), I was wondering, if there are also constructions for which key and data can be switched and the cipher is a permutation over the key space for a fixed (data) input?
So the question is, if the output space of $E_k(a)$ for all possible $k$ covers the entire space of $\{0,1\}^n$
More formally:
$E_k$ is a block cipher with key size equal to block size: $\{ 0, 1 \}^n \times \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^n $
and $\exists a \forall k_1, k_2: E_{k_1}(a) = E_{k_2}(a) \Rightarrow k_1 = k_2$
Or more generally: with $f$ a function $\{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^n$
$\forall k_1, k_2: E_{k_1}(f(k_1)) = E_{k_2}(f(k_2)) \Rightarrow k_1 = k_2$
Or is this even true for every block cipher?

I am not sure about the "more generally" since in the latter definition you are applying a function of the key. This now makes it related to circular security. Regarding the basic question, this is not true in general, and I don't know if it's possible to build such a construction. What I can say is that there is a construction where the pseudorandomness property holds if the key is random OR if the data is random. This notion is studied in the paper Symmetric and Dual PRFs from Standard Assumptions: A Generic Validation of an HMAC Assumption by Mihir Bellare and Anna Lysyanskaya. This paper would be a good starting point for research.


Is there any general description language for block ciphers? In page 9 (16 in the PDF) of Final report of European project IST-1999-12324 (NESSIE), it is mentioned that:

  The NESSIE project is also developing a new generic tool to analyze block
  ciphers with differential [78] and linear cryptanalysis [422]. This tool is based on
  a general description language for block ciphers.

Is this "description language" publicly available?
Is there any other general description language for block ciphers or stream ciphers?
Is This tool publicly available?

I think what is meant by this paragraph is the language defined in report NES/DOC/TEC/WP2/007/2, "A System for Assisting Analysis of Some Block Ciphers", by Arueh Bibliowicz, Pnina Cohen, Eli Biham. It is listed on the "NESSIE public reports" page.

The language is something like a special-purpose programming language for block ciphers. It supports functions (with special notations for S-boxes and "Selections", rounds, key schedules), variables, constants, primitive arithmetic/binary operations (AND, OR, XOR, ADD, SUB, MULT, ROL, ROR, SHIFTL, SHIFTR).

The appendix contains DES as an example.

The analyzer tool mentioned there (which interprets the language and does some automated cryptanalysis) seems to be not public, though.


Validating subset of a password Is anyone aware of an algorithm/method that allows me to validate just a few letters (or other characters) from a password. For example, the application asks for the 2nd, 3rd, 6th and 9th letters from the password. Which letters are requested is determined randomly.

I really, really don't want to store passwords in plain text. This technique is used by at least one UK bank.

I this a good idea? Can anyone offer any help? I'm a fairly competent programmer.

1st Edit

When a password is required, the user is prompted to provide a random selection of the characters in their correct positions. This selection might be, say, the 2nd, 3rd, 6th and 9th characters, or might be some other selection, chosen at random. The only feedback that the user gets is "pass" or "fail". He cannot use this to probe each character in the password at his leisure.

Validating individual letters of a password reduces complexity of guessing that password by trying all possible variants, so I would suggest avoiding such a design.

PCP (probabilistic checkable proofs) is a well-known case of validating just a small portion of the "witness" (defined in that context), with focus on algorithm complexity.

Regarding "1st Edit": pass/fail response to "simplified" query is exactly how complexity is reduced. Random selection of letters requested might be considered a challenge/response scheme, on condition it can not be affected. Worst case would be repeated or single-letter queries.


Complexity of preimage resistance Why is the complexity of pre-image resistance $2$ raised to the power of $n$?
I have been looking in everything lecture about pre-image resistance, but I still didn't know the answer.

When the output of the hash function is $n$ bits, then there are $2^n$ possible outputs.

For a preimage attack you are given a hash $h$ and you need to find a message $m$ where $h = H(m)$.

Since there are $2^n$ possible outputs, the probability of guessing an input that that maps to the given output is $\dfrac{1}{2^n}$. So on average you need to try $2^n$ preimages. That is where the $2^n$ complexity comes from.


Encryption & decryption in AES CBC mode - Which is faster? I wrote a small code to compute the time consumption by the AES in CBC mode, I noticed that the encryption is faster than the decryption, my question: Is my result correct? If yes, why is the encryption faster?

I notice that AES-CBC encryption is faster than the description, is my result is correct?

It is plausible for a software-only implementation if single-threaded or if CPU time is cumulated across the multiple threads. For an implementation using AES instructions, the difference in speed can be barely noticeable or in either direction. For a competently made multi-threaded implementation with concurrently running threads and speed measured according to wall clock time elapsed, decryption of large amounts of data should be much faster than encryption.

Among reasons why AES CBC decryption can be slower than encryption (contrary to AES CTR which typically is nearly the same speed in both directions, since only IV generation differs)

AES CBC decryption involves the AES block cipher in decryption mode (when AES CTR does not), and in AES (contrary to DES) the design of the block cipher has reasons to make it slower in decryption mode:

The MixColumns step of encryption purposely uses a matrix with many coefficients at 1, when the inverse MixColumns used in decryption does not, thus requires more field operations. However that often makes no speed difference in hardware-assisted implementations.
The derivation of the AES round subkeys from the main key can be performed as the rounds are applied in encryption mode, but not in decryption mode, where the first subkey used is the last derived one. However that will make no difference for implementations that compute round subkeys only once, which is typical of software implementations optimized for many blocks.

Implementations of decryption that both decipher in place and process data blocks in the order used in encryption (rather than reverse) need to keep a copy of the previous ciphertext block in order to decipher the next, and that can add some time.
Sometime decryption is just not optimized as carefully as encryption is.

Among reasons why AES CBC decryption can be faster:

Decryption can be trivially parallelized on multiple CPUs, when encryption cannot (because the output of the previous block encryption needs to be known to prepare the input of the next block encryption). That leads to less wall clock time for decryption of multiple blocks in multi-threaded implementations when multiple CPUs or even simultaneous multithreading is available.
For the same reason, on architectures with high instruction latency, a single thread can interleave the decryption of multiple blocks from the same encrypted data stream and reach higher performance than for encryption (BearSSL uses that, as noted by SEJPM).
Decryption does not need to generate a random IV, when encryption does.


Module LWE with an even modulus Does module-LWE remains hard for an even modulus $q$, or a power of two?
This is true for Ring-LWE (pseudorandomness) and Module-LWR (SABER).
I can't find any reference to it!

Yes. Learning with Rounding (LWR) is a special case of LWE, where the errors are introduced deterministically by scaling and rounding operations. If you had an algorithm that could solve LWE, the same could be used to solve LWR.
Thus, Module-LWE is at least as secure as Module-LWR.


Understanding why Semantic Security implies Message Recovery Security I am stuck in the proof  where it says $$p_0=1/|M|$$ , I just do not understand how we can infer this equality.

Also, am I right in understanding that B is defined as choosing his two messages at random each time (i.e sampled uniformly from $M$)?

This is the link to two pictures: the first one containing the definition of Semantic Security, the second containing the definition of Message Recovery Security and the Proof I cannot follow:
https://imgur.com/a/ZP6xtgq

They are from Dan Boneh and Victor Shoup's free e-book 'A Graduate Course in
Applied Cryptography'"A Graduate Course in Applied Cryptography"

The definition of semantic security we see in the Shoup book is better explained in his well-known paper Sequences of Games: A Tool for Taming Complexity in Security Proofs.
You must pay the very attention to their words on page 15 of the book:

Actually, our attack game for defining semantic security comprises two alternative "sub-games",
or "experiments" --- in both experiments, the adversary follows the same protocol; however, the
challenger’s behavior is slightly different in the two experiments.

So, the point here is that we consider two games: this is why sometimes the adversary $\mathcal{B}$ receives from the SSChallenger a c (that I'll call it here) "well formed"; this is the Game 1, or the game of message $m_1$;
Sometimes, c is only "semanticly" equivalent to an encryption of $m_0$ or $m_1$; let me call it "dummy c"; this is the Game 0, or game of message $m_0$.
Furthermore, after receiving a c", the adversary $\mathcal{B}$ passes it on to $\mathcal{A}$, the message recovery adversary. When that c is "well formed", the chance of the adversary $\mathcal{B}$ is equal to the chance of $\mathcal{A}$ guessing.
But when c is dummy, $\mathcal{A}$ cannot help, and $\mathcal{B}$ best chance is $1/|M|$.


How can you extract individual characters of an encrypted string such as a password? Many banks and other systems have some sort of a  "select the Nth, Nth, and Nth characters of your password" system.

I don't believe they are going to be storing in plain text, nor would it make much sense to hash and salt each character of the password. Someone I asked mentioned they believe there are algorithms that can check or manipulate parts of encrypted data.

Do these algorithms exist and how do they work?

Most financial services companies that I've come across who make use of this kind of system are encrypting the password using a Hardware Security Module ("HSM").

In this kind of system the password is symetrically encrypted with a key held in the HSM, and then stored on disk.  The application will then pass the encrypted password and the individual characters into the HSM which will decrypt the password, make the comparison with the supplied characters and return a true/false answer to the application.

The security of this kind of system relies on the intended properties of the HSM which should be resistent to tampering and which run a very limited number of functions to reduce attack surface.

Also in this kind of situation key management is obviously very important as compromise of the key would allow for easy access to all customer passwords. This tends to lead to split authority and key parts being stored in safes, as a backup for the HSM.


Breaking ZIP 2.0 encryption without password I have an old sourcecode backup from my DOS days stored in a ZIP 2.0 encrypted archive, but I lost the password.

The password was written on a paper slip, but I remember that it consisted of 30+ completely random alphanumeric characters with some special symbols in between.

I have read that a GPU cluster will crack old ZIP 2.0 archives almost instantly, and that there is a vulnerability in the ZIP 2.0  encryption allowing an attacker to recover the password instantly if there are multiple files in the archive.

But what if there is only one file in the archive, and the password consists  of 30  completely random characters?

Can I expect fast recovery if I can run the process on a GPU cluster?

Addition: The archive was created with PKZIP 2.04C and there is nothing known about the filename extension and nothing known about the plaintext.

Does it change the calculus that the archiver was 2.04C and not 2.04G?

I will start with all relevant references I found, then tentatively answers the question. Feel free to improve this community wiki.

It was originally asked the effort to break PKZIP 2 encryption, described in section 6.1 of the .ZIP File Format Specification (with some refinements in the derived Info-ZIP appnote), assuming a high-entropy password (that is, next to 96-bit entropy for the internal key after password preprocessing), and a single file in a zip archive.

A most relevant attack on this cipher was made by Eli Biham and Paul C. Kocher: A known plaintext attack on the PKZIP stream cipher (1994, in proceedings of the 2nd FSE workshop).

That was improved by Michael Stay: ZIP Attacks with Reduced Known Plaintext (in proceedings of FSE 2001).

Peter Conrad's PkCrack is an implementation of the above with source and additional comments. It is the basis of the PKZIP section in Mark Stamp and Richard M. Low's Applied Cryptanalysis: Breaking Ciphers in the Real World (2007, Wiley-IEEE Press), nicely summarized in these slides.

In a single-file setup, these attacks depend heavily on the availability of some of the plaintext (formed by a 12-byte header, and the compressed form of the original file). At least about 13 known plaintext bytes are required (for a complexity of $2^{39}$ operations), more plaintext makes the attack easier. In the aforementioned 12-byte header, at least 1 byte is always known (part of the CRC in the archive's directory), or 2 bytes in archives made to be decipherable by PKZIP prior to version 2. Depending on the encryption/archiving program, some of the 11 or 10 other header bytes maybe low-entropy, for they are generated by a non-cryptographic RNG (sometimes rand() with 31-bit state as described in Michael Stay's article, or a variant where the additive constant is omitted according to this source; for a generator once in PKZIP 1.xx, refer to the Paul Kocher's ZIPCRACK documentation).

Further improvements are claimed by Kyung Chul Jeong, Dong Hoon Lee and Daewan Han's: An Improved Known Plaintext Attack on PKZIP Encryption Algorithm (in proceedings of ICISC 2011, paywalled); from the abstract, there seem to be improvements including in the single-file setup.

The following is thus very relevant (and unstated in the original question):

the exact program that generated the archive (that may be ambiguous from the archive);
the compression format/parameters (mostly known from the archive's directory);
the type/extension of the file (typically known from the archive);
whatever else is known about the plaintext and context of the creation of the zip file.

I have so far failed to locate information about details relevant to cryptanalysis:

the RNG (and its seeding) as in various versions of PKZIP 2;
the nature of the changes documented in late PKZIP 2 (see whatsnew.204) as:

  The security of (encryption) has been significantly improved in PKZIP/PKUNZIP 2.04c

how many files enciphered under the same password, each giving 1 plaintext byte, allow carrying an efficient attack (but that's irrelevant to the question).

It was added:

  The archive was created with PKZIP 2.04C and there is nothing known about the filename extension and nothing known about the plaintext.

Notice that in this sentence plaintext likely refers to the original file data, when everywhere else in this answer (following the terminology in the quoted literature) plaintext refers to the 12-byte header and the compressed form of the original file data.

It would be unusual that the filename and extension are not in the archive: by default, PKZIP 2 includes it in clear starting at offset 30, and before the PK marker at offset -22 from end-of-file. At least, the compression method used to produce the plaintext from the original file data, and one byte of the 12-byte header (taken from CRC), are bound to be in any undamaged archive (and readily shown by opening it with a modern zip tool such as 7-zip). The file name and extension, and ensuing reminiscence of the legitimate file owner, usually give some information on the original file. Let's, however, consider that a random file was given as input.

As stated, I found no analysis of the RNG used to prepare the 11 bytes of the header in PKZIP 2.04c and later; I'm incompetent about x86 code reverse-engineering; and anyway, from the whatsnew.204 citation above, likely this RNG is not nearly as bad as it was assumed to be in early ZIPCRACK, so I can best describe these bytes as random. I am not aware that the compression methods in PKZIP leave an easily modeled redundancy in their output. The only method that I can imagine to recover the (internal) key is to subject some of $2^{88}$ candidates to an impractically expensive test: that the plaintext could not have been generated by the compression method used (assuming the file is compressed rather than stored, I guess that a test of the CRC of the deciphered and uncompressed file can not help by a huge factor: if the original file data is short enough that this test is relatively inexpensive, too many candidate keys will remain that pass whatever automatic test we apply). Baring hypothesis change or progress in some of the above, it is inconceivable that the original file data can be recovered from the archive using anything remotely comparable to the computing effort that a GPU cluster can make in its operational life: if we had a thousand units of some kind each weeding a hundred thousand keys per microsecond for a century, odds are one in a thousand that the right key would be found.

Addition following partial quotation: I want to stress that the above bold statement makes multiple hypothesis:

a single file is encrypted; this is often not the case with real ZIP archives; multiple files enciphered with the same key, including in the same zip archive, do ease breaking PKZIP crypto;
nothing exploitable is known about the file's content; like, it is fully random, including its start; this is seldom the case for real files, to the point of making my statement theoretical in nature;
PKZIP 2.04g was used (which has become increasingly uncommon);
the PKZIP 2.04g TRNG has no major weakness (which I have not verified, and may depend on context; like, running in a VM);
the key has 96-bit entropy (most passwords used in practice have much less entropy);
the compression method used does not introduce exploitable redundancy (I only stated that I am not aware that this occurs).


Multivariate Cryptography: Security of the affine transform T In this question, I'd like to discuss the security of the last transformation $T$ employed in the construction of a MV-scheme. MVCrypto is based on solving a system of polynomial equations, but eventually, those polynomials are constructed by a linear combination of $T$ and a vector represententing an univariate polynomial in $F_{q^n}$ with coefficients in $F_q[x_1,\cdots, x_n]$. The following construction illustrates a typical description, where $\alpha : F_{q^n} \mapsto F_{q^n}$ is the transformation function (i:e Matsumoto-Imai) that changes the coefficients of $x'$ that are multivariate linear polynomials to multivariate non-linear polynomials. Note that here $v_s,v_t=[0]_n\in F_q^n$.
\begin{equation}
S,T \in F_q^{n \times n}, \quad x=(x_1,\dots,x_n)\in F_q^n \\ x'=S\cdot x \\y'=\alpha(x')\\y=T\cdot y'
\end{equation}

Matrices are very useful since we can represent $F_{q^n}$ as $F_q^n$: the n-dimensional vector space over $F_q$. So $x'$ can be viewed as a polynomial with coefficients that are linear combinations on $x$.

$$x'= \sum_{i=1}^{n}(\sum_{j=1}^{n} S_{i,j}\cdot x_j)y^{i-1}$$

The attacker has $n$ multivariate polynomials and their evaluation on $x=(x_1,\cdots,x_n)$. If he finds out the transformation $T$, he could attempt to invert $\alpha$ to obtain $x'$ and finally, $x$. My intuition tells me that an attacker can find a pair $z\in F_q^n, T'\in F_q^{n\times n}$ s.t satisfies $T'\cdot z = y$. As an example, consider the following case where $V=F_5^2$:

$T=\left(
\begin{array}{cc}
 1 & 2 \\
 3 & 1 \\
\end{array}
\right)$
$y'=(x_1x_2-1,x_1^2x_2+3)$

$T\cdot y' = y = (x_1x_2+2x_1^2x_2, 3x_1x_2+x_1^2x_2)$

It's pretty straightforward to recover $T'=T$ and $z=(x_1x_2,x_1^2x_2)$ since $y$ contains coefficients that are $n$ sums of the same $n$ factors, here $n=2$. Note that $z\neq y'$ but in this case is not hard to "bruteforce" until reaching the correct one.

EDIT: It's important that you note that $S$ and $T$ are interchanged in my example, $S$ is the first affine transformation and $T$ is the last one, however, in literature you found this to be the opposite. So the remark is that this question is about the last transform applied in the construction.

Question: Is there any information that describe an inversion of this construction, not by solving the polynomial eqs. but inverting the maps?

Almost a year since I posted this question, back then I was starting the study of the field. Now I can answer myself:

The security of both affine transforms $(T,S)$ relies on the IP2 assumption defined in the Isomorphism of Polynomials. Plus, if the private polynomial $\mathcal{F}$ is known there are other implications, like finding $T$ or $S$ would reveal the other affine transform.

This is, any multivariate scheme where $F,S$ or $F,T$ is known gives us the ability to break it. When $F$ is not known, as usually, we could obtain $T\cdot S$ as a matrix if both are linear transform instead of affine, and the linear part of $F$ is the identity matrix. From here nothing else can extracted, from the moment, in my study.

Regarding IP1, it can be broken when $F$ is known, or when $F$ is unknown by quering an oracle $n$ times with the canonical vectors $\overrightarrow{e_i}$.

Besides other techniques to strip out $T,S$ exist, i.e: when the characteristic is not $2$ and both transforms are linear.

There is more work not published in literature that I've discovered, i.e: the special structure of matrices $S$ that make the private polynomial invariant in a way that we can revover $T$, and more techniques that the audience must await for.


Performing differential cryptanalysis for randomly generated S-boxes As far as I know, performing differential or linear cryptanalysis always requires a knowledge of the S-boxes' content and order. Yet in Bruce Schneier's Applied Cryptography, it is stated that random key dependent S-boxes and/or randomly reordered S-boxes for DES can make the algorithm weaker.

So my question is, how would an attacker perform such attacks on a cipher without knowing the content of the S-boxes ?

With DES, the issue is the size of the s-box. The DES s-boxes are highly tuned for their security properties, but if you compare their nonlinearity to the larger AES s-box, the are quite inferior.

Note than random s-boxes and key dependent s-boxes are not the same thing. Random = fixed random, key dependent = permuted s-boxes based on the key. A random set of key dependent s-boxes is a different story, essentially, you are generating random s-boxes using key material.

If you tried to apply random key dependent s-boxes to DES, it can indeed make the whole algorithm weaker. With enough ciphertext/plaintext pairs, and knowledge of the the algorithm less s-boxes and keys, it is quite possible to perform key recovery. The biases are substantially larger with inferior s-boxes. I believe it reduced the data requirements of a differential attack by more than 10000X. Since the attack is much more effective than brute force, the additional complexity of using key material to generate the s-boxes does not strengthen it enough, only by about 32 times vs fixed random. See CS0816 for more detail.

A variant of DES exists where extra key material is used to reorder the standard s-boxes into one of 32 orders known to increase the strength of the algorithm, it is similar to having a key dependent s-box, and it does make the DES variant stronger.

With larger s-boxes and better design (and more importantly, larger keys), key dependent s-boxes work. Twofish is a great example of this. The key dependent s-boxes are not random, they are generated in a specific way from the key material as to be strong. However from a purely mathematical perspective they are not as strong as the AES s-box, but they have the advantage of not being known to the attacker. This may or may not be an advantage in the face of improving attacks. The additional advantage Twofish has is multiple s-boxes, which leaves less attack surface is one of the s-boxes does have a problem, but increases implementation complexity.

Another example is Khufu and Khafre, which are quite similar, but Khufu has key dependent s-boxes, and is more secure.

Overall, Twofish is thought to have better security than AES, and the key dependent s-boxes are one of the reasons why. DES in comparison, is not designed for key dependent s-boxes, which is why using them can weaken it more than it can strengthen it. The modified order however does work, and combined with DES-X style whitening, makes DES essentially invulnerable to linear and differential analysis, since the amount of plaintexts would be at least $2^{60}$ for linear, maybe more, and exceed the codebook for differential.

EDIT
Here is a new paper where AES variants with a secret s-box are attacked. Integral cryptanalysis was the method of attack.


Is XCBC where k2 and k3 might be the identical, secure? XCBC paper says all three keys should be independent. It doesn't say they must always be different. However it seems this is necessary to differentiate padded message and message without padding.

Lets say we derive all three keys so that key 2 and key 3 might be the identical (randomly). Is it secure?

If key 2 and key 3 has a nonnegligible chance to be the same, then the attacker has a nonnegligible chance of being able to generate a valid (Message, MAC) pair.

Here's how it works, if the message is not a multiple of 16, then XCBC pads the message out to the next multiple of 16; if it already is, the message remains the same.

Then, XCBC logically does a CBC mode encryption (using key 1); except that when it gets to the last block, it xor's in either K2 (if no padding was added) or K3 (if padding was added) before the final encryption.

Note that this padding operation is public; anyone can compute it.

What the attacker would do is request the MAC of a message M (which is not a multiple of 16); he gets a valid T.

Then, the pair (Pad(M), T) has a nonnegligible chance of being also valid; if K2==K3, then the message will be a multiple of 16, and so no padding is added; XCBC will xor in K2, but since K2==K3, that'll give the same result as the corresponding step during the query, and the final encryption will also be the same.


Why can't you decrypt an encrypted message with just the public key? How does asymmetric crypto work?
For example, if you use PGP in emails, you generate a private key that is known only to you and a public key, which is available to everyone.
Is there a simple way to explain, why you need a private key and why no one can decrypt the message with just the public key?
I think of an explanation like for example with prime numbers:

If you multiply two large prime numbers, you get a huge non-prime number with only two (large) prime factors.
Factoring that number is a non-trivial operation, and that fact is the source of a lot of Cryptographic algorithms. (See one-way functions for more information.)
The product of the two prime numbers can be used as a public key
The primes themselves as a private key. So the private key is the knowledge of two very large prime numbers

for easy understanding lets take the simple example (very large) prime numbers: 3 and 5:

private key: the knowlege of 3 and 5
the public key is just those numbers multiplied: 15
you cannot find out 3 and 5, so the message encrypted with 15 is ...

Here is a quite good explanation already, but it is not clear enough:
Is there an intuitive explanation as to why only the private key can decrypt a message encrypted with the public key?
Can you please add an example with those numbers?

I stumbled onto this great write up by Cloudflare a while ago as I was trying to understand Elliptic Curve Crypto better. It however starts of with some background on Public Key Cryptography followed by a detailed explanation and example of RSA key pair genaration AND how those keys (smallish primes) are used to encrypt a basic message. I suspect you will find that example answers some of your questions.

Specifically refer to the sections titled "The dawn of public key cryptography" and "A toy RSA algorithm".

All subsequent sections deal with ECC and go into a fair amount of detail (a great article on the whole).

Edit: If you tinker with the values in the example it should illustrate why the mathematics would not allow you to decrypt a message using the public key.


Why would this method of discrete logarithm finding not work? Say we do know $b$ but not $k$, and are given $g$ such that $g\equiv b^k\pmod p$. And say there exist factors $E = e + m'p$ ($e \equiv b^i \bmod p$) and $F = f + m''p$ ($f \equiv b^j \bmod p$) of $g$. Then $EF = g + pm = b^k$ for some $m$, $m'$ and $m''$.

So if we can find the right $(m, m')$ we can factor $G = g+pm = EF$. Then $E$ is congruent modulo $p$ to a power of $b$, and so is $F$. But note that $E$ and $F$ may not be perfect powers of $b$.

So we generate values of $E$ that are perfect powers of $b$, and then see if we can factor a member of the congruence class of $g$ mod $p$ — i.e. are any members of the congruence class of $g$ mod $p$ multiples of $E$? We can use the Extended Euclidean algorithm for this if $g$ is $\pm1$. Maybe we could also use the EEA for this if $g$ is any number $d$, by reducing the $g+pm$ and $E$ by the multiplicative inverse of $g$ mod $p$ (which we can find).

So if we can find a solution in $F$ to : $g \equiv b^i F\bmod p$ then we can reduce the problem to finding the exponent (to base $b$) of $F$ mod $p$. So then shouldn't we be able to find a sequence of exponents of our perfect power (the $E$s, the exponents being the $i$s) = until $F = 1$. At that time the sum of those exponents will be congruent (mod $p$) to the exponent of $g$.

It is on this basis that I claim that factoring is equivalent to the discrete log problem.

Is this hopelessly confused, or is there something here?

The flaw in your reasoning lies in your assumption that finding the discrete log of $f$ is any easier than finding the discrete log of $g$.  It just isn't.  That assumption is not correct.  And if you try to recurse and apply your procedure to $f$, you'll recurse for a very long time, and your algorithm will take exponentially long.

Let me summarize your algorithm: to find the discrete log of $g$, you suggest we  pick some specific power of $b$, say $e \equiv b^3 \pmod p$, then compute $f \equiv g/e \equiv g b^{-3} \pmod p$, then somehow magically find the discrete log of $f$.  The problem with this algorithm is that "magic" doesn't exist.  If you want to find the discrete log of $f$, that's every bit as hard as finding the discrete log of $g$.  So the "factoring" hasn't helped you one bit.

I imagine you're going to be tempted to respond "but I just recurse, and apply my method recursively to $f$!", so let me proactively explain why that ain't gonna work: first, you have not identified any base case, so your recursion never terminates; and second, if you identify a reasonable base case (e.g., if $g$ is a perfect power of $b$, stop immediately), you'll find that you will need to recurse an exponential number of times, so the running time of your algorithm will be worse than brute-force search.

There is no known reduction that proves that the discrete log is as easy as factoring.  Lots of people have tried to find one, and failed.


What is the difference between pseudorandom permutation/pseudorandom function/block cipher? What is the difference between;

pseudorandom permutation
pseudorandom function
block cipher?

Very confused with the 3 terms and I am not good at advanced math. Can someone explain in plain word?

All three are families of functions.  For example, $f_k(x) = k \oplus x$, where $\oplus$ is xor and $k$ and $x$ are 256-bit strings, is a family of functions; for any 256-bit string $k$, there is a function $f_k$ which given another 256-bit string $x$ returns the xor of $k$ and $x$.  The input and output spaces need not be the same; we could imagine a family of functions $f_k$ from a 512-bit input $x$ to a 128-bit output $f_k(x)$, keyed by a 256-bit string $k$.  Here is a small function family $g_k$ with a 1-bit key, a 2-bit input, and a 3-bit output:

\begin{equation*}
\begin{array}{c|c}
x & g_0(x) \\
\hline
00 & 111 \\
01 & 000 \\
10 & 100 \\
11 & 110
\end{array}
\qquad\qquad
\begin{array}{c|c}
x & g_1(x) \\
\hline
00 & 011 \\
01 & 110 \\
10 & 100 \\
11 & 100
\end{array}
\end{equation*}

A pseudorandom function family is a family of functions—say functions from 512-bit strings to 128-bit strings, indexed by a 256-bit key—which has the following property.

Suppose I flip a coin 256 times to pick $k$—that is, I choose $k$ uniformly at random.
Suppose I also pick a function $F$ from 512-bit strings to 128-bit strings uniformly at random from all $(2^{128})^{2^{512}}$ such functions, by flipping a lot of coins—enough to fill a book with $2^{512}$ pages so that each page has a 128-bit answer on it.

(Each table above has $4 = 2^2$ rows, because the input is 2-bits long, with a total of $3 \cdot 2^2 = 12$ bits of outputs written down, because there are three bits of output for each distinct input and $2^2$ distinct inputs.  For a uniform random 512-bit-to-128-bit function, you need $2^{512}$ rows, and each row has $128$ bits of output, for a total of $128 \cdot 2^{512}$ bits just to write down one of the $(2^{128})^{2^{512}} = 2^{128 \cdot 2^{512}}$ different functions of that shape!)
I will pick one of these functions—$f_k$ or $F$, but you don't know which—and tell you what the value of the function is at any point you ask.

(Actually I don't need to fill the book up front; if I chose $F$, I can fill out the pages of the book lazily as I get queries from you.)

You can't figure out whether I gave you a member of the function family, $f_k$, or a uniform random function, $F$.

In other words, the probability distribution on functions $f_k$, when the key $k$ is chosen uniformly at random, is very close—as far as computationally bounded decision algorithms can discern—to the probability distribution on functions $F$ chosen uniformly at random from all functions.

A pseudorandom permutation family is similar, except $f_k$ and $F$ are restricted to be permutations, i.e. their input and output spaces are the same, say the set of all 256-bit strings, and they map every input to a unique output so that there is also an inverse function.  So there aren't quite as many possibilities for $F$—while there are $(2^{256})^{2^{256}}$ functions of 256-bit strings, there are only $2^{256}! \approx (2^{256}/e)^{2^{256}}$ permutations of 256-bit strings.  A block cipher is just another term for pseudorandom permutation family, for the most part.*

Here's an example of a small permutation family $\pi_k$ for comparison—again the key is 1-bit, and the inputs and outputs are 2-bit strings:

\begin{equation*}
\begin{array}{c|c}
x & \pi_0(x) \\
\hline
00 & 00 \\
01 & 11 \\
10 & 10 \\
11 & 01
\end{array}
\qquad\qquad
\begin{array}{c|c}
x & \pi_1(x) \\
\hline
00 & 01 \\
01 & 00 \\
10 & 10 \\
11 & 11
\end{array}
\end{equation*}

Note that unlike the tables for $g_k$, each output appears exactly once in each table here, so we can flip each table around to get an inverse permutation.

We can interpret the bit strings as integers in (say) big-endian binary, and write this using the alternative notation $\pi_k = (\pi_k(0) \; \pi_k(1) \; \pi_k(2) \; \pi_k(3))$ for permutations, by saying that $\pi_0 = (0 \; 3 \; 2 \; 1)$ and $\pi_1 = (1 \; 0 \; 2 \; 3)$.  Of course, for a pseudorandom permutation family like AES, the number of elements being permuted is not $2^2 = 4$ but $2^{128} = 340282366920938463463374607431768211456$, so we don't quite have enough space here to write AES down exhaustively in either notation even for a single key.

Actually it's not so much that a family of functions is or is not a pseudorandom function family, but rather we quantify your advantage as an adversary in playing that game.  Specifically, we consider a decision algorithm $A(\mathcal O)$ which takes an oracle $\mathcal O$—which might be $f_k$ for uniform random $k$, or might be a uniform random $F$—and returns a decision in $\{0,1\}$, and we consider the distance between the probability that $A(\mathcal O)$ returns $1$ given $f_k$ for uniform random $k$ and the probability that it returns $1$ given uniform random $F$, called the advantage of $A$ as a PRF distinguisher:

\begin{equation*}
  \operatorname{Adv}^{\operatorname{PRF}}_f(A)
  := \lvert\Pr[A(f_k)] - \Pr[A(F)]\rvert.
\end{equation*}

The PRP advantage is similar, but again $f_k$ and $F$ are restricted to be permutations.  If it's very hard to tell whether the oracle is answering for $f_k$ or $F$, then this distance is nearly zero.  Obviously, there is always a distinguisher with nonzero advantage: guess a key $\hat k$ at random and check whether $\mathcal O(x) = f_{\hat k}(x)$, but the advantage is very small, inversely proportional to the size of the key space.  What's more interesting is distinguishers that have much higher advantage.

We conjecture for certain functions like HMAC-SHA256 or KMAC128—based on a long track record of failure by cryptanalysts to find good distinguishers—that this distance is small no matter what the adversary $A$ is, as long as $A$ makes an imaginable number of queries.  (For example, we're not interested in an adversary that makes $2^{256}$ queries to the oracle, because nobody can do that.)

Then, when studying higher-level constructions like CBC-MAC, we set a bound on the forgery probability of the higher-level protocol in terms of a bound on the distinguishing advantage against the underlying PRF.  That way, we can study whether something like CBC-MAC is a good way to build a MAC out of a PRF separately from whether AES is a good PRF.

‘Wait, AES is a good PRF?’, you say, ‘I thought AES was supposed to be a permutation!’  Well, any PRP makes a good PRF up to the birthday bound.  Specifically, there's a theorem, sometimes called the PRF/PRP-switching lemma, that if $f_k$ is a $b$-bit permutation, then for any adversary $A$ making at most $q$ queries to the oracle, $$\operatorname{Adv}^{\operatorname{PRF}}_f(A) \leq \operatorname{Adv}^{\operatorname{PRP}}_f(A) + \binom{q}{2} 2^{-b}.$$  As long as $q \lll \sqrt{2^b} = 2^{b/2}$ so that $\binom{q}{2} = q(q - 1)/2 \lll 2^b$, the term $\binom{q}{2} 2^{-b}$ is very small.  In other words, as long as our application keeps its data volume well below the birthday bound of $2^{b/2}$ blocks, a good pseudorandom permutation family like AES is nearly as good as a pseudorandom function family.  This is, incidentally, the general reason why cryptosystems involving AES are not safe for more than a few petabytes of data under a single key—and for some of them the safe data volume limit is much lower.

* In some security analyses, it may be convenient to model a block cipher with a slightly stronger idealization than pseudorandomness: the ideal cipher model.  Pseudorandomness is a kind of logic quantifier: for uniform random $k$, $f_k$ is hard to distinguish from a uniform random permutation, and it applies to specific function families like HMAC-SHA256.  In the ideal cipher model, we study protocols where the function family itself is randomly chosen: for all distinct $k$, $f_k$ is an independent uniform random permutation.  Like the random oracle model, it is a model for how adversaries are structured, rather than a ‘property’ that a specific computable thing like SHA-256 or HMAC-SHA256 can exhibit.


Why does PBKDF2 use HMAC? When I learn PBKDF2, I found out most of the articles say that the PBKDF2 use HMAC as PRF. Why is HMAC? Can I use other pseudorandom functions? Is HMAC safer than any other functions for PBKDF2?

TL;DR: Bit values of passwords are "weirdly" distributed and hash functions (and thus HMAC) are generally believed to deal better with them.

Why is HMAC?

Presumably originally the idea was to improve on previous designs which were all very hash-focused. People wanted to use hash functions in some way to process passwords. But the designers of PBKDF2 probably considered it wise to use a PRF (thereby reducing assumptions on the underlying function) and HMAC is the standard way of turning a hash into a PRF. Also they probably liked the idea of not having to jump through hoops to define ways to process arbitrary-length passwords.

Can I use other pseudorandom functions?

So, if your password was a uniformly random bit sequence, then yes absolutely you could use other PRFs and get a PRF out of PBKDF2. However, passwords generally don't stay to that model. In that case one usually turns to hash functions to map a high-entropy non-uniform value to a high-entropy uniform value.
Of course the above argument raises the question "what about KMAC and other hash-based PRFs"? They should work similarly well as they tend to inherit the security advantages of their underlying hash functions. Note however that some such constructions (not KMAC) have weaknesses with regards to variable-length keys. For those fix the length of your salt.
As for actually using KMAC (and this Keccak / SHA-3), this is a difficult situation. In principle it works. However you usually want to use functions for password derivation where the optimal ASIC to brute-force it would essentially be the hasher's normal CPU (or only marginally better). However until we get specialized Keccak extensions dedicated Keccak circuitry will likely be much faster than software implementations making PBKDF2-KMAC a much inferior choice to e.g. Argon2.


How can I turn this cipher into a perfect cipher by altering only its encryption algorithm? Given a toy cipher that picks a key, k, from the key space of {00,01,10} and a message,m, from the same set {00,01,10} and encrypts using E = m ⊕ k.

How can I change the encryption function E in order to make this cipher perfect(according to Shannon's perfect secrecy rule)?

NOTE: This cipher is not perfect because there's no way to get a ciphertext of 11 if the k or m are 00 thus the ciphertext reveals extra information about the plaintext which makes this cipher imperfect.

Any hints or suggestions as to how to approach the problem would be helpful.

Two ways to go about it:

Enlarge the key space so that every possible ciphertext is equally likely.
Change the operation from XOR to one that stays in the set of the three values you have.

Either would work, but since you asked for hints I will leave the specifics for you.


How we can calculate AES Inverse SBox? I am trying to find out the inverse of and SBox, but in vain, I have seen multiple questions over StackExchange, But I cant be able to solve my issue.
As in this question, How are the AES inverse S-Boxes calculated? As in this link I followed all the procedure and I made a 16x16 Matrix of inverse. But When I multiplied two(Multiplication in GF-2^8) corresponding entries against a SBox value to a inverse SBox value. If this is true in that question then my multiplication would be resulted into 1. But it is not resulting into 1.
I used X = 0x52. Sbox Generated with C = 0x63 is given Below

 S box Generated
 Inverse Sbox

S-Box's are invertible. The inverse S-box is simply the S-box run in reverse.

One way to calculate the inverse of an S-box is; all you need to use the S-Box itself to find an element's inverse.

For example; look at the Wikipedia example.

00 maps to 63 in the S-box, 63 maps to 00 in the inverse S-Box
54 maps to 43 in the S-box, 42 maps to 64 in the inverse S-Box

This can be executed by passing only once the elements of the S-Box. The complexity will be $\mathcal{O}(n^2)$ where $n$ is the $row=column$ size of the matrix.


Why a key pair is used in OpenSSL ECDSA_sign or ECDSA_do_sign instead of only private key ? If the digital signature in ECC (ECDSA) is made using a private key, why is the OpenSSL library using ECKEY pair as an input parameter instead of the private key only ?

ECKEY object may contain:

Group
Private key
Public key

Both Group and Private key are needed to be able to calculate signature. It is most convenient to use generic ECKEY object (from API perspective), as it easy to e.g. convert between commonly used PKCS#8 PEM encoded EC private keys and ECKEY objects, and because just a BIGNUM would not be sufficient.

It is possible to use ECKEY object that does not have public key field filled in for ECDSA signing. Likewise, certain functions (most notably verify operation, where private key usually is not accessible) can be used with ECKEY that does not private key filled in (i.e., it is NULL).


Understanding the big picture with regard to how anonymous credentials work I'm trying to learn about anonymous credential systems. I started with Lysyanskaya's thesis, which gives an outline of how to build an AC system given some particular primitives (signature scheme, commitment, etc.), and then looked at some papers building those particular primitives. I have also come across some papers (one using RSA assumptions and one using bilinear pairings) which don't follow Lysyanskaya's "formula" but still manage to form a valid AC system.

I can follow along in each of the papers from one line to the next, but I still don't exactly understand what makes it "tick". Can someone suggest a way to better understand this? Of course, the various assumptions (pairings, discrete log, RSA, etc.) offer some way of "hiding" information to achieve anonymity. But I don't really see what property exactly is necessary to make the system work.

Apologies if this question is vague. Can someone suggest what to do to better understand what makes these systems work? I fail to see the commonalities between the schemes.

I'll try to give some high-level intuition of the used construction paradigms in my answer below. First, note that we distinguish between one-show and multi-show anonymous credential schemes.

For one-show credential schemes, you essentially have that multiple showings of the same credential can be linked to each other, while showings are unlinkable to the issuing. Those schemes are typically instantiated using Blind signatures (e.g. Brands' credential scheme, or Baldimtsi and Lysanskaya's anonymous credentials light). Essentially, a Blind signature scheme is an interactive protocol where the signer does not learn the signed message. The issuer usually signs a blinded version of a commitment to the attributes of the user and the user then uses the unblinded, signed commitment together with a proof of knowledge upon showing. From a very high-level point of view, the property that the signer does not learn the signed message helps to achieve unlinkability between issuing and showing.

For multi-show credential schemes you essentially have that even multiple showings of the same credential are unlinkable. Those schemes are typically instantiated using a signature scheme where the signatures can be publicly randomised and which is compatible with zero-knowledge proofs. The issuer signs commitments to the attributes and upon showing one randomizes the signature and proves knowledge of the signature and the attributes (only the attributes which should be shown get revealed). The most prominent instantiations of this paradigm are Camenisch and Lysyanskaya's anonymous credential schemes (both the RSA variant and the pairing variant). Recently, another paradigm to construct multi-show anonymous credentials was introduced by Hanser and Slamanig. The use signature schemes where signatures and signed messages can be publicly randomised, together with a compatible commitment (i.e., one which still binds the committed message even when re-randomised). Here, the issuer issues a signature on commitments and showing amounts to re-randomizing the signature and the signed message and opening the commitment with respect to the attributes to be shown (they also require a simple zero-knowledge proof to guarantee freshness).


How are m2 and m3 boxes computed? I stumbled upon an AES implementation that uses boxes with multiples of 2 and 3 for its MixColumns operation. When inspecting the m2 box, I saw that the first line is :
0x00,0x02,0x04,0x06,0x08,0x0A,0x0C,0x0E,0x10,0x12,0x14,0x16,0x18,0x1A,0x1C,0x1E,

So nothing abnormal, but once we reach 0xFE, the next line is :
0x1B,0x19,0x1F,0x1D,0x13,0x11,0x17,0x15,0x0B,0x09,0x0F,0x0D,0x03,0x01,0x07,0x05,

Why does it become so weird ? How were those boxes computed ?

A byte $b$ in AES represents a polyonmial of degree at most $7$ where the coefficients are the bits of $b$. An example is the byte written in hexadecimal f3 represents $x^7 + x^6 + x^5 + x^4 + x + 1$ (with big endian order).
There are two operations with these polynomials: the addition and the multiplication. Given the polynomials $f(x) = a_7 x^7 + \cdots + a_1 x + a_0$ and $g(x) = b_7x^7 + \cdots + b_1 x + b_0$, then the addition is
$$
f(x) + g(x) = (a_7 \oplus b_7) x^7 + \cdots + (a_1 \oplus b_1) x + (a_0 \oplus b_0),
$$
using a xor between the coefficients of each polynomial, so the resulting polynomial is also of degree at most $7$, with binary coefficients.
Concerning the multiplication it is necessary to add a reduction in case the degree of the polynomial is greater than $7$. Example:
$$
f(x) \cdot x = a_7 x^8 + \cdots + a_1 x^2 + a_0 x.
$$
In particular for AES, it is a modular reduction with the polynomial $h(x) = x^8 + x^4 + x^3 + x + 1$. It means that in all the calculcations, we have
$$
x^8 = x^4 + x^3 + x + 1,
$$
so the previous calculation becomes
$$
\begin{array}{rcl}
f(x) \cdot x & = & a_7(x^4 + x^3 + x + 1) + a_6 x^7 + \cdots + a_1 x^2 + x \\
 & = & a_6 x^7 + a_5 x^6 + a_4 x^5 + (a_7 \oplus a_3) x^4 + (a_7 \oplus a_2) x^3 \\
& & + a_1 x^2 + (a_7 \oplus a_0) x + a_7
\end{array}
$$
Why in particular this polynomial $h(x)$ is because it has degree $8$ and cannot be written as a product of two (or more) non-trivial polynomials (similar as prime numbers that cannot be written as the product of two or more integers greater than $1$).
Now, all that is said above is enough to understand the m2 and m3 boxes that can be encountered in some implementations. The m2 box is only the multiplication by $x$ of all polynomials. For polynomials of degree at most $6$, it means only a bitwise shift left, but for polynomials of degree $7$, a reduction is necessary.
$$
\begin{array}{ccc}
\hline
\text{hex} & \text{polynomial} &  \text{times } x & \text{hex}\\
\hline
\texttt{00} & 0 & 0 \cdot x = 0 & \texttt{00}\\
\texttt{01} & 1 & 1 \cdot x = x & \texttt{02}\\
\vdots \\
\texttt{7F} & x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 & x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x & \texttt{FE} \\
\texttt{80} & x^7 & x^7 \cdot x = x^4 + x^3 + x + 1 & \texttt{1b} \\
\vdots \\
\hline
\end{array}
$$
The m3 box is the multiplication by $x + 1$ and is easily obtained with an addition of the polynonmial $f$ with the result of the m2 box since:
$$
\begin{align}
f(x) \cdot (x + 1) & = f(x) \cdot x + f(x) \cdot 1 \\
& = f(x) \cdot x + f(x)
\end{align}
$$
More information on the wikipedia page of finite fields for a more general description finite fields.


Alice answering Bob without knowing the question I'm a student and I don't know how to solve the following problem :

Alice is proposing a 10 questions list to Bob.
Bob choose only 1 question and wants to know the answer without Alice knowing the question.
Alice wants that Bob can only have 1 correct answer.

Is it possible ? If yes how ?

In my mind it should begin like this :

Bob & Alice knows the 10 questions
Alice encrypts each answer with a different key
Alice sends the 10 encrypted answers to Bob
Bob chose a question (ex : question 2)

Here comes the intricate part in my mind :

Bob should crypt the question (How?)
Bob sends the encrypted question to Alice
Alice answer to bob with the encrypted decrypting key (How?)
Bob can decrypt his answer, Alice doesn't know what key she gave

Thanks :)

You can use Oblivious transfer protocol for the answers: https://en.wikipedia.org/wiki/Oblivious_transfer

Here is an example with only 2 answers ($m0$ and $m1$) and uses RSA ($e,d,N$) :

In your case Alice would have to send $x_0 \ldots x_9$ and Bob would have to pick $b \in \{0,\ldots,9\}$ where $b$ is the number of his question. The operation $m + k$ can be considered as a symmetric encryption of $m$ with the key $k$.


Capacity of Advanced Encryption Standard in terms of File Encryption what is the capacity of AES in terms of File Encryption?
is it really good to encrypt a large files in AES? ex. I am encrypting a 8GB of File... is it still good to used AES?
is it still good to used AES-OFB in encryption of large files?

What also will be the issue if I used AES-ECB in file encryption? is the only issue will be the odds of having a same 128-bit block of data?

If you mean how much data can safely be encrypted by AES with a single key (and IV), AES is designed to encrypt up to $2^{64}$ blocks of data before becoming susceptible to certain statistical attacks (in particular distinguishing the encrypted file from truly random data), because of its 128-bit block size. 8GB (= $2^{36}$ bits = $2^{29}$ blocks) is quite below this limit, you are fine.

That said, AES-OFB alone is not enough, as it is a streaming mode the plaintext can be altered rather trivially assuming it is partially known beforehand. You will want something like a HMAC on top to ensure the file does not get corrupted by an attacker at some point (note that this does not mean a block mode like CBC does not need one - it does, but plaintext cannot be altered in such predictable ways)


PGP Encryption and signing There is a requirement for me to both encrypt a file with the clients public key provided to us and sign the same file with our (my own) private key which they have the corresponding public key for.

Should this be a 2 step process (i.e. first encrypt then sign) Or can this be done in one shot using a single PGP command with multiple parameter? If so, can you please provide a sample of what the command would look like?

Should this be a 2 step process ...

Yes, you need to do it in 2 steps with common algorithms such as RSA, ECDSA, ECIES, etc. (because they're not signcrypt algorithms).

You should first encrypt, then sign, as this ensures with (slightly) better confidence that signature don't reveal information about the file/message.

  If so, can you please provide a sample of what the command would look like?

Programming questions are off-topic. But if you really don't know how to use the command line, there is a high chance you can hurt yourself doing it, so a GUI app is recommended.


Why must s be kept secret in pedersen commitments? I was reading up on Pedersen commitment over at this website: https://asecuritysite.com/encryption/ped, where they calculate $h=g^s \bmod p$, and they say that $s$ must be a secret.
I wonder why this is a requirement? Since verifiers will know the value of both $h$ and $g$ anyways, and a random value $r$ is used for creating the commitment, I don't see why $s$ must be kept secret?

I wonder why this is a requirement?

If the prover knows what $s$ is, they can open the commitment to any value they want.
Suppose that the commitment was $c = g^x h^r$, where $x$ is the originally committed value.
Then, if the prover knows $s$, then he can take an arbitrary value $y$ and compute $r' = r + s^{-1}(x - y)$; then, he can open the commitment as $c = g^y h^{r'}$
This would be accepted as a valid opening, because $g^xh^r = g^{x+sr} = g^{x + s(r' - s^{-1}(x-y))} = g^{y + sr'} = g^y h^{r'}$, and so he has successfully opened the commitment to a value selected after the commitment was published.


Generating a NIST P-256 private key From the Curve25519 spec I learned that it possible to take a random 32 bytes and with a few operations make it on the curve:

To generate a 32-byte Curve25519 secret key, start by generating 32 secret random bytes from a cryptographically safe source:

mysecret[0], mysecret[1], ..., mysecret[31].

Then do

mysecret[0] &= 248;
mysecret[31] &= 127;
mysecret[31] |= 64;

Is there a similar way to take random bytes and use it for a p-256 private key?

A NIST P-256 secret key (for ECDH or ECDSA) represents any scalar modulo $\ell$ for $$\ell = 2^{256} - 432420386565659656852420866394968145599,$$ whereas an X25519 secret key represents an integer multiple of 8 between $2^{254}$ and $2^{255}$, interpreted as a scalar modulo $8 p_1$ for $$p_1 = 2^{252}  + 27742317777372353535851937790883648493.$$  In both cases, the secret key should be chosen uniformly at random from all possibilities, so that every possibility has equal probability.  Here $\ell$ and $p_1$, both large primes, are the orders of the standard base points on the respective curves.

The NIST recommends, in FIPS 186-4 Appendix B.4 pp. 61–64, that you either generate 320 bits uniformly at random, reduce modulo $\ell - 1$, and add $1$; or do rejection sampling, drawing 256-bit $n$ and starting over unless $0 < n < \ell$.  These methods keep the modulo bias respectively either small or nonexistent, and avoid $n = 0$.  The benefit of this negligible, so I would just accept the modulo bias of picking 256 bits uniformly at random and performing a single conditional subtraction, losing less than a single bit of theoretical security.  But if you're using NIST P-256, you're probably slave to compliance with government bureaucracy standards, so you should probably follow the letter of the standard.

Technical details, or, why is it different for (say) ECDH over NIST P-256 and X25519?

The curve group NIST P-256 has prime order $\ell$, and the standard base point generates the entire group, so even if you reveal $[n]P$ for attacker-controlled points $P$ where $n$ is your secret scalar, there are no active small-subgroup attacks possible on NIST P-256; and although the quadratic twist of NIST P-256 does not have prime order, it happens to have the modest cofactor $34905 = 3 \cdot 5 \cdot 13 \cdot 179$ which confers a degree of twist security.  Caveat: If you foolishly handle uncompressed $(x, y)$ inputs, twist security is not enough; you must still validate them to thwart invalid-curve attacks.

In contrast, the curve group Curve25519 has composite order $8 p_1$, and its twist has composite order $4 p_2$ for another large prime $p_2$, while the standard base point has order $p_1$.  So to thwart small-subgroup and twist attacks without requiring point validation, the secret scalar $n$ is always chosen to be congruent to zero modulo the cofactor 8 and the twist cofactor 4, and public keys are transmitted as $x$ coordinates only so the only possible invalid curve is the quadratic twist.


Reusing keys with AES-CBC I heard that key/IV pairs must not be reused in AES-CTR, or when using any stream cipher for that matter. Yet the attacks described do not seem to apply to AES-CBC.

Is reusing the same key several times dangerous in AES-CBC mode? Does the use of a random IV preclude all possible attacks in such cases?

Key/IV pairs should not be reused for either AES-CTR and AES-CBC - or for any other symmetric cipher for that matter. As a cipher is a Pseudo Random Permutation (PRP) inserting the same input will result in identical output. If a key/IV pair is reused then information is leaked to an attacker; the attacker can distinguish data with the same contents.

CTR is a streaming mode for block ciphers. In AES-CTR the key stream depends only on the key and the IV, not the plaintext. This key stream is XOR-red with the plaintext. It is possible to find additional information about the plaintext in addition to the issue above; if the key and a counter value are reused then the XOR of two ciphertexts is identical to the XOR of the plaintexts. So the key would still be safe, but the plaintext can be easily retrieved.

Reusing the key for any cipher should be no issue as long as the IV is unique - up to the specified amount of plaintext that the cipher can handle, usually a very large amount. In the case of CTR the IV should be unique enough to make sure that the counter does not repeat. Please read into CTR mode to see what that means when generating an IV. Make sure that it is understood what IV/nonce means for the specific application of CTR; the terms can be mixed up and may be used differently for specific protocols and implementations.

For CBC there are additional constraints: information about the IV should not be available in advance to an attacker that can alter the plaintext (chosen plaintext attack or CPA). Using a 16 byte value that is indistinguishable from random to an attacker should indeed preclude any attacks on the block cipher mode. That IV may simply be prefixed to the ciphertext in plain. If an authentication tag is used over the ciphertext then the IV must however be included in the calculation of the authentication tag (e.g. HMAC value).


Can someone explain the definition of four square roots as it pertains to groups in Z*p? So I'm given the following as a problem:

When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $Z^∗_N$ have either
zero or four square roots. A quarter of the points have four square roots; the rest have no square
root. The four square roots of $x ∈ Z^∗_N$ will look like $±a, ±b$. (Of course, −a means N − a since
we’re working modulo N.) Suppose that I give you an efficient deterministic algorithm S that, on
input x that has square roots, finds some square root. (If x does not have a square root, it returns
⊥.)
Use S to make an efficient probabilistic algorithm F that factors N.

I am not asking for a solution to the problem, rather an understanding of what "four square roots" could possibly mean? How can a single element $x∈ Z^∗_N$ have "four square roots"?

"$x$ has four square roots" means there are four distinct elements $r$ in the group such that $r^2 = x$.

For example, in $\mathbf{Z}_{15}^\times$ the element $1$ has four square roots, which are $1$, $4$, $11$, and $14$ (note that $11 \equiv -4$ and $14 \equiv -1  \pmod{15}$).


What does the linear assumption over bilinear groups mean? In the abstract of "Cryptography with Tamperable and Leaky Memory", at the end of the 3rd paragraph, the authors say:

  In both schemes we rely on the linear assumption over bilinear groups.

What is the linear assumption ? How do you break this linear assumption ?

I would appreciate if somebody could give me concrete examples. More specifics about the paper where they talk about linear assumption:

The problem you are referring to seems to be the Decisional Linear Assumption (DLIN), which states that given $(u,v,u^a,v^b)\in \mathbb{G}^4$, it is hard to distinguish a couple $(h,h^{a+b}) \in \mathbb{G}^2$ from a totally random couple $(h,h') \in \mathbb{G}^2$.

There is also the Computational Linear Assumption (CLIN), which states that it is hard to  compute $h^{a+b}$ given $(u,v,u^a,v^b,h)$.

The Decisional Linear Assumption is a weaker assumption (in the sense that it's harder to break) than Decisional Diffie-Hellman Assumption (DDH), so it can come in handy when DDH does not hold, which often happens in pairing-based cryptography.
According to this paper (page 9), we even have the following reduction :
$$DDH < DLIN < CLIN < CDH$$

I tried to sum up what I found but I'm not an expert in pairing-based crypto so I hope everything was correct.


Do all ciphers have equivalent decryption keys? Do all ciphers suffer from the problem of multiple equivalent decryption keys? Is the existence of equivalent keys an essential property for the security of a cipher?

If you could prove that a cipher had no equivalent keys, would that lead to a procedure for recovering the key under the known-plaintext attack model?

Do all ciphers suffer from the problem of multiple equivalent decryption keys?

No. The number of non-equivalent keys is bounded by the number of permutations. Since the number of permutations is very high there is a very big chance that ciphers do not have equivalent keys. This is especially true for ciphers with a high block size (AES with 128 bits). Even if an equivalent key would exist, it would probably be rather tricky to find a set of two equivalent keys. How tricky depends on the cipher of course.

  Is the existence of equivalent keys an essential property for the security of a cipher?

Therefore no.

  If you could prove that a cipher had no equivalent keys, would that lead to a procedure for recovering the key under the known-plaintext attack model?

No. Finding that a cipher does not have equivalent keys would enhance the security of the cipher, not decrease it.

More information about equivalent keys here.


Doubt on elliptic curve over a finite field and binary representation I'm a programmer, i.e. agnostic to the mathemathics behind most of cryptographic scheme, but I'm trying to remediate. I'm writing this premise for any possible error or imprecision that I probably put in this question.
However, I'm studying Elliptic Curve and I got to Elliptic Curves over Finite fields topic. For what I understood an elliptic over a finite field $F$ are the points that fulfill the Weierstrass equation where coefficients and coordinates belongs to $F$.
So far I always thought of F as the integer modulo $p$ (with $p$ prime). Point addition, doubling must be thus performed modulo p and all the points that pop out along with the point at infinity form a cyclic group. Ok, I got this.
Now problems begin: reading some handouts that a professor of mine gave to me, I read two things that I couldn't figure out.
First, they say that the order of a finite field is always a prime power (and such a power is named extension degree that he denotes with $m$): of course I trust this result but I couldn't figure out a field of order, say, $4$, $8$, $9$ or $16$. What are examples of such fields?
Secondly, if $p=2$, $m>1$ and $q=p^m$ (binary field), they say that (I'm citing):

The elements of the a binary field of order $q=2^m$ cannot be represented as integers modulo $2^m$. A convenient way to represent them is by means of binary polynomials of degree less than m.

Why can't they be represented as integers modulo $2^m$? Any answers and/or reference is appreciated.

I couldn't figure out a field of order, say, 4, 8, 9 or 16. What are examples of such fields?

Let's do that with $8=2^3$.

Elements of that field $\mathbb F_{2^3}$ will be assimilated to $3$-bit quantities, that is the set $\{\mathtt0,\mathtt1\}^3$, or equivalently polynomials of degree less than $3$ with binary coefficients, where e.g. $\mathtt{110}$ is the polynomial $x^2+x$, and $\mathtt{101}$ is the polynomial $x^2+1$.
Our addition is bitwise exclusive-OR, or equivalently addition of polynomials, so that $\mathtt{110}\oplus\mathtt{101}=\mathtt{011}$, or equivalently $(x^2+x)+(x^2+1)=x+1$.
For our multiplication we choose an irreducible_polynomial $P(x)$ of degree $3$ with binary coefficients (among two such polynomials, see this list of irreducible polynomials over GF(2) up to degree 11), e.g. $P(x)=x^3+x+1$; and we define multiplication as polynomial multiplication followed by reduction modulo $P(x)$. This simply tells that when in the product we get a term of degree $d\ge3$, we can get rid of it by adding the polynomial $x^{d-3}\,P(x)\ =\ x^d+x^{d-2}+x^{d-3}$. So for example
$$\begin{array}{lll}(x^2+x)\,(x^2+1)&=(x^2+x)\,x^2+(x^2+x)\\
&=x^4+x^3+x^2+x\\
&\equiv(x^4+x^3+x^2+x)+(x^4+x^2+x)&\pmod{x^3+x+1}\\
&\equiv x^3&\pmod{x^3+x+1}\\
&\equiv x^3+(x^3+x+1)&\pmod{x^3+x+1}\\
&\equiv x+1&\pmod{x^3+x+1}\\
\end{array}$$
thus $\mathtt{110}\otimes\mathtt{101}=\mathtt{011}$.

The full multiplication table goes
$$\begin{array}{c|cccccccc}
\otimes     &\mathtt{000}&\mathtt{001}&\mathtt{010}&\mathtt{011}&\mathtt{100}&\mathtt{101}&\mathtt{110}&\mathtt{111}\\
\hline
\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}\\
\mathtt{001}&\mathtt{000}&\mathtt{001}&\mathtt{010}&\mathtt{011}&\mathtt{100}&\mathtt{101}&\mathtt{110}&\mathtt{111}\\
\mathtt{010}&\mathtt{000}&\mathtt{010}&\mathtt{100}&\mathtt{110}&\mathtt{011}&\mathtt{001}&\mathtt{111}&\mathtt{101}\\
\mathtt{011}&\mathtt{000}&\mathtt{011}&\mathtt{110}&\mathtt{101}&\mathtt{111}&\mathtt{100}&\mathtt{001}&\mathtt{010}\\
\mathtt{100}&\mathtt{000}&\mathtt{100}&\mathtt{011}&\mathtt{111}&\mathtt{110}&\mathtt{010}&\mathtt{101}&\mathtt{001}\\
\mathtt{101}&\mathtt{000}&\mathtt{101}&\mathtt{001}&\mathtt{100}&\mathtt{010}&\mathtt{111}&\mathtt{011}&\mathtt{110}\\
\mathtt{110}&\mathtt{000}&\mathtt{110}&\mathtt{111}&\mathtt{001}&\mathtt{101}&\mathtt{011}&\mathtt{010}&\mathtt{100}\\
\mathtt{111}&\mathtt{000}&\mathtt{111}&\mathtt{101}&\mathtt{010}&\mathtt{001}&\mathtt{110}&\mathtt{100}&\mathtt{011}\\
\end{array}$$
The neutral for $\otimes$ is $\mathtt{001}$ that is the polynomial $1$. The distributive property and other commutative field properties follow from that for polynomials.

The elements of the a binary field of order $q=2^m$ cannot be represented as integers modulo $2^m$.

Actually it's OK to represent them as integers, and even convenient in some computer languages (perhaps our $\oplus$ is just the bitwise-XOR operator ^). But when $m>1$, addition and multiplication modulo $q=2^m$ give the ring $\mathbb Z_q$, which is essentially useless to build the field $\mathbb F_q$, for $\mathbb Z_q$'s addition and multiplication bear no relation with $\mathbb F_q$'s $\oplus$ and $\otimes$.

A convenient way to represent elements of the a binary field of order $q=2^m$ is by means of binary polynomials of degree less than $m$.

Indeed. That's what we did above.

Following comment

If $m=1$ then coordinates over elliptic curve are just scalars, whereas if $m>1$ then a coordinate is in its turn a "set of coordinate".

Yes, that's a useful way of seeing it. An element of the field $\mathbb F_{p^k}$ is most naturally expressed as $k$ "coordinates" each in $\{0,1\ldots,p-1\}$ when devising a general computer implementation of arithmetic in $\mathbb F_{p^k}$. The usual mathematical statement of the same thing is that such element is a polynomial of degree less than $k$, with coefficients in $\mathbb F_p==\mathbb Z_p$.
In the first part of the answer I have specialized to $p=2$, since the question mentioned binary in the title, but we can do the same for any prime $p$, and that makes polynomial notation shine: it implies the definition of addition, and of multiplication with the help of an irreducible polynomial.


What does it mean to be "sound"? I've been reading this in many places and I still don't properly understand what it means to be "sound". As an example of what I am asking for:

The Fiat-Shamir transfrom is sound in the Random Oracle Model (ROM), where hash functions are assumed to behave as Random Oracles.

I know that being in the ROM means that hash functions are thought to be trully random functions and the Fiat-Shamir is a technique to transform interactive $\Sigma$-protocols to non-interactive. So what that means?

An interactive or non-interactive protocol is said to be sound for a language $\mathcal{L}$ if it is "hard" for a (malicious) prover $\textsf{P}$ to convince a verifier $\textsf{V}$ of a statement $I\not\in\mathcal{L}$. Depending on how "hard" it actually is for $\textsf{P}$ to cheat, we either get a (interactive or non-interactive) proof system (when $\textsf{P}$ is computationally unbounded) or an argument system (when $\textsf{P}$ is computationally bounded).
The Fiat-Shamir transform compiles an interactive protocol into a non-interactive protocol by, roughly-speaking, replacing the verifier $\textsf{V}$ with a hash function $H$. To be more precise, the prover computes -- by itself -- the $i$-th verifier message $\beta_i$ by hashing the transcript so far (which consists of the statement $I$, the prover messages $\alpha_i$s from the previous rounds and the previous values of $\beta_i$s): see the figure below (which is taken from here). In the random oracle model (ROM), the hash function $H$ is modelled as a random oracle, i.e., a random function accesible to all parties via an oracle.

The Fiat-Shamir transform is said to be "sound", if it "preserves" the soundness of the interactive protocol being applied to. That is, the non-interactive protocol $(\textsf{P}_{FS},\textsf{V}_{FS})$ that results by applying the Fiat-Shamir transform to a interactive protocol $(\textsf{P},\textsf{V})$ is also sound. We say that the Fiat-Shamir transform is sound in the ROM if the above holds when $H$ is modelled as a random oracle.
When is the Fiat-Shamir transform sound? It is known to be sound in the ROM when applied to constant-round interactive proof systems [PS00]. In particular, we end up with a non-interactive argument system. One of the most common examples of this is the Schnorr signature scheme, which is obtained by applying the Fiat-Shamir transfom to the Schnorr identification scheme.
On the other hand, we know of certain counterexamples where the transform is "unsound" even in the ROM. I'd finish by adding that there has been a lot of exciting recent works that have aimed at proving the soundness of the Fiat-Shamir transform in the standard model (i.e., without random oracles): see [C+19,PS19] and reference related to them.
[C+19]: Canetti et al. Fiat-Shamir from Simpler Assumptions, STOC'19
[PS00]: Pointcheval and Stern, Security arguments for digital signatures and blind signatures, JoC, 2000.
[PS19]: Peikert and Sheihan Non-Interactive Zero Knowledge for NP from (Plain) LWE., Crypto'19