Revealing random bit permutation I am new in cryptography. I want to determine the complexity of revealing a random bit permutation which is used as block cipher for plaintexts (bitstrings of length n). An adversary catches different ciphertexts (the permuted bitstrings of length n) and he also knows the set of possible plaintexts. If he tries all possible inverse permutations at the end there are more permutations that result in legal plaintexts. The difference is that all of the remained permutations result in different sending order of the plaintexts. Is it possible to reveal the used permutation?

Any insight will be helpful.
Thank you in advance

I thought you were using a block cipher, i.e. a pseudorandom permutation. Instead as per your comment you are only permuting the order of the plaintext bits. This is not secure.

For example, you can imagine the bit permutation is an n-by-n square matrix, where each row and column has a single 1 and the rest 0s. The input and output are then vectors of size n.

Take a random input and output pair. If each has $\frac{n}{2}$ 1s and 0s on average, you get to know $\frac{n}{2}$ matrix evements from each row – those where the input is different from the output must be 0. So you get about half the matrix elements.

After two random pairs of plaintext and ciphertext you know on average about $\frac{3}{4}$ of the matrix. Then $\frac{7}{8}$, etc. You need on the order of $log_2(n)$ pairs to find the whole matrix. (With non-random plaintext it may take slightly more pairs than with random.)

Even before leaking the whole permutation, you will leak all sorts of information about the plaintext – for example, the number of 1 and 0 bits will be the same in the ciphertext. Two plaintexts that differ in $k$ bits will have ciphertexts differing in $k$ bits, etc.

Old answer based on using a block cipher:

  Is it possible to reveal the used permutation?

Not if the keyspace is large enough. There are $2^n!$ different $n$-bit permutations, but a block cipher typically has only a 128-bit or 256-bit keyspace, so not all permutations are possible. Unless the cipher is broken, the only way to narrow it down is a brute force search of the keyspace, which is intractable for 128+ bits.

As an aside, you would be using the block cipher directly on plaintexts. Unless the plaintexts are random (or known unique) bitstrings of length $\le n$ bits, that is not a secure mode of operation, it is ECB and is not semantically secure.


How do I find the key of the Vigenere cipher is if I already know the key length? Hi I am stuck in trying to crack the code of finding the key to decrypt a huge message. I have the frequencies of the letters:

A 121
B 0
C 10
D 60
E 39
F 100
G 123
H 19
I 0
J 74
K 87
L 119
M 35
N 8
O 30
P 2
Q 27
R 0
S 135
T 26
U 47
V 47
W 140
X 24
Y 29
Z 78
A 121
B 0
C 10
D 60
E 39
F 100
G 123
H 19
I 0
J 74
K 87
L 119
M 35
N 8
O 30
P 2
Q 27
R 0
S 135
T 26
U 47
V 47
W 140
X 24
Y 29
Z 78

So far I figured out that the first letter is an "S" since W = 22 so 22-4 = 18 which is "S"

If you know the key length of a Vigenere cipher, you should group the letters in the given huge message by each of the key letters, then compute the frequencies for each group separately. If I understand right, you are doing a total frequency analysis, which is of no use.


Converting NewHope/LWE key exchange to a Diffe-Hellman-like algorithm By a “Diffe-Hellman-like” algorithm, I mean one that has the same API as Curve25519, etc (disregarding trivial differences such as the size of parameters): a function

$$F: (P_\text{other}, S_\text{self}) \rightarrow \text{Shared secret}$$

where $S_\text{self}$ can be used arbitrarily many times with different values of $P_\text{other}$.

It has been folklore (since at least 2010) that you can do what you propose, but less efficiently than the "key transport" method of any Ring-LWE based encryption scheme or KEM.

So here is what you can do: there is a public polynomial $a\in Z_q[X]/(X^n+1)$ that is shared by everyone.  It needs to be uniformly random, so it can be set to XOF(1), where XOF is something like SHAKE.  This way, it's "random" and we're pretty sure there are no planted trap-doors in $a$.

Then person $i$ selects two polynomials $s_i,e_i\in Z_q[X]/(X^n+1)$ with small coefficients and publishes his key $b_i=as_i+e_i$.  Now if party $i$ and $j$ want to share a key, party $i$ computes $s_ib_j = as_is_j+s_ie_j$ and party $j$ computes $s_jb_i= as_is_j+s_je_i$.  Since $s_ie_j$ and $s_je_i$ are products of polynomials with small coefficients, the coefficients of the products themselves are bounded (say by $\beta$).

So what we would really like is that the coefficients of $s_ie_j$ do not affect the higher order bits of $as_is_j$.   This could happen if $q$ is much larger than $\beta$.  Basically, if $q=2^k \beta$, then the probability of the higher order bit not being affected is around $1-2^{-k}$.  So by setting $q$ large enough, the way to retrieve a shared key would be to compute HighOrderBits$(s_ib_j)$.

So why isn't this done?  Because you would need to set $q$ quite large and the underlying hard lattice problem becomes easier the larger the gap between $q$ and the coefficients of $s_i,e_i$ are.  So you would have to increase the dimension of your ring to compensate.  It is possible to set such parameters, but I would estimate that achieving similar security as regular Ring-LWE encryption / key exchange schemes would result in keys that are around 20 - 40 times larger than in Ring-LWE based schemes.  So something around 20KB - 40KB could be expected.


PBKDF2 PRF: HMAC or just hash? I understand the way $\textrm{PBKDF2}$ can be used to 'stretch' a password/passphrase that does not provide full entropy.

My question: how does one choose the PRF? A common choice is any well-known cryptographic hash like $\textrm{SHA256}$, and I understand why that works. Some systems, however, use $\textrm{HMAC}_{\textrm{SHA256}}$, where the password is used to key the MAC.

Why would one use $\textrm{HMAC}_{\textrm{SHA256}}$ over $\textrm{SHA256}$ as the PRF? I don't see any advantage to this. Surely the weaknesses of Merkle-Dåmgard hashes adressed by $\textrm{HMAC}$ are irrelevant when the password is a secret used to derive another secret?

HMAC is sometimes called a keyed hash. The key is not part of the input of a secure hash (as CodesInChaos already indicated in the comments). HMAC is a relatively simple construct to allow a key to be used as input to the underlying secure hash. It specifically is constructed to disallow length extension attacks - although those are not likely an issue in PBKDF2.

You could use If you'd use SHA-256 directly you would have to make sure you're not vulnerable against those kind of attacks. You would basically be without the security proofs of HMAC.

KDF1 and KDF2 are KDFs/PRFs that simply concatenate elements in a certain way before entering the result into the hash. SHA-3/KMAC will (largely) be a concatenation of key and message before hashing. So it certainly can be done that way.

You should however reverse your question: Why wouldn't you use a secure PRF instead of directly using a hash?.

HMAC is relatively efficient. Inn PBKDF2 (which requires a work factor / iteration count) the small inefficiencies may actually be a benefit (a good implementation should however store the intermediate hash value of the password, otherwise an attacker may have an advantage).

Furthermore, HMAC is still considered secure, even if the underlying hash is vulnerable to certain kind of attacks (such as those against MD5 and SHA-1).

For the SHA-1 and SHA-2 algorithms I'd advice you to keep to HMAC unless you've got very strong (performance related?) reasons not to.


How can an S-Box be reversed? So, as an exercise to greater understand some things about cryptography, I decided to try and implement GOST 28147-89, which uses eight 4x4 S-Boxes. I can grasp the concept of putting 4 bits through the S-Box and getting four out, but how would one reverse this?

Furthermore, how would one reverse uneven S-Boxes, such as DES's 6x4 S-Box, when multiple inputs give the same output (e.g., for DES's S-Box S5, where inputs of 100011, 101110, 011101, and 010000 all give an output of 1000).

Ciphers that use S-boxes are typically in the form of a Feistel network. This has the property that inverting the cipher does not involve inverting the round function, but simply applying the rounds in the opposite order. Therefore one doesn't need to invert the S-box to decrypt.


Does collision resistance imply (or not) second-preimage resistance? I've seen contradictory results. Sometimes hash functions are collision-resistant but not necessarily second-preimage resistant. I've seen this kind of things in papers from Bart Preneel:

“Security Properties of Domain Extenders for Cryptographic Hash Functions”
(See the chapter "Other Domain Extenders").

How that can be possible ?

We have theorems that say that if a hash function is collision-resistant then it is second preimage resistant as well:

http://en.wikipedia.org/wiki/Preimage_attack

With the definitions that a function $F$ is

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

yes, collision-resistance implies second-preimage resistance. Proof by contraposition: assume the property for second-preimage-resistant does not hold. Repeatedly pick a random $a$, perform the attack that exhibits a $b$ with $a\ne b$ and $F(a)=F(b)$, until it succeeds. By our assumption, that requires a feasible amount of work. Once exhibited, that pair $(a,b)$ proves that the property collision-resistant does not hold.

However, as pointed by CodesinChaos in his comment, the answer is no for definitions of collision-resistance and preimage-resistance that quantify the difficulty of finding a collision or (respectively) preimage, to roughly $2^{n/2}$ or (respectively) $2^n$ evaluations, where $n$ is is the number of bits in the output.

Proof by counterexample: for even $n$, assume a hash function $H:\{0,1\}^*\to\{0,1\}^n$  that behaves as a random function. Now construct $F:\{0,1\}^*\to\{0,1\}^n$ as
$$F(x)=\begin{cases}x||x&\text{if }x\text{ has }n/2\text{ bits}\\H(x)&\text{otherwise}\end{cases}$$
$F$ has the collision-resistant property (when $a$ and $b$ are both $n/2$ bits, $a\ne b\implies F(a)\ne F(b)$; when neither $a$ nor $b$ are $n/2$ bits, collision resistance is that of $H$; when a single of $a$ or $b$ is $n/2$ bits, the other must have a hash with two equals halves, and it takes effort about $2^{n/2}$ hashes to exhibit such input). However the following algorithm breaks the second-preimage resistance property for $F$ at cost comparable to $2^{n/2}$ hashes, much less than required: if the random $a$ is not of size $n/2$, compute $H(a)$, and if its two halves are equal (which is expected to occur after $2^{n/2}$ hashes), let $b$ be that bitstring of $n/2$ bits; it holds that $a\ne b$ and $F(a)=F(b)$.

In summary: a function's second-preimage-resistance is always at least as strong as its collision-resistance; but it can be not much stronger, rather than quadratically stronger, which is the theoretical ideal. So depending on definition, collision-resistance implies second-preimage-resistance.. or not! That's true when we keep the same security level (effort and odds of success of adversary) to assess the two properties. That's false when we expect a security level consistent with the property and the function's output size.

Addition following comments: The question links to a paper by Elena Andreeva, Bart Mennink, and Bart Preneel Security Properties of Domain Extenders for Cryptographic Hash Functions. That highly technical paper considers various proposed extension methods to iterate the core building block of a hash function over much larger input than the core block accepts; and if security properties of that core are conserved in the extended construction, to comparable level (work for attack and odds of success).

As any good paper should, that paper gives its specific definitions, and for some established ones refers to its reference [15]: P. Rogaway & T. Shrimpton Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance. All these quantitative definitions stay fully consistent with the classical result that for any given level (work for attack and odds of success), collision-resistance implies second-preimage-resistance.

The paper shows that some extension methods demonstrably (mostly) preserve the level of collision-resistance but do not demonstrably (mostly) preserve the level of second-preimage-resistance. That is entirely consistent with the above rule.

For example, starting from a core block assumed collision-resistant to $\mathcal O(2^{n/2})$ effort and second-preimage-resistant to $\mathcal O(2^n)$ effort, some extender might construct a hash that is collision-resistant to $\mathcal O(2^{n/2})$ effort and second-preimage-resistant to $\mathcal O(2^{2\cdot n/3})$ effort. The less-than-perfect extender conserved the level of collision-resistance, but not the level of second-preimage-resistance. Yet, for the hash built using that extender, collision-resistance to some effort level still implies second-preimage-resistance to that effort level.


Source for examples with broken cryptography I've heard again and again that many crypto systems have been broken in the past for one reason or another and that it is best to use one that has been peer reviewed, etc etc. However, I've yet to see a source (website, book) that gives information about these systems. Is there such a thing?

If you want to look back in time, ENIGMA was the standard used by the nazis in the 30-40's. It would be useless to encrypt anything with it now.

More recently, pratical attacks have been done against parts of the GSM standard (what cell-phones use). The cipher A5/2 which is considered completely broken and has for this reason been remove from the standard. Actually, A5/3, supposed to be better, is not looking great either right now as an attack requiring a regular computer has been done recently (2010, see wikipedia link).

These are example of practical attacks against "real life" algorithms.

You also have algorithms which never made it outside academia because of their weakness. For instance, MacGuffin was broken at the same conference it was presented!

At last, "broken" is a rather vague concept. An algorithm is usually considered "broken" if attacks much more efficient than brute-force can be done... But that does not mean they are pratical! For instance, PUFFIN (a lightweight cipher) is considered broken due to vulneranility against differential cryptanalysis. However, the amount of data required to perform the attack remains unpractically high.

For this reason, you may consider DES to not be broken because no attack is more efficient than brute-force in its case (as far as I know). However, the problem is that a brute-force attack is possible nowadays because the key size (56 bits) is too small.


Significance of y-coordinates in ECDH public key exchange In the research paper Breaking the Bluetooth Pairing – The Fixed Coordinate Invalid Curve Attack? by Biham and Neumann, 2019,
they talk about attacks in Bluetooth pairing, they state that in the pairing process which involves ECDH key exchange- "sending both the x-coordinate and the y-coordinate during the public key exchange is a design flaw as it is unnecessary and highly inadvisable, and it greatly increases the attack surface"
I'm aware that in other implementations only $x$-coordinate is sent in compressed form. I'm curious to know how sending both coordinates increases the attack surface, how important it is to know the information about the $y$-coordinate and what are the possible attacks related to this.

The paper you reference mentions that although both coordinates are sent, the protocol only requires the x-coordinate to be authenticated and validated. This means that the y-coordinate is free to be manipulated in implementations that do the bare minimum. As mentioned in a comment, "poor programmers and bad quality testers will not consider [this vulnerability]".
Sending only one coordinate makes it less likely for an implementer to make a mistake. With only one coordinate, it's impossible for the second coordinate to be manipulated, and it's significantly harder to force someone to use a point not on the curve. It's easier to test that given a value, a function always generates a valid point or throws an error than it is to test that a protocol works correctly end-to-end for all possible inputs.


Simple Electromagnetic Analysis vs symmetric cryptography I've asked this question here and was advised to post this question on this forum in hopes of an answer.

I'm currently taking a security class and i came into this issue when writing a report about side channel attacks. When reading about electromagnetic attacks, more specifically about Simple Electromagnetic Analysis in Wikipedia (https://en.wikipedia.org/wiki/Electromagnetic_attack), it states:

  It is very effective against asymmetric cryptography implementations...

I understand why it is effective agaisnt an algorithm such as RSA, which is asymmetric, but doesn't the reason for its effectiveness resides on the way the algorithm is implemented and not if its symmetric or asymmetric cryptography?

  For example, a common attack on asymmetric RSA relies on the fact that the encryption steps rely on the value of the key bits. Every bit is processed with a square operation and then a multiplication operation if and only if the bit is equal to 1. An attacker with a clear trace can deduce the key simply by observing where the multiplication operations are performed.

So i don't really understand why it says its effective against asymmetric cryptography.

Thanks for your attention!

SEMA is effective against a naive implementation (e.g. using binary square and multiply) of raising to a secret value in some group. Raising to a secret value in some group is used in common asymmetric cryptography techniques, including based on hardness of integer factorization (RSA) or the discrete logarithm (DSA, ECDSA..). That's why SEMA happens to be effective against naive implementations of common asymmetric cryptography.

It would be wrong to say that only asymmetric algorithms are vulnerable to SEMA. For example, the Pohlig-Hellman exponentiation cipher is a symmetric encryption algorithm where encryption goes $x\mapsto x^k\bmod p$ for public prime $p$ with $(p-1)/2$ prime, and $k$ a secret exponent. A naive implementation would be vulnerable to SEMA just like a naive implementation of RSA is. And it is all too frequent that a very naive implementation of DES is vulnerable to SPA/SEMA.

It would also be wrong to say that all asymmetric algorithms are vulnerable to SEMA. Careful implementation of raising to a secret value can be made secure (using the Montgomery ladder or other techniques, including blinding). And some asymmetric algorithms (e.g. Lamport signature) do not raise to a secret value, and can be made immune to SEMA with careful coding and control of the underlying hardware.


Are there any practical examples of breaking a system using linear attacks? I've read some papers about linear cryptanalysis. But since I am going to give a lecture about it I am looking for an example of breaking a system using this attack. Is there such an example available?

The most well known example of a cipher practically broken with linear attacks is by no doubt DES, a cipher with 56-bit key and 64-bit block. Equipped with a cluster of PCs in the year 1994, Mitsuru Matsui has experimentally found a secret key after 10 days of the analysis (the data generation took additional 40 days on the same machine set).

By that time the behaviour of linear attacks was not well understood, but eventually a simple concept emerged. Given $N$ (plaintext,ciphertext) pairs of 64-bit blocks, a cryptanalyst obtains a list of candidate keys ordered by their likelihood to be the right key. There are estimates of the probability $P$ that the right key is among top $R$ candidates. Clearly, $P$ increases as $N$ or $R$ grows, and it is in fact the success rate of the attack under parameters $(N,R)$.

A comprehensive treatment of this subject has been given by Junod in his PhD thesis, where  Figure 3.3, p.80, provides a plot of the success rate given fixed $N =2^{40}..2^{45}$. Both theoretical and implementation details are given in Section 3.2 of the same text.


Subgroup generation: should we check that order is not 2? or g in not too small? For $p=2q+1$,where p and q are primes, we have subgroups of order $p−1$, $q$, $2$ and $1$. To find $G_q$, usually we just check that  $g^q\bmod p=1$ and that's it.

However,here it's mentioned that there is a chance (very unlikely but still) that a group satisfying $g^q\bmod p=1$ is of order $1$ or $2$.

Ok, suppose we start checking  whether $g^q\bmod p$ is equal to $1$ starting from $g=2$ (to eliminatie $g=1$). I don't see how a subgroup can satisfy $g^q\bmod p=1$ and be of order $2$ (so $g^2\bmod p=1$ too). It seems that for all even $a$ in $g^a\bmod p$ the result is $1$. On the other hand, since $p$ is a prime and $g^q\bmod p=1$  holds, then for all odd $a$ odd it's equal to $1$ too. I fail to see, how any generater except $g =1$ can satisfy it. Do we rally need to chech that $g^2\bmod p$ is not $1$?

Additional question, is it a good idea to check all integers in the increasing order starting from $g=2$? Is there any security issues related to a small $g$? Suppose, in the real ElGamal implementation with $p$ of 1024-bits or 2048-bits, I check all $g$ from $2$ till I find the $G_q$ subgroup generator.

Assuming you have the same setting as the linked question (in particular $q$ is prime, it's true: you cannot have $g^2 = 1\bmod p$ and $g^q = 1\bmod p$ simultaneously unless $g=1$ or $q=2$.

It's important to notice that if the condition $g^q = 1\bmod p$ is satisfied and $g$ is not the identity, then $g$ will be a generator.

I think that what PulpSpy means in the answer you linked is that either you're lucky and $g^q = 1\bmod p$, with $g$ not the identity, or you're not lucky and $g^2 = 1\bmod p$ (not both congruences simultaneously), in which case you have to try again with another $g$.


How to interpret a specific mathematical notation in "FIPS 202" (SHA-3 / Keccak) tl;dr  What does "d <= |Z|" mean in the context of bit array manipulations?

As a learning exercise I'm working on an implementation of SHA-3.  I am not a cryptography specialist in any way but I have implemented similar algorithms in the past such as MD5 and SHA1, so I am roughly conversant with the kinds of operations that happen in such algorithms.

I have been working through the document "FIPS PUB 202" (freely available as a PDF here: http://dx.doi.org/10.6028/NIST.FIPS.202).

I am finding this a hard document to understand but I'm getting near to completing the program and I'm unsure about the meaning of the following line of text in section 4, algorithm 8 (page 19)  the SPONGE function...

My problem is with step 9.  I do not understand what "|Z|" means in this context.

This algorithm deals with truncating and concatenating an array Z of bits (which could be several hundred bits long) until this condition is met at which point the first "d" bits of Z is returned to the calling function.

My first thought was that |Z| means "the length of Z in bits", but that would be inconsistent -- they are using "len(...)" for that purpose in steps 1 and 2 (and elsewhere in the document).  This is the only place in the document where this "|...|" notation is used.
I don't think it would mean "Abs(Z)" in the mathematical sense of converting Z to a positive value because the resulting number would be extremely large in almost all cases.  Converting Z (effectively a list of random bits) into an integer seems pointless and arbitrary.
The "|...|" syntax is not mentioned in the glossary section. ("a || b" is mentioned but that's for array concatenation, which this is definitely not).
I was also a bit puzzled by the use of "<=" in this condition.  Why bother to truncate if the length is equal, just return it as it is?  Further suggestion that it doesn't mean "length of Z".

So, how should I understand this slightly weird bit of text?  I doubt it's a mistake in the document because it's such an important algorithm and will have been stringently vetted by thousands of people much smarter than me.

It means the length of $Z$ in bits; in other words, squeeze out consecutive $r$-bit blocks from the sponge until you have a $d$-bit string, truncating the last block if necessary.

I expect you may overestimate the number of people who proofread this document with an eye for details like that.  Most cryptographers studying it will have read the Keccak reference, which uses slightly different notation meaning the same thing; most implementors will likely correctly guess that $|Z|$ and $\operatorname{len}(Z)$ mean the same thing when $Z$ is a bit string, or compare to another reference to confirm.


Is it possible to get the PGP public key from PGP message? Is it possible to get the public key from PGP message in PEM(Base64) format? Here is the message:
-----BEGIN PGP MESSAGE-----

hQEMA1W24kYEriipAQf9FEOPPTiqBj9kDSqCWTJmCvceU3n9oEqA7umKFYWG60nv
nWEk09AvrYK1dakfYVTKlolqV6kkxoQqt5DlsQ6YOa7I4Xfy58l9yzJQlf1KU/xN
vp3sBb8FHCkT789hZ8h9On/GoFFaDTp2rHB63ylLzcPNedlYdUS2DtooZQkt6g07
C8D0B9t66UGCGCPky0bEquihBz7u48oV+F3DVTdHV7XYCHayuMNuMAExiOv7hpRh
VauO3ryTm5R/6D06/QYAVsfrqR/UWaCdz26FQVmFc5Z9HqLaS00ppjqfktaYACNz
M88A6I0eUchpCSz8tqpURTUKdNZTjOun4pqQ+9c/TNLpAQ0uQRpuXSt1KYrbiq8l
4glvmrFqkSM/n8soDpoatjwW2BMu3IByV/OJZ1heWsxfUw/qImE5qZPxxI1CjLDe
3yGSb2SAE6l/mnfnkSPDEOxE3LRfSoOapUOc+9MtGl/gF3+TwYZ0qpXevSCOWKLz
1fnIuQU4PvWYHR3vkBuoxJ9+0aNtvr+JRsx1Wg1lNJqu6T5rQHc7ne7VocD5coi4
YyOENKDPfELi6o6/MhdFmMblTu4/AbUoErAg6zGP9CUMdYngFfNQyfFB9x2jG6fe
Pfq+g1Y6NW527Bjy8Qfd0Iy1Xz+838bvqZt5MhDXTWW+YYcPm5htL+1H2o3FoQhW
qmAM577UnjVQXoL4bg046dyA0fqd5E32xGlVOXKL6RgeGouZu8V43wrQKzJhROoV
pk6T7QEUMSiBiAoZjTAg5BalpIr+G/PWj5mCI0ys75tNeH3zQOgf0+Be7Q+AkO7/
PQHR0qfWVg+9PdEfR05ciuJ6A4SiI0QtqziMmHvgc213KWGqKuYqYr22xgkqcJWP
7lFT/56zCoyiObcEPWH9WEXwYYakEPxCn/i16c4HgZVzgeJ1x04I5t//ZM9cT15g
N3EBi58ANV8BjgLaklcoxm9XjOpIlW952Y6qvwDMMh3SRNCpGsq+Ma6+zi/T6fqW
O2psDgYjQsjsDaAmdPzGeHUTWAp752rJPKbMoInA9Bb3xMjjKg==
=ioKX
-----END PGP MESSAGE-----

I sent this to someone and I was just wondering what if someone other than us knows the PGP message and wants information like the recipient's pubkey or other info.

No, the PGP format doesn't contain the public key of the sender. But it does include a key ID of the key (pair) so that you know which private key to use to decrypt the message. It is rather easy to verify this by reading the OpenPGP specifications which defines the packet format(s) used. Or you can take a look using gpg --list-packets --verbose.
It is possible to lookup the public key (which in the case of PGP acts more like a certificate, containing more information than just the key value) using one of the various PGP servers. However, the use of these servers has become a problem in itself. Knowing the key ID is of little help if the key is not registered in a known key server or location (i.e. communicated out of band or kept locally).


Examples of protocols that are insecure when run concurrently I was reading Canetti00 Universally Composable security paper. The first page of introduction says that there are some MPC protocols and Zero knowledge protocols that are insecure under concurrent composition. I don't see why protocols might break when concurrently composed together.

Please provide some examples of protocols that are insecure under concurrent composition.

Does the same type of attacks hold for parallel composition? What's the difference?

Does the same type of attacks hold if the protocols are run many times one after another (Let's say to improve soundness error)?

Edit: @Mikero gave a nice MPC protocol that is not secure under concurrent composition. Can anyone give an example of ZK protocol that is insecure under concurrent composition?

Consider the function $f : \{L,R\} \times \{ U,D \} \to \{0,1,2\}$ defined by the following table:

$$
   \begin{array}{c|cc}
      f & L & R \\
      \hline
      U & 0 & 0 \\
      D & 1 & 2
   \end{array}
$$

Let's say Alice has input from $\{L,R\}$ (she chooses a column) and Bob has input from $\{U,D\}$ (he chooses a row).

A simple protocol for $f$ is as follows:

Bob announces his input in the clear. If his input is $U$, then parties can halt, as they know the output must be 0.
If Bob's input is $D$, then Alice announces her input in the clear. With both inputs known, the parties can compute the output.

This protocol is secure against active adversaries in a standalone security model, but it is insecure when three instances are executed concurrently.

Imagine the following scenario:

Bob is honest and chooses one of the instances to have input $U$ and the other two to have input $D$. There are three such combinations ($UDD, DUD, DDU$) and he chooses with uniform probability.
Alice is corrupt. She wins the game if she can cause the 3 instances to have all distinct outputs. It's not hard to see that she can only win by using different inputs in the two instances where Bob chooses input $D$.

If parties have access to 3 parallel instances of ideal $f$, then it is easy to see that Alice can only win with probability 1/3. In this setting, Alice's choice of input is independent of Bob's. There must be (at least) two $f$-instances where Alice uses the same input, and with probability 1/3 those will both be ones where Bob uses input $D$.

But in the presence of concurrent protocol instances, it is easy for Alice to win with probability 1. The protocols can be run in lockstep, and Alice just waits for the first protocol message in each instance. Then she can send appropriate (different) protocol messages in the instances that proceed to step #2.

Since Alice can influence the protocol in some way that she cannot influence ideal instances of $f$, the protocol is insecure in this setting.

This example is a bit simplified. I assumed that the ideal calls to $f$ were done in parallel. But it is not hard to adapt this kind of example to different requirements on the ideal world.

The big picture is that a standalone-secure protocol can leak some information early in the protocol, with the reasoning that this information is something that could be deduced from the output anyway (like Bob's input in this case). But in the presence of concurrent composition, and correlated inputs between different instances, this kind of leakage can be unsafe.


Why is there no "ephemeral non-DH EC" key exchange in TLS? In RSA key exchange, the client picks a premaster secret and encrypts it with the RSA public key in the server certificate, and sends it to the server. This offers no forward secrecy.

In ECDHE key exchange, the client and server both generate ephemeral EC key pairs, and use DH key exchange to negotiate the premaster secret. The server public ephemeral public key is signed using the server authentication certificate. This gives forward secrecy.

In the latter, two ephemeral key pairs have to be generated, by the server and the client. How about the following mix of both key exchange methods that does not need the client to generate an EC key pair:

Server generates ephemeral EC key pair, signs the public key using the server authentication certificate.
Server sends the ephemeral EC key pair public key to the client.
Client picks a premaster secret, encrypts it using the server ephemeral EC public key and sends it back.

What are the inevitable downsides that make ECDHE superior? I don't see a glaring security hole. Maybe difficulties to use an EC keypair for encryption?

"Maybe difficulties to use an EC keypair for encryption?"; yes exactly, as there are no direct EC encryption primitives that can be used. ElGamal EC encryption is possible, but it requires all kinds of tricks to get it working. There is the mapping of the message to an EC point, for instance. There is ECIES, but that really comes down to performing ECDHE in the first place, with the additional disadvantage of needing a cipher.

Besides that, for RSA, key pair generation is one of the slowest algorithms that you may see. Not only is it slow, but it is also very unpredictable as it is unknown when the two required primes are found. With EC, it is very easy:

create a random number between 1 and N (exclusive);
perform point multiplication of that number with the base point G to get to the public point.

So basically it is as fast as the DH operation itself. There is no long waiting time for primes to be generated at all. So because the key generation itself does not pose much of a problem, there is no pressing need to change either.

One important idea of TLS 1.3 was bringing down the number of round trips. It even guesses the algorithms present at the other end for the initial key agreement. It can then immediately send the ephemeral public key of the client to the server, which responds with the server's ephemeral public key to setup the channel. That way the encrypted channel can (and will) be setup after only two messages. With encryption the client (who has to initiate the connection) first asks for the public key, receives it and then encrypts with it.

That is, ECDH speeds things up if the client doesn't use session resumption, a separate trick to speed things up.

Another smaller difference is that the random key in ECDH is now dependent on the random data of two parties. The various clients may have different strengths of random number generator, and encryption of a secret has the disadvantage that the secret itself is not fully random, e.g. when a RNG is used that is not cryptographically secure. However, with ECDH is does mean that a completely failing RNG will completely show the established shared secret as the ephemeral private key may become known.

Note too that simply bringing the number of options down was an important initiative in TLS 1.3. Having options just for the sake of it only makes a protocol less secure, not more secure. IMHO it doesn't even make sense to have different security levels for the various algorithms used for a specific ciphersuite (not including the difference with the security level of the certificates used for authentication).


When is it safe to not use authenticated encryption? I have read the post Why should I use Authenticated Encryption instead of just encryption? When is it safe to not use authenticated encryption?

I assumed hard drive volume encryption or per file encryption that is not transmitted over an insecure network should be considered safe to do without a MAC. Is that right?

The advantage might be that if you do not provide a MAC, an attacker that has gained access to the physical storage and performing a brute force search does not know if they have successfully decrypted the volume/file as they do not have the MAC to verify that the key is correct. Perhaps an attacker could try decrypting and testing if decryption matches English phrases, however there could be multiple keys that produce valid plaintexts.

What is done in practice, do programs like TrueCrypt or Keepass perform authenticated encryption?

What Stephen says in the comment is correct. It is safe to not use authenticated encryption whenever your adversary model assumes that the attacker does not have the ability to manipulate ciphertexts.

  I assumed hard drive volume encryption or per file encryption that is not transmitted over an insecure network should be considered safe to do without a MAC. Is that right?

What if the attacker can install a program on your machine that can modify the ciphertext? It all depends on adversary model.

  The advantage might be that if you do not provide a MAC, an attacker that has gained access to the physical storage and performing a brute force search does not know if they have successfully decrypted the volume/file as they do not have the MAC to verify that the key is correct. Perhaps an attacker could try decrypting and testing if decryption matches English phrases, however there could be multiple keys that produce valid plaintexts.

In practice, for most applications, it will be pretty easy to know when they got the right key. But also, in practice, brute force is not the attack you should be worried about. Very rarely does the attacker attack the cryptography. They usually attack other pieces (password entry, key generation, key storage, side channels, etc) to render the crypto useless.

  What is done in practice, do programs like TrueCrypt or Keepass perform authenticated encryption?

Truecrypt does not provide authenticity and integrity.

It looks like keepass does provide integrity protection, but I couldn't quickly find anything that says exactly how. See the relevant quote from here:

  In repair mode, the integrity of the data is not checked (in order to rescue as much data as possible). When no integrity checks are performed, corrupted/malicious data might be incorporated into the database. Thus the repair functionality should only be used when there really is no other solution. If you use it, afterwards you should thoroughly check your whole database for corrupted/malicious data.


Breaking hashless variant of the Rabin Signature system with chosen message attack I heard that we can break the Rabin Signature system using chosen-message attack. For a message $M$ that is a quadratic residue modulo $N$, the signature is $x$ such that $x^2 \equiv M \pmod N$. I can't find a message to ask for its signature in order to spoof my message $M$.

Any suggestions?

Here's how the attack works:

Select a random value $y$
Compute $a = y^2 \bmod n$
Ask for the signature of $a$, that is $x$ with $x^2 = a$
If $x \ne y$ and $x + y \ne n$, then $\gcd(n, x+y)$ is a proper factor of $n$

The last step will succeed with probability $\approx 0.5$.  You can make it probability 1 if you select a $y$ with Jacobi symbol -1.


Do AEADs also authenticate the nonce? I'd like to include an authenticated timestamp in my messages.  I'm wondering if I can save a little space by putting the timestamp in the nonce.

Concrete example:

Let's say I'm using XChaCha20-Poly1305 with a shared secret key.
I generate the nonce/IV by concatenating an 8-byte timestamp and a 16-byte random value.
I send concat(nonce, ciphertext, auth_tag)
The receiver runs the decrypt+verify procedure and it succeeds.

Can the receiver then extract the timestamp part of the nonce and trust that it is authentic?

With a more "traditional" composition, like AES-CBC-then-HMAC, the nonce is obviously authenticated.  Is that still the case for these newer AEADs?

Yes, AEAD constructions always authenticate the nonce. If they didn't then the integrity and authentication of the resulting plaintext after decryption would not be ensured.

You can see the definition in RFC 5116: An Interface and Algorithms for Authenticated Encryption, section 2.1. Authenticated Encryption:

  The nonce is authenticated internally to the algorithm, and it is not
     necessary to include it in the AD input.  The nonce MAY be included
     in P or A if it is convenient to the application.

Not all AEAD ciphers may necessarily keep to the letter of this RFC (the inclusion of the authentication tag in the ciphertext is debatable if you ask me - I consider it a separate field). However, I haven't seen any AEAD cipher that doesn't authenticate the nonce by design.

You're writing that

  With a more "traditional" composition, like AES-CBC-then-HMAC, the nonce is obviously authenticated.

This is obviously not true. Yes, it is possible to design such a scheme and any competent cryptographer would not for get to authenticate the IV. There are even tries to standardize such a scheme, see e.g this scheme based on CBC with HMAC-SHA-1.

Less competent protocol designers are however free to shoot themselves in the foot when designing or implementing such a scheme. When using a well designed / reviewed / tested library and an AEAD scheme such mistakes are avoided.


Password-based encrypted key storage? RFC 5959 specifies the encrypted storage of private keys based on PBKDF2-HMAC-SHA-256 and AES encryption (in ECB mode).

Is there a particular reason AES is used, instead of simply XORing the key material with the PBKDF2 output? Is it simply to make storage of long keys faster, because a long PBKDF2 output takes long to derive?

When storing a short key, e.g. a 256-bit ECC private key, is there a good reason to use AES or is the XOR with a single PBKDF2 (or other KDF) output block sufficient?

Yes. $\:$ "simply XORing" is obviously malleable, which may allow related-key attacks.

"When storing a short key, e.g. a 256-bit ECC private key," the "good reason to use AES" is

that "the XOR with a single PBKDF2 (or other KDF) output block" is not necessarily sufficient,

since an adversary might also have changed the stored public key.


Is there a difference between $\mathbb{Z}_2^b$, $\text{GF}(2^b)$ and $\text{GF}(2)^b$? I have read a lot about Galois Fields (GF). They are also presented in The The Design of Rijndael: AES - The Advanced Encryption Standard on pages 13 and 14.

  In computer memory, the polynomials in $F[x]|_l$ with $F$ a finite field can be stored efficiently by storing the $l$ coefficients as a string.

  Example 2.1.6. The polynomial in GF$(2)|_8$ $$x^6+x^4+x^2+x+1$$ corresponds to the bit string $01010111$.

In their paper Differential propagation analysis of Keccak, they also use the notation $\mathbb{Z}_2^b$ :

  In general, for a function $f$ with domain $\mathbb{Z}_2^b$, we define the
  weight of a differential $(u′, v')$ as
  $$w(u' \xrightarrow{f} v') = b - \log_2 |\{u: f(u) \oplus f(u \oplus u') = v'\}| $$

While I do understand the meaning of this notation (a binary input of length $n$), I also know that we can use finite fields to model such numbers. Hence my question:
Is there a difference between $\mathbb{Z}_2^b$, $\text{GF}(2^b)$ and  $\text{GF}(2)^b$

$\mathbf{Z}_2^b$ is the direct product of $b$ copies of $\mathbf{Z}_2$ ($\mathbf{Z}_2 \times\cdots \times \mathbf{Z}_2$, $b$ times). That is, its elements are $b$-tuples of elements of $\mathbf{Z}_2$, with both addition and multiplication defined componentwise. If $b > 1$, it is not a field. In fact it is not even an integral domain, because $(0,1)\times (1,0) = (0,0)$.

$\mathrm{GF}(2^b)$ is the field with $2^b$ elements. Because it is a field, it is not the same thing as $\mathbf{Z}_2^b$ if $b > 1$.

You should know that for any prime $p$, $\mathbf{Z}_p$ is a field with $p$ elements, so it is the same thing as $\mathrm{GF}(p)$.


AES-GCM -- what is ICV and what happens if I don't use it I am interested in using AES-GCM and after hours of reading on Internet I still have a few questions:

What will ensure the ICV, is it only Integrity ? If I don't need it on my purpose, can I spare it and still have secure encrypted data on my channel ? (If integrity is not verified, my packet will be dropped anyway)

our aim is just to encrypt data so that no one can get the information.

Thanks

ICV is the integrity check value (beware that it may also mean Initial Chaining Value). You cannot do without for GCM mode.

I'm not sure what you mean with: "If integrity is not verified, my packet will be dropped anyway". GCM uses an authentication tag which provides cryptographic integrity. Unless you have another way of adding cryptographic integrity then you cannot just skip verifying the tag.

If you do have another authentication tag, say HMAC over the ciphertext, then you don't need GCM. You could use AES-CTR mode instead. Except for some changes during initialization AES-CTR mode is used within GCM to provide confidentiality.

Beware that GCM and CTR modes do directly leak the plaintext size and possiblty timing information. That's something to solve - or not - at protocol level.


Combining multiple PRGs together Got some theoretical questions about PRGs to solve (given by lecturer for self-learning, no score involved).

Tried to find on the internet but couldn't figure out how to solve them, so I will mention my own intuition but I would appreciate a formal answer to the questions to fully understand.

$G_1$ , $G_2$ are safe PRGs in range $\{0,1\}^n \rightarrow \{0,1\}^{2n}$, s.t. $G_1 \not = G_2$.
Is $G$ necessarily a PRG? Prove your answer.

$G(s) = G_1(s) \oplus G_2(s)$
$G(s) = \overline{G_1(s)} \oplus G_2(s)$
$G(s) = G_1(s) \oplus G_2(s \oplus 1^{|s|})$
$G(s) = \overline{G_1(s)} \oplus G_2(s \oplus 1^{|s|})$
$G(s) = G_1(s) \oplus G_2(0^{|s|})$
$G(s) = \overline{G_1(s)} \oplus G_2(0^{|s|})$
$G(s) = \overline{G_1(s) \oplus G_2(0^{|s|})}$

Now $G$ is in range $\{0,1\}^n \rightarrow \{0,1\}^{n+1}$.
Is $G'$ necessarily a PRG? Prove your answer.

$G'(s) = G(s \oplus s^R)$ ($R$ is reverse)
$G'(s) = G(s \oplus G(s)^{1,...,n})$ ($G(s)^{1,..,n}$ stands for $G(s)$ first $n$-bits).

Intuition:

I belive XOR maintains the PRG attribute, so a. (and therefore b.) is true.

In 3. we essentialy flipping the bits of $G_2$ input, can't see any harm at this, same goes for d. but we flip bits of result.

Well, I think I should stop the guessing now and get a true answer for the questions, since I really have no clue.

No, A is not true.

Suppose that $G_1$ is a secure PRG and $G_2(s) = G_1(s) \oplus 1$, obviously $G_2 \neq G_1$ and $G_2$ is a secure PRG.

You can see that $G(s) = G_1(s) \oplus G_2(s) = G_1(s) \oplus G_1(s) \oplus 1 = 1$ which is obviously not a secure PRG.

Now you have a hint. You should think the rest of the problems.


Comparing messages given only the ciphertext Under RSA protocol I was wondering how a message sent could be verified
under the following scenario

Alice has a private (encryption key) and public key (decryption key)

If Bob sends Alice cipher-text but does not know the plain-text message
he sent to Alice

Can Bob send Alice a second message in plain-text to determine
what he had originally sent? Does Alice send back Bobs message
encrypted using her public key so that bob has cipher-text he can compare?

Can bob only compare cipher-text? or can he do anything else?

With messages bob sends or receives is there anything bob can do
to verify/check if the two message he sent are the same or not?

Can Bob decrypt a message with just the public key? Is he allowed to get private key from alice?

Under RSA protocol I was wondering how a message sent could be verified under the following scenario

RSA is not a protocol, it's a crypto system. It contains several algorithms that utilize the same trap door function but different encryption and signature generation methods.

  Can Bob send Alice a second message in plain-text to determine what he had originally sent?

Of course. He could also send a hash of the message he send, so that an attacker cannot view the message that was send, but note that brute force attacks may be possible. In general it doesn't make sense to send a message in plaintext if you're after confidentiality.

  Does Alice send back Bobs message encrypted using her public key so that bob has cipher-text he can compare? Can bob only compare cipher-text? or can he do anything else?

No, because a ciphertext is supposed to be CPA-secure. That means that - in general - a random padding or IV is used. So the ciphertext should not give any information about the plaintext, including equality of the plaintext.

  With messages bob sends or receives is there anything bob can do to verify/check if the two message he sent are the same or not?

No, not unless he had access to the first plaintext message, but it seems that's not envisioned in your question.

  Can Bob decrypt a message with just the public key? Is he allowed to get private key from alice?

No, and no.

This question contains answers for generic RSA. You may want to have a look at homomorphic encryption to see if anything in there suits your needs. Currently it is not clear to me if homomorphic encryption would meet your requirements.


Adapting RSA Timing Attack for Square And Multiply from right-to-left vs left-to-right I'm trying to reconstruct the fairly well-known RSA timing attack by Kocher. I'm working with simulated timing data, so I have completely noise-free "measurements". My attack is successful in guessing the exponent, as long as I use a "right-to-left" square and multiply method, i.e. an algorithm as follows (R=b^d mod m, with d having w bits):
R = 1
for i from 0 to w-1:
  if getbit(d, i) == 1:
    R = R * b mod m
  b = b * b mod m

The attack hinges on the conditional reduction when using Montgomery modular arithmetic, which my simulation uses. For each bit, I simulate the two paths (bit is zero/one) and group my measurements by whether an additional reduction was performed. I choose the path which shows the larger difference of means between the groups. Another criteria that works well is checking which path reduces the empirical variance of all measurements when I subtract the time taken by the square+mult vs just square.
Now I'm trying to adapt the attack to a left-to-right square and multiply:
R = 1
for i from w-1 to 0:
  R = R * R mod m
  if getbit(d, i) == 1:
    R = R * b mod m

I can't seem to find a suitable criteria to choose between the two paths when iteratively guessing the bits. When I just press on, correcting wrongly guessed bits as I go along, the attack still works on the lower bits, but is completely wrong (always guessing 1) for the higher bits in the beginning. I can't find any sources on how to adapt the attack to this kind of square and multiply algorithm.

I was finally able to adapt the attack. The solution is to use the reduction of the squaring of the following bit as a discriminator between the two groups. That is we split into two paths, i.e. (R^2 mod m)^2 mod m and (R^2*b mod m)^2 mod m. For each path we create two groups by whether the final mod has an additional reduction. Finally we check which two groups has a higher difference of means, just like the right-to-left variant. This works very nicely, except for the last bit, which we can simply solve by checking for a difference in variance as before.


how does the simulator work when the corrupted party has no input? "the only thing the simulator can do in the ideal model is to choose the corrupted parties' inputs." Yehuda Lindell said.

1- what will happen when the corrupted parties have no inputs to the protocol? e.g. in cases that the corrupted party/parties are just some computing servers with no input.

2- in these cases, is it any relationship between security against malicious and semi-honest adversaries. As I am thinking that, as the corrupted party has no input, anything that a malicious adversary is able to do is also possible for the semi-honest adversary.

if not,

is it possible in any way to conclude security against malicious adversaries in these cases when we have proved security against semi-honest adversaries?

A simulator is a thought experiment whose purpose is to:

show that the adversary learns no more about the honest party's inputs than he's supposed to,
show that the adversary's effect on the honest party's output is consistent with a legitimate input.

If the functionality takes no input from the corrupt party, #2 is moot but we still have #1. A canonical example is the zero-knowledge functionality, which takes no input from the verifier. When the verifier is corrupt, the purpose of the simulator is to demonstrate the zero-knowledge property.

There is no general implication between semi-honest and malicious security. Take any semi-honest protocol and modify it to add the behavior "if the other person sent me the message $(\textsf{asdf}, v)$ then send my input to that party and output $v$." Adding this behavior to the protocol doesn't affect semi-honest security since honest parties never send each other $\textsf{asdf}$ messages. But the effect on malicious security should be clear, and it has nothing to do with which party has input, etc.


PRF and deterministic polytime function implie PRG I'm struggling while trying to resolve this exercise. I already read all questions about PRG and PRF here and some proofs around the internet but none of them helped me.
let's consider a function $C$ as follow: there exists a polynomial $p$ for every $n$ in natural numbers, $C(1^n)$ is a sequence $\langle s_1,...s_m\rangle $ such that:

$2<= m <= p(n)$
for every $i \in \{1,...,m\} , s_i \in \{0,1\}^n$
$s_i = s_j $ implies $i = j$

Let's consider a length preserving partial function $F: \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^*$ and let's define $F_C$ as a function on binary strings such that
$F_C(r) = F(r,s_1) || ... || F(r,s_m)$
where $C(1^{|r|}) =  \langle s_1,...s_m\rangle$ and || is string concatenation.
Prove that if  $F$ is pseudorandom and $C$ is deterministic and polytime  $\rightarrow F_C$ is a pseudorandom generator.
Studying from Introduction to modern cryptography, I'm trying to prove that $F_C$ is a PRG following this definition:

Definition 3.14: Let $\ell$ be a polynomial and let $G$ be a deterministic polynomial-time algorithm such that for any $n$ and any input $s\in\{0,1\}^n$, the result $G(s)$ is a string of length $\ell(n)$. We say that $G$ is a $\mathsf{pseudorandom\ generator}$ if the following conditions hold:

(Expansion:) For every $n$ it holds that $\ell(n) > n$.
(Pseudorandomness:) For any PPT algorithm $D$, there is a negligible function $\mathsf{negl}$ such that:
$$\left|\Pr[D(G(s)) = 1] - \Pr[D(r) = 1]\right| \leq \mathsf{negl}(n)$$
Where the first probability is taken over uniform choice of $s\in\{0,1\}^n$ and the randomness of $D$, and the second probability is taken over uniform choice of $r\in\{0,1\}^{\ell(n)}$ and the randomness of $D$

and I understood that...

Expansion holds because $l(r) > r$ since, looking at how $C$ is defined and remembering that $F$ is length preserving , we can deduce that $l(r)$ is always at least 2 times $r$'s length because $m$ is at least 2 and each $|s_i| = r$ and they're all distinct.
Our assumption says that $F$ is a pseundorandom function and $C$ is deterministic and polytime. Concatenation is also polytime so I think $F_C$ is polytime too because it concatenates $r$ with output from $C$ but I don't know how to wirte down a formal proof about it.
I have to prove that there's no PPT algorithm $D$ such that its probability to distinguish between a random input $r$ of lenght $l(n)$ and a $F_C$ 's output of the same lenght is larger than a negligible function but I don't really know how to proceed...I read also some reduction proof but I don't know if is the right way for me because all of them proved that a new defined G is a PRG starting from another PRG.

Please can someone help me with this three points?
Thank you a lot for reading my question!

For your points:

Your discussion of expansion is correct. In particular, you can show that $\ell(r) = mr \geq 2r > r$, which is essentially what you explain.

You can write a formal proof that $F_C$ is poly-time in essentially the same way you would show any algorithm is poly-time. In this case, it is quite obvious that the result is poly-time, so if it feels obvious to you that this is the case that should be normal. That being said, there are some subtleties --- concatenating two things with polynomially-sized representations is poly-time, but what if you have exponentially many things? This would no longer be poly-time. Can you be sure the algorithm is still poly-time in light of this (and if so, why?)

You have a definition of pseudorandomness for PRGs (definition 3.14), which likely want to relate to a definition of pseudorandomness for partial function (in particular $F$). I would suggest finding the particular definition you're working with first. Your proof strategy should be reduction to $F$'s pseudorandomness -- some statement along the lines of "Any distinguisher for $F_C$ implies a distinguisher for $F$, which as $F$ is pseudorandom does not exist, so the distinguisher for $F_C$ cannot exist as well". This is the "general template" of proofs by reduction within cryptography, so you would do well to internalize this "strategy".


RSA decrypting of a huge file by parts I need to decrypt a huge file that I own previously encoded by myself with a RSA public key (it's possible for this step using a symmetric algorithm key). Problem is that I can't load it in my disposable memory for specific embedded architecture reasons.

I need to decrypt it with the private key associated to the identity of that architecture (or the shared symmetric case if there were the algorithm chosen). I want to know if its possible to decrypt the file loading it in memory by parts and decrypting each of them, without losing security against brute force attacks. As far as I know, in a typical RSA encoding process first you transform the whole char string that is the file into a number, to be encrypted, so my assumption is that is not possible in a typical RSA encoding-decoding process. However, as I have the file I can encrypt it line by line or char by char, instead of encoding the whole, to decrypt it later again slice by slice. I'm assuming that a line or a char after encryption would have the same length in bytes, which may be a wrong assumption.

EDIT:
Let's complicate things a little bit more: After decrypting through RSA or symmetric key, I'll have to encrypt again the slices of my huge file, this time with a RSA public key. So, first: Encrypting huge file on a custom basis to make it decryptable part by part; second: take each part and encrypt it with RSA.

Is this a feasible solution? Am I losing efficiency and would be more exposed to brute force attacks?

EDIT2:
Keysizes would be the typical for opensource implementations: a minimum of 256bits. I've to investigate the hybrid encryption, can't tell yet. When I say a line I mean chunks of data of, let's say, 50-60 chars. I pretend to encrypt-decrypt a binary file, so char length doesn't matter (consider them 1 bytes ASCII if it helps)

As far as I know, in a typical RSA encoding process first you transform the whole char string that is the file into a number, to be encrypted, so my assumption is that is not possible in a typical RSA encoding-decoding process.

That's not typical. A typical real world RSA encryption process uses hybrid encryption, encrypting the data with a single-use symmetric key that is then encrypted using the actual RSA algorithms.

Depending on what the symmetric encryption is, you may be able to "seek" within the encrypted file without decrypting other parts. In most cases you'll at least be able to read it from the start and throw away decrypted parts as you go, avoiding excessive memory use.

  However, as I have the file I can encrypt it line by line or char by char, instead of encoding the whole, to decrypt it later again slice by slice. I'm assuming that a line or a char after encryption would have the same length in bytes, which may be a wrong assumption.

  Is this a feasible solution? Am I losing efficiency and would be more exposed to brute force attacks?

Using context-dependent (e.g. lines) blocking could leak data on the plaintext, so I wouldn't recommend it.

If you need to be able to quickly jump within the encoded file, you should use a symmetric encryption algorithm (under RSA if you want) that makes this easy. For example, AES in CTR or CBC modes. You will not be able to safely modify a small part of the file, but for read-only access that would be fine.

  EDIT: Let's complicate things a little bit more: After decrypting through RSA or symmetric key, I'll have to encrypt again the slices of my huge file, this time with a RSA private key. So, first: Encrypting huge file on a custom basis to make it decryptable part by part; second: take each part and encrypt it with RSA.

I.e. the file is read-write?

In that case, I would divide the file into constant-sized blocks that get independently encrypted using any symmetric encryption algorithm that accepts a large nonce (24+ bytes would be good, but 16 at the very least). Generate a single symmetric encryption key, which you encrypt with RSA. For each block generate a random nonce/IV that gets prepended to the ciphertext. When something is modified, rewrite the whole block(s), generate new random nonces.

Block size should be chosen to balance the memory expansion caused by nonces with the write amplification caused by rewriting blocks. Something like 4KiB blocks would probably be OK, I would think.

Instead of random nonces, one could use an incrementing counter, but in that case there might need to be additional safeguards to prevent an attacker feeding you an old version of the file, so random nonces are simpler.


Encrypt a single file, chunk-by-chunk, each chunk using different key (AES) Encrypt a single file, chunk-by-chunk, each chunk using different key.
I am a security newbie (only took 2 security courses before)
But currently I am using this encryption method for my Android application, which perform client-side encryption and upload each encrypted chunk into different cloud storage (Dropbox, Box, Google Drive, SkyDrive) {The app is not yet published in google market, and is planned for publish after it is stable}
But somehow I think it seems like it is doing extra works without adding extra level of security.

Steps as below:

Using PBKDF2, I derive 1 master key (Km) and 1 database key (Kd) from two passwords provided by user
Then I further derive multiple partial keys (Ki...Kn) from (Km) using PBKDF2 with random salts. The salts (Si...Sn) are stored in a database encrypted with (Kd)
Then I split a file into multiple chunks (4MB), and encrypt each chunk with different partial key (Ki...Kn)
The information of which salt is associated with which chunk is stored as file metadata in database. (the database is stored in cloud storage too)
The same steps goes for decryption, in reverse way (take 2 passwords from user, derive Km and Kd, decrypt database, retrieve salts from database, derive Ki...Kn from Km + salts, decrypt each file chunk, merge each chunk back to original file.

Initialization vector (iv) is also used when initialize the cipher, but I don't mess anything with it. I follow the original method and I just append it infront of my file chunk as plain text.

As far as I understand the usage of Salt is we don't need to keep it secret. As it simply makes brute force attack slower.
But in my case, I am keeping the salt secret (some people call it pepper, or shared secret)

My main questions are:
1) Is my design flawed?
2) If it is not flawed, does it provide extra security? instead of just slowing down brute force. Or is my design totally pointless and extra?
3) Any else comments are welcomed.

Step 1: good job, this is the right way. You can also use bcrypt or scrypt for extra resistance. Make sure you have chosen sufficiently strong parameters, that is, 64-bit salt and 10000 rounds absolute minimum.

Step 2: no! once you have a strong derived master key, you don't need to apply PBKDF2 on any keys derived from this master key. You are just wasting time and effort and it doesn't scale at all. Use HMAC with a random nonce and keyed with the master key.

Step 3: Why not just encrypt the whole file with a single (derived) key? Why would you want to split the file into chunks? If you do have a good reason, ignore this.

Step 4: I.. suppose.

Step 5: Yeah.

Is my design flawed? Well I won't lie to you, it is a bit weird. You don't need to split the file into chunks if you just want to encrypt it. You are making it needlessly complex. Unless you have good reason. Now the real problem is you have no mechanism in place for integrity checking and authentication. That is BAD.

Or is my design totally pointless and extra? Frankly, yes, it is.

Any else comments are welcomed. Do not design your own real world cryptosystem. Either you do it the simple way and have someone competent (or better yet, multiple) look over it  before deploying it, or don't do it at all. Mindlessly throwing cryptography at a problem isn't the right approach.

The problem I have with this question is that you have no clear goal in mind. What are you protecting against? What is your threat model?  Where is the database stored? Who or what  will access it? etc..

Without knowing this, "extra security" doesn't mean anything. More secure than what, against what?

TL;DR: design is flawed and over-engineered, designer should not be designing cryptosystems for real world use (though it's fine to experiment, of course). Best use an existing file encryption scheme (there ought to be millions for Android, but OpenSSL will do fine) and store metadata in a secure database.


Password cracking: What if attacker is lucky? We have always measured password or private key strength by the amount of entropy it contains, but what if the attacker who cracks it is lucky.

Consider the following simple scenario, we have 1 bit [0,1] secret , the attacker should choose between 2 combinations, but the attacker already has a 50% chance of guessing the right one.

Now consider a 128 bit secret. It should have 2^128 combinations, so the attacker should go through 340282366920938000000000000000000000000 combinations before guessing the secret, but he actually only has to go through half of that: 170141183460469000000000000000000000000, because he probably has a 50% chance of guessing it right.

So if at each bit he has a 50% chance, that means that 1 bit is actually only half bit.

And if he is very lucky, say 90% chance, that means that 1 bit is actually only 0.1 bit.So in face of a very lucky opponent, a 128 bit password has only 12.8 bit strength.

What is your opinion about this?

"lucky" is not a property of the attacker. There's no "lucky" attacker nor "normal" attacker. They both have the same probability (low, very low) to guess the key. You can decrease the probability at will by increasing the length of the key (i.e. the no. of bits). You cannot really argue "what if the attacker is lucky" because "being lucky" is a posteriori statement; you say that an attacker is lucky only when he/she was... lucky


How can I prove that a Feistel round is its own inverse for DES? I'm having difficulty on proving the fact that each round of DES algorithm is its own inverse. Can someone put a concise explanation for it please?

If a function, say $f$ ,is its own inverse than $f(f(x))= x$  right? I try to prove that, given a round function $Rd$, that: $Rd(Rd(L_1\|R_1))= L_1\|R_1$.  Here $L_1$ and $R_1$ are the left and right portion of the input.

Then I get:
$$Rd(R_1\|L_1 \oplus F(R_1,K_1))=L_1 \oplus F(R_1,K_1)\|R_1 \oplus F(L_1+F(R_1,K_1), K_2)$$
... this must be equal to  $L_1\|R_1$.

But I cannot see how this would be equal to $L_1\|R_1$? Where am I making a mistake?

There's a simple way by which "each round of DES algorithm is its own inverse". Consider round $n$ of DES as involving (almost  only) a function $g_n$ with
$$g_n(L\mathbin\|R)=\bigl(L\oplus f(R,K_n)\bigr)\mathbin\|R$$
where $K_n$ is the 48-bit subkey for round $n$, function $f$ is the "cipher function" (given in the definition of DES), and $L$ and $R$ are 32-bit bitsrings forming a 64-bit block.

That function $g_n(L\mathbin\|R)$ verifies $g_n(g_n(L\mathbin\|R))=L\mathbin\|R$, as thought in the question; or in other words $g_n$ is an involution; or in yet other words $g_n\circ g_n$ is the identity function. Proof:
$$\begin{align}
g_n(g_n(L\mathbin\|R))&=g_n\Bigl(\bigl(L\oplus f(R,K_n)\bigr)\mathbin\|R\Bigr)\\
&=\Bigl(\bigl(L\oplus f(R,K_n)\bigr)\oplus f(R,K_n)\Bigr)\mathbin\|R\\
&=\Bigl(L\oplus\bigl(f(R,K_n)\oplus f(R,K_n)\bigr)\Bigr)\mathbin\|R\\
&=\left(L\oplus0^{32}\right)\mathbin\|R\\
&=L\mathbin\|R
\end{align}$$
That proof invokes the definition of $g_n$ (twice), associativity of $\oplus$, that $f$ is a function, that for all 32-bit $X$ it holds $X\oplus X=0^{32}$ (the bitstring of 32 zero bits), which is the neutral for $\oplus$.

DES encryption chains these 33 operations on 64-bit quantities:
$$\mathsf{IP}\,,\,g_1\,,\,\mathsf S\,,\,g_2\,,\,\mathsf S\,,\,\ldots\,,\,\mathsf S\,,\,g_{15}\,,\,\mathsf S\,,\,g_{16}\,,\,\mathsf{IP}^{-1}$$
where $\mathsf S$ is the "swap" involution defined by $\mathsf S(L\mathbin\|R)=R\mathbin\|L$, function $\mathsf{IP}$ is some permutation of bits, and $\mathsf{IP}^{-1}$ is the inverse permutation.

DES decryption chains these 33 operations on 64-bit quantities:
$$\mathsf{IP}\,,\,g_{16}\,,\,\mathsf S\,,\,g_{15}\,,\,\mathsf S\,,\,\ldots\,,\,\mathsf S\,,\,g_2\,,\,\mathsf S\,,\,g_1\,,\,\mathsf{IP}^{-1}$$

We see that DES encryption then decryption is the identity function: the $(34-j)^\text{th}$ operation of decryption cancels the $j^\text{th}$ operation of encryption:

For $j=33$, because $\mathsf{IP}$ cancels $\mathsf{IP}^{-1}$.
For $j=1$, because $\mathsf{IP}^{-1}$ cancels $\mathsf{IP}$.
For other even $j$, because $g_{j/2}$ is an involution.
For other (odd) $j$, because $\mathsf S$ is an involution.

Importantly, encryption and decryption use the very same structure, only the indexes (that, is, the order of the subkeys $K_n$) differ. That allow to use identical hardware or code for both encryption and decryption.

The usual definition of a round of a Feistel cipher includes the swap $\mathsf S$:
$$\begin{align}
g'_n(L\mathbin\|R)&=\mathsf S\bigl(g_n(L\mathbin\|R)\bigr)\\
&=R\mathbin\|\bigl(L\oplus f(R,K_n)\bigr)
\end{align}$$
and this function is not its own inverse per the sense in the question.

With that notation, DES encryption and decryption are the 18 operations
$$\mathsf{IP}\,,\,g'_1\,,\,g'_2\,,\,\ldots\,,\,g'_{15}\,,\,g_{16}\,,\,\mathsf{IP}^{-1}\\
\mathsf{IP}\,,\,g'_{16}\,,\,g'_{15}\,,\,\ldots\,,\,g'_2\,,\,g_1\,,\,\mathsf{IP}^{-1}$$
In that presentation, it is less apparent that decryption undoes encryption. But that still holds, and becomes obvious again if we expand the $g'_n$ into $g_n$ followed by $\mathsf S$.

When it is said that DES has 16 rounds, it is ignored $\mathsf{IP}$ and $\mathsf{IP}^{-1}$. And, for a strict Vulcan, only the 16th round (the one without swap) is its own inverse.

The DES specification, and many textbooks on Feistel ciphers, give indexes to $L$ and $R$ before and after round $n$ of encryption, with $L_0\mathbin\|R_0$ the plaintext after $\mathsf{IP}$. The above equation for $g'_n$ can then be written as:
$$\begin{align}
L_n&\gets R_{n-1}\\
R_n&\gets L_{n-1}\oplus f(R_{n-1},K_n)
\end{align}$$

DES (which as $m=16$ rounds) and some textbooks consider the ciphertext (before $\mathsf{IP}^{-1}$) to be $L_m\mathbin\|R_m$, and specialize the last encryption round's equations:
$$\begin{align}
L_m&\gets L_{m-1}\oplus f(R_{m-1},K_m)\\
R_m&\gets R_{m-1}
\end{align}$$

There are other conventions around: some texts use the same equations for all rounds. Then some add a final swap, or consider the ciphertext to be $R_m\mathbin\|L_m$; others consider $L_m\mathbin\|R_m$ as the ciphertext (that later kind does not obtain the same ciphertext as DES).

As to decryption, DES uses the same round equations for encryption and decryption except for the numbering of subkeys, that is for $1\le n<m$:
$$\begin{align}
L_n&\gets R_{n-1}&&&L_m&\gets L_{m-1}\oplus f(R_{m-1},K_1)\\
R_n&\gets L_{n-1}\oplus f(R_{n-1},K_{16-n})&&&R_m&\gets R_{m-1}
\end{align}$$
with the decryption's $L_0\mathbin\|R_0$ defined as the encryption's $L_n\mathbin\|R_n$, from which it follows that for $1\le n<m$, the decryption's $L_n\mathbin\|R_n$ is the encryption's $R_{m-n}\mathbin\|L_{m-n}$ (notice the inversion), and the decryption's $L_m\mathbin\|R_m$ is the encryption's $L_0\mathbin\|R_0$.

Other texts use the same naming for equal variables in decryption and encryption, and define different round equations for decryption. For regular round structure that gives:
$$\begin{align}
R_{n-1}&\gets L_n\\
L_{n-1}&\gets R_n\oplus f(L_n,K_n)
\end{align}$$

Footnote per comment: There is always some form of swap between rounds of a Feistel cipher, so that the fraction of the state that did not change in a round changes in the next round. That's essential for security (not for decryption to work). A round is its own inverse only if we exclude the swap as part of its definition.


How does the energy consumption of the SHA-3 finalists compare? I am curious, is there any paper where SHA-3 competitors are compared in terms of energy efficiency?

I found the answer in the paper "Comparison of the Power Consumption of the 2nd Round SHA-3 Candidates" (PDF version) by Benedikt Westermann, Danilo Gligoroski, and Svein Knapskog, published at the ICT Innovations 2010 Conference.


How can I exploit the structure of the secp256k1 prime for fast arithmetic? I'm implementing logic on an FPGA (programmable chip) that does the key verification part of ECDSA on the curve secpk256k1, in which all operations are mod p where $p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$ (a Mersenne prime).

I'm starting with building a circuit to do the modular reduction, I know about Barret's and Montgomery's algorithm, but I have been reading in several guides that because of the $2^n - c$ form, as well as it being a Mersenne prime that there are simpler ways to do the modulo reduction.

But I'm getting stuck on understanding the actual logic underneath this, I was wondering if any one have any good example or pointers to understand how to do this modulo operation a bit better?

There was a similar question here (except I'm doing this on FPGA not CPU, so the word size is irrelevant) but I don't totally understand the answers reply, so even just some helpful comments explaining the same thing would be a huge help. Fast modular reduction

This paper also has a fast implementation on page 7 (http://cse.iitkgp.ac.in/~debdeep/osscrypto/psec/downloads/PSEC-KEM_prime.pdf) which looks like it came from one of these optimizations above, but I would like to try understand how to get there myself.

Let $p = 2^n - c$.  Then $2^n - c \equiv 0 \pmod p$, so $2^n \equiv c \pmod p$.
 Suppose you have an integer $$x = 2^n x_{\mathrm{hi}} + x_{\mathrm{lo}}.$$  Then $$x \equiv c\cdot x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p.$$  In other words, you can compute a reduction step by shift/multiply/add: shift right by $n$, multiply by $c$, and add to the low $n$ bits.

The best case is when $c = 1$, so $p$ is a Mersenne prime: then you can skip the multiplication altogether.  But you can generalize this further for $p = 2^n - 2^m - d$, since $2^n \equiv 2^m + d \pmod p$, so $$2^n x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv 2^m x_{\mathrm{hi}} + d \cdot x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p.$$  That is, you can compute a reduction step by an $n$-bit shift, an $m$-bit shift, a multiply by $d$, and two adds.

Similarly, if $p = 2^{2m} - 2^m - 1$, like Ed448-Goldilocks uses, then you can compute a reduction step $$2^{2m} x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv 2^m x_{\mathrm{hi}} + x_{\mathrm{hi}} + x_{\mathrm{lo}}$$ with two $n$-bit shifts and two additions.

Obviously, you can always write any modulus as a sum of powers of two; the more terms there are, the more costly the reduction step is to write as a series of shifts and adds.  In software implementations, at some point it may be faster to use the CPU's multiplier than your own shift-and-add steps.  For instance, in secp256k1, I'd guess that it is fastest to write it as $2^{256} - 2^{32} - 977$ if you can take advantage of a CPU's 32x32->64-bit multiplier, but you should consult libsecp256k1 for the state of the art in arithmetic modulo this prime.


Symmetric key pair on app and low power device I have a microcontroller based device that is controlled by a smartphone app. To make the communication between the two secure, I'm encrypting the communication between the two using AES. However, this means that both devices need to know the private key to decrypt the exchanged messages. A single instance of the app (on a single smartphone) can communicate with multiple devices.

If I were to have the same key for all devices and hardcode that key in the app it would work, however, if for some reason if the key is compromised then all the devices are open to misuse and MITM attacks as well. I'm hoping someone experienced here can help me figure out how each device can have its own unique key and how the app should handle this. Any help would be appreciated. Thanks!

It seems you are mistaking the block cipher AES to be a secure transport protocol.

To provide transport security a secure transport protocol is required. In those protocols the session keys are usually distributed using either encryption with the help of a (trusted) asymmetric key pair or by a key agreement primitives. Together with symmetric message encryption this makes up a hybrid cryptosystem.

For embedded devices usually ECDSA and ephemeral ECDH are used as underlying primtives. Note that in general transport security also requires message authentication.

If you are just looking for a method of securely sharing symmetric keys then you can secure one master key at the server and distribute derived keys to the clients. The master can always perform KDF(master_key, client_id) to derive the keys again. HKDF is probably the best known key based KDF right now.

I'd recommend a careful study of TLS and DTLS before proceeding.


Fastest algorithm for message authentication? I'm searching for the fastest way to verify that a message was sent by the correct user.

The first solution I know of is to use HMAC. But in order to verify, I'll have to produce another signature and compare it with the original. In my case, this does not seem to be the best choice, because the time needed to verify is practically equal to the time needed to produce the signature.
To use a classic cryptographic signature (RSA or AES) over a MD hash.     I didn't find benchmarks/times for verifying a signature (but just for producing the signature). Surely, to produce a signature is slow, but to verify?
Finally, is there any algorithm that use a statistical  method for granting authentication (most of the messages are valid)?

After comparing benchmarks, it seems there is a third way which is a lot faster (10 times more): to use the GMAC/VMAC algorithms.

I'm developing in Java, but a C/C++ library would also be OK.

Specifically, my questions are:

Can you confirm that the best solution is GMAC/VMAC for this scope?
If yes, does anyone have an example for how to write the code for generating/verifying a byte array in Java (perhaps with the Bouncy Castle library).

eventually is there any algorythm that use a statistical method for
  granting authentication (the most of the messages are granted valid) ?

This would be a non-cryptographic way of doing it and would likely allow malicious users / attackers to fake authentication.

  to use a classic cryptographic signature (RSA or AES) over a MD hash.
  i dint find benchmarks/times for veryfying a signature (but just for
  producing the signature) . Surelly to produce a signature is slow, but
  to verify?

RSA and Rabin-Williams signatures are highly asymmetric in speed. Signature generation is slow, but verification is comparatively fast. However, RSA, ECDSA, RW and thelike are still very slow compared to symmetric methods.

Note that AES is not an asymmetric algorithm and thus does not fall into this category.

  first solution I knows it to use HMAC. For veryfing the data i have to
  produce the signature and comparing it with the original. It seams not
  the best in my case because the time for verifying is equal pratically
  to the time for producing the signature.

HMAC is a way construct a Message Authentication Code from a hash function. There are other MACs as well, which usually are faster (because hash functions are slow), which include GMAC, VMAC and CMAC (/OMAC).

The standard recommendation would be to use HMAC with a decently fast hash function. If that doesn't cut it, and you need more speed, you probably want CMAC with AES (assuming you have hardware acceleration for AES). If even that doesn't cut it, you are probably in a hardware deployment scenario and won't use Java anyways.

Note that HMAC and CMAC don't require a nonce for proper security, which makes them a nice choice most of the time. Other algorithms like GMAC and VMAC do require a nonce and there usually will be severe security implications (like a leak of the key), if the nonce is ever re-used.

  if yes in question 1, it would be usefull to see a example how do
  write the code for generating/verifying a byte array in java(probably
  the most idoneus is bouncy castle library). I thank you if you can
  show a short example for using it.

You will have to ask this question on a more programming focused site such as StackOverflow. Maybe also have a look at this previous Q&A there.


Biased RSA moduli and ROCA Say I can generate many 1024-bit RSA public keys $(N,e)$ with fixed public exponent $e = 65537$. They turn out to be heavily biased when computing $N \bmod x$ for small primes $x$. These congruences always seem to hold:

$N \equiv 1 \pmod 2$
$N \equiv 1 \pmod 3$
$N \equiv 1 \pmod 5$
$N \equiv 1 \pmod{11}$
$N \equiv 1 \pmod{89}$

So $N = 29370 * k + 1$. What does this mean for $p$ and $q$? Can a ROCA-style attack be carried out? How does one use this information to factor $N$?

A similar observation as yours was the starting point for the ROCA attack. In 2016, some of the authors of the ROCA attack (with other coauthors) had published a paper a USENIX about determining the origin of RSA keys. Some SW-libraries or smart cards generate public RSA-keys with certain characteristics that allow to identify with high probability which library was used given in some cases just one and in other cases just few public RSA keys.

The five equations you found are for sure not enough to break a 1024-bit key. Your first two equations one can easily explain. Being odd is necessary. Having $N = 1\bmod 3$ can come from the fact that the implementor of the library chose to generate only primes that are $2\bmod 3$ (like I always do). The reason for this choice is that usually one first tests the prime candidate $q$ (after a pre-selection using trial division or a sieve or something more creative) with a Fermat test, before inverting $e \bmod q-1$. But if $q = 1\bmod 3$ and a public exponent $e$ is given that is a multiple of $3$ (some like $e=3$), then the inversion always fails, so that a Fermat test would have been a waste of time.

For your other three equations I cannot imagine any reason. So try to find other restrictions for the RSA-keys generated by your library. What you should look for is if for some other small primes $p$ not all values $\ne 0\bmod p$ are possible, and if maybe the set of possible values is a subgroup of the multiplicative group $\mod p$ (i.e., closed under multiplication $\bmod p$). If you find such subgroups for different primes $p_1$ and $p_2$, you should then take a look also at the values $\bmod (p_1\cdot p_2)$, and if there are more restrictions. If, for example, you see that only the values $\pm 1\bmod 7$ and $\pm 1\bmod 13$ show up, then check if all values are $\pm 1\bmod 91$ or if also $27\bmod 91$ and $64\bmod 77$ are possible (which would be worse for the attacker).

For a successful attack you would have to hope that the modulus $N$ is modulo some small primes in certain subgroups, because both primes lie in those subgroups. This does not have to be so (it's quite easy to generate RSA-keys that look like they are vulnerable to the ROCA attack, but are perfectly safe), but it is a reasonable assumption for the lack of any other reason for it.

For using Coppersmith's method one would need to know the value of one of the primes $q$ modulo a product $\Pi$ of small primes which has bitlength more than 256 (for 1024-bit modulus $N$), better at least 270. For $\Pi$ big enough, a simple application of Coppersmith takes less than a second, so one can try it for some billions of possible values of $q\bmod \Pi$ to factor $N$.

So Coppersmith's method allows to factor $N$ even if the remaining entropy for the prime $q$ is still $>100$ bit (this was verified in the certification of the Infineon key generation), as long the entropy of $q\bmod\Pi$ is low enough.


Adding a Password Hash (key derivation) function to existing password storage solution As always we are trying to improve password storage; before just adding new ways of storing our password we need to define what threats we will mitigate by adding in a new way to store our password.

Currently we store passwords with HMAC (using SHA-1), individual salts generated with a PRNG

(RSA X 9.31) function, the HMAC key also generated with the PRNG function.

So, currently each user password is generated as follows

securePassword = CSPRNG Salt + (HMAC-SHA1-256Function(HMAC-KEY, CSPRNG Salt+Plaintext))

So, adding a slow hash, KDF or Bcrypt etc as follows

securePassword =

CSPRNG Salt + PBKDF2 ((HMAC-SHA1-256Function(HMAC-KEY, CSPRNG Salt+Plaintext)))

What does this give us in addition to our existing solution?

All I can say it gives us is:

Makes brute force more difficult i.e. slows down the brute force by significant factor.
provides a way to increase the iteration counter for when computation becomes faster.

Does adding this slow hash add any other additional

security measures or prevent any other security threats?

Currently our HMAC key is held in the same database as the password,

I know not ideal, though this is outside my control.

HMAC already helps prevent against brute force so adding in the

slow hash really only provides point two above. Any other thoughts?

Since your HMAC key is held in the same database as the passwords you shouldn't count on it to do anything... If the attackers get the passwords, they get the HMAC key. So HMAC doesn't prevent brute forcing, and a password hashing function would provide both points 1 and 2 above.

Depending on your timeline you may want to consider using whatever function ends up being chosen as the winner of the Password Hashing Competition (https://password-hashing.net/). That's not expected to happen until Q2 this year though, so switching to or adding scrypt, bcrypt, or PBKDF2 in the mean time is probably a good idea.


"One-Wayness" of SHA 1 I recently started learning about Hash Functions for my first time, and I've gone through and have tried to understand the SHA1 process.

Brilliant does an excellent job of explaining it step by step.

https://brilliant.org/wiki/secure-hashing-algorithms/

As far as I've understood, hash functions are meant to be collision-resistant and really hard to back-calculate, even if one knows the exact process.

Although I can see the process, to me who doesn't know much about cryptography yet, the process seems extremely random - as if a drunk person was asked to perform mathematical operations on a bunch of bits.

I can't really see the motivation for the precise steps taken in SHA 1...

What about those steps make it collision resistant?
What makes it hard to "back-calculate"?
Why is the process...what it is? Why not some other "random mathematical operations"?

SHA-1, like the earlier MD5 and SHA(-0), and the later SHA-2, is built per a carefully devised hierarchical design:

Merkle-Damgård at the outer, building a collision+preimage-resistant hash with a security argument based on a fixed-width compression function.
Davies-Meyer to build that compression function, with a security argument based on a block cipher with strong related-keys security (message blocks are the key).
Iteration of unbalanced Feistel rounds to build that block cipher.
Sort of an Add/Rotate/Xor (ARX) strategy with Shift/AND selectively added to implement the necessary non-linear round functions of the block cipher and of its key schedule.

The only distinctly haphazard aspect is the multiple non-linear functions changing after 20 rounds. That's an idea inherited from MD5, and it did not much help SHA(-0) or SHA-1. It was dropped in SHA-2, in favor of a uniform round function combining several non-linear functions. That was a reasonable move.


How to securely deal cards? Thanks to a certain pandemic going around I was wondering whether there is any cryptographic way to remotely deal cards without the dealer being able to know them and without requiring to trust a server for that. My first impulses involved secret-sharing and zero-knowledge-proofs but that is probably not even related... Some first thoughts:
Given a stack $S$ of $N$ cards, $n$ shall be dealt to each hand $H_i, i\in\{1,2,...,p\}$ of $p$ players with the following requirements:

$N\ge n\cdot p$ (obviously)
Once a card has been drawn it cannot be drawn by someone else as well, i.e. $$\forall i\neq j: H_i\cap H_j = \{\}$$
No one must be able to determine which cards anyone else has nor which ones remain in the stack. Just passing around the encrypted state of a shuffle bag is thus not good enough. Maybe everyone should contribute some encrypted randomness which in a second round is used to determine the dealt cards?
At some point one must be able to proof a specific card is§ currently in the hand.

Is there any method which can achieve this?

§ I guess a blockchain could be used to keep track of the cards changing places later on

I think you are looking for "mental poker".
Here is a video of Ron Rivest specifically discussing how to deal cards via mail/internet.
The paper here might also be a good read (from the creators of RSA).


Are all stream ciphers algorithms based XOR with the key? I'm new to cryptography and I try to understand more how the stream encryption works.
When it comes to stream encryption I understand that the paradigm is to perform 1-to-1 bit encryption; the input message is XOR'ed with the key.

What happens when the key length is less than the size of the message?
Does all algorithms perform the same XOR operation with the key or there are other operations to be performed as is the case with block cipher where multiple rounds and derivate keys are used?

How can I better understand the stream cipher?

Are all stream ciphers algorithms based XOR with the key?

Almost all. The reason is simple; x-or is a cheap operation and  $c = m \oplus k$ then
$$c \oplus k = (m\oplus k) \oplus k = m$$
Therefore if you x-or the message with the keystream then re-xor is equal to the message. This helps to use the same logic as encryption and decryption. This reduces the cost of hardware.
There is another important property of the x-or;

x-or of a random sequence with a non-random sequence is random. Therefore it can hide our non-random messages very well if the produced sequence for the stream cipher has good randomness.

Note that a stream cipher doesn't need to output one bit per cycle/encryption.  AES in CTR mode is a stream cipher that produces 128-bit per AES encryption/counter. The ChaCha20 stream cipher has a 64-byte block size, in other words, it produces 512 bits per counter.
As pointed FGrieu, there is also modular addition/substruction, when the number of the symbols are not power of 2, $c = m + k \bmod n$ for encryption and $m = c - k \bmod n$ is used. The Solitaire manual stream cipher uses this operation.

What happens when the key length is less than the size of the message?

Stream ciphers are designed to produce a very long sequence of bits, so there is no issue here. The real issue is reusing a (key,nonce) pair more than one. This can result in the loss of confidentiality.

Does all algorithms perform the same XOR operation with the key or there are other operations to be performed as is the case with block cipher where multiple rounds and derivate keys are used?

Well, the obvious answer is the x-nor, that is $\neg\oplus$. Can we use other than x-or and x-nor? Exercise:

find a binary operation that doesn't destroy information yet doesn't leak, too!

How can I better understand the stream cipher?

Well, reading a book about stream ciphers and designs? You can start from

The Handbook of applied cryptography chapter 6
Study LFSR-based stream ciphers, they are easy to understand.
Study RC4
Andreas Klein's Book : Stream Ciphers
Next step is eSTREAM: the ECRYPT Stream Cipher Project. Read the eSTREAM candidates/winners and attacks on them.


OMAC 0 in EAX cipher I am reading Rogaway's original paper on EAC, page 7, where the MAC function is an OMAC with a 0.

Iwata´s web page only refers to versions 1 and 2 of the OMAC cipher. So which algorithm is used for OMAC 0?

The OMAC version used by EAX is OMAC1, which is equivalnent to CMAC. The zero you're talking about is probably the zero in $\operatorname{OMAC}^0_k$. This does however not distinguish different algorithms but it displays the tweak value. The tweak itself is simply prepended to the message before OMAC1 is applied.

This is explained in figure 1:

  Algorithm $\operatorname{OMAC}^t_K(M)$
  (50) return $\operatorname{OMAC}_K([t]_n | M)$

so t is encoded in $n$ bits before being put in the OMAC function.


Check if this cryptosystem is safe Let $G$ be any group where group operations, as well as finding the inverse of an
element, can be performed quickly, but the discrete log problem is difficult. Consider
the following cryptosystem:

Alice chooses an element $g ∈ G$, a message $m ∈ G$, and an integer $k_A$.
Alice computes $s = mg^{k_A}$ and sends $s$ to Bob.
Bob chooses an integer $k_B$, computes $t = sg^{k_B}$ , and sends Alice $t$.
Alice computes $u = tg^{−k_A} = mg^{k_B}$ and sends $u$ to Bob.
Bob computes $ug^{−k_B} = m$ and recovers the message.

Is this cryptosystem safe?
I've noticed that Eve has $s$, $t$, and $u$
and that they are all divisible by m. Does this mean it's not safe? Or what am I missing?

Help is appreciated

This is extremely insecure. The discrete log is a red herring -- nowhere in the problem is the difficulty of discrete log relevant, because neither party ever uses their knowledge of their private exponent (computing $g^{-k}$ given $g^{k}$ does not require knowledge of $k$, so if inverses are fast to find, knowing one gives you the other quickly). That means we can ignore the exponentiation; all you have is Alice picking $a\in G$ and Bob picking $b\in G$, so $s=ma$, then $t=mab=sb$, then $u=ta^{-1}=mb$. Eve intercepts $s,t,u$, and computes $s^{-1}$, then $s^{-1}t=b$, then $b^{-1}$, then $ub^{-1}=m$. The issue isn't really that they're all divisible by $m$, it's that you rely on keeping $a$ and $b$ private but then send $s$ and $sb$ over a public channel (which means an attacker can easily recover $b$ and thus $m$).

In actual ElGamal, you actually use your private exponent. Instead of having to keep $g^{k_A}$ and $g^{k_B}$ secret, you rely on the fact that Alice (who knows $g^{k_B}$ and $k_A$) can compute $g^{k_Ak_B}$ while an attacker cannot. To use the security of discrete log, you have to do something that's easy for someone knowing the exponent but difficult for someone else; finding the inverse is not that something.


Negative numbers with additive ElGamal I'm trying to implement Private Set Intersection using the additive ElGamal public key encryption system. The code I've written can encrypt and decrypt numbers using the ElGamal system, so far so good. Adding and multiplying the cipher also works. Or at least, it works with positive numbers.
As I understand modulo arithmetics negative numbers can be think of by the following: $x + a = 0 \mod q$ where $a$ is a negative number. So if I have the group order set to 8009 minus one can is 8008, because $1 + 8008 = 0 \mod 8009$.
Now I noticed that no matter which generator I use, when I use power-mod such that $g^{q-1} \mod q$ the result always 1. I didn't dig much in the math of encryption yet, but it seems to a consistent result. $2^6 = 1 \mod 7$, $1151^{8008} = 1 \mod 8009$ and so on. Which then brings me to a problem. The whole 'additive' part comes in due because of using exponentials, such that $g^x g^y = g^{x+y}$ But would this be true in modulo arithmetic here? $g^{-1} g^{+1} \mod q$ should evaluate to 1 to have the $x + y = -1 + 1 = 0$, yet if $g^{-1} \mod q$ is always 1 then the result of $1 * g$ will be just $g$, so I would be off by one. In fact, the $g^{-1} \mod q$ is always one, but then $g^0 \mod q$  is also 1. What's going on here? I'm really confused.

Now I noticed that no matter which generator I use, when I use power-mod such that g^(q-1) mod q the result always 1

Congratulations, you just rediscovered Fermat's Little Theorem which says that for all primes $p$ and all non-zero integers $a$ which are not multiples of $p$, it holds that $a^{p-1}\bmod p=1$.

So if I have the group order set to 8009 minus one can is 8008, because 1 + 8008 mod 8009 = 0.

Indeed, this is how it works for plain addition $\bmod 8009$, however it seems you're not actually doing that and are actually using lifted ElGamal, i.e. encrypting as $(g^k \bmod p,g^m\cdot y^k\bmod p)$ (because standard ElGamal only has a multiplicative homomorphism).
But at that point you're no longer adding $m+m'$ but you're instead adding $g^m\cdot g^{m'}=g^{m+m'}$ and as it turns out, these exponents don't operate in the group $\mathbb Z_p$ (i.e. $\bmod p$) but instead in the group $\mathbb Z_{\operatorname{ord}(g)}$, where $\operatorname{ord}(g)$ is the smallest non-zero integer $q$ such that $g^q\bmod p=1$. If you are using a safe prime $p$, i.e. a prime $p$ such that $(p-1)/2=q$ is also prime, then $\operatorname{ord}(g)$ can take exactly 4 values: $1,2,q,2q$ (by Lagrange's theorem and the multiplicative order being $p-1$ for a prime).