AES - Encrypting multiple blocks of files On my site, users can download files which are stored on public hosting, so I need to encrypt them. A downloaded file is divided into blocks of 1 kB and I want encrypt them individually, using the same key. I have read that the best option for performing the encryption is AES, but I don't know which mode should I use.

Also, I want also ask, is using similar keys insecure? If that practice is safe, I needn't generate long keys and store them, because all can have same beginning. The main problem is user could find the encrypted files, then they will have the file both before we perform encryption, and afterways; does this raise the possibility of finding the key?

If you don't allow changes, renames and overwrites then you could create an IV by hashing (e.g. with SHA-256) the unique location of the file. If you want to allow changes/renames/rewrites you could re-encrypt with an IV that also uses the time of the change, if that is unique and stored reliably. That is, if you want to keep the size of the files to the one stated. If you are OK with slightly larger files, it is better to prefix a random IV.

Once you've got your randomized IV then you can encrypt with any secure mode. CBC would be an option, or CTR mode encryption. If you always use exact file sizes then you may be able to forgo padding - only do this if 1KB is the maximum size, otherwise perform PKCS#7 padding. You may reuse your key as long as the IV remains unique. In response to the question, yes, this would be protected against known plaintext attacks.

If your keys are similar then you've got a big problem. You should use random keys or use a password based key derivation function (PBKDF) to derive keys from passwords. Even then, you would require quite a strong password, as offline attacks seem possible.


What can I do if I get private key of signing algorithm in Digital signiture I am confused in digital signature. what is use of encryption with private key and decryption with public key. Using public key we can decrypt the signature then what is use of private key privacy. Explain in detail.

When talking about digital signatures, the private key is what proves the authenticity of the signature, precisely because it is private.

The use case proceeds like this: I choose a private and public key pair. Because I chose it, only I know both keys. I then send a message and sign it by using my private key, typically by encrypting a digest, hash, or checksum of the message with the private key, so that it can only be decrypted with the matching public key.

I publish my public key for others to verify my signature with.

The receiver then manually computes the same digest of the message, decrypts the signature I sent along with it using my public key, and compares the two. If they are identical, the only way that is possible is if I am indeed the person who has the private key and published its matching public key. Otherwise, I would not have been able to properly sign the message without my private key.

This works because it is exceedingly difficult to compute the private key from the public key, so much so that it would take a very long time even on a supercomputer.

You might ask at this point, why is the signature an encrypted digest or hash of the message? If the message differs in any way (was tampered with or intercepted, as with a man-in-the-middle attack), the digest won't match whether it's decrypted correctly or not. So tampering with the message necessarily invalidates the signature, because it's a digest of the message itself, proving it's the same message sent by the person who signed it.


Why every access structure is a multipartite access structure? The set of authorized subsets of participants is called an access structure.

In a multipartite access structure,  the set of participants is divided into several parts and all participants in the same part play an equivalent role.

In the 12th line of abstract of this paper,  it is given that every access structure is multipartite,  I am getting confusion regarding this statement. How to understand that every access structure is a multipartite access structure?

From p5 of the paper:

  An $r$-partition $\Omega = \{P_1,\ldots,P_r\}$ of a set $P$ is a
  disjoint family of non-empty subsets of $P$ with $P=P_1 \cup \ldots
 \cup P_r$. ... A family of subsets $\Lambda \subseteq \mathcal{P}(P)$
  is said to be $\Omega$-partite if $\sigma(\Lambda)=\Lambda$ for every
  permutation $\sigma$ such that $\sigma(P_i) = P_i$ for every $P_i \in
 \Omega$.

Thus any access structure $\Lambda$ on $n$ parties is trivially an $n$-partite access structure: take the $n$-partition $\Omega = \{\{1\},\ldots,\{n\}\}$; then for any $\sigma$ fixing all sets in the partition (which is only the identity permutation), it holds that $\sigma(\Lambda) = \Lambda$.  Since $\Omega$ contains $n$ partitioning sets, $\Lambda$ is an $n$-partite access structure.

The abstract also says that Shamir's scheme is unipartite.  This is by taking the partition $\Omega = \{\{1,\ldots,n\}\}$, which is a $1$-partition, since for every permutation fixing all sets in the partition (which is every permutation) it holds that $\sigma(\Lambda) = \Lambda$.  This is because of the symmetry in Shamir's scheme: every party can be swapped with any other party and you still have "all subsets of $\{1,\ldots,n\}$ of size at most $t$".


How much more secure is $c = mg_1^r + g_2(g_1(g_1^r-1)/(g_1-1)) \mod p$ compared to just $c = mg_1^r \mod p$ (dis. log), all known but $r$? To encode a message $m$ to a cipher $c$ you can use the only hard solvable problem of computing the discrete logarithm with a generator $g$ in base over a prime $p$.

$c = mg_1^r$ mod p

If an attacker want to derive $r$ he can use e.g. the Baby-step giant-step algorithm. He can solve this in $\mathcal{O}(\sqrt{p})$.
I'm looking for a way to make it harder to reduce the size of $p$ and still be safe.

Are there any records about solving something like this:

$c = mg_1^r + g_2\frac{g_1(g_1^r-1)}{g_1-1} \mod p$

Or do you know any? Would it (significantly) increase the solve time $\mathcal{O}(\sqrt{p})$?

The potential attacker has the source code and so he knows $g_1, g_2$ and $p$. So if he picks a known $m$ and $r$ he can also compute $c$. In my usage scenario each computed $c$ can be used as $m$ to compute the next $c$. So the main aspect is not to encode a message. I'm looking for a way to make the computation of r as hard as possible for a given $m$ and $c$. That means the attacker has by default a given $m$ and some $c$'s. He should not be able to compute the respective $r$'s which allows him to compute those $c$'s out of the $m$. And if he somehow managed to compute $r$ for a $m$ to get $c$ it should not be easier if $m$ or $c$ changes.

Derivation of formula:

If you use $+$ instead of $*$ operator you can encode like:

$c_1 = m+g_2 \mod p$

$c_2 = m+g_2+g_2\mod p$

so for $c_r$ you can shorten it with multiplication by r

$c_r = m+rg_2\mod p$

But this can easy be solved with computing $g_2^{-1}$ with e.g. eucl. algorithm.

But how about a combination with $*$ operator?

$c_1 = (m+g_2)*g_1\mod p$

$c_2 = ((m+g_2)*g_1+g_2)*g_1 = mg_1^2+g_2g_1^2+g_2g_1\mod p$

$c_3 = mg_1^3+g_2g_1^3+g_2g_1^2+g_2g_1\mod p$

so for $c_r$

$c_r = m*g_1^r + g_2*\sum_{i=1}^r g_1^i \mod p$

$c_R = mg_1^r + g_2\frac{g_1(g_1^r-1)}{g_1-1} \mod p$

If the attacker knows everything (including $m$) except for $r$, he can rewrite it to:

$$g_1^r = (c + g_1 g_2 (g_1 - 1)^{-1}) ( m + g_1 g_2( g_1 - 1)^{-1})^{-1} \pmod{p}$$

He knows everything on the RHS, and so it's a simple discrete log problem.

BTW: for the $\mathbb{Z}_p^*$ group, there are much faster attacks than Baby-step-Giant-step


Security equivalence proofs for breaking RSA It is my understanding that while a practical solution to the factoring problem will definitely break RSA, it has never been proven that the security of RSA is equivalent to factoring.

In otherwords, theoretically, someone could mathematically break RSA without breaking the factoring problem.

Are there any problems for which breaking RSA would be equivalent to (besides the obvious RSA Problem)?

The summary in the Rivest-Kaliski paper does indicate that two specific problems are equivalent to the RSA problem itself.

Due to the algebraic properties of the field $Z_n$, if there exists any small fraction of weak cipher texts (i.e. a particular subset of cipher texts $C$ for which finding the solution $M$ to $C = M^e \pmod N$ is easy), then the RSA Problem is at most as hard as the running time of the adversarial procedure for decrypting the weak cipher texts times a polynomial factor. IOW: The RSA Problem guarantees that all cipher texts are equally hard to invert.
A similar argument applies to each individual bit of a RSA cipher text. If an adversary has a non trivial advantage to determine any bit of a RSA plain text $M$ given a RSA cipher text $C$, then all bits of $M$ are equally easy to determine.


Different inputs but able to generate consistent outputs across different SHA engines Say I'm feeding in few thousand bits data (INPUT AAAA) into both SHA256 & SHA3 256 engines at the same time. (Both engines using different hashing architecture) and hence it will generate different 256-bits of output, lets say SHA256 generate ABCD while SHA3-256 generate EFGH.
I'm curious about if we can try to find the alternative input (INPUT BBBB) later that can generate the same HASH output like above (SHA256 generate ABCD & SHA3 256 generate EFGH).

In short, this will be not be possible, even if we only use one secure hash function rather than two.  You seem to be describing a sort of dual second-preimage attack where we need to find two inputs that clash over two separate hash functions.
A secure hash function will be resistant to such attacks.  As such for either SHA2 & SHA3, it will not be possible to find another input that makes a desired output.
I believe that even SHA1 is only weak in terms of collision resistance.  See here for further details.


Do I need to use a CSPRNG when creating salts for user accounts? I'm not sure about the need of using CSPRNG to create salts for each user account.

I found “Cryptographically Secure Pseudo-Random Number Generator in Qt/C++ (Cross platform)” (at StackOverflow) with some useful information, but I can't fully understand the reasoning behind it.

If an attacker have access to a copy of my users database table containing each salt and the related salted password, I can't understand how a CSPRNG would be more secure than a SHA12 hashed UUID. Can someone elaborate?

Answering your question

If an attacker have access to a copy of my users database table containing each salt and the related salted password, I can't understand how a CSPRNG would be more secure than a SHA12 hashed UUID. Can someone elaborate?

I’m not sure if you only have read the question “Cryptographically Secure Pseudo-Random Number Generator in Qt/C++ (Cross platform)” at StackOverflow, or if you also noticed the accepted answer. The answer practically answers your question here, just like it answered the question at StackOverflow.
Quoting the accepted answer:

If you think you need a cryptographically secure PRNG for generating salts then I must tell you that you do not understand what the salt is and how and why it works and against which kinds of attacks it is useful.
The simple fact that the salt must be stored in plaintext alongside the hash of the salted password should have given away that you do not really need a cryptographically secure PRNG for salt - or any PRNG for that matter. Frankly, you could have a simple 64-bit number, which you increase by one every time you need a new salt and it would be just as secure as a salt generated by a cryptographically secure PRNG.

Even though that answer was posted back in 2012, things haven’t changed and it is still valid.
That is why CodesInChaos already commented correctly…
Quote:

Salts only need uniqueness, so a UUID is fine. A CSPRNG is just the simplest way to generate a salt, not the only one.

and Quote:

If you prefer a UUID that's perfectly fine, though I don't know why you'd want to implement password hashing on the database side instead of the application. In general I recommend using higher level APIs which take care of hashing and salting at the same time. e.g. php's password_hash/password_verify functions.

In the unlikely case you’re still unsure about salts and what exactly the reason for their existence is, I would like to point you to the question “Can you help me understand what a cryptographic “salt” is?“ and its accepted answer, which explains things using different wording. Quoting part of the accepted answer which seems to be the most relevant to your request for elaboration:

A salt is simply added to make a common password uncommon. A salt value is generated at random and can be fairly small, the only purpose is to lower the probability that the hash-value will be found in any pre-calculated table. A common way to combine the salt and the password is to simply concatenate them, i.e. the stored hash value is Hash(salt||password). The common password password1 now magically becomes, e.g., 6$dK,3password1 and is very unlikely to be found in a table.
The salt can be stored completely in the clear in the database, next to the hashed value. Once the attacker has the database and wants to find the passwords, he needs to generate the pre-calculated table for each salt individually, a costly operation.

Besides that Q&A, you might want to search Crypto.SE for Q&As related to “salt” which might help you to fully grasp things related to salts. One of many examples: “Why not encrypt salt?”
Diving into your comments

I'm asking because I disagree it is the simplest. MySQL, for example, doesn't have a native CSPRNG.

Then you could use a simple incrementing integer, or anything else that would produce a UNIQUE salt. (Please note the word “unique” has been capitalized as a hint, not to represent frowned-upon “online shouting”.)

There are several reasons. First, database servers are way more secure than web servers. They are, most of the time, only accessible through the application.

First off, I have to disagree with your database servers are way more secure than web servers because that is not really the case. But let’s assume that to be correct (as it is not relevant to your question anyway).
You have to remember that your salt only needs to be unique, not secret. It isn’t there as “a secret to secure data”. A salt is merely used to make things like passwords unique – slowing attackers down in situations where they might want to use things like hash-tables.

Second, if your application is stolen, having the salt logic on it gives the attacker an edge.

That argument isn’t really relevant in your scenario as the attacker would still have to “guess” the passwords – which are the real secrets (in contrast to the salts, better: the salting function within your application). That edge you see is rather minimal… and if you use a separate database server anyway, your attacker would be looking at a function within your application that can produce salts… but he/she would still have no copy of the database(s) to do anything useful with his/her ability to replicate the salts your application uses. For that, they would need to also steal the database.

Third, I use salt in the database and pepper in the application, this way the attacker needs to stole both the application and the database.

Great. Now all you need to do is to understand that a salt is not a secret. If an attacker knows the salt because – for example – he/she stole a copy of your database and can look it up quick and easy, that attacker would still need to brute-force the hashed passwords. Only when using a hash that is known to be cryptographically insecure, you would have given the attacker some kind of edge. But if you used something sane and cryptographically secure (like – for example – SHA256, HMAC256, or bcrypt), such an attacker will still be facing a loooong and painful brute-forcing attempt.
Knowing how to recreate salts will not magically make brute-forcing password hashes easy. That is, unless you use a cryptographically insecure password hashing method (like plain MD2 or MD5). Therefore, I tend to recommend that – instead of trying to secure non-secrets like salts – you rather focus on how you hash the real secrets… the passwords. See, I mentioned SHA256 above as a cryptographically secure hashing function, but it’s not the most optimal way to hash secrets like passwords. In fact, things like SHA256, HMAC256, or SHA512 (which you mentioned in relation to creating salts) are not meant to be used as password hashing functions and should - as a logic consequence - not be used for that purpose (not saying you should avoid them when creating unique salts). That‘s why I also mentioned bcrypt – which is one of many dedicated password hashing functions out there and definitely more recommendable when it comes to hashing passwords. Other good password hashing functions besides bcrypt would be scrypt, PBKDF2, or Argon2. No salt and/or pepper on this planet will save you when you mess up the password hashing part, but even the worst salt won’t be able to cause much damage if you implement the rest of your password hashing correct.
TL;DR
Salts are not secrets. They do not have to remain secret; they only need to be unique.
Non-secrets like salts (and peppers) can be stored “in the open”; in your case: as plaintext, integer value, or binary blob in your database. Both your application as well as your database can contain the functionality for creating unique salts.
Instead of trying to “secure” salts, it’s more important to focus on how you hash the passwords. Use a dedicated password hashing function to do so.


Is this key management scheme secure? I'm designing a scheme for management of a small number of cryptographic keys (< 100 at any given time) and I had an idea: rather than storing all the keys, could I just store one master key and use a KDF to derive the particular key I need by varying the salt in a certain way?

For example, if I need the second encryption key for usage X, I'd give something like PBKDF a salt of

$$2||“encryption”||X||<random value>$$

which would uniquely derive the second version of that particular key.

You should not use a Password Based Key Derivation Function (PBKDF) for this. Instead you need a Key Based Key Derivation Function (KBKDF). You could use for instance NIST SP 800-108 (PDF) or HKDF. Both specify means for key derivation using some kind of context which is used as input for the KDF (e.g. a label or sequence number).

A salt is used in a similar fashion in PBKDF, but a salt has a different purpose than context data. Furthermore, it is not that likely that you need key strengthening which is delivered by the salt and iteration count commonly used in PBKDF's. If your master key is strong enough, then the derived keys should be safe without additional measures. PBKDF's are deliberately slow, KBKDF's aren't.

Note that KDF implementations may not be that widespread. They are however relatively easy to compose using the MAC or HMAC primitives that supply the necessary PRF functionality. If you go that way, don't forget to test against the available test vectors though.

If you go for the NIST defined KBKDF's I would advice for a counter mode KDF based on either HMAC using SHA-256 or AES-CMAC as they are easiest to implement and seem to be the most common implementations in the field.

[EDIT] When using HKDF it is advisable use use a Salt value even if your input key material (the master key) provides a lot of entropy. It is however not required for this use case. Neither do you have to use the extract function of HKDF, but normally you would want to perform it anyway for the sake of compatibility. Basically: only skip the Salt and extract function if you have strong resource constraints.


Checking both Quadratic residuosity and Jacobi symbol simultaneously and efficiently I have to randomly generate a number $u$ such that $u \in J(N)-Q(N)$

where $J(N)$ denotes the set of elements less than $N$, whose Jacobi symbol value is equal to 1; and $Q(N)$ denotes the set of quadratic residues in $J(N)$ .

What is the best time-efficient way to generate it ?

I am thinking to generate like this:

1) Select an  positive integer $x$such that $(x+1)^2 \le {N}$.

2) Select any integer $y$ between $x^2 $ and $(x+1)^2 $ then check for $\big{(}\frac{y}{N}\big{)}=1$ and continue until we get .

The above method is not correct and counter example is provided in comments below .

Is it good and correct one ?

Given a composite $N$, it is asked to construct a random $u$ in $\mathbb Z_N^*$ with $\big({u\over N}\big)=+1$ that is not a square $\pmod N$.

The method proposed in the question does not work. Counterexample: $N=77$; $x=7$; $y=53$ which is such that $x^2<y<(x+1)^2\le N$ and $\big({y\over N}\big)=+1$. However $y$ is a quadratic residue since $53\equiv19^2\pmod {77}$. Problem is, it is asked that $y$ is not a square $\pmod N$, but the construction method proposed in the question only insures that $y$ is not a square in $\mathbb N$.

Here is a method that works assuming we know just one fixed $s$ in $\mathbb Z_n^*$ with $\big({s\over N}\big)=+1$ that is not a square $\pmod N$:

generate a random $x\in\{1\dots N-1\}$, until $\gcd(x,N)=1$;
compute and output $u=s\cdot x^2\bmod N$.

Using multiplicative properties of the Jacobi symbol, that $\big({s\over N}\big)=+1$ and $\big({x\over N}\big)\ne 0$, it follows from the construction of $u$ that $\big({u\over N}\big)=+1$. And because $x^2\bmod N$ is a non-zero quadratic residue, and $s$ is a non-zero non-quadratic residue, their product $u\pmod N$ is a  non-zero non-quadratic residue. $u$ is random-like because $x$ is random. I conjecture (without proof) that $u$ is uniform on the desired set; that would follow from proof that each distinct $x^2\bmod N$ with $\gcd(x,N)=1$ has an equal number of square roots $\pmod N$.

It remains to construct $s$. That seems impossible in the general case without knowing the factorization of $N$; however, in some practical cases, $N$ could be generated so that its factorization is known but secret, which allows to efficiently generate $s$; then $(N,s)$ can be made public and the factorization of $N$ forgotten.

Here is how the generation of $(N,s)$ could go:

generate two large random distinct primes $p$ and $q$;
compute $N=p\cdot q$;
generate a random $s\in\{1\dots N-1\}$ until $\big({s\over p}\big)=-1$ and $\big({s\over q}\big)=-1$;
output $(N,s)$.

Using multiplicative properties of the Jacobi symbol, $\big({s\over N}\big)=+1$. Because $\big({s\over p}\big)=-1$ and $p$ is prime, $s$ is not a quadratic residue $\pmod p$; thus $s$ is not a quadratic residue $\mod{p\cdot q}$.

Update following Poncho's answer: if $N=p\cdot q$ with $p$ and $q$ primes such that $p\equiv3\pmod4$ and $q\equiv3\pmod4$, then $s=N-1$ does the job.


How does Schnorr signature actually work? I'm trying to get a grip on how Schnorr signature works. Suppose Alice sends Trent a tuple $(P, M)$, which contains a payload and a message to be signed by him. She then passes the certificate to Bob who verifies it.

Using Wikipedia's description (http://en.wikipedia.org/wiki/Schnorr_signature), is Alice supposed to compute $r = g^k$ and then passes it to Trent who then computes $e = H(M \| r)$ and $s = (k - xe)$? If that's how it works, then isn't Alice supposed to transform what she receives rather than passing $(s, e)$ straight to Bob? Bob could take $(s, e)$ to Trent and find out about Alice's payload.

Thanks

Signatures do not keep the message secret.

Verification in Schnorr is by recovering $r=g^s*y^c \textrm{ mod } p$ and then checking that $c$ depends on $r$ in the right way; i.e., $c=H(r||M)$.

Efficiently generating an $s$, $c$ pair requires knowing the private key, so that raising to $s$ can cancel the $g^x$.


Need help understanding math behind Rijndael S-Box in Rijndael SubBytes() step all bytes of input block are substituted based on a lookup table S-Box. S-Box is initialized by taking all elements of $GF(2^8)$, calculating their multiplicative inverse and then calculating their affine transform.
Here is C code which does that as found on wikipedia page.
#include <stdint.h>

#define ROTL8(x,shift) ((uint8_t) ((x) << (shift)) | ((x) >> (8 - (shift))))

void initialize_aes_sbox(uint8_t sbox[256]) {
    uint8_t p = 1, q = 1;

    /* loop invariant: p * q == 1 in the Galois field */
    do {
        /* multiply p by 3 */
        p = p ^ (p << 1) ^ (p & 0x80 ? 0x1B : 0);

        /* divide q by 3 (equals multiplication by 0xf6) */
        q ^= q << 1;
        q ^= q << 2;
        q ^= q << 4;
        q ^= q & 0x80 ? 0x09 : 0;

        /* compute the affine transformation */
        uint8_t xformed = q ^ ROTL8(q, 1) ^ ROTL8(q, 2) ^ ROTL8(q, 3) ^ ROTL8(q, 4);

        sbox[p] = xformed ^ 0x63;
    } while (p != 1);

    /* 0 is a special case since it has no inverse */
    sbox[0] = 0x63;
}

I cant wrap my head around how multiplicative inverse is being calculated here. I assume p here acts as input while q is its inverse. Hence $p*q = 1$.
I want to understand how exactly this works because I am trying to implement a function that initializes Rijndael inverse S-Box, where first the inverse affine transform is calculated and then the multiplicative inverse.

The code is using the fact that the Rijndael's* Galois field has the following generators†:

3 5 6 9 11 14 17 18 19 20 23 24 25 26 28 30 31 33 34 35 39 40 42 44 48 49 60 62 63 65 69 70 71 72 73 75 76 78 79 82 84 86 87 88 89 90 91 95 100 101 104 105 109 110 112 113 118 119 121 122 123 126 129 132 134 135 136 138 142 143 144 147 149 150 152 153 155 157 160 164 165 166 167 169 170 172 173 178 180 183 184 185 186 190 191 192 193 196 200 201 206 207 208 214 215 218 220 221 222 226 227 229 230 231 233 234 235 238 240 241 244 245 246 248 251 253 254 255

A multiplicative generator $g$ means that $\langle g \rangle$ generates all of the element of $\operatorname{GF}(2^8) \text{ - } \{0\}$ or equivalently, $\mathbb{F}_{2^8}^*$. More formally, they form the cyclic multiplicative group of the finite field. The zero case handled at the end.
The choice of 3 in the code
/* multiply p by 3 */
p = p ^ (p << 1) ^ (p & 0x80 ? 0x1B : 0);

is simply due to the optimization that 3 enables the smallest calculations to generate all of the elements. The 3 is actually a numerical expression of $x+1 \in \operatorname{GF}(2^8)$ in polynomial representation. Therefore, the above code is the multiplication of the current $p$ with $x+1$ as p ^ (p << 1). The ^ (p & 0x80 ? 0x1B : 0) part is the reduction with the primitive polynomial of the field by the equality $x^8 = x^4 + x^3 + x + 1$, in hex 0x1B where $x^8 + x^4 + x^3 + x + 1$ is the irreducable AES polynomial to that used to extend $\operatorname{GF}(2)$ to $\operatorname{GF}(2^8)$
The code is also using the fact that ;
$$1 = pq=pq \cdot 3 \cdot 3^{−1}=3p \cdot 3^{−1}q=1$$ now call $p′=3p$ and $q′ = 3^{−1}q$ and get $p′q′=1$. In this way, $p$ and $q$ get all valus of the table - expect 0 - since 3 is a generator. Then, by using the $q$, the affine transformation is computed for the table.
What is the advantage here?

No need to find the inverse by using the Ext-GCD or its better versions.
No multiplication is used for generating the elements.

* Rijndael $\neq$ AES (Actually, Rijndael $\supseteq$ AES). Rijndael is an AES candidate that won the competition and standardized as AES. The Rijndael is designed for  128, 192, or 256  key and block sizes. The AES has fixed block size 128 and have the  128, 192, or 256 bits key sizes.
† SageMath code to find all of those generators. Need sorting.
R.<x> = PolynomialRing(GF(2), 'x')
S.<y> = GF(2^8, modulus=x^8+x^4+x^3+x+1, repr='int')

for i,x in enumerate(S):
    if x == 0:
        continue
    if x.multiplicative_order() == 255:
        print("{} {}".format(i, x))


AES MDS matrix: can we maintain security if we change the arrangement of elements in the matrix? Apologies for 'unclear' question. And, 'yes' it is similar to an earlier one. I hope this is clearer.

AES uses the matrix below for the mix columns:

Would security be affected if the columns (or rows) were swapped around?
For example, if the first and second column were swapped to give:

Would this matrix be just as secure for the mix columns?

An $n\times n$ circulant matrix $A$ with all entries nonzero is known to generate an MDS matrix. Here $n$ is 4, with alphabet $GF(2^8).$

An MDS matrix guarantees maximum diffusion in the MixColumns step. See the answer to the following question how-to-calculate-active-s-boxes-from-branch-number on why the fact that the minimum (symbol) Hamming weight achieving the maximum possible value of $n+1$ is important.

As pointed out by @Amin235 the new matrix you obtain is still MDS, but not being circulant, you've sacrificed computational speed. Since all MDS codes have the same weight distribution, not only the minimum possible diffusion, but all diffusion properties for all input/output vectors are identical between your new matrix and the original AES MDS matrix.


What exactly could be accomplished with a backdoor in Dual_EC_DRBG? Assume that some entity really holds the private key corresponding to the recommended/dubious constants of Dual_EC_DRBG.

According to this presentation, they would be able to reconstruct the internal state from only 32 bytes of random output and thereby predict all future output as well.

Would the backdoor also allow recovering previous output of the RNG, or does the
resistance against state compromise extensions still hold in that situation?

State update takes $s$ to $x(sP)$, so you would have to compute d.log.s to run the state backwards.


Relationship among secrecy-constant, key space and message space Here scheme $\Pi$ is $\epsilon $ -
perfectly secret.
Given that encryption scheme $\Pi$ =  $(\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ over $(\mathcal K,\mathcal M,\mathcal C)$ is called $\epsilon $ -
perfectly secret if for any distribution over $\mathcal M$, any $m \in  M $ and any $ c \in C$,
$|Pr[M=m|C=c] - Pr[M=m]|<\epsilon$
then how to prove that ,
$|\mathcal K|\geq (1 - \epsilon)|\mathcal M|$
I am not getting idea how to proceed as here $\epsilon$ can be anything i.e non-negligible or negligible both.

HINT: here you can prove the above thing by contradiction. Start with the reverse of what needs to be proved and see you can arrive at contradiction or not. Treat $\epsilon$ as a parameter any, by the way, you are right it can be anything negligible or non-negligible.


To what extent is WhatsApp's statement on secure messaging realistic? As those of you who use WhatsApp Messenger probably know, with their recent update chats and calls are now encrypted. Here's what WhatsApp claims:

  Messages you send to this chat and calls are now secured with
  end-to-end encryption, which means WhatsApp and third parties can't
  read or listen to them.

Now let's put aside how WhatsApp is honest but what they claim is a technological feature. Is it really not possible for them to read or listen to our messages? If that's a lie, then  don't they risk that some guys like you might say "Hey, what the hell are you talking about? Why do you lie?". So my question is, if they are the ones who encrypt this, then why can't they also decrypt it?

So my question is, if they are the ones who encrypt this, then why can't they also decrypt it?

Because it’s not them encrypting your message, it’s the App on your device… which is why it’s called End-To-End encryption.

According to the security whitepaper (PDF), WhatsApp uses the Noise Protocol Framework which is based on the Signal protocol (formerly known as “Axolotl”). The Signal protocol has been designed by Open Whisper Systems (names like “Zooko” might ring a bell) and  uses strong and well-vetted cryptographic approaches like ECDH using Curve25519. Besides that, WhatsApp additionally encrypts all communications between client and server via – so called – Noise Pipes (see Noise Protocol Framework for more information on that).

Skipping the details to keep it short, it seems as if WhatsApp did its homework and chose a well-vetted approach to provide encryption et al.

But there’s that little thing with WhatsApp that indeed represents a bit of a problem when looking at it from an InfoSec and/or cryptographic point of view: WhatsApp was, is, and remains closed source up until today. Practically, this means that you can’t really review the actual sourcecode and classify WhatsApp security based on that. So, you can’t really tell how much security it practically might (or might not) offer.

If you’ve ever looked at (or used) Signal as a messaging app, you’ll notice WhatsApp and Signal work in similar ways (read: usage-flow is very alike) which hints at the fact that WhatsApp has indeed implemented what it is saying. Yet, in contrast to Signal (which is open source) you can’t tell if WhatsApp has indeed implemented things correctly and without (let’s just call it) bugs in the code, which might or might not provide room for attack vectors.

All in all, your question uses the correct term: “claim”. That’s all it is and all you can trust in. A “claim” isn’t called “proof” for a good reason… in this case, you can not verify WhatsApp security claims by looking at WhatsApp sourcecode – as that’s unavailable to the public. All you have is their words (aka publications like the security whitepaper) and the fact that close-source WhatsApp somewhat feels like the open-source Signal app. In the realms of cryptography, small errors can (and will) break your neck – which is why I personally prefer to keep using Signal instead of switching to WhatsApp. OTOH, I’m weird… and there’s no real reason to suspect WhatsApp would even think about risking their business by publishing claims they can’t hold. Yet, they don’t provide much reason to trust them either. As Tylo commented correctly: it could all just be propaganda (aka marketing). In the end, it is a company with commercial interests and a close-source product… that somewhat renders “trust” into a “personal opinion” thing.

TL;DR

So, if your question boils down to “Is WhatsApp secure?” I would tend to say “According to their whitepaper, it should be”. If your question boils down to: “Can you prove it?” I’ld have to disappoint with a “No, as proof expects the ability to verify, which we can’t.” And if you want to know the details of “how WhatsApp handles End-To-End encryption and authentication”, check the security whitepaper and the Noise Protocol Framework links at the top of my answer. That should answer all those little cryptographic nit-bits (which are a bit too broad to mention here).


Is there any Private Set Intersection scheme that only leak whether intersect or not without the real intersection value? If there are two people Alice and Bob, and each has one set. They want to know whether their sets have intersect or not.
Is there any Private Set Intersection scheme that only leak whether intersect or not without the real intersection value?
Thank you!

What you are asking for is also known as a test for disjointness of private datasets.

Kiayias, who introduced this problem in 2005, called a protocol solution the Private Intersection Predicate Evaluation (PIPE) protocol.

Reference:
Kiayias, Aggelos, and Antonina Mitrofanova. "Testing disjointness of private datasets." In International Conference on Financial Cryptography and Data Security, pp. 109-124. Springer, Berlin, Heidelberg, 2005

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.61.7661&rep=rep1&type=pdf


How to communicate authentication tag for GCM? I have written some code to do AES in GCM. I currently manually append the tag property to the ciphertext, is this the proper way to communicate the authentication tag?

I currently manually append the "tag" property to the ciphertext, is this the correct method of authentication?

That is a perfectly acceptable method. In the end, there needs to be some protocol which tells the other party where the ciphertext is and where the authentication tag is. In your case, the other party knows that the last 128 bits of the message contains the authentication tag.


Does AES-ECB with random padding added to each block satisfy IND-CPA? I present a modified version of AES-ECB. Suppose I want to encrypt the string hello, world. this is a test. For each block, I use the first eight bytes as my actual message, while the second eight bytes are random. For the last block, I'll pad my first eight bytes deterministically. So my four blocks are (I'll use * to denote random bytes, and $ to denote deterministic padding):

hello, w********
orld. th********
is is a ********
test$$$$********

Then I encrypt each block with AES to obtain my cipher text.

I know that this encryption scheme is still malleable. Is it still distinguishable under chosen plaintext?

First, I would not call this AES-ECB, since adding randomness means that it is not ECB. Second, when limiting the message space to what fits into one block, asymptotically -- meaning for a pseudorandom permutation with block size $n$ -- this construction is actually even CCA-secure (and so non-malleable, since indistinguishability and non-malleability are equivalent under CCA attacks). This is actually Exercise 4.2.5 in Introduction to Modern Cryptography, 2nd edition. (When using multiple blocks as in the question, it would be CPA-secure and certainly malleable.)

I just want to note (with respect to @poncho's answer) that this is asymptotically secure. This means that when considering a pseudorandom permutation with block size $n$, no adversary running in time polynomial in $n$ can succeed with probability that is more than negligible in $n$. In practice, with a 128-bit block cipher, this construction will give very poor bounds. However, $2^{32}$ is really here $2^{n/4}$ which is super-polynomial. Thus, there is no contradiction.

In conclusion, this isn't a great idea in practice (unless you have a very large block cipher). However, it works in theory.


Understanding Unique-SVP and Kannan's Embedding I am trying to understand the Kannan embedding technique. But I am confused about the formation of the B' and the finding of the short vector inside that basis. How does this basis matrix in the algorithm produce a lattice? Or more specifically why a uSVP instance consist of a vector(e^T) and an integer(M)?
Thanks.

The columns of matrix $B'$ generate a lattice $\Lambda'=\{\mathbf v'\in\mathbb Z^{n+1}\}$ where the first $n$ entries form a vector which differs from a vector of $\Lambda$ by some multiple of $\mathbf e$ and the last entry is the same multiple of $M$. We also need some guarantee that $\mathbf e$ is shorter than the shortest vector of $\Lambda$ by some amount and that $\mathbf {As}$ is the closest vector to $\mathbf b$.
$M$ is not necessarily an integer, but is some value such that e.g. $M=||\mathbf e||$ when we know $||\mathbf e||<\lambda_1/2$ where $\lambda_1$ is the length of the shortest vector of $\Lambda$. It follows that the vector $(\mathbf e, M)^T$ has length at most $\sqrt 2M<\lambda_1/\sqrt 2$. This is shorter than any vector of the form $(\mathbf x, 0)^T$ which corresponds to a vector $\mathbf x$ of $\Lambda$ and so is of length at least $\lambda_1$. It is shorter than any other vector of the form $(\mathbf y, M)^T$ by the definition of the closest vector. It is also short than any vector of the form $(\mathbf z, kM)^T$ for any $|k|\ge 2$ as such a vector has length at least $|k|M>\sqrt 2 M$ based on the final component. It follows that $(\mathbf e, M)$ is the unique shortest vector of $\Lambda'$.


Are there any strong manual ciphers? Are there any strong manual (i.e. performed only by pen and paper) ciphers for practical use?

It should be:

no less strong than modern cryptography algorithms used in computers,
at least relatively fast/easy to encrypt/decrypt with just a pen and paper (say, no more than 10 minutes per character),
key should be memorable (i.e. it shouldn't be a 256 random character string, because it's nearly impossible for an ordinary human to memorize it and remember for a long time).
not necessary, but if possible, it should be quantum resistant.

I believe that latest progress in mathematics and cryptography made all this possible, but we are just unaware of it, as it stands in the "shadow" of easily accessible and powerful computer cryptography. So, cryptography experts, please enlighten us, lay people.

You may have a look at the Schneier's blog https://www.schneier.com/blog/archives/2018/05/lc4_another_pen.html

There are two ciphers described (LC4 and Solitaire).

I am not sure a  card-pack based cipher would fulfill #4, but imho still having good strength for a field hand-only cipher

edit: now I noticed Maarten linked the Solitaire cipher too,


Modes for encrypting small binary blobs? Suppose I am building an encrypted document storage system.  Suppose each user has a "user key": a symmetric key.  Suppose each document is encrypted with a "document key".  So, in order to give a user access to a document, we store a tuple of (user_id, document_id, encrypted_doc_key) where the encrypted document key is encrypted using the user key.  In this case, is there an appreciable difference in encryption modes?

The plaintext would be 1-2 blocks long, and random.  Every time data is encrypted or decrypted, the entire thing is needed, so the ability to decrypt arbitrary blocks is not necessary.  Even ECB seems like it should be relatively secure here, but I'm thinking using something with a random IV would be a better option.  Given that the data being decrypted (the wrapped keys) shouldn't be able to be modified by an attacker, I'm not as concerned about authentication.

Is there an existing protocol that does something like this?

You can use a key wrap scheme.  Frankly, any authenticated encryption mode would probably be fine, but a key wrap scheme is designed for exactly this purpose: encrypting one key under another key.  So, you might as well use one of the accepted key wrap schemes.


Uniform vs discrete Gaussian sampling in Ring learning with errors The Wikipedia article on RLWE mentions two methods of sampling "small" polynomials namely uniform sampling and discrete Gaussian sampling. Uniform sampling is clearly the simplest, involving simply uniformly selecting the coefficients from the set of small coefficients, thereby guaranteeing they will be small. However, the articles mention that security proofs rely on discrete Gaussian sampling.

However, I have a bit of difficulty wrapping my head around

Why discrete Gaussian sampling would be better than uniform, security-wise?

I mean, usually uniform is preferable - it maximizes the entropy/information in each sample, making the outcome more unpredictable. I could understand it if the Gaussian sampling technique would somehow serve to avoid (at least with high probability) "weak" parts of the space of outcomes but I have found no information/justification that this is the case.

Another reason I can see why discrete Gaussian might be better is that there is, after all, a chance (albeit a small one) one would select a non-small coefficient, so the space of outcomes is actually larger. However, given that this probability of hitting this extra space is (by design) quite small but also that one would likely immediately reject such a sample (because the algorithm calls for a small polynomial), this seems to be irrelevant.

It is not because I am against discrete Gaussian sampling I just want to understand why it is more secure. Also, I want to understand if it really IS more secure or it is simply easier to prove security in that model. I would actually consider that very interesting if it is the case because it raises the question of why is it easier to prove the security under conditions that are intuitively worse (i.e. discrete Gaussian vs the intuitively better uniform case)? If it is so intuitively clear that uniform sampling is better, surely it must be possible to transform that intuition into a security proof of RWE also under uniform sampling. Otherwise, I would fear the intuition must with high likelihood be wrong or at least dubious.

The TL;DR:

From a theoretic point of view, Gaussians are the better choice, both for the easiness of the security proof and its optimality in terms of tightness;
In practice, most of the time you can replace Gaussians by other distributions without too much trouble.

Theory

First, let me elaborate on a few reasons why Gaussians are better in theory:

When you use an error distribution in LBC, your distribution impacts the scheme in two conflicting ways:

Correctness: if the standard deviation of the error distribution is too large, then the correctness of the scheme is not ensured anymore. For example, in the key exchange in your Wikipedia link, if we set the error distribution to be uniform over R_q then the two parties effectively send each other random noise and thus it is impossible for them to agree on a common key with this protocol.
Entropy: the entropy of random distributions often play an important role in proving the security of a scheme. This is of course not restricted to lattice-based schemes, but since they are the topic at hand we can for example consider the leftover hash lemma (see this SE post: Relation between decisional SIS and leftover hash lemma in lattices). The SE post considers the error distribution to be over $ \{0,1\}^m$, you can use other distributions as well, but you need them to have sufficient entropy.

So you are faced with two somewhat conflicting conditions: you need a small standard deviation to ensure correctness, but you require sufficient entropy for the security proof to go through. As it turns out, for a fixed mean and standard deviation, the entropy is maximized for Gaussians. Which is why they look like the best compromise between these conditions.
While it is not exactly easy to work with Gaussians, they have a few "magical" properties which are handy when doing security proofs: for example, the sum of two Gaussians is a Gaussian. We can't say the same for uniform distributions (of restricted support).

Practice

Generating Gaussian distributions in a fast and secure (against side-channel attacks) way has proven to be difficult, and some methods for doing so have been subjected to devastating side-channel attacks. In addition it can be tedious, so many schemes (but not all) have tried to ditch full-fledged Gaussians without compromising security. For example:

Approximated Gaussians (using a table and 16 bits of randomness per coefficient sampled) have been considered. See FrodoKEM.
A popular choice is to rely on centered binomial distributions: they "look like Gaussians", but they can be sampled efficiently and securely (a binomial distribution is a sum of uniform samples in [0,1]). See NewHope and Kyber.
I have no knowledge of the uniform distribution being used in key exchange, but it is popular in Fiat-Shamir signature schemes which use variants of LWE (see qTESLA, Dilithium).

Funnily, you can even ditch the error distribution entirely and use truncation instead; of course now you no longer rely on the LWE hypothesis but on LWR (Learning with Rounding). This is what Saber does.


What's different between ground setting and ring set in the Enigma machine? I am writing a python program for the Enigma machine. I know what the ground setting (Grundstellung) is but I don't know the difference between ground setting and ring setting.

What's different between ground setting and ring set in the Enigma machine?

Terms
As stated on Wikipedia:

Ring settings (Ringstellung) – the position of each alphabet ring relative to its rotor wiring.
Starting position of the rotors (Grundstellung) – chosen by the operator, should be different for each message.

Functions
The ring setting changes the output letter of a rotor. A rotor has a fixed permutation installed (by the wiring) as seen here, i.e. one rotor would encrypt the letter A to the letter G. After one encryption the rotor would turn and the next wiring comes into effect and the new encryption of the letter A would now be encrypted to the letter C.
With the ring setting you could additionally change this fixed permutation of the rotor, i.e. with a ring setting of B (a.k.a. 02) it would change the output of the rotor. It functions like a caesar cipher. Using the example above with the ring setting of B would change the letter A to the letter H (because B is mapped to A (difference of 1) H is mapped to G).


While doing the affine mapping after calculating the inverse of my polynomial using the EEA, I am not getting the value of the inverse as it should be This is the image of matrix multiplication. It is the affine mapping step in the s box layer of AES. My value is not what it should be, therefore I just wanted it to be confirmed by someone else.

I'm getting $(11001000)$ as answer while it should be $(10000011)$; the value of my input is $(11111110)$.


Is creating an authentication-key (mac) from the encryption password a vulnerability? I can think of at least one problem with it - that testing for a correct key (when brute forcing) is simpler with a mac key (at least for short messages) and therefore can help brute force decryption.

It is possible to create both an encryption key and authentication key from a password securely.

It is very likely that an attacker knows part of the plaintext most of the time. That makes it very possible to verify correct guesses of the password, even without verifying an authentication tag (MAC). This is especially true if there are multiple messages to test.

So although it is perfectly possible to verify a MAC key over purely random messages and impossible to do the same for encryption keys, the addition of a MAC should not make much of a difference for structured messages.

For passwords brute forcing can certainly be used, but slightly more advanced techniques such as dictionary attacks may also be used. Usually some form of key strengthening is used to derive master key material. That master key material can then be used to derive an encryption and MAC key.

These keys can be made cryptographically independent from each other. But that doesn't matter much since finding the password is the easiest form of attack and finding the password will of course allow an attacker to calculate both keys.


Is the inverse of a secure PRP, also a secure PRP? If a block cipher is a secure PRP, is it's inverse a secure PRP as well?  My intuition says yes but I'm not exactly sure.

On a related note, if a block cipher is a secure sPRP, is it's inverse a secure sPRP?

I'm using the terminology "PRP = secure against chosen-plaintext attacks", "sPRP = strong PRP = secure against chosen-plaintext/ciphertext attacks", where "secure = indistinguishable from a random permutation".

In theory. No.  The inverse of a secure PRP need not be a secure PRP.

Here is what we can guarantee.  The inverse of a secure sPRP (strong-pseudo random permutation) is guaranteed to be a secure sPRP.  Any secure sPRP is a secure PRP.  Therefore, the inverse of a secure sPRP will be a secure PRP.

FYI, if you are not familiar with PRP/sPRP, the difference between PRP and sPRP is:

a PRP is secure against adaptive chosen-plaintext attacks
a sPRP is secure against adaptive chosen-plaintext/ciphertext attacks

Caution: I've just learned that apparently this terminology is not 100% standard, and some people use different terminology (e.g., weak PRP / PRP or PRP-CPA / PRP-CCA instead of PRP / sPRP).  So, beware, and make sure to translate my statements accordingly if you prefer the other terminology.  I realize this could affect the meaning of your question.

In practice. In practice, when we make statements like "AES is secure", we usually mean that "AES is a secure sPRP".  Sometimes you might see people being sloppy about the distinction between PRP and sPRP, but any modern block cipher that is not broken can usually be assumed to be a secure sPRP.  Therefore, the inverse of any modern block cipher (like AES) will also be a secure PRP.

Proof. For the crypto-purists, here is a proof of the statement that the inverse of a secure PRP need not be a secure PRP.

Define $E_k$ as follows:

$$E_k(x) = \begin{cases}
0 &\text{if $x=k$}\\
\text{AES}_k(k) &\text{if $x=\text{AES}_k^{-1}(0)$}\\
\text{AES}_k(x) &\text{otherwise.}
\end{cases}$$

It is easy to check that $E_k(\cdot)$ is a permutation for each $k$.

It is also straightforward to prove that $E$ is a secure PRP (making plausible assumptions about AES, e.g., that it can be modelled as an ideal cipher).  Why?  Because $E_k(\cdot)$ agrees with $\text{AES}_k(\cdot)$ on all but two input values, and the adversary has no clue what those input values are.  The best the adversary can do is hope to hit one of those two inputs by chance.  The probability that the adversary happens to hit one of those two values by chance is miniscule: after 1 query, the probability is $2/2^{128}$, and after $q$ queries, the probability is $\le 2q/2^{128}$.  If $q$ is bounded by any reasonable value (say $q \le 2^{64}$), this probability is negligible.

It is also easy to prove that $E^{-1}$, the inverse of $E$, is not a secure PRP.  All you have to do is query the inverse on the plaintext $0$, and you get back the key (since our definition of $E$ has ensured that $E^{-1}_k(0)=k$).  So, a single chosen-plaintext query completely breaks $E^{-1}$.

This proves that there exists a cipher that is a PRP but whose inverse is not a PRP, or in other words, that the inverse of a PRP is not necessarily guaranteed to be a PRP.


Breaking variations of Linear Congruential Generators So I have been trying to learn a bit of cryptanalysis and breaking pseudorandom generators as of recently, but I have run into a roadblock in my learning as I cannot crack this one problem.  Basically it is a variation on an LCG, but I cannot figure out how to solve it, even though I am pretty certain it is weak, I just lack the understanding of what technique to try.

The generator is from the random number generator used by TI calculators as found here.

Basically it goes as follows:

$$\begin{align}
s_1&\gets s_1\cdot a_1\bmod m_1\\
s_2&\gets s_2\cdot a_2\bmod m_2\\
r&\gets (s_1-s_2)/m_1\\
\text{if }&r<0\text{ then }r\gets r+1
\end{align}
$$
[Notes of the editor: That generator is equivalent to the one of figure 3 in Pierre l’Écuyer's Combined Multiple Recursive Random Number Generators, CACM Volume 31 Issue 6, June 1988, p. 742-751. The moduli $m_i$ are primes slightly below $2^{31}$ with $\gcd(m_1-1,m_2-1)=2$ and $m_1$ slightly larger than $m_2$. The $a_i$ are even constants somewhat below $\sqrt{m_i}$, giving maximal period and said to give good results for the spectral test of the multiplicative LCGs. Variable $r$ is floating-point. In l’Écuyer's paper, we have $r=((s_1-s_2)\bmod m_1)\cdot(\widetilde{1/m_1})$ where $\widetilde{1/m_1}$ is a close floating-point approximation by default of $1/m_1$, and $v=u\bmod m$ means that $0\le v<m$ and $m$ divides $u-v$. ]

This small variation has stifled my attempts (which have been off and on for a few months).  If anyone has an explanation of how to get the next number from only the results I would love to know, or even if you could point me in the right direction it would be greatly appreciated.
Thanks!!!

P.S.: I hope this is in the right category, I am new to this website and have also searched through the similar questions and couldn't find any that would help me out here.

This generator has a state defined by $s_1$ and $s_2$, and can take just below $2^{62}$ states. This can't be cryptographically secure by today's standards, which call for more than 80-bit security, but is still quite too much for fast cryptanalysis by pure brute force using a single CPU. We need at least one serious speedup.

The most obvious is: enumerate the (less than $2^{31}$) states $s_1$, and for each deduce $s_2$ from one output (giving us $(s_1-s_2)\bmod m_1$ ) and $s_1$ (or, in rare case, that $s_1$ can't have that value); then check these $s_1$ and $s_2$ with a few more outputs.

The devil is in the details, and in particular the error we have on $(s_1-s_2)\bmod m_1$ as reverse-computed from actual output. If $r$ is given with 6 decimal figures on the right of the decimal point, we only get about 20 out of 31 bits (but if $r$ is given with 6 significant digits, we'll get more for small $r$). This is however enough to reconstruct $s_2$ from two consecutive outputs and values of $s_1$ without enumerating all the possible values of $(s_1-s_2)\bmod m_1$ (that would only be a last resort).

The above is crude, but will get the job done in seconds with a careful implementation on a modern CPU. And (quoting Bruce Schneier, attributing the saying to the NSA):

  Attacks always get better; they never get worse.

Note: since Pierre l’Écuyer's generator has been around for nearly 3 decades, is quite usable for non-cryptographic purposes like simulations, portable, relatively efficient given that constraint, and apparently often used, I would not be surprised if it had been studied in depth, and a much better attack found.

Assuming we have an $r$ (like 4.833936e-5) that let us walk back to $(s_1-s_2)\bmod m_1\ =d$ exactly, the unoptimized algorithm goes:

for $s_1$ from $1$ to $m_1-1$

$s_2\gets(s_1-d)\bmod m_1$
if $0<s_2<m_2$

$s_{1.1}\gets s_1\cdot a_1\bmod m_1$
$s_{2.1}\gets s_2\cdot a_2\bmod m_2$
if $(s_{1.1}-s_{2.1})\bmod m_1$ matches output well enough

$s_{1.2}\gets s_{1.1}\cdot a_1\bmod m_1$
$s_{2.2}\gets s_{2.1}\cdot a_2\bmod m_2$
if $(s_{1.2}-s_{2.2})\bmod m_1$ matches output well enough

success, output $(s_1,s_2)$ and stop.

Failure, refine.

A possible improvement is that most of the time $s_{1.1}−s_{2.1}$ varies by $a_1-a_2$ from one step to the other of the outer loop, and that's small, which allows to fast-forward $s_1$ considerably. I believe that alone will reduces the attack to a mere fraction of a second (c.f. saying).


What is the proper way to implement AES CTR with 128 bit nonce and 64 bit counter? While encrypting AES in CTR mode, the input to the AES encryption function is the either a combination of IV + $m$ bit counter or is either $0$ IV bits with an $m$ bit counter. It is however rare to see the full usage of the input block ($128$ bits) as just a counter.
Since CTR mode essentially converts a block cipher to a stream cipher, the implementer must be careful that the XOR of ciphertexts should not reveal XOR of plaintexts. For this requirement, the $(nonce, key)$ pair should be unique for each invocation.
I'm particularly interested in file encryption, or a large (in size) session of encrypted communication over a network , (say file download > 64 GB).
My encryption scheme:
Use a 128 bit IV to populate the initial block. For every requirement of a 16 byte keystream increment the counter and add it with the initial block populated with the IV. (EDITED)
This will be the protocol: $C_{i} = AES_{k}(IV  + i) \oplus P_{i}$  where $i$ is 64 bit counter, $IV$ is $128$ bit nonce and $+$ is arithmetic addition modulo $2^{128} -1$.

Is this secure (confidential sense)?
Will there be collisions in the input
block to the AES function since we have already populated the initial
block, with random IV (Can modular addition of counter cause collision) ?
Is this a standard way of doing AES CTR ?
What is the proper way to check for overflow? Should I check whether initial block (treated as a big endian integer) equals to $2^{128} -1$ or only whether $i$ equals $2^{64} -1$ and then raise an exception?

This will be the protocol: $C_{i} = AES_{k}(IV  + i) \oplus P_{i}$  where $i$ is 64 bit counter, $IV$ is $128$ bit nonce and $+$ is arithmetic addition modulo $2^{128} -1$.

Is this secure (confidential sense)?

Well, you didn't really specify the nonce to be random. If it is a serial number then it is obviously not secure at the next file uses the same block as what the other one started with.

Will there be collisions in the input block to the AES function since we have already populated the initial block, with random IV (Can modular addition of counter cause collision)?

If it is random then you don't really know what the distance is towards the next IV. If you are (rather) unlucky then it is less than $2^{64}$ and then the really big files could be in trouble as the last part of one file and the first part of another may use the same counter and thus key stream. So serial number: clearly not secure

Is this a standard way of doing AES CTR?

Generally the counter value and the nonce would use separate bits. You'd round up the number of required bits for the counter and use as many as possible for the nonce. Sometimes domain separation could also be encoded in one or more bits.

What is the proper way to check for overflow? Should I check whether initial block (treated as a big endian integer) equals to $2^{128} -1$ or only whether $i$ equals $2^{64} -1$ and then raise an exception?

In your scheme you'd not really know when the overflow happens. In the general sense you could simply test if the counter returns to zero, or calculate the amount of bytes and make sure that you keep below that value.

You could also derive a different key per file, then you can use all 128 bits for the counter.
Let's describe such a system. $K_F = {KDF}(K_M, \mathbb{nonce}_F)$ where each value is 256 bits. Then start the ${IV}$ / counter at all zero so you can just perform $C = E_{CTR}(K_F, {IV}=0, P)$ and $C_{total} = ({nonce}_F, C)$ where $P$ is the original file and $C$ is the encrypted file.


Is there a theorem to determine the elliptic curve parameters based on the group order? By Hasse's theorem we know that range of the group order of the elliptic curve. And similarly, there exist a theorem on the admissible order of elliptic curves. Suppose by the theorem on the admissible order of elliptic curve we know there exist a curve of desired order then how to determine the curve parameters. For example in case of simplified/short Weierstrass equation the value of the parameters $a,b$.

My question: is there a theorem to determine the curve parameters based on the group order? Does the form of the curve matter? The different forms of the curve are Weierstrass, Montgomery, and Edwards.

There is a method known as "Complex Multiplication". However, it is not simple at all, and tends to be overly expensive for most target orders. See this article for some details. There is also the (theoretical) concern that a curve constructed that way may have a special structure though could possibly be leveraged into an attack one day; generally speaking, cryptographers do not like special cases and prefer the immunity of the herd by relying on random values in big sets (unless there is a performance advantage to be had with the special structure, in which case to Hell with it, let's milk the precious clock cycles -- that's how modern curves tend to be defined in fields of prime order $2^m-c$ with a very small $c$).

CM has been used to define pairing-friendly curves (curves that have a demonstrated special structure which is on the verge of being a weakness, but also enables nifty three-way protocols).


Final permutation table example with DES This question has been asked by another already but I can't comment on that.

There is a question in a book:

  Find the output of initial permutation box when input given in hexadecimal as:

$\texttt{0x0002 0000 0000 0001}$

How does this input have two 1s at bits 15 and 64?

How do I look into the initial permutation table for the output:

$\texttt{0x0000 0080 0000 0002}$

Please also give any reference material.

The reference for DES is FIPS 46-3. See page 10 for the permutations.

Write $\texttt{0x0002 0000 0000 0001}$ in binary. Start with $\texttt{0x0002}$:

0: 0000 (bits 1-4)
0: 0000 (bits 5-8)
0: 0000 (bits 9-12)
2: 0010 <--bit 15 is 1 (bits 13-16)

Bits 17-48 are all 0. Now look at $\texttt{0x0001}$:

0: 0000 (bits 49-52)
0: 0000 (bits 53-56)
0: 0000 (bits 57-60)
1: 0001 <--bit 64 is 1 (bits 61-64)

Thus, bits 15 and 64 are set.

At this link, you can see the initial permutation and final permutation. It looks like the answer you're referring to is actually talking about the final permutation, so to match what you have, I'll be using that. Looking at the final permutation, the number "63" is the 15th bit, and the number "25" is the 64th bit. So your result is, in binary,

$\texttt{0000 0000 0000 0000 0000 0000 1000 0000}$ (bits 1-32, bit 25 set)
$\texttt{0000 0000 0000 0000 0000 0000 0000 0010}$ (bits 33-64, bit 63 set)

Or, in hexadecimal,

$\texttt{0x0000 0080 0000 0002}$.

This is the final permutation, not the initial one.


Why are multiple rounds with generated subkeys used? In AES-128, 10 rounds are used with subkeys generated from the 128-bit key. In DES, 48-bit subkeys are generated from a 56-bit key. This seems to be common in symmetric encryption.

I ask this because of my understanding of entropy and randomness. If you were to take a random integer and put it through some function to expand it (the terminology used in the AES standard), aren't you making it more predictable/less random?

If I were to take a random integer and use it as the seed to a PRNG, I'm not getting anything unpredictable from the seed as I retrieve values from it. Surely the stream has the same randomness as the seed alone. I would have thought that it follows that multiple rounds result in encryption with multiple low quality subkeys with significantly less randomness than the original key, assuming the original key was random, or at least we don't know what it is.

(This PRNG and randomness analogy may be misinformed; I'm simply trying to say that you can't make an unpredictable value bigger and be as unpredictable as it was before, which is my understanding.)

Please could someone clarify why using multiple rounds of a lower quality subkey is more desirable than, say, one round with the whole key (in the case where key length is the block length)?

It's true that a badly designed key schedule weakens the cipher.

However the main point is to "stretch" the randomness across all subkeys by using diffusion techniques, while using only $k$ bits of randomness for the key instead of $kr$ bits of randomness if all round keys were independently chosen.

This is doable. AES is a good example where the components of the cipher are used in the key schedule.

More theoretically, James Massey (and one of his students whose name escapes me now) has proved that a construction called perfect local randomiser can extract random looking $k-$tuples (subkey bits) from a uniformly distributed $n-$tuple (randomly uniformly chosen master key) such that these $k-$tuples are locally uniformly distributed. The construction uses orthogonal arrays which can be obtained from certain MDS codes under certain conditions. MDS codes are intimately related to the branch number of AES MixColumns operation, see, e.g. The answer to this question.

Edit: Also, a one round cipher will not have enough diffusion for linear and differential probabilities to drop to safely low levels, as it happens through multiple rounds.


Is this simple PRNG secure? $G$ is a PRNG used in a stream cipher and defined in the following way:

G receives $s_0$ as an input, which is a random string drawn from a uniform distribution.
The output of step $i$ is $s_i = (s_{i-1}\cdot (N+1) + 1) \bmod{N}$, for $i=1,2,3\dots$

Is this PRNG secure? If not, what is the distinguisher?

$s_i = s_{i-1}\cdot(N + 1) + 1 = s_{i-1} \cdot N + s_{i-1} + 1$

but $s_{i-1} \cdot N = 0 \pmod N$, so

$s_i = s_{i-1} + 1 \pmod N$

which means you can discover the next number to be generated just looking to the current one...


On randomness related terminology clarification It was suggested to provide a new question in the comments in
How to combine $n$ 'less random' bits to generate one 'more random' bit?.

Why there is no unbiased randomness (seeking theoretical underpinnings)?

How can a hash function extract randomness (seeking theoretical underpinnings)?

Is there intuition behind leftoverhash lemma and can it useful in correlated randomness (seeking theoretical underpinnings)?

Is there references for 1. and 2.?

Where would it come from, and how would you measure it? If we had $P(x_i = 0, x_i = 1) = 0.5 \pm 0.0$, that would be mathematical perfection given a large enough sample. We believe that ChaCha is a fairly decent cryptographic random number generator. Yet see the abridged ent output from a pass over a 2GB sample from /dev/urandom:-
 Arithmetic mean value of data bytes is 127.5018 (127.5 = random)

It's 0.0018 $(\approx 2^{-9})$ out from the expected value . That's because it's random. And that's expected too. And consider that we are considering infinitesimally small biases of the order of $2^{-64} - 2^{128}$. I use the 128 value in some of my designs. Bigger sample? And due to large data sets necessary (or new maths), we don't know the output biases of our current cryptographic primitives. If any, theoretically. I tried to find out, but no satisfactory answer was presented.
2.
Clearly hash functions can extract randomness as you've seen in your opening link. I've shown how to do it.
3.
There is lots of intuition, but unfortunately I have to leave that for the more mathematically capable. I just build this stuff. Others understand the basic theories. All I can do is highlight the lemma and it's usage.
It is predicated on min.entropy ($H_\infty$). And this is a measure allowing for auto-correlation in the raw input data. Since we build with it, we can set the final bias ($\epsilon$) ourselves. So it's possible to go silly with $\epsilon \approx 2^{-10,000}$ if you believe that hash functions are entirely unbiased (as per the prior linked question). But as you see, nevertheless it would still be biased. A little. Maybe.

Auto-correlation $(R)$ also has the same issues in measurement as does bias. It's a continuous statistical metric so again the user has to decide the degree before stating that it exists or doesn't. Typically $R \le 10^{-3}(physicists); p > 0.001 (NIST); p > 0.01 (RRR)$ but those  are anecdotal thresholds which influence the bias measure and $H_\infty$.
Interesting (Daniel) this also directly affects von Neumann extraction. vN is predicated on a totally uncorrelated stream, otherwise auto-correlations can propagate to the output. By virtue of the above paragraph, we can't prove when $R = 0.0$ with sufficient certainty to celebrate $\epsilon_{vN} = 0.0$.
I'm not suggesting that IID data doesn't exist. It's just that proving it with 100% certainty, rather than say 95%/$3 \sigma$ is difficult. MY ent test from above had $R = 0.000009$. But not zero.


Using AES-CTR as a PRNG AES-CTR is not considered as a CSPRNG, why ?
Is it unsecure to use it when a password is hashed with Argon2id to produce the seed to generate all random data needed for an end-to-end encyption system such as keys and IVs.

AES-CTR is not considered as a CSPRNG, why?

I don't know why this was given as a negative.
AES-CTR can certainly used to generate a pseudo random stream of values. If that alone makes it a CSPRNG is up for debate if you ask me. For instance, the DRBG's specified by NIST all provide a reseeding operation, which is missing from AES-CTR. Although they do provide a counter based operation as well, AES-CTR clearly doesn't qualify.

Is it unsecure to use it when a password is hashed with Argon2id to produce the seed to generate all random data needed for an end-to-end encyption system such as keys and IVs.

It is probably not insecure, but it seems to me that you are not in need of a CSPRNG. It seems to me that you need a key derivation method. Now Argon2id is already that, so if you just need more data then you can just ask Argon2 for it. It can generate up to over 4 billion bytes ($2^{32}$), which should be plenty.
If you need multiple keys derived by sequence, I'd recommend to use a Key Based Key Derivation Function such as HKDF afterwards, using a label or indeed counter to generate multiple keys. Or you could use a ratchet or similar methods of key derivation.

A practical reason not to specify to use a CSPRNG is that the output of CSPRNG is generally just not precisely defined. The output must be pseudo-random of course, but slight changes in the implementation will generate random but different output even for the same seed. It is often not entirely clear if and when a reseed happens either. In that sense the output of a stream cipher such as AES-CTR is probably better defined in practice.


What security risks does exposing the size of the plaintext entail? For this question my focus is exclusively on symmetric block ciphers (with a particular interest in AES256 in CBC mode).

I have read much discussion on various ways to pad the plaintext so that the length of the input to the encryption algorithm is a multiple of the blocksize.

The real problem here is not padding to a suitable size (which, by itself, is trivial), but rather undoing such padding after decryption.

One very simple scheme for undoing the padding is to store the length of the (unpadded) plaintext in a header section, unencrypted.  Then, after the ciphertext is decrypted, the raw result is truncated to this saved length.

Since this simple solution is never mentioned in discussions of padding (I've consulted several textbooks), I have to assume that there are some very serious problems with it, but these problems are never spelled out, and they are not obvious to me.  What are they?

Exposing the size of the plaintext has no security risks. The size of the plaintext is always considered public data. It's not done because it has limited benefit.

With a mode like CBC, you cannot encrypt a fractional block. You must pass a whole number of blocks to the encryption function. So you need padding in some form. The ciphertext is a whole number of blocks. If the ciphertext itself doesn't encode the message unambiguously, you need to pass the size separately, at least the size of the last block (or equivalently the size of the padding). In practice, that means you need at least one extra byte to indicate the size. If you do this, then the padding doesn't need to be unambiguous, so you can allow it to be empty if the plaintext happens to be a whole number of blocks. Compared with unambiguous padding, this method results in ciphertext-plus-size that's one block minus one byte shorter if the plaintext is a whole number of blocks, and one byte otherwise. So in terms of ciphertext size, it's a wash.

In terms of ciphertext and decoding complexity, passing the size separately makes things a little more complicated. The ciphertext isn't a black box anymore: the padding size needs to be sent with it. The ciphertext-plus-size can be a black box, but it's a little harder to process: the last pseudoblock is one byte longer than the others.

This scheme does have a security benefit. Since the recipient does not need to decode the padding, it eliminates direct padding oracle attacks, if done right. However this was poorly understood when CBC was in vogue: people generally followed the usual wisdom to verify everything, thus revealing information about the content of the last block. Today, serious protocol designers are well aware of the dangers of padding oracle attacks, but the solution is not to use padding at all.


Are these emerging threats against AES affecting your designs? Recentally, an attack on AES was discovered which reduces its computationally complexity,  by a very slight amount.

The first key recovery attack on the full AES-128 with computational
complexity $2^{126.1}$.
The first key recovery attack on the full AES-192 with computational
complexity $2^{189.7}$.
The first key recovery attack on the full AES-256 with computational
complexity $2^{254.4}$.

There is also the new AES-NI instruction set, which allows attackers to make hundreds of billions of parallel guesses per day.

In light of these emerging threats, have you made changes to your designs to mitigate the impact?  If so,  what has changed?

No, an attack on AES-128 requiring $2^{126.1}$ computations and $2^{88}$ bytes of known plaintext is not a concern. Brute-force guessing of keys (e.g., using the AES-NI instructions you mentioned) will succeed in $2^{127}$ computations on average and requires negligible known plaintext. Part of why key lengths are selected conservatively is precisely to ensure a safety margin which renders these tiny differences insignificant.

What the paper presents is an interesting method of analyzing block ciphers using a technique developed for analyzing hash functions. That this novel cryptanalysis technique fails to improve on brute force by even a full bit confirms the fundamental soundness and resiliency of AES's design.

Still, this technique is new and the paper explores multiple approaches to applying it. Cryptographers will be watching with interest to see if anyone goes farther with it, either through refinement or in combination with other cryptanalytic techniques.

Edit: In other discussion it was pointed out that this attack succeeds with probability 1, so an apples-to-apples comparison would be with worst-case brute force at $2^{128}$. It would be an exceedingly unlucky attacker who actually paid worst-case cost! A comparison of the typical scenario seems more relevant. The average-case for this AES-attack is probably a bit better than $2^{126.1}$, but it's not obvious from the paper. Still, the difference seems likely to be under a couple of bits (for now), while brute force retains its overriding advantage of not requiring $2^{88}$ data.

Of course one can build a weak protocol (or use a non-weak protocol in a weak way) on top of AES-128. WPA2-PSK can usually broken quite easily, because the pre-shared key is derived from a user-given password, which can be brute-forced in a short time. Even changing to an algorithm with a 10000-bit key would not help, if this key is derived from a weak password.


How secure is the Bitcoin protocol? Are there any evidence (other than not being cracked so far) that the Bitcoin protocol is secure? "How secure" is it?

(I realize that this might not qualify as a meaningful question - feel free to edit if you can improve it. Also, if you liked this question, you might like the Bitcoin Proposal.)

There are several uses of cryptographic algorithms in the protocol.

Accounts/Transactions

To move money from one account to another, you need to collect some data (the previous transaction(s) which got you the money, the target account, the amount you want to transfer) and sign them, using the private key which belongs to your account.

For this signature Bitcoin uses the ECDSA algorithm.

If I can fake your signature, I can also steal your money.

The (public) addresses of the accounts are given as address = version || hash || checksum, where version = 0 (one byte), hash = RIPEMD-160(SHA-256(public-key)) and checksum = first 4 bytes of SHA-256(SHA-256(version || hash)). (The checksum mainly protects against transmission errors.)

If I can somehow generate a private key whose corresponding public key has the same SHA-256 hash as your one, it will have the same address, and I can steal your money. If I can create a fitting private key for your public key, this is also possible.

For now, there is no known attack at the ECDSA algorithm (and I think even with second-preimage attacks at SHA-2 to find a second public key with same hash, you would need an attack at ECDSA to get a useful private key).

It is much easier for now to use a trojan or such to steal the actual private key of the owner. (But this would be off-topic here.)

The Block chain

For a transaction to be deemed valid, it has to be included in the block chain, e.g. in one of the blocks consisting this chain.

To create this block, a miner uses a Merkle tree of hashes, which refer the individual transactions included in this block, the previous block, and some other data. This tree uses SHA-256, too.

A block is considered valid (e.g. other peers will accept it, and build their own blocks on it) if the hash of the header is lower than some number (the "target"). This can be reached by manipulating one part of the block, the nonce value, calculating the hash, and repeating until one is lucky hitting the right nonce to make this block valid.

If there are several valid blocks running around (which are not descendants of each other), "good" miners will usually build on the one with the longest chain.

So, how could we cheat here?

If we can break SHA-2, e.g. by finding a faster way to get the right nonce than trying many of them, we can generate the blocks faster than everyone else. This would mean that we will get all of the mined coins, at first. Having a monopole, we can also effectively decide which transactions to include and which ones not (this could be a denial-of-service for competitors who want to transmit money).

I'm not sure if we could in fact include bogus transactions this way (or by other SHA-2 breaks means) in our Merkle tree - I think the receivers of a blocks should still check if its transactions have actually a valid signature.

For now, no such break of SHA-2 is known.


OT extensions paper: Why is $G_{m+1} \nleq m \times AND_B$? I am reading this paper, in which Beaver shows how to take a small number of Oblivious Transfers (OTs) and extend them into an arbitrary number of OTs by implementing a pseudo-random number generator inside of a garbled circuit. Very cool.

He then goes on to show that, while this works in the settings where the parties are computationally bounded, it is in fact impossible to do OT-extension when the parties are not computationally bounded.

This is where I'm getting stuck. I don't understand his proof of Lemma 7. What does "Bob applies 1" mean? What are $x$ and $y$? (I thought they were Alice's and Bob's respective inputs to an $AND$ gate, but that does not seem to make sense in the context.)

First, what is $AND_B$? $AND_B$ is the asymmetric AND protocol, in which Alice and Bob each has a bit $x$ and $y$, at the end Alice always learns nothing (get output 0) and Bob learns $x \land y$. In Lemma 4 it says $AND_B$ can be realized by 1 invocation of $(^2_1)OT$.

Then what is $G_{m+1}$? $G_{m}$ is a protocol in which Alice has a $m$-bit long string $x$, and Bob has a bit $y$. At the end, Alice always learns nothing (gets output $0^m$ -- $m$-bit string with all 0s), and Bob gets $0^m$ if $y=0$ or $x$ if $y=1$. Lemma 6 says $G_{m}$ can be realized by $m$ invocation of $AND_B$. It is simple: for the $i$-th invocation of $AND_B$, Alice uses $x_i$, the $i$-th bit in $x$, as the input to $AND_B$, and Bob uses $y$ as the input to get either 0 or $x_i$. After $m$ invocations, Bob get either $0^m$ or $x$.

Lemma 7 then shows $G_{m+1}$ cannot be realized by $m$ invocation of $AND_B$ (in the presence of a computationally unbounded adversary). Now $x$ is Alice's input that is an $m+1$ bit string and $y$ is Bob's input that is a bit. One thing immediately clear is that if Alice and Bob continue to do what they did above, there is no way Bob can get all $m+1$ bits securely because there is always the last bit that cannot be securely transferred to Bob.

So they have to do things differently. But how? One possibility is that instead of always using $y$ as the input to $AND_B$, Bob may use $y'\ne y$ as input, with some probabilities. The first part in the proof simply tries to say "no, Bob has to always use $y$". In the proof ``Bob applies 1 | y=0'' means Bob uses $y'=1$ as input to the invocation of $AND_B$ even though $y=0$. There are 3 cases, in the first case Bob gets nothing from the invocation -- so no point doing this; in the second case Bob gets things he should not know (violation of Alice's privacy); in the third case it is secure and Bob gets what he is entitled, but he has to use $1$ when $y=1$ and $0$ when $y=0$. In conclusion, Bob cannot do anything differently.

Then can Alice do something differently? Alice can encode her message $x$ into something $(\tau,\sigma)$ such that $\tau$ is given to $Bob$ in clear, and $\sigma$ is $m$-bit long. So if $y=1$, Bob can receive $\sigma$ using $m$-invocation of $AND_B$. Then Bob can decode $x$ back using $(\tau,\sigma)$. However, $\tau$ is not independent of $x$, thus giving $\tau$ to Bob will leak information about $x$ when $y=0$. Note that Alice cannot give $\tau$ to Bob only when $y=1$ because that implies Alice knows $y$. Thus Alice cannot do this encoding thing and has to act as before.

Now since Bob and Alice cannot do anything differently, there is no way $G_{m+1}$ can be realized by $m$ invocation of $AND_B$.


Is there a variant of Merkle tree with no traceability from root to leaves? I'd like to store a large amount of objects, all authenticated using something like a Merkle tree. The root will be published, and I'd like to make sure there is no way to enumerate these objects from the root of the tree, or even prove a document is in the tree, unless this information has been published by me.

Is there an existing variant of Merkle tree to do so, or should I invent something myself? I came up with the following scheme, but it is most probably utterly broken:

A root is a hash(first-level nodes + salt).
Every node is a hash(next-level nodes/documents + salt).
A separate salt is stored for every document and for every node
In order to reveal a document I publish the path in the tree with all the salts along the way.

Merkel trees already allow you to decide how much you reveal. To prove presence of one leaf, you reveal it and the commits along its copath.

If your documents contain enough entropy then you do not need salts. If the documents do not, then you may prepend each document with a salt I.e. $\text{hmac}(\text{secret} \| \text{index}, \text{message})$.

The intermediate nodes do not need salts.

To avoid leaking the number of documents you can fix the copaths length to $\lceil\log_b(N)\rceil$. This adds an additional $N - b^{\lceil\log_b(N)\rceil}$ zero-sized documents as additional noise. $b$ is the number of branches per depth (usually $2$). The padding should be uniformly shuffled with all documents, not ordered or appended to the end. The $\text{index}$ identifier is the position from root-to-leaf left-to-right after flattening the tree. I.e. $[0], [1, 2], [3, 4, 5, 6]$.


Security of the Goldreich–Goldwasser– Halevi (GGH) Scheme There is a statement in the article of "Public-Key Cryptosystems from Lattice Reduction Problems" that presents GGH encryption scheme:
"The cryptanalytic problem underlying our scheme is to approximate the closest vector problem (CVP) in a lattice, given a "non-reduced" basis for that lattice"
On the other hand, in his survey Peikert says:
" Unlike the works of Ajtai and Ajtai-Dwork [AD97], the GGH proposals did not come with any worst-case security guarantees; their conjectured security was merely heuristic. "
Also he says "Because no cryptosystem has yet been proved secure based on CVPγ, we do not formally define that problem here"
Which one is true?

If you look at the GGH paper, they explicitly say that they reduce to a random instance of CVP. At the end of the paragraph on CVP in Section 2.1, it explicitly says: "As we explain in Section 3, an attack against our trapdoor function amounts to finding an exact solution for some random instance of CVP." Peikert is referring to worst-case guarantees (i.e., hardness for any instance of CVP) whereas GGH considered an average-case problem (when the instance is generated at random).


What is the complexity to break second preimage resistance? In the context an of hash functions we have three required properties.

Preimage resistance
Second preimage resistance
Collision resistance.

The bounds for Pre image collision is $O(2^{n-1})$, the bounds for collision resistance is $2^{n/2}$, what are the bounds for breaking second preimage resistance?

The right terminology is second preimage resistance and preimage resistance.

Edited to reflect comment by otus. Preimage attack takes $O(2^{n})$ hash function calls on average.

Second preimage attack takes just one extra call so the complexity is essentially the same as that of the preimage attack. Given $x$ you want $x'\neq x$ such that $H(x)=H(x').$ So evaluate $H(x)$ for one extra query, and then apply the preimage attack to $y=H(x).$


Symmetric encryption using RSA for random generated password I'm fairly new to encryption, so I wanted to check the logic for a .net solution I'm working on that encrypts data between two parties. the receiving (decrypting) party will have an RSA key pair stored. They will transmit the public key to the encrypting party via a web service call. The encrypting party will use the public key to encrypt a random generated password. Prior to the RSA encryption, this password will be used to derive the Key/IV (using Rfc2898DeriveBytes) for RijndaelManaged symmetric encryption for the main data.

The RSA-encrypted password will be transmitted along with the RijndaelManaged-encrypted data via another web service call. The receiving party will decrypt the RSA password using their private RSA key. They will then use the password to decrypt the RijndaelManaged-encrypted data.

The thinking is that the use of the random password will avoid the pitfalls of storing a constant password if I were to only use symmetric encryption. It also provides for a different key/IV each time as well as a different RSA key each time. The reason I'm thinking of this Symmetric/Asymmetric hybrid approach is after reading about some of the performance pitfalls of just using RSA. My question is whether this is any better or worse than going with one encryption method or the other, or if I'm missing something that will make this approach impossible or open me up to some sort of vulnerability.

The concept of using an asymmetric key (RSA) to encrypt a symmetric key (AES) is not new.  This was first popularized by PGP, which is probably what I would encourage you to use to solve your problem.  SSH (well SFTP in particular) also uses a somewhat similar approach and could also be pressed into transmitting files securely.

Pretty much any approach you could dream up would suffer from the problem of the establishment of initial trust.  In general, you probably don't want to constantly regenerate the asymmetric keys as then you have to also regenerate the trust for them.

One of the simplest ways to handle initial trust for a program/automation is to establish it yourself by supplying the same PSK (pre-shared key) on both (or all) ends of a connection.  If you did that, then you have a different problem, of keeping the shared secret secure.  There are devices that can do that for you, such as HSM (hardware security module) but they are frequently expensive.  (The cheapest one that comes to mind is $500US from Yubico.)


Can I generate same random number given same entropy value? Given the hypothetical fact that I can predict the same entropy value used to generate a random number, can I generate the same random value, say in a Windows based python application?

Yes, of course you can do that hypothetically. By definition random numbers are generated based on the entropy together with known values and algorithms. It would of course be necessary to know those constants and algorithms though. Quite often this is possible as the source code for the random number generator is often known in some way or other (open source or research program).

Usually runtimes make use of the random generator of the operating system, and the Microsoft algorithm is pretty complex and may change for different versions of the operating system. However, good random number generation has been known to be complicated on VM's.

Nowadays it may well be that the OS mixes in values of the hardware based RNG on Intel and AMD processors or a TPM module on the motherboard, making it nigh impossible to guess the entropy used to seed the OS PRNG.

TL;DR is it possible? Yes, if you truly know all the entropy - which usually is a questionable assumption. But even then it requires a lot of practical knowledge and a lot of effort.


Better than diceware? And sha512 related question I am working on a secure password generator based on the following setup:

choose a publicly know (text) file
make some deliberate memorable changes to it
use collected entropy for a secure password ???

Details:

The text file can be anything provided it has a reasonable character count.
For example: pick a book with $2^{20}$ characters ≈  550 pages of human readable text
Changing/inserting *) a character within this text from the base64 alphabet yields an estimated entropy of: 20 + 6 + 1 = 27bits  correct ???

20bits = from the positions within the text

6bits = from the changed character (this is slightly less since the character that is to be changed can not be used from the base64 alphabet, but we can add an additional special character to base64 to overcome this)

1bit accounts for insertion or change of a character

*) any modifications to the text add different additional entropy: deleting passages, copying passages to different location, reversing passages, deleting pages etc,…

This yields more than twice the bits of diceware entropy (≈ 13bits)

3) Repeat step 2 to accumulate desired level of entropy in an other location of the file. Thus one could accumulate 135bits of entropy with only 5 modifications!?

4) Use this entropy to generate the password but how???

PROBLEM:
I find using a simple sha512 on the modified text file and using the output as password might endanger the setup since:

The idea is to make the unmodified text file public and the adversary would then know  $2^{20}$ - 5 = 1048571 characters (that’s almost 100%)  that were not changed.

Is the below solution viable???

1) Transfer the text file into a $2^{10}$  characters by $2^{10}$ + x  matrix
(x is for padding, since the original length of the text file of $2^{20}$  characters  might have increased if the user inserted some characters as part of his/her modification)

2) Hash with sha512: line by line to create an other $2^{9}$ bit by $2^{10}$ + x  matrix

3) Hash the resulting matrix with sha512: column by column to create the final $2^{9}$ by $2^{9}$  matrix

4) finally xor the resulting matrix line by line to receive the $2^{9}$ bit password

Would this withstand the issue with the adversary knowing  $2^{20}$ - 5 = 1048571 characters?

thanx

I don't really see the problem with just hashing the modified text. Even when the original text is public information, you've already shown that introducing $n$ independent changes gives you $\approx27n$ bits of entropy. Hence given an output hash, finding the modified text should be as difficult as exhaustive search if the hash function has pre-image resistance (and collision resistance, to ensure that the hashes of your modified text “look random“ conditioned on your original text).

Anyway, your line-by-line construction looks to me equivalent to some other hash function which combines multiple SHA512 invocations, so I can't imagine it'd be any more secure. Why don't you simply make a diff (e.g. insert a at position 12381, change position 812931 to f) and hash the result?


Why can we not use the group $Z_{p}^{*}$ for cryptography? Sorry if this is a noob question, but for instance in ECDSA, we start by considering the field $\mathbb F_p$, whose the elements also form a group under multiplication. Why don't we just use this group instead of the one that is generated by the solutions of an elliptic curve equation lying in this field? I.E. choose an element lying in this field $g$ and choose a random number $n$ as a private key, and let $g^n$ be the public key. Is is just because of the reduction in key size? It seems like a high price to pay for the additional structure imposed by the curve equation.

You can use the multiplicative group $\mathbb{Z}_p^*$, provided you use a key long enough to be secure.

Diffie-Hellman key exchange, DSA and the ElGamal cryptosystem were originally defined based on the hardness of the Discrete Logarithm Problem (DLP) over finite fields.

The challenge is that since then several methods have been found to reduce the complexity of the DLP (e.g. number field sieve, Pohlig-Hellman algorithm, Pollard's Rho algorithm). Consequently for these algorithms to be secure today it is necessary to use long (>3072 bits) prime fields. Additionally, since the scaling of hardness is sub-exponential in p, doubling the hardness of the problem requires that p is increased by much more than 2 (so secure key lengths will grow near-exponentially over time).

The advantage of using cryptography over elliptic curve groups is that you end up with smaller key lengths and ciphertexts for equivalent hardness (e.g. 256-bit ECC versus 3072 bit) and it scales better (so doubling the complexity means adding a single bit instead of adding many bits).