Which is stronger: Threefish 1024-bit, SHACAL-2 512-bit, or AES-256? I found some App in the Google Store, and there were features only for the PRO version: Threefish 1024-bit and  SHACAL-2 512-bit. Meantime, AES-256 was available in the free version of app.

So I concluded that the Threefish 1024-bit and SHACAL-2 512-bit algorithms are stronger, and I did a little research and discovered that AES-256 was invented in 2001, Threefish 1024 in 2008, and SHACAL-2 512 was also invented in 2001.

SHACAL-2 512 - I have read that this algorithm was something like "partly hacked for 50%" but for now considered as solid and unhackable.

Threefish 1024-bit - in the opinion of the authors who invented this algorithm it is more effective than AES. And it has a 2.9 security index, while AES has only a 1.7 security index (bigger is better).

Neither SHACAL-2 nor Threefish are "more" secure than AES because it's a case of "meh cannot break" with all of them.

All three ciphers are unbroken and all three use keys larger than 128-bit* meaning the bigger numbers in the key size have no value except to impress people with being bigger and with the company being able to waste computation time. Also note that in the most rares cases it is actually the crypto (and especially unlikely the block cipher) that is broken but rather the implementation and especially the data handling implementation.

Now for a bit of discussion on each cipher:

SHACAL-2. It is based on SHA-2's compression function and from what I can tell turning it into a block cipher was a case of "we did it because we could". It's practical deployment is absolutely negligible and cryptanalysis results are sparse, so I wouldn't trust it more than AES.
Threefish. Threefish was the block cipher underlying the Skein submission to the SHA-3 competition. It has some well-reputed names behind it and is a very useful tool block-cipher with a large block size that is especially hardened against related-key attacks and side-channel attacks. I would actually prefer Threefish over AES if you don't have a well-hardened implementation of AES available and you are on a 64-bit platform and you don't have hardware-accelerated AES available. This is because Threefish only uses additions, rotates and XORs (ARX) which makes it quite easy to implement securely and with solid performance. Analysis-wise it has seen quite a bit during the SHA-3 competition and a bit afterwards, but as Skein wasn't selected it hasn't seen much analysis since.
AES. AES is an excellent block cipher which has with-stood nearly two decades of intense cryptanalysis. Not only hasn't it been broken in this time, but we have also figured out how to implement it securely and it has wide hardware support these days, making it the performance- and security-wise best choice if available. If not, using a more modern ARX based cipher is also appropriate, but especially on a modern phone secure AES implementations should be available.

On this topic, also see the mandatory blog post by Matthew Green.

* If you believe that large-scale quantum computers will exist at some point, you need 256-bit symmetric keys to force $2^{128}$ quantum operations (thanks to Grover's Algorithm) which all three cipher support.


openssl encryption salt length when i was reading the latest source code of openssl, i found openssl enc has
an 8-byte (64-bit) salt length; because the same (password, salt, iter) will
generate the same (key, iv), birthday paradox tells that you may reuse a
(key, iv) pair within about 2^32 encryptions;

openssl source:

//  apps/enc.c;
int enc_main(int argc, char **argv)
{
    ...
    unsigned char *buff = NULL, salt[PKCS5_SALT_LEN];
    ...
}

//  include/openssl/evp.h;
# define PKCS5_SALT_LEN                  8

personally i do not think 2^32 (around 4 billion) is a very large number; there
are almost 8 billion people around the world now; in some use cases there are a
lot of personal data records that need to be encrypted; the number is even larger
when you include other animals such as cats and dogs;

pkcs #5 (in 2017) recommends at least 64-bit salt length; while
nist (in 2010) says you shall use at least 128-bit salt length; there is
also a github issue proposed in 2017;

my questions:

is 64-bit salt length deemed secure right now? if so, why does nist said you
shall use at least 128-bit salt length 7 years earlier?
is openssl enc meant for production use or only a demo of the openssl
library?
if the salt length cannot be easily improved in openssl, what other
libraries and shell tools are both secure and easy to use?

Some sites even suggest using a salt that is the length of the digest of the hash function, created by a CSPRNG, but 16 bytes is generally the minimum salt length used (128 bits).


Input Hash Size of ECDSA Signature over Curve secp521r1 For encryption authentication, I am using ECDSA signatures over the curve secp521r1. There is a hash function parameter, and as the curve is 521-bit, the hash output length should be > 512 bits, which is the highest offered output of the Standard SHA-2 hashes available.

However, in the SHA-3 specification, the cSHAKE function allows for variable length outputs, so is it recommended to use cSHAKE with an output length of something like 521 < n < 1024. If so, what is the recommended hash length to use?

The hash output length does not need to be larger than 512 bits; the ECDSA specification can handle any length. The curve secp521r1 is usually considered to provide 256 bits of security (even though it provides a bit more), see Table 2 of NIST SP 800-57 for example. Therefore, a 512-bit hash, i.e. SHA-512, should be fine ("The security strength of the hash function used shall meet or exceed the security
strength associated with the bit length of n", NIST FIPS 186-4)

Regarding cSHAKE (you probably meant SHAKE; cSHAKE is its customizable variant that is used to define KMAC and TupleHash), you could use any output equal to or larger than 512 bits. The NIST FIPS 186-5 draft mandates SHAKE256 with 512-bit output.


How to combine pepper in random string generation I am writing a key generator program.

Indeed it generates a key in the form of a random text string (not binary), with its characters chosen randomly from a set of defined characters, with a specified length.

You can see an example of my program's config.ini file for clarification:

[general]
key_chars = abcdefghijklmnopqrstuvwxyz
            ABCDEFGHIJKLMNOPQRSTUVWXYZ
            0123456789
key_len = 22
pepper = G89ne_^DFIM"]12@\z2's#GBA

Ignoring the pepper part, we can generate the desired key with a code like this (code is in Python language):

Warning: The following code is not secure! *

def generate(self, keyLen, keyChars):
    key=''
    for i in range(keyLen):
        randIndex=randint(0, len(keyChars))
        key+=keyChars[randIndex]
    return key

But I don't want my keys' security rely solely on the OS/Language (presumably) secure random generator (In this case, pycrypto module's CSPRNG that probably itself uses OS' CSPRNG under the hood), so I want to engage the pepper in the procedure too, but I am not sure about the proper way to do that securely. Please tell me how to combine the pepper in the above code (Or maybe you suggest a different method for doing that which is better suited to such purpose).

*: I used randint in my example code because I thought it is part of pycrypto module, then I realized that is not the case!

First of all, you should just trust the random source that the OS provides and call it via os.urandom(n). Not only is it generally safe, but if your OS is unsafe you may have bigger problems on your hands.

If you really do want to use your pepper as an input to the random bytes that are generated, the obvious way would be to encrypt the OS's stream using a block cipher. You then use the ciphertext as your new random source.


Decrypt RSA ciphertext with two middle bits leak Given RSA public key (e.g. 1024 bits) and decryption oracle that outputs 2 middle bits of decrypted ciphertext (pow(ciphertext,d,n) >> (1024/2)) & 3, how can we decrypt whole message?

Question related to "Pinhole Attack" task from Tokyo Westerns/MMA ctf.

This appears to be homework, and so I won't tell your outright; I will give you a hint.

Suppose you compute:

$$c_1 = c \times 2^e \bmod n$$

How are the decryptions of $c$ and $c_1$ related?

Suppose we compute a long series of:

$$c_i = c \times (2^i)^e \bmod n$$

What does the middle two bits of $c_i$ tell us?


Group Signature Scheme without Opening but with Revocation After reading many papers about group signature schemes, I saw that basically all of them employ the possibility of "signature opening": The Group Manager (GM) can identify any signature made by his group's members. But I would like to completely eradicate that feature and rather revoke group members by their public key/ID token, preserving signature anonymity at all times.

(I am thinking about very dynamic and large groups with their members "expiring" after a certain time: the GM keeps a public key list and revokes keys when they expire. Maybe existing cryptography is not scalable enough for that yet, though.)

An option would be to take a GSS that seperates the issuer GM and the opener GM and just throw away the opener's key. But that gives me two issues:

Firstly, the users should stay anonymous even if the GM (the server) is compromised.
Secondly, existing GSS do not actually seperate the opener's and the revoker's key, but since I need to revoke users' access rights, this is unfeasible.

Is there any such GSS that satisfies my security requirements? Are there any existing GSS that I could alter a little bit to remove the opening ability - preserving their security proof - and use? Are there entirely other options?

(The actual problem giving me headaches is more general security related and I didn't want to explain it here because it is rather complex. But if you have any further questions about my requirements, please go ahead!)

(If members "expiring" is the only reason for revocation, then you could just skip the whole "standard signature scheme" part of the following, encode the expiration dates into the IDs, and have the signers' arguments include that issue too.)

Well, there's always the generic approach:

the GM generates a common reference string for an otherwise-noninterative computationally witness-indistinguishable system that is co-sound as a stand-alone argument of knowledge; i.e., it's infeasible to give a valid argument for any statement that it would be infeasible to know a witness for
the GM chooses a function from a collision-resistant hash family
the GM generates a two inner key-pairs, one for a standard signature scheme
and one for an identity-based signature scheme
the GSS's public key is the ordered quadruple whose entries are
the common reference string and the collision-resistant hash function and the inner public keys
the GM's private key is the ordered pair whose entries are the inner private keys
the GM uses the standard signature scheme for signing [the root hash of a Merkle tree of the result of sorting the revoked identities] along with [other information, such as a date], and regularly gives out that signature along with that sorted list, similarly to how CRLs are issued in standard implementations of PKI
for users issuing and verifying signatures, let "the sro" denote the most recent version known to the signer of the previous bullet point's signature together with [the root hash ... revoked identities] and the specified other information
the GM issues for the GSS by issuing for the identity-based signature scheme
users sign by generating a key-pair for a strongly unforgeable one-time signature (OTS) scheme, choosing enough information to specify what Identity Revocation List to use, arguing knowledge of a signature on the OTS verification key by an identity and two branches through the tree witnessing that the identity is not on the list, using the OTS signing key to sign the ordered triple whose entries are the sro and the argument and the message, and letting the signature be the ordered quadruple whose entries are the sro and the OTS verification key and the argument and the OTS signature
receivers verify by verifying the signature on the sro, verifying that its "other information" is appropriate (specifically, it's date is recent enough), verifying the argument for the sro and the OTS verification key and the message, and then verifying the OTS signature

The main problem with this approach is the size of the witness-indistinguishable arguments.

If you use the modification of figure 3 in this link obtained by replacing $K_{\text{binding}}$ with $K_{\text{hiding}}$,

then the existence of a witness that the commitment key is hiding suffices for perfect anonymity.

Thus, you could have the GM keep such a witness and give
concurrent zero-knowledge proofs that such a witness exists.

There are apparently lots of identity-based signature schemes that can work in bilinear groups.

It is possible that the type of system described in this paper can be adapted to such a scheme. $\:$ Although I'm not sure, it seems likely that NIZK co-sound arguments constructed from the previous two sentences could provide the same anonymity as I mentioned in the previous paragraph.

This paper gives a NIZK protocol with whose use in this approach comes with a trade-off:

soundness is based on the generic bilinear group model (analogous to the Random Oracle Model),

but by having users verify the common reference string's structure as described on page 3,

perfect anonymity is guaranteed without needing to trust or interact with the GM.

I have not managed to come up with any scheme for what you

are asking about that does not use a non-interactive argument.


What key exchange do OpenSSL and CryptoAPI prefer by default? Here is what I know.

When I connect to a brand-new Linux Web server with Chrome and click the "lock" icon, the key exchange algorithm is described as "ECDHE_RSA". (Yes I know what that is.)

When I connect with Internet Explorer 8 on Windows 7, the key exchange is described as "RSA with 2048 bit exchange". I know what that is, too.

With Firefox, it says I am secured by "AES-256, 256 bit keys". Which is (a) redundant and (b) tells me nothing about the key exchange algorithm.

When I run openssl ciphers on my brand-new Linux machine, the output starts with:

ECDHE-RSA-AES256-GCM-SHA384:ECDHE-ECDSA-AES256-GCM-SHA384:...

(I suspect these are listed in order of OpenSSL's preference, but I do not know where this is documented.)

ECDHE stands for "elliptic curve Diffie-Hellman, ephemeral". That's great, but I want to know the actual key exchange algorithm, including the specific elliptic curve.

Here is what I really want: A big table, containing all possible pairs of SSL client and server (all versions), telling me what specific key exchange algorithm (including the actual elliptic curve) would be negotiated between them. Or enough information to construct that table.

I would settle for simply knowing how the latest versions of OpenSSL and CryptoAPI behave by default, and where this is documented.

Given a SSL-enabled web site, the Qualys SSL tester will tell what ciphersuite would be negotiated by a bunch of different browsers if they connected to that web site.  It will also tell you the list of ciphersuites supported by that server and the list of ciphersuites are supported by each of those major browsers.

For example, here is the output for one web site you mentioned elsewhere: output.  The section labelled "Handshake Simulation" will tell you what cipher suite many different major browsers would negotiate with this server.  For instance:

Chrome 29 (Win 7) would negotiate TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA over TLS 1.2;
IE 8 (Win 7) would negotiate TLS_RSA_WITH_AES_128_CBC_SHA over TLS 1.0 (which does not provide forward secrecy);
Firefox 22 (Win 7) would negotiate TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA over TLS 1.0;

and so on.  This doesn't tell you what elliptic curve they would use or the key size, but it gives you the other information you were looking for.

By testing one representative web site for each possible SSL server, you should be able to get close to the grid you want of the key exchange algorithm negotiated by all (browser, server) pairs.


Collision resistance in a hash function I'm confused about whether the following hash function is collision resistant.
$x \sqsubseteq y $ denotes that x is equal to y or x precedes y.

$ H:\{0, 1\}^* \rightarrow \{0, 1\}^n$

If $x \sqsubseteq y $ then $h(x) \sqsubseteq h(y) $

Does this mean H is collision resistant?

Does this mean H is collision resistant?

No, it cannot be collision resistant.

Consider $H(x)$ over all possible values $x \in \{ 0, 1 \}^k$ for $k \ggg n$.  There are $2^k$ possible inputs, and only $2^n$ possible outputs; furthermore, the preimages for any specific output must be contiguous.

Hence, if we consider $x$ stepping from the minimal possible value $0^k$ through consecutive values to the maximal value $1^k$, then $H(x)$ must be split up into (at most) $2^{n}$ ranges, where any two inputs in the same range will generate the same output; for those $2^k$ inputs, there are at most $2^n-1$ places where adjacent inputs produce different outputs.

Hence, if we select a random $r \in \{ 0, 1 \}^{k-1}$, and consider $H( r \mathbin\Vert 0 ), H( r \mathbin\Vert 1)$, then with high probability (at least $1 - 2^{n - k - 1}$), those two hashes will be the same, and that's a collision...


Minimum number of public and private keys depending on signature? I'm trying to make sure I understand and intuit things properly here, so I'm going to be somewhat lengthy? With this, as I did a cursory search here and couldn't find exactly the case examples I'm looking at.

As we generally know, this is how public key crypto would be working.

Asymmetric: Two key pairs on each branch, e.g., Joe and Jill must each have a public and private key.  The number of key pairs is N * (N – 1)

Symmetric:  One key per branch, e.g., Joe and Jill share a single key.  The number of keys for N managers is N*(N-1) / 2 implying exponential growth.

Our situation is as thus, and currently ignores man in the middle and other methods of attack that would require additional keys, and we, as a head of department want to communicate with (N-1) staff members and conducting a secure conversation (N total personnel including head of department, let's call them Smith)

1) If we want to send identical information to the other (N-1) using asymmetric cryptography, but also digitally sign the communication so that the other members know it's from Smith and has not been modified. Assume no compromising of keys and the message can be sent in the clear or encrypted.

--My initial thought is, let's say we have 10 personnel including Smith (N=10). Based on the above formula, that is 10*9 or 90 public/private key pairs, however we're going to digitally sign: do I need to just add 10 to the total, or is there something else?

2) The personnel (N-1) must be able to send information back to Smith using asymmetric; assuming the keys are known only to members of the group, how many public and private keys must exist? In this case, Smith does not need to verify the actual identity of the member sending the message. The actual message must be encrypted and all messages should be private with respect to all other members of the group, i.e., no member of the group can read another members messages to Dr. Cooper.

--On this, I want to assume that, it's 9*8, so there would be a lack of need for the key pair from the 10th (Smith) because they're only sending information back to him.

3) The (N-1) members of the group must be able to send information to Smith using asymmetric cryptography. Assuming the keys are only known to member of the group, what is the minimum number of private and public keys to accomplish the task? Smith must be able to verify the identity of each group member sending a communication.

--Again, I'm thinking the same formula of N*(N-1) is still necessary, but I also feel that it needs modification for Authentication and non-repudiation, only I've been unable to find clear information regarding this.

4) The (N-1) members of the group must be able to send information to the Smith using symmetric cryptography.  Assuming the keys are only known to appropriate members of the group, what is the minimum number of symmetric keys to accomplish the task?  Smith must be able to verify the identity of each group member sending a communication and verify each message has not been modified using the digital signature of the message hash.

--This one is a bit different; let's assume our actual N is the N-1, so 9. 9(9-1)/2 or 9*8 = 72 / 2 = 36 keys.

Long story short, what might I be missing?

I'm having a little trouble following your reasoning. I think your difficulty comes from an invalid initial assumption.

  Asymmetric: Two key pairs on each branch, e.g., Joe and Jill must each have a public and private key. The number of key pairs is N * (N – 1)

No! It is in fact the main advantage of public-key cryptography that each participant only needs one pair of keys. For $N$ participants, the number of key pairs is $N$.

More precisely, each participant needs one pair of key for each purpose. Using the same keys for encryption and for signature can be ok, but it can also lead to trouble for various reasons:

It can lead to protocol errors where a participant is tricked into signing something, but the thing in question was encrypted with the corresponding public key, and the signature reveals all or part of the content because the signature operation uses the same key that the decryption would.
Conversely, a participant may be tricked into decrypting something, and the result may be used to forge a signature.
Decryption and signature keys typically have different retention policies: you shouldn't keep signature keys around when you want to stop using them, but you often need to keep decryption keys for a long time to decrypt old messages.

Still, that's only two pairs of keys per participant if each participant both signs and decrypts messages. The point is that the number of keys does not grow super-linearly with the number of participants.

  1) If we want to send identical information to the other (N-1) using asymmetric cryptography, but also digitally sign the communication so that the other members know it's from Smith and has not been modified.

When Alice sends a message, she encrypts it $N-1$ times, once with each recipient's encryption public key. Each recipient will decrypt their copy with their decryption private key. Alice signs the message only once, with her signature private key. Each recipient will verify the signature using Alice's verification public key.

That's a total of $N$ key pairs: $1$ signature key pair and $N-1$ encryption key pairs.

  2) The personnel (N-1) must be able to send information back to Smith using asymmetric; assuming the keys are known only to members of the group, how many public and private keys must exist? In this case, Smith does not need to verify the actual identity of the member sending the message.

For $N-1$ participants to send encrypted data to Smith, only one key pair is necessary: the senders encrypt with Smith's encryption public key, and Smith decrypts with his own decryption private key.

  3) The (N-1) members of the group must be able to send information to Smith using asymmetric cryptography. Assuming the keys are only known to member of the group, what is the minimum number of private and public keys to accomplish the task? Smith must be able to verify the identity of each group member sending a communication.

Each of the $N-1$ senders signs their own message with their own signature private key. Smith verifies using the sender's verification public key.

  4) The (N-1) members of the group must be able to send information to the Smith using symmetric cryptography. Assuming the keys are only known to appropriate members of the group, what is the minimum number of symmetric keys to accomplish the task? Smith must be able to verify the identity of each group member sending a communication and verify each message has not been modified using the digital signature of the message hash.

Here, $N-1$ symmetric authenticated encryption keys are needed, or $2 (N-1)$ if you count encryption keys and authentication keys separately. There's the AE key that Alice shares with Smith, the AE key that Bill shares with Smith, the AE key that Charlie shares with Smith, etc.


How can I avoid calculating with huge numbers when implementing the RSA algorithm There is 26-letter English alphabet.

There is the plain text: TRYAGAINLATER.
I need to encrypt it by RSA algorithm with the public key 53.
What is the ciphertext?

Therefore:
M = TRYAGAINLATER,
M=19 17 24 0 6 0 8 13 11 0 19 4 17.

Encryption: $c = m^e \pmod n = m^{53} \pmod{26}$

The problem is that $m^{53}$ is huge number. How can I avoid this?

$\def\Z{\mathbb Z}$Usual (i.e. real life) RSA works with huge numbers, not with small numbers like 53 and 26. (The numbers there are, for example, 1024-bit numbers for the lowest acceptable security level nowadays.)

But anyway, the core mathematic operation behind RSA is modular exponentiation - you exponentiate not in the ring of integers $\Z$, but in the modular ring $\Z/_{n·\Z}$ (where $n$ is the modulus). You get the same result by exponentiating in $\Z$ and then reducing, or by reducing after each multiplication step ... and the latter avoids the overhead of really huge numbers.

So, you calculate $c = (…((m · m \bmod n) · m \bmod n ) · … · m \bmod n)$, such that each intermediary result is a number smaller than $n$, instead of calculating the huge number $m^e$ directly.

(This is the naive exponentiation, which takes $e$ steps - there are faster algorithms which only need around $\log_2 e$ steps, like square-and-multiply.)

But your example is faulty, too - the public exponent is normally a number smaller than the modulus (which is a part of the public key, too, and actually the more important part).


Ciphering the output of a password hash In an article on password hashing security, Anthony Ferrara suggests using bcrypt to hash passwords and then using a "strong cipher (AES-128-CBC) with a key rotation policy".

This seems like a good suggestion which would help to counter ASIC attacks on bcrypted passwords. However, this could be circumvented if the secret key (or key rotation system) was compromised along with the password hashes.

The Question:

is the suggestion to cipher the password hash a good one, or could it actually weaken security?
would it be appropriate to use a public key cryptography algorithm like RSA, generate a public and private key pair, and then 'throw away' the private key to prevent the ciphertext from being reversed?

Q1 : It won't weaken things assuming a few things. Normally storing cipher text is at worst equivalent to storing plaintext. Encryption is invertible. That means no information is lost in the process. It's not different, in that sense, from storing data in a different format. (Raw bytes, base64 encoded text, hexadecimal, etc.)

The assumptions are:

The cipher implementation is bug-free. (No guarantee that something doesn't go wrong in some way if encryption can go wrong in some known or unknown ways.)
The key is independent of inputs or personal data. (If a key is derived from the password or personal data, then cracking the key means that data gets leaked. Use a randomly generated key.)
No side channels. (Implementations of an algorithm can leak  plaintext or keys.)

Q2 : That defeats the purpose of encrypting hashes. If you don't have the private key then you cannot rotate keys. This also isn't going to help if people who can crack your passwords have access to the public key.

With the ciphertext, $E_K(H(\text{salt}, \text{password})$, and public key, $K$, the strategy for cracking the encrypted hashed password is about the same as the strategy for cracking hashed passwords.

Normally password cracking is done by generated candidate passwords and testing if
$$ H(\text{salt}, \text{password}) = H(\text{salt}, \text{candidate)}$$

Cracking encrypted passwords with known public key K instead tests

$$ E_K(H(\text{salt}, \text{password})) = E_K(H(\text{salt}, \text{candidate)})$$

I assumed the public key encryption method is deterministic. (Or if it includes a IV that value is known, making it deterministic.) If you cannot decrypt the data then you must have determinism because that leaves only comparing ciphertexts as a possible means of verifying passwords.

The intuition behind using public key encryption here is that it means the password cracker cannot decrypt encrypted data and that the encrypted password hashes are therefore no good to him. That's wrong because the public key (if it becomes "public" or at least known to the cracker) enables him to do, on his own computer, whatever the server does for verifying passwords.

Strong asymmetric encryption with a public key after deleting the private key will act like a one way function, just like hashing. You can compute $H(x)$ but not $H^{-1}(x)$. Similarly you can compute $E_K(x)$ with public key $K$ but not $E_k^{-1}(x)$ without $k$, the private key corresponding to the public key $K$. A password cracker does not need the ability to compute the inverse operation. It suffices to use the forward (one-way) function and compare his result to stored data.

(Also, there are scenarios where I wouldn't worry about symmetric ciphers inadvertently having side channels, but I might worry about public key side channels. If, for example, it didn't have a constant time implementation or if attacks requiring physical proximity were a concern.)

Should you encrypt password hashes?

It shouldn't (and probably won't) hurt. It's a plus to be able to rotate keys.

One "helpful" (odd) scenario: Your password database gets stolen, then your encryption key. You find out so you tell your users to change their passwords. The hacker gets your password database again (but not your encryption key for some reason) and wants to crack new passwords. The new password database isn't useful then.

If you're using a typical database it also helps to encrypt data before it goes into the database. If you delete or modify rows, then that doesn't necessarily mean the data disappears from the hard drive. It will disappear from database dumps, but instead of overwriting the space where data used to reside with zeros it might set a "deleted" bit flag or simply change what address a pointer points to. With encrypted data you can do a sort-of-delete of arbitrarily long ciphertext simply by overwriting the key used to encrypt it. It's good to encrypt your hard drive for the same reason.

It's best if you can store your key in a HSM. This means if your password database gets leaked it won't be possible to do offline cracking.

If a hacker can bypass your password check rate limit or is able to execute arbitrary code on your server, however, then he can still do online cracking or use your server for cracking passwords.

Maybe if you have a second server you can implement a kind of poor man's HSM. Use the first server as your front facing web server, allow the public internet to access it. Use your second server to verify passwords on behalf of the first. Do not allow access from the public network to the second server. The second server can store salts and hashes but only return salts in response to a user-id or true/false in response to a hash. It can do rate limiting on verifications against individual user-ids.


Replay attacks and LWE Just a small question. Since in LWE the error is rather small, is there a problem with replay attacks? What I mean is that if we use the typical scheme of Regev [1] to encrypt a vector m, but this vector is sent, e.g. 1000 times, then an eavesdropper may perform a simple voting scheme to approximate the original message. Am I losing something?
References:
[1] Regev, Oded. "On lattices, learning with errors, random linear codes, and cryptography." Journal of the ACM (JACM) 56.6 (2009): 1-40.

By looking the encryption procedure, you will see that we use a different sum of the vectors $\vec a_i$'s at each encryption. Thus, every ciphertext has the form
$$(\vec a, ~\vec a\cdot \vec s + e + \frac{p}{2} \cdot m)$$
with different terms $\vec a \in \mathbb{Z}_p^n$ and $e \in \mathbb{Z}$.
Notice that the probability that two ciphertexts have the same term $\vec a$ is already around $1/p^n$ (exponentially small), and the chance that you will see ciphertexts with the same pair $(\vec a, e)$ is even smaller.
Therefore, your attack does not work.
About the relation with LWE
You said that you are "not trying to break LWE", but this scheme is CPA-secure under the assumption that the LWE problem is hard. Thus, even if you are not trying to solve the LWE problem directly, your attack would provides us with an algorithm for the LWE problem (because your attack satisfies the CPA-security game, since you are only using an encryption oracle). This is basically what Lemma 5.4 of this paper is saying:

[...] if there exists a polynomial time algorithm $W$ that distinguishes between encryptions of 0 and 1 then there exists a distinguisher $Z$ that distinguishes between $A_{\vec s,\chi}$ [the LWE distribution] and $U$ [the uniform distribution] [...]


TLS re-negotiation vs resumption Please explain the difference between TLS re-negotiation and resumption.

My understanding is as follows: in the context of TLS 1.2, re-negotiation and resumption look the same, but the former can be started with either a HelloRequest/ClientHello from server/client while the latter can start with just with ClientHello from the client. In both cases, a client-server dialog followed by an abbreviated handshake occurs (or not ?), security parameters do not change, and new keying materials are recalculated using an "old" pre-master secret with new random numbers.

From the record layer point of view, all re-negotiation/resumption messages  should be processed using "current record state"-- which means they are encrypted/authenticated using "current" keys.

Re-negotiation may happen in the middle of an existing session, a "session ticket" or "session Id" are not required to find "current state parameters", just 5 tuple may be used to look for proper running session context. ( is it true ?)

Moreover, resumption may happen even after actual connection has been closed (is it true? ) and we need sessionTicket or sessionId to look for security parameters and DO decryption, BUT the ClientHello message itself is encrypted.
How is this solved for TLS1.2 ?

In the context of TLS1.3, renegotiation is done by using KeyUpdate message, and is clearly described by draft, but resumption has the same issues.
How is resumption solved for TLS1.3 ?

Re-negotiation may happen in the middle of existing session, "session
  ticked" or "session Id" are not required to find "current state
  parameters", just 5 tuple may be used to look for proper running
  session context.

Yes.

  [...]BUT ClientHello message itself is encrypted. How this is solved for
  TLS1.2 ?

The ClientHello on an abbreviated handshake is in fact not encrypted. The message flow for an abbreviated handshake goes roughly as follows: Client sends unencrypted ClientHello, Server responds with ServerHello, ChangeCipherSpec and Finished message and client answers with ChangeCipherSpec and Finished message and application data. Also see page 37 of RFC 5246.

  in both cases client-server dialog follow abbreviated Handshake

No, only for session resumption the abbreviated handshake is used, for renegotiation a full handshake is performed.

  In opposite resumption may happen even after actual connection has
  been closed

Yes.

  In context of TLS1.3 renegotiation is done now using KeyUpdate message
  and clearly described by draft, but resumption has the same issues.
  How resumption is solved for TLS1.3 ?

Section 2.2 of the TLS 1.3 draft (-23) talks about the session resumption protocol flow. Section 4.6.1 talks about how the ticket mechanism works in detail. Section 4.2.11 talks about how the tickets are used in the Hello Messages. It turns out that the client may offer the server multiple PSK identities in the (cleartext!) ClientHello of which the server selects and thus "consumes" at most one and indicates which in its ServerHello message.


What is the advantage of CFB over OFB? I was wondering if CFB can be better than OFB in any ways. I would like to know in what cases one would use CFB over OFB.

The only reason I can imagine why one would prefer CFB over OFB or CTR is error propagation. Another reason may be technical issues with the relieability of the transmission line.

This comes from the fact that if you flip a single bit in an OFB ciphertext then you only get the same bit flipped in the underlying plaintext. But if you flip a single bit in CFB mode, you get the bit flipped in the plaintext and get the following block to decrypt to gibberish. So there's a larger chance of you detecting a manipulation of the ciphertext because the effect on the plaintext is bigger.

However the above reason stems from the dark ages of cryptography, where authenticated encryption was usually done ad-hoc or not at all, so people actually relied on these error propagation properties. These days, using anything but CTR is pointless, because CTR allows very nicely for SIMD parallelization and error propagation as a property is kinda irrelevant because the authentication tag will catch any modifications.


Password entropy much lower than entropy of encryption keys. Why is this acceptable? When talking symmetric encryption, a 56 bit key is known to be so weak. If you use it for your encryption, you are considered a goner.

When talking passwords however, the standard these days is about 8 characters selected from about 94 characters on the keyboard. This translates to about $94^8$ possible passwords, which means about 52 bits of entropy.

Now, 52 bits is obviously less than 56 bits. But somehow a 56 bit key is considered weak while a 52 bit password is considered safe (i.e., many systems force you to use the 8 characters). Why is this so; I mean why are the standards lower when we talk passwords yet both passwords and keys are subject to the same kinds of brute-force attacks?

I know that humans would find it impossible to maintain a 128 bit password -- however, I wonder if there is some technical reason why a 52 bit password would not be as weak as a 52-bit encryption key for that matter.

I know that humans would find it impossible to maintain a 128 bit password -- however, I wonder if there is some technical reason why a 52 bit password would not be as weak as a 52-bit encryption key for that matter.

First, I would argue that 128 bits is not impossible to remember. My current password manager master password is almost 100 bits (6 words from a large dictionary) and I could increase it to 128 bits if I wanted to by tacking a couple of extra words at the end.

However, yes, there are reasons passwords with much less entropy are often considered acceptable:

It is good practice to use a good password hash that slows down attacks to a similar degree as e.g. an extra 20 bits of entropy would.
Many uses of passwords do not allow an offline attack with as much computing power as the attacker has. E.g. a login password on a website can only be attacked online, usually with a strict rate limit. (Until the password hashes are stolen.)
Two-factor authentication is seeing some use. With it finding the password alone is insufficient.

When some of the above factors do not apply you need to make sure you have enough entropy. E.g. a "brainwallet" Bitcoin password does not benefit from 2. or 3. so it should have at least the 50+ bits so that a password hash makes attacking it too expensive to be worth the effort.


IVs in WEP encryption First, I'm pretty new to the world of encryption. As I understand it, in WEP, the plaintext and CRC are XOR'd with the IV and the key (or more accurately, the key/stream, which is produced by a pseudo-random generator) to get the resulting ciphertext.

Basically, given two different messages encrypted with the same IV and key, an attacker can XOR both ciphertexts and soon reveal the plaintext.

So, why is the IV sent in plaintext with the message? When the attacker knows the IV, isn't it easier to work out the key and decrypt the messages?

Generally, the security contract for a cipher involving an IV or nonce does not require the IV/nonce to be secret, for the cipher to provide any security.  Not only is there no need to keep the IV/nonce secret, but it often provides negligible additional security to do so, and it often enhances security to use a (public, observable) message sequence number as a nonce.

However, it's anyone's guess what ‘design’ might have gone into WEP, and certainly it had no input from any competent cryptographer, who might have alerted them to the stupidity of their design and to the fact that RC4 was $55v$1@mhadg.production.compuserve.com>, 1994-09-15.">broken within 48 hours of its publication, not to mention the plethora of other ways it has been found to broken since then because people kept using it in protocol after protocol despite being broken.

You could change one small part of WEP's cryptography at a time, and the rest would be just as much of a disaster; the only thing to be done with it is to throw the whole thing out and start over.


What is the maximum size of the plaintext message for RSA OAEP? OAEP is an important technique used to strengthen RSA. However, using OAEP
(or any technique that adds randomness) reduces the size of plaintexts that can be encrypted.

Assume for instance that OAEP is using a 160-bit seed and a hash function that produces a 256-bit value. In that case, how large a plaintext can be handled when RSA is used with 2048-bit key?

The input length of OAEP is directly specified in the standard:

M        message to be encrypted, an octet string of length mLen,
         where mLen <= k - 2hLen - 2

or simply mLen = k - 2 * hLen - 2 if we want to calculate the maximum message size.

Where:

k - length in octets of the RSA modulus n
hLen - output length in octets of hash function Hash
mLen - length in octets of a message M

The key size of RSA is defined as the number of bits within the unsigned modulus representation. So the key size is identical to the modulus size in bits.

So to complete the calculation we have to include k = ceil(kLenBits / 8) where kLenBits is the key size in bits. This can be rewritten as k = (kLenBits + 7) / 8 for integer-only calculations. However, since kLenBits is commonly limited to multiples by eight k = kLenBits / 8 usually suffices.

The same goes for hLen which is practically always the hash output in bits - say hLenBits divided by 8. From here on all calculations will be in octets / bytes.

To calculate the maximum payload of RSA OAEP we then substitute the nLen and hLen by their respective calculations (and <= by = because we're looking for the maximum):

mLen = k - 2 * hLen - 2

becomes

mLen = kLenBits / 8 - 2 * hLenBits / 8 - 2

If we observe this we see that the amount of overhead only depends on the hashlength: 2 * hLenBits / 8 - 2. This makes it easy to write out the possibilities for SHA-1, SHA-2 and SHA-3:

\begin{array} {|l|c|c|}
\hline
\text{HASH} & \text{OVERHEAD} & \text{RSA 1024} & \text{RSA 2048} & \text{RSA 3072} & \text{RSA 4096} \\
\hline
\operatorname{SHA-1} & 42 & 86 & 214 & 342 & 470 \\
\hline
\operatorname{SHA-224} & 58 & 70 & 198 & 326 & 454 \\
\hline
\operatorname{SHA-256} & 66 & 62 & 190 & 318 & 446 \\
\hline
\operatorname{SHA-384} & 98 & 30 & 158 & 286 & 414 \\
\hline
\operatorname{SHA-512} & 130 & \text{N/A} & 126 & 254 & 382 \\
\hline
\end{array}

note that SHA-1 has an output size of 160 (or hLen = 20 in PKCS#1). Probably better to simply include the calculation in your source code if the function to calculate the maximum input size is missing from your crypto library. Of course you want to avoid 1024 bit RSA; I've added it just for when backwards compatibility is required.

Great so now we can finally fill in the numbers as kLenBits = 2048 and hLenBits = 256:

mLen = 2048 / 8 - 2 * 256 / 8 - 2 = 256 - 64 - 2 = 190

so the message has a maximum size of 190 bytes.


Does using crypto_stream_xor allow listeners to forge crypto_secretbox messages? I understand that NaCl's crypto_stream and crypto_stream_xor don't do any authentication like crypto_secretbox does. Does using them allow listeners to forge crypto_secretbox messages for any key you use them with?
I'm worried about a known plaintext attack. If I use crypto_stream_xor to encrypt a bunch of zeroes, the listener now has the full keystream for whatever nonce I just used. I think they can use the first 32 bytes of that as a crypto_onetimeauth key to forge valid authenticators for crypto_secretbox messages, with whatever plaintext they want (up to the length of the zeroes I encrypted, minus 32).
If that's right, then using crypto_stream_xor seems to break authenticity just as badly as nonce reuse does. The NaCl/libsodium documentation is pretty clear about saying "never reuse a nonce with the same key", but there's nothing in there about "never use crypto_stream_xor with a key that you also use for crypto_secretbox."

crypto_secretbox uses the first 32 bytes of XSalsa20 output as the key for Poly1305. Thus you are correct that using crypto_stream_xor on a known plaintext will reveal the authentication-key used by crypto_secretbox, allowing forgeries under that key and nonce.

Not using a key for multiple purposes is a general crypto design principle. Perhaps that's why the authors of NaCl didn't think of explicitly warning about this pitfall.


Explaining RSA to the people Alright so I have some understanding of encryption and how it works. I was trying to explain it to my friend and a few others I couldn't at the time. I later came up with an analogy.

How accurate is this without getting too in depth

Dale, Sam, and Max are all sitting in a class room at their desks
[Dale]---[Sam]---[Max]

Dale wants to send a message to Max. Max knows this so he takes a pencil and breaks it in half handing Dale the tip so he can write the message. Max then keeps the eraser. Dale is to far away to send his message to Max so he has to send it through Sam. Dale doesn't want Sam to read the message. Dale writes his message "Hi Max" he also takes 2 random letters and mixes them in with his message so it reads "qMaxHiD" he then passes the message to Sam to pass to max. Sam then passes the message to Max. Max's special eraser only erases the random letters. So that he can read message." Max would like to reply but he only has an eraser so he can't. So Dale takes a pencil and breaks it in half and sends the tip to Max so that he can send his message.

From Sam's perspective he sees a bunch of random letters "qMaxHiD" he tries to read the message by scrambling the letters until he reads "Hi Max" since their aren't many random letters it's fairly easy for Sam to do this. there are only 5,040 combinations this will take some time for max to do but if he can 100 combinations in a minute it will take Sam about 50 minutes to read the same. Knowing this Dale could add one more random letter bringing the possible combinations to 40,320 taking Sam 6.72 hours to read and making it so the Max only has to erase one more letter. Encryption works because it's easy to erase one letter but really hard to go through all the combinations.

-The pencil is the keypair
-Sam is both the internet the message travel through and uncle same trying to read it
-Having a bigger pencil with more lead allows you to write more random letters to mak

Does this analogy work. Could I improve on it.

How about this (and, at this level, it's not specific to RSA, but is equally analogous to any public key encryption method):

Max makes a safe with a slit on the top.  Max made the safe, so he knows the combination, but no one else does.  He gives the safe to Sam, who gives it to Dale.  Dale writes his note, and inserts it into the safe.  He gives the safe back to Sam.  Now, Sam can't open the safe, so he gives it to Max.  Max uses his combination to open the safe and read the note.

The nice thing about this analogy is that it captures some of the real concerns from a straight-forward use of public key crypto:

How does Dale know that the safe he was handed was actually made by Max?  That's quite valid, and is also a concern with public key cryptography.
What if Sam inserts his own message into the safe?  That's also a valid concern with public key crypto; as designed, Max has no way of knowing who wrote the message.

Both of these can be addressed, however that's a deeper topic.

(And, I'm pretty sure I read this somewhere, but I don't remember where...)


Decrypt simple CBC with XOR I have searched and my problem is exactly the same as shown here:

Decrypt simple CBC message with known IV using XOR encryption

However, when I implement the solution it doesn't work, neither does my own solution.
I will restate the problem:

I've been given a ciphertext message, encrypted using CBC. I know that the block size is 12 bytes and I know the plaintext value of the first block.

I also know that the encryption function is a simple XOR:

Ci=K⊕(Mi⊕Ci−1)
where C0=IV.

My (incorrect) solutions, programmed in Java:

Terminology:
"encrypted" is a byte-array holding the ciphertext
"decrypted" is a byte-array holding the recovered plaintext (decrypted cipher)
"first_block" is a byte-array holding the decrypted first block (which is the IV)
"key" is a byte-array, which will hold the key after it is recovered
^ is the java expression for XOR

The IV is known

attempt 1, using my own imagination:

// corresponds to K = IV (+) C0, where C0 = K (+) IV

for (int i = 0; i < 12; i++)
    key[i] = (byte) (first_block[i] ^ encrypted[i]);

// corresponds to K (+) Ci (+) Ci-1

for (int i = 12; i < 24; i++)
    decrypted[i] = (byte) (key[i-12] ^ encrypted[i] ^ encrypted[i-12]);

Result: I decrypt the first block of twelve, which is the IV that I already know, but the second block is just gibberish

attempt 2, using the information gotten from the previous question linked above copied:

//K = C0 + C1 + M1

byte[] key = new byte[12];
for (int i = 0; i < 12; i++)
    key[i] = (byte) (encrypted[i] ^ encrypted[i+12] + first_block[i]);

// Mi = K + Ci + Ci-1
byte[] decrypted = new byte[encrypted.length];

for (int i = 12; i < 24; i++)
    decrypted[i] = (byte) (key[i-12] ^ encrypted[i] ^ encrypted[i-12]);

Result: Still just gibberish, but different gibberish that I got above

What I'm looking for: Any kind of help

So, you are dealing with CBC decryption:

(image from Wikipedia)

What you want to do, is firstly to compute the key $K$ used by the block cipher at hand, since yours is a plain XOR, you can compute the key by XORing the ciphertext, the IV and the plaintext:
$$K=C_0\oplus M_0 \oplus IV$$

Next, once you've got your key, you can apply the CBC decryption, by XORing the key with the ciphertext block at hand and XORing the result with the previous ciphertext block to get the current plaintext:
$$M_i=C_{i}\oplus K \oplus C_{i-1}$$

Now, I do not see the whole code, but it seems strange that the IV is given as the first plaintext block.

If you were given: 1 block of known plaintext, 1 block of IV and 2 blocks of ciphertext, then you would be able to decrypt the second block of the ciphertext using the method I described above...

But there is something strange with your statement:

  "first_block" is a byte-array holding the decrypted first block (which is the IV)

So, the decryption of the first block is the IV? Are you sure? Because this amount to having a all 0s first plaintext block then you have that:
$$C_2 = (K\oplus IV) \oplus (M_2 \oplus K) = IV \oplus M_2$$
and so have a second block which is just an XOR of the IV and the second block plaintext, which defeats the purpose of CBC mode.

Which means you could simply decrypt your second block by XORing the second ciphertext block with the IV, since the key already canceled out, and the "chaining" doesn't apply because the first message is all 0s.

Notice that anyway, doing CBC mode with an XOR with a fixed key $K$ as an block cipher actually cancels the key $K$ for all  odd blocks:
$$\begin{aligned}
C_0 &= K \oplus M_0 \oplus IV  \\
C_1 &= K \oplus M_1 \oplus C_0 = K \oplus M_1 \oplus K \oplus M_0 \oplus IV =   M_1 \oplus M_0 \oplus IV   \\
C_2 &= K \oplus M_2 \oplus C_1 =K \oplus M_2 \oplus M_1 \oplus M_0 \oplus IV \\
C_3 &= K \oplus M_3 \oplus C_2 = M_3 \oplus M_2 \oplus M_1 \oplus M_0 \oplus IV \\ \cdots
\end{aligned}$$

This can also help you.


Computing the padding of MD5 So I'm reading this question to learn more about length extension attack, and I want to make sure I understand the basics of padding.

It says in the post that given the hash and the length of the message, I can easily compute the padding.

Now, from what I understand, each block will always be 512 bits, or 64 bytes.

So does this mean if I have a message that says "LengthExtensionIsSuchAnInterestingConcept", which has a length of 41, it occupies 41 bytes. (Looked at some other posts, ASCII character is 1 byte per character. please correct me if I'm wrong.)

64 - 41 = 23 bytes, so the padding will be 23 bytes. And the entire MD5 in this case will only consists of one block.

Am I correct in my understanding above?

That's correct.  Here are the padding instructions from RFC1321, the MD5 spec:

3.1 Step 1. Append Padding Bits

   The message is "padded" (extended) so that its length (in bits) is
   congruent to 448, modulo 512. That is, the message is extended so
   that it is just 64 bits shy of being a multiple of 512 bits long.
   Padding is always performed, even if the length of the message is
   already congruent to 448, modulo 512.

   Padding is performed as follows: a single "1" bit is appended to the
   message, and then "0" bits are appended so that the length in bits of
   the padded message becomes congruent to 448, modulo 512. In all, at
   least one bit and at most 512 bits are appended.

3.2 Step 2. Append Length

   A 64-bit representation of b (the length of the message before the
   padding bits were added) is appended to the result of the previous
   step. In the unlikely event that b is greater than 2^64, then only
   the low-order 64 bits of b are used. (These bits are appended as two
   32-bit words and appended low-order word first in accordance with the
   previous conventions.)

   At this point the resulting message (after padding with bits and with
   b) has a length that is an exact multiple of 512 bits. Equivalently,
   this message has a length that is an exact multiple of 16 (32-bit)
   words. Let M[0 ... N-1] denote the words of the resulting message,
   where N is a multiple of 16.


Trying to udnerstand textbook sample solution I am preparing for the final exam in my Data Security class so I am trying to read and understand the textbook's exercise questions. The sample solution at the end the textbook is more like a hint instead of being a step-by-step solution.

Question:

Textbook solution: Yes. They are equivalent.

My answer: I do not know to check if some scheme is equivalent to RSA. So I tried to verify $D$.

Step 2:
$(P-1)(Q-1) - 1 = (PQ -P-Q+1) - 1 = (N -P-Q+1) - 1 = (N-(P+Q-1) - 1 \equiv 0 \ (mod \ E)$

Step 4: $DE = (P-1) (Q-1) (E-1) + 1 = (PQ - P-Q + 1) (E-1) + 1 = (N - P-Q + 1) (E-1) + 1 = NE-N-E(P+Q-1) + 1$

Take $(mod \ E)$ of both sides:

$[DE = NE-N-E(P+Q-1) + 1] \ (mod \ E)$

$0 \ (mod \ E) \equiv 0 - N - 0 + (P+Q-1) + 1 \ (mod \ E)$

$0 \ (mod \ E) \equiv - (N - (P+Q-1)) - 1 \ (mod \ E)$

$0 \ (mod \ E) \equiv  0 \ (mod \ E) \leftarrow$ verified $D$ is correct.

But obviously this is not a concrete reasoning on why this scheme is equivalent to RSA. Any hints would be appreciated.

You are correct; your "proof" is invalid; even if you show that $d$ is the correct value modulo $e$, that doesn't immediately imply that it is the correct value.  If you replace $d$ with $d+e$, that is also is correct modulo $e$, but is also obviously wrong (it is even).

Instead, here is a better line of reasoning:

Two integers $d, e$ work as the private, public exponents modulo a product of two primes $pq$ iff both the following hold:

$$de \equiv 1 \pmod{p-1}$$
$$de \equiv 1 \pmod{q-1}$$

What you need to show is:

That $d$ as specified in the above formula is actually an integer; that is, that $(p-1)(q-1)(e-1)+1$ is a multiple of $e$
That $de \equiv 1 \pmod{p-1}$
That $de \equiv 1 \pmod{q-1}$

None of these three should be difficult to prove.


Why does solving the underlying polynomial system "break" the multivariate cryptosystem I was wondering why exactly does solving a polynomial system (directly or indirectly) "break" a multivariate cryptosystem as a digital signature.

I realize that the exact reason differs from system to system, but in general, from what I can see, it then allows attackers to sign messages with a private key that is not theirs. Am I on the right track here?

Multivariate cryptographic schemes that perform digital signatures like HFEv, FLASH and Quartz have something in common. As opposed to enciphering data like in a normal cryptosystem where a public multivariate polynomial $P(X)$ is given as:
$$P(X) = P(p_1(x_1,\ldots,x_n),\ldots,p_n(x_1,\ldots,x_n))$$
You input the plaintext bits $x=(x_1,\ldots,x_n)$ into $P(X)$ right? Well when dealing with digital signatures we do the opposite. This is, as we are the owners of the construction, given $Y=H(m || salt)$ where $m$ is a message, we can find the plaintext tuple that sends $X$ to $Y=H(m || salt)$ by inverting the construction:
$$X=P(Y)^{-1} = S^{-1} \circ \varphi^{-1} \circ F^{-1} \circ \varphi \circ T^{-1}(Y)$$
which clearly yields $X$ such that $P(X)=Y$. Now Alice sends the tuple $(m,salt, Y,X)$ and Bob verifies as $P(X)=Y=H(m||salt)$.
Thus if Eve wants to forge digital signatures to trick Bob into thinking she's Alice, Eve must solve either the $\mathcal{MQ}$-Problem or the Isomorphism of Polynomials ($\mathcal{IP}$) which both are reasonably hard.


computational complexity class of decryption of AES I haven't really seen what computational complexity class of decryption of AES is. Can anyone provide reference papers or answers here?

The time of AES encryption/decryption in any of the standard modes like CBC or CTR or GCM is polynomial (more precisely, linear) in the size of the message.

Proof: One call to the AES encryption/decryption function takes some constant number of steps, which we can represent with the constant $c$.  For example, AES-128 makes one call to the key schedule to generate the round keys, one 'whitening' step with a round key, and then 10 calls to the round function, which itself takes a constant number of simpler steps - 16 parallel applications of the S-Box, one 'ShiftRows' transposition of bytes, 4 parallel applications of the MixColumns linear function (absent in the last round), and one AddRoundKey step.  AES-192 and AES-256 similarly make constant numbers of calls to the round function.

For any of the standard modes and a message of bit-length $\ell$, the number of calls to the AES encryption/decryption function is some linear function, $f(\ell)$.  For example, the cipher-call function for CTR is: $f^{CTR}(\ell) = \lceil \frac{\ell}{128} \rceil$.

Sometimes these modes have to do other things than make calls to the block cipher (e.g. GCM has to do one finite field multiplication per 128-bit message block), but in the standard modes these are also always linear or constant in the length of the message.  Let's say the function $g(\ell)$ returns the number of 'extraneous' (non-AES) steps as a function of the message length.

Therefore, the encryption/decryption time for AES in any of the standard modes is some linear function of the length of the message, $c \cdot f(\ell) + g(\ell)$.


More suitable Substitution Box Can anyone suggest me any fast searching method or algorithm to find best S-Box among a big number of S-boxes? For example; if I have 100 different S-boxes, I want to pick that one which is more secure than the others.

There is no such specific algorithm to find the best S-box but you can construct a Diference Distribution Table(DDT) like this and check out the values in it .A DDT is a matrix containing input differences as rows and corresponding output differences in column.

A better S-box has-
1- Lower values in its DDT
2- Less occurence of higher or highest value


Security of RSA variants with $e=n-2$ and $e=n$ RSA as defined by PKCS#1v2.2 allows public exponent $e=n-2$. And textbook RSA was born with $e=n$ (see second bullet here).
Are these variants essentially as secure as (textbook) RSA with fixed $e$? With random $e$? Can we reduce the security of one to the security of the other, or of another variant of RSA?

Note: as in RSA with fixed $e$, we choose $p$ and $q$ large random distinct secret primes. And further:

for $e=n-2$, it must hold $\gcd[q-2,p-1]=1$ and $\gcd[p-2,q-1]=1$ ;
for $e=n$, if must hold $\min(p,q)$ does not divide $\max(p,q)-1$.

Rather obvious, but does answer one of the questions: both can be reduced to the security of RSA with $e' = a_n n (n-2)$ for any (reasonably sized) public integer $a$ which can be a function of $n$. For example, given $c \equiv m^n$ for a random unknown $m$, we solve $c^{n-2} \equiv m^{n(n-2)}$ for $m$. With probability at least $1/gcd(e,\lambda(n))$ the answer will be $m$.


Why is OpenSSL generated 256-bit AES key 64 characters in length? This might be a noob question, but I couldn't find its answer anywhere online: why does an OpenSSL generated 256-bit AES key have 64 characters? The command I'm using to generate the key is:

$ openssl enc -aes-256-cbc -k secret -P -md sha1
salt=E2EE3D7072F8AAF4
key=C94A324B7221AA8A8760DA0717C80256EF4308EC6068B7144AA3BBA4A5F98007
iv =5C7CB13DBDA69B2C091E0D5E95943627

I thought I could just read the key string and base64 decode it to get a 256-bit AES key, but that didn't work because 64 characters turned into a 384-bit byte array after decoding.

/* read keyString from config... */
byte[] secretKey = Base64.getDecoder().decode(keyString);
Preconditions.checkArgument(secretKey.length == 32,
            "Length of secretKey is %s-bit instead of 256-bit: %s",secretKey.length * 8, config.getSecretKey());
SecretKeySpec secretKeySpec = new SecretKeySpec(secretKey, "AES");

If I'm doing math correctly, a 256-bit key should be 41 characters in length after base64 encoding. Am I missing something obvious here?

The key is hexadecimal. So every two characters makes up one hexadecimal byte, which brings the length down to 32 actual bytes. There are 8 bits per bytes, so 8*32 = 256.


repeatedly hashing result and using reverse sequence as RNG secure? I want to have a source of randomness for which:

no one but me can predict the next number in the sequence.
I know the entire sequence in advance, but I have no way of manipulating it once the first number in the sequence has been shared with others and everyone can verify that this is the case.
it's okay for this sequence to be finite, with the total length being determined in advance.

So, one idea was to take a secret and hash it a few million times. Something like this:

N1 = sha3(secret)
N2 = sha3(N1 + 1)
N3 = sha3(N2 + 2)
N4 = sha3(N3 + 3)
.....

I would then publish the sequence in reverse, starting with Nn. The +# in each step is to avoid loops.

Now the question is, is this secure? Thinking back to my information security classes I recall that one shouldn't apply encryption multiple times as this weakens security.

So,

A: does this mechanic of creating the pseudo-random sequence somehow facilitate it for an attacker to predict an arbitrary future element (from which he then easily could rebuild the chain down to the current element)?
B: does this mechanic of creating the pseudo-random sequence somehow allow me to cheat?

A: No, an attacker can not guess an earlier number. That would amount to a preimage attack for the hash. S/he can not even gain a sizable advantage towards such guess. Arguments (not proofs)

Assuming $\text{secret}$ is full-entropy, the first hashing causes a sizable entropy loss ($0.827\ldots$ bit, see this), and each further hash causes a further entropy loss, but by an heuristic argument, after $k$ iterations, only $\approx\log k$ entropy is lost, thus plenty enough remains (for SHA3-224 and a million millions iterations, >195 bits).
Because it is added a counter rather than a constant, the $N_i$ falling into a short cycle becomes next to impossible, rather than very improbable.

B: The first number disclosed $N_k$ should come with it's index $k$, so that verification of the next number disclosed $N_{k-1}$ is possible by checking $N_k=\text{SHA3}(N_{k-1}+k-1)$ without guesswork on $k$. You can't manipulate the sequence once $N_k$ and $k$ have been shared with others. If you could, that would break the collision resistance of the hash.

Without $k$ published you would have a narrow possibility of fraud: on the second day you can publish $N_{k-1}+j$ and pretend $k$ was $j$ less than it really is; you wont be caught until the next day, and can't be caught if $j=k-1$.

Note: you could manipulate the $N_i$ when choosing the secret, e.g. so that $N_{987}$ is odd; and of course you know all the $N_i$.


Are there order-insensitive, constant-space MAC constructions? Are there well-studied MAC or PRF constructions that can authenticate a sequence of strings in a way that:

Is sensitive to the count of each string in the sequence but not their order;
Uses constant space independent of sequence length and string length;
Uses time proportional to the sum of the lengths of the strings in the sequences?

Something like a keyed function $F_k(M) : \{0,1\}^n \times \{0,1\}^{**} \to \{0,1\}^t$, such that if $M$ is any permutation of $[m_1, ..., m_n]$, then $F_k(M) = F_k([m_1, ..., m_n])$.

The most naïve thing I can think of is to XOR of the outputs of a PRF over the individual strings, but that clearly won't do because $F_k([m]) = F_k([m, m, m])$ for any $m$.

Yes.  Let p be a large prime that's also bigger than 2$^{\text{output_length_(innerMAC)}}\hspace{-0.03 in}$.

If innerMAC "Uses constant space independent of" message length, then

outerMAC$_p\hspace{-0.03 in}\big(\hspace{.16 in}$k$_{\hspace{.02 in}outer}$ || k$_{\hspace{.02 in}inner}\hspace{.08 in}$,$\hspace{.09 in}$multiset$\hspace{.15 in}\big)$
$=$
PP-MAC$\left(\hspace{-0.07 in}k_{\hspace{.02 in}outer},\left(\hspace{-0.08 in}\left(\displaystyle\sum_{\operatorname{string} \in \operatorname{multiset}} \operatorname{int}\hspace{.02 in}\hspace{-0.04 in}\left(\operatorname{innerMAC}\left(k_{\hspace{.02 in}inner},\hspace{-0.03 in}\operatorname{string}\right)\right)\hspace{-0.08 in}\right) \operatorname{mod} p\hspace{-0.08 in}\right)\right)$

will give such a privacy-preserving MAC.

If additionally PP-MAC is a PRF, then outerMAC$_p$ will also be a PRF.

Since [having a composite affects neither order-independence nor space-usage] and

[security is only computational anyway], it's enough for $p$ to be probably prime.  Rather than being hard-coded, such $p$ can be efficiently generated using an additional part of the key, falling back on any large-enough odd number if finding a probable prime takes too long.


Is Pseudo-Random Generator (PRG) in OpenSSL uniformly distributed? I need to know can we use PRG of OpenSSL as a PRF?

Yes, the Pseudo Random Number Generator (PRNG) in OpenSSL is Cryptographically Secure, which means it passes statistical tests, but as @Maarten Bodewes suggests in his comment, why not go one step further and use that PRNG directly, rather than through OpenSSL?

OpenSSL can use EGD (which stands for Entropy Gathering Daemon). It is a process that taps into configurable entropy sources in a given system to provide cryptographically secure random numbers. EGD is actually modeled after /dev/random in *Nix Operating Systems, so it would not be available in a Windows system, for example, but its function is the same as /dev/random which is to gather entropy for random number generation.

If you are creating an application in a *Nix system (OS X, Linux, etc) chances are that EGD is taking input from /dev/random, so your best bet is to use it. If you are in a different OS, then EGD is probably the way to go.


When does the first rotor in Enigma machine rotate? I read a ton of articles about the Enigma machine. And the one thing that I can't get is when the first rotor stars rotating.

Some articles says the rotor rotates after the first letter of message has been encrypted. So if the first rotor is set to 'A', the first input would go through 'A', the second - through 'B', etc.

But some articles say that the rotor starts rotating when you press a key. Only after that the machine encrypts the letter. I mean, I set the first rotor to 'A'. The I press a key to input the first letter of my message. When I press a key, the rotor goes to 'B' and the first letter goes through 'B'.

Which articles are correct?

Having had the privilege of using one of the original machines, I can tell you the sequence is the following:  set the plugs, and set the rotors.  Once you push the key, you can feel the force of the rotors turn, and the light turns on for the encrypted letter.  The light turn off when you take pressure off the key.

This was on a 3-wheel Enigma, and I do not have any personal experience with the later models, but I will assume they work the same way.


Is it possible to break AES-128 ECB if you are given a ciphertext and a small portion of the key? If you are given the ciphertext and the first half bytes (8 bytes) of the encryption key (key is 16 bytes in total), can you use this to break AES-128 ECB encryption and determine the last 8 bytes of the encryption key? (As opposed to trying all 256^8 possibilities for the last 8 bytes of the key, which is A LOT of possibilities and would take days/months to compute)

You can't use it to "break the encryption", but you can guess at the remaining 8 bytes of the key. The remaining 8 bytes should be feasible to find, especially if you can run the search in parallel.


Why was Davies–Meyer chosen over Miyaguchi–Preneel most of the time? The only Miyaguchi–Preneel MD hash I know is Whirlpool. I suppose there are likely others.

Why do most MD hashes choose Davies–Meyer?

If anything, Davies–Meyer relies on related-key resistance while Miyaguchi–Preneel relies on chosen-plaintext resistance. The former ought to be far more difficult to achieve.

So I'm curious about the rationale.

Edit:

After some further research all I could find was the fact that Davies-Meyer is more efficient because it allows you to stretch the message block based on how the key schedule of the underlying block cipher works. Whereas Miyaguchi–Preneel forces you have

length(key) = length(message block) = length(output)

and deviating from that while possible (with padding) complicates security. So I guess the question is whether that the only reason? Performance? Flexibility? SHA2 may not be able to have variants (eg: 256, 512) as easily with Miyaguchi-Preneel.

Some ideas (not a definitive answer):

Davies–Meyer is one of the two simplest among the 12 secure methods by which a block cipher and XOR can be turned into an iterative hash with one encryption per block, per the analysis of Bart Preneel, René Govaerts, Joos Vandewalle's Hash functions based on block ciphers: a synthetic approach, in proceedings of Crypto 1993.Note: in the above table, the block cipher $E$ uses its first argument as key.
Davies–Meyer (method 5) is the only of the 12 that works with a block cipher having a key of width different of its block without needing an adapter (the g in the first drawing of the question).
When the key is wider than the block, that characteristic 2 makes Davies–Meyer use less encryptions for large messages, and that can translate into a speed advantage.
MD4, which was influential on MD5, then SHA, SHA-1 and SHA-2, essentially used Davies–Meyer (except for replacement of XOR with modular addition on a word).


Best method for checking integrity of 50 GiB files? I'm making backups of compressed data (using ZPAQ), some compressed archives are large (50 GiB)

I was just going to use sha3sum -a 512, for example:

sha3sum -a 512 "Total_DOS_Collection-RELEASE#17-[1981-1995].zpaq"

Then storing the value and later periodically checking if the value of the backup is still the same

Then I started wondering if there would be a better/safer/more appropriate/effective method...

Tree hashing would be a natural way to do it.

However, the data still needs to be read. And in practice the hash computation time is negligible compared to I/O, even with a fast SSD.

So, just use a standard hash function. SHA-3 is slow in software, so you'd better opt for BLAKE2.


How to enhance randomness of AES? I'm using PHP to encrypt a string and Java to decrypt it on a remote server. To perform the encryption, I'm using the strategy that can be found here.

My problem is that the strings I encrypt are pretty small and very similar each other. Nevertheless, I'd like a high degree of randomness in the encrypted values.

Just to be clear, at current this is what happens:

$$encrypt(foo1) \rightarrow barA$$
$$encrypt(foo2) \rightarrow barB$$

While I'd like something like:

$$encrypt(foo1) \rightarrow b3SA$$
$$encrypt(foo2) \rightarrow 4FrB$$

How can I enhance the randomness of the encrypted values, by keeping the algorithm I'm already using?

If you are doing things right, then you will get the level of randomness you are after. Translation: you are not doing things right. You use AES with CFB8 mode, which requires a random initial value. The initial value is a 16-byte string which should be generated randomly and uniformly, and a new IV shall be generated for every single encrypted message. Since you need it for decryption, the IV for an encrypted message shall be stored/transmitted along with the said message.

Failure to use a new IV for each message results in a wide range of weaknesses, including what you are witnessing right now (if two strings begin with the same characters, the resulting encrypted strings will also begin with the same bytes).


Probability that two different files can have same MD5 hash for both an unencrypted and encrypted version (AES256, same key between files) This math is way over my head, and don't even know if it can be done, but here are the assumptions:

Take unencrypted File [Fu] of variable length, but assume 100KB as an example.
Let File [Fe] be the AES256 encrypted version of [Fu].
Let Hash [Hu] be the cryptographic hash using MD5 Algorithm of [Fu]
Let Hash [He] be the cryptographic hash using MD5 Algorithm of [Fe]
Let File [Fmu] be an unencrypted file that is different from file [Fu] by at least one bit.
Let File [Fme] be the AES256 encrypted version of [Fmu]
Let Hash [Hmu] be the cryptographic hash using MD5 Algorithm of [Fmu]
Let Hash [Hme] be the cryptographic hash using MD5 Algorithm of [Fme]
Assume the key for AES256 to be constant.

Question:
What is the probability that both [Hu] = [Hmu] and [He] = [Hme]. In english, what is the chance that two different files can have identical hashes in both an unencrypted and encrypted form? My guy says it isn't possible, or the odds are dependent on the size of [Fu]. Thoughts?

What is the probability that both [Hu] = [Hmu] and [He] = [Hme]. In english, what is the chance that two different files can have identical hashes in both an unencrypted and encrypted form?

Depends on whether they are "random" files or attacker controlled.

MD5 is a 128-bit hash, so for two random files that differ the probability that they have the same MD5 hash is $2^{-128}$. If they are encrypted with strong encryption, their encrypted versions will be random files with again $2^{-128}$ probability of having the same hash. The chance that both happen for the same files is then $2^{-256}$.

For attacker chosen files it's a different matter. It is easy to construct two files with the same MD5. If the attacker knows the encryption key, they may even be able to construct two files with equal hashes in both unencrypted and encrypted forms (brute force search takes about $2^{64}$ if nothing else helps).

  My guy says it isn't possible, or the odds are dependent on the size of [Fu]. Thoughts?

As for file size, it doesn't matter beyond the files having to be large enough that collisions exist. In practice something like 512 bits (64 bytes) is enough. In theory there are inputs that are only about 64 bits and collide, but finding them may be more difficult.


Why must an elliptic curve group for ECC have prime order? What is the deeper reason, a group must have prime order for usage in cryptography?

Well, it doesn't have to. In short, as a consequence of the Pohlig-Hellman algorithm the ECDLP is only as hard as the largest prime order subgroup. So the requirement is that there exist a large prime order subgroup. In (a little) more detail:

Elliptic-curve cryptography is mostly based on the Elliptic Curve Discrete Logarithm Problem (ECDLP). That means that given some elliptic curve $E$, we want that the ECDLP is hard in $E$.

Suppose that the group $E$ has order $p_1p_2\cdots p_n$ for some (not necessarily distinct) primes $p_1,\ldots,p_n$. Then the Pohlig-Hellman algorithm reduces the ECDLP in $E$ to ECDLP in subgroups $G_i$ of order $p_i$ respectively. If all the $p_i$ are small, this means that ECDLP is easy in all $G_i$, e.g. by simply building a table of all $p_i$ elements. This leads to a solution of an ECDLP in $E$. Hence to make the ECDLP hard in $E$, we need that at least one of the $p_i$ is large.

For example, prime order elliptic curves trivially have a large prime order subgroup (the group itself!). On the other hand, Montgomery curves (e.g. Curve25519) have order 4*n, so can never be prime. To securely base protocols on Montgomery curves we have to make sure that $n$ has at least one very large prime factor.


What kind of decryption is used in this example? I stumbled upon an encrypted text on a website, to which Google had brought me, showing me the plain text also. So does anyone know what kind of encryption was used here and how to decrypt it, so I can decrypt the rest of the text?

Encrypted text:

  Deälldllod Lokl Koih, dg emlll ld kmd Llshlloosdelädhkhoa Lühhoslo ha Melhi hlhmoolslslhlo, dgiill kll shllll Hmomhdmeohll kld M8-Modhmod

Plain text:

  Spätestens Ende Juli, so hatte es das Regierungspräsidium Tübingen im April bekanntgegeben, sollte der vierte Bauabschnitt des A8-Ausbaus

First it looked to me like a substitution cipher, but there are multiple letters which translate to l. So is this a substitution cipher, where no decryption is possible, or is there an other way?

I look forward to your suggestions.

Well, it seems it is a basic substitution cipher, with a twist: some letters map to the same cipher text letter (not just e,r,t map to l, also e.g. n,u map to o . So decryption is not unique. But a pattern matching algorithm with a German dictionary could probably filter those. The mapping seems to group letters in such a way, that only one combination makes sense.

Anyway, from the example text you can probably find most character mappings, and then you just need to guess words based on valid combinations in a dictionary.

In general, I would not actually call this encryption at all. A scheme like this won't work for just any non-injective mapping, so it's unclear if there is some key involved or not. Also, an encryption scheme requires, that (with overwhelming probability) the decryption is unique and correct, s.t. $D(E(m))=m$.


Is CBC theoretically harder to brute force when compared with ECB? Theoretically – is CBC mode harder to bruteforce when compared with ECB when assuming:

we ignore computational cost for the XOR operations, and
the IV is made public?

As Maarten Bodewes already wrote in a comment, if you ignore the computational overhead of XOR, then there is essentially no difference in CBC and ECB for a bruteforce attack.

However, the question is actually mixing oranges and apples (and it is not obvious), because the security weakness of modes of operation has nothing to do with the underlying symmetric cipher - and a brute force attack has everything to do with the underlying cipher.

The problem is, that brute force attacks are a completely different scenario than what the different modes of operation try to achieve. In brute force you actually try out keys until you find the correct one. In cryptanalysis this is called a total break. The weakness of ECB compared to CBC is, that you can actually can achieve an easier goal of the attack: A distinguishing attack works on ECB and doesn't (with proper randomness, etc.) on CBC - under the assumption that the cipher is secure.

Btw, your 2. assumption is not needed. The IV is always assumed to be publicly known (and generated randomly for security arguments).


How can I find the prime numbers used in RSA? I got this question in a local hacking event, but I couldn't solve it.

  Problem Statement ----

  Continuing their snooping habit, NSA kept bugging Alice's communication. Resorting to the age old RSA encryption, Alice used 128-bit RSA encryption to exchange messages. Alice shares her public key as 0xffffffa95256a837568a41c265f4fe27110814aae19f144762d5cc0bcb931807 and her public key exponent $e$ (derived from $\phi(n)$) as 0x11 with Warden.

  However, NSA, with its enormous resource, cracked this 128 bit encryption super easily. Seeing your work on the previous ciphers, NSA decided to offer you a job in their Cryptography group. As a final test, NSA shared this public key which they intercepted from Alice and Warden's conversation. They also gave away the private key that they computed from their message exchange.

Public Key:
    0xffffffa95256a837568a41c265f4fe27110814aae19f144762d5cc0bcb931807
    0x11

Private Key:
    0xffffffa95256a837568a41c265f4fe27110814aae19f144762d5cc0bcb931807
    0xc3c3c3817b3335577e69b9d0e48e2bc1fdf71f1f4f73a38a7d628d39739bbaf1

  What are the values of $p$ and $q$? (the prime numbers used in key generation)

How can I find the prime numbers used in RSA?


Multiparty secret generation protocol The goal is to create a secret S on a trusted server by having users A, B and C each send a private seed to the server, in such a way that any 2 of them can later recover S by resubmitting their corresponding seeds.

Edit: the actual use case is to create a secret that the server can use in memory but won't persist on the disk. If the memory is reset, any two users can collaboratively recreate the same secret in the server's memory (with the possible help of some persistent recovery parameters that cannot, on their own, recreate the secret).

It looks like a "reversed" version of the Shamir Secret Sharing Scheme, where all users start with their chosen share and the algorithm needs to crunch those shares into a secret that meets the threshold recovery criteria.

What is the simplest way to implement such a protocol?

You can do the following:

The server generates a linear equation $y=ax+s$ where $a$ is chosen randomly from a finite field $F_p$ and $s\in F_p$ is the secret.
For the values from $A,B,C$, let’s call them $x_A,x_B,x_C$. Evaluate the linear equation at these $x$ values and the server gets $y_A,y_B,y_C$.
The server returns $y_A, y_B,y_C$ to $A,B,C$ respectively.

Each party now has a share which is a pair $(x_i,y_i)$. Any two shares can reconstruct the secret $s$.

This is essentially (2,3)-Shamir secret sharing.


Combining two almost universal hash functions We say that a set of functions $S$ is $\epsilon$-almost-universal if for any function $f \in S$, it holds that $\Pr[f(m) = f(m')] < \epsilon$ for $m \not = m'$.

Assume that we have the following two sets of hash functions:

$F = \{f:M \rightarrow X\}$, which is $\epsilon_1$-almost-universal.
$G = \{g:X \rightarrow Y \}$, which is $\epsilon_2$-almost-universal.

Then, there exists a third set of hash functions $H$ for that it holds:
$H=\{h:M \rightarrow Y\}$ where $h(M)=g(f(M))$ and $H$ is $(\epsilon_1 + \epsilon_2)$-almost-universal.

Now my question is: Why is this the case? Why is $H$ $(\epsilon_1 + \epsilon_2)$-almost-universal?

Under what circumstances is $g(f(m)) = g(f(m'))$ for any $m \ne m'$?  With what probability do these circumstances happen?

(Hint: Write $x = f(m)$ and $x' = f(m')$ and consider the probability of $g(x) = g(x')$.)


Generator for Group $QR_{N}$ Let $N=PQ$, where $P=2p+1$ and $Q=2q+1$. $P,Q,p,q$ are prime numbers. $QR_{N}$ is the set of quadratic residues modulo $N$.

Please help me to prove $QR_{N}$ is a cyclic group.  Note: $QR_{P}$ and $QR_{Q}$ are cyclic groups.
How to find/determine generator for $QR_{N}$?

Well , I think DrLecter's great answer in here can be used to answer this question indirectly. But as you want to prove so I will give a proof.
To prove $QR_N$ is a cyclic group, first, you have to know the order of it. In fact, the order of $QR_N$  is $pq=\phi(N)/4$($\phi$ is Euler function ).Actually, we can show this with the help of this map:$$x\to (x_P,x_Q)$$ from $Z_N^*$ to $Z_P^* \times Z_Q^*$.Denote  $Z_N^* \cong Z_P^* \times Z_Q^*$. It's a one to one map. There is a fact about this map we need to use:

$x$ is quadratic residue if and only if $x_P, x_Q$ are all quadratic residues.

Proof.  if $x$ is quadratic residue then  there is a $y$ such that $x=y^2 \pmod{N}$. So $x_P, x_Q$ are all quadratic residues. If  $x_P, x_Q$ are all quadratic residues, then there are $x_1$, $x_2$, such that $$x_P=x_1^2 \pmod{P}$$ $$x_Q=x_2^2 \pmod{Q}$$ .So we the following equation holds:
$$(x_P,x_Q)=(x_1^2,x_2^2)=(x_1,x_2)(x_1,x_2)$$, then using the Chinese remainder theorem, $(x_P,x_Q)$ and $(x_1,x_2)$ point to two elements say $x, y$ in $Z_N^*$. So vice versa.
So with the above fact, we can get $$QR_N \cong QR_P \times QR_Q$$. So $|QR_N|=|QR_P||QR_Q|=\frac{P-1}{2} \frac{Q-1}{2}=pq=\phi(N)/4$.
In order to prove $QR_N$  is a cyclic group,   then you must show that this is an element in it that has the order of $pq$. We know that $QR_P$ is subgroup of $ Z_P^*$  and 'cause its order is prime $p$, then it must be a cyclic group. So does $QR_Q$. So, we can choose  non-identity elements  $x_P \in QR_P$ and  $x_Q \in QR_Q$, and they must be generator. According to Chinese remainder theorem and the fact above, then  $(x_P,x_Q)$ goes to a element in $QR_N$, and its order is $pq$.
Over...
P.S. Although,  i answer your question, but i agree with DrLecter, it likes like your homework, you should think about it yourself.


How can data be encrypted in a client-server application so only clients can read it? Requirements

We are building a system that connects multiple clients through a restful API. It allows the creation of groups of trusted clients. We need a way to store group shared data encrypted on the server side, which only the clients in that certain group can decrypt. Clients are expected to be able to join the group at any moment and still have access to the stored data.

In a more basic description let’s assume:

Client1 and Client2 belong to the same group.
Client1 wants to share data with Client2. To accomplish this, Client1 saves the encrypted data on the server, which Client2 will fetch.
Client1 is expected to be able to understand the data.
Client2 is expected to be able to understand the data.
The server MUST NOT understand the data
When a new client (Client3) joins the group he is expected to be able to understand the data.

Solution

All the clients in a group have a pair of public/private keys.
All the clients in a group have access to all the public keys of all the other clients in the group.
Each group will have a master key ‘K’ used to encrypt/decrypt data to be shared with the group which is initially not set.

The first client who joins the group (lets say it’s Client1) will create and store K locally and mark the group as having initialized its master key. It will then post group shared data encrypted using K and AES-128 to the API.

When Client2 joins the group the following will happen:

Client2 will check if the group has a master key (K) which it does, as it was created by Client1
Client2 will request K from any one of the group members
Client1 will encrypt K with Client2’s public key and send it over
Client2 will decrypt the key with his private key and store it locally so as to not have to request it anymore
Client2 will fetch the encrypted data from the server and use K to decrypt it (note that Client2 does not need to get/store all the data from the server, only the parts that it is interested in)

K is always exchanged by encrypting it using the public key of the client requesting it. This should happen at most 1 time when the client is first joining the group.

Problems

if all the clients leave the group (at which moment they delete K from their local store), all the information on the server will be useless as nobody has K anymore
if Client2 comes online for the first time and another group member is not online it will not be able to obtain K and will not be able to decrypt any of the data stored on the server

Am I correct when seeing these problems? And is there a solution to handle them?

I am not a expert in this domain, so your advice will be very helpful.

if all the clients leave the group (at which moment they delete K from their local store), all the information on the server will be useless as nobody has K anymore

Yeah, that is gonna happen, and there is no way to prevent it, unless you add some trustworthy instance to the system to store such keys.

  if Client2 comes online for the first time and another group member is not online it will not be able to obtain K and will not be able to decrypt any of the data stored on the server

Correct. Basically this is the same as the first question, with the others just being temporarily unavailable instead of permanently.

However, there are several aspects of your current solution, which should be discussed:

As cygnusv pointed out in the comments: You have no mechanism to remove users. Changing the master key is necessary then, as you can't enforce deletion of anything.
Encrypting files with the master key... this is bad. Especially if you have to exchange the master key, this would mean that you also have to decrypt and encrypt every single file/database again. Create a fresh key for each file, table, and so on, and then put it in a list, and work with this list afterwards.
You have a hard requirement that the server must not know the data. Have you made sure that the server does not join the group as a dummy-server (just to get the keys)? Because your access control structure is completely missing right now. You also don't state who handles permissions, creates and publishes the keys, etc.
How does the invitation work? Do group members invite? Who publishes the public keys, etc....
What do you want to do with the data? Especially in databases this is an issue, because you can not work on encrypted data. Instead of posting SQL queries, the clients always have to request a lot of data from the DB, decrypt locally and then apply their operations locally. Almost any optimization of this gives information to the server, which he should not have.


One way hash of data records (PBKDF2?) I'm looking for a way of one way hash data for multiple records. We have a privacy requirement to anonymise information "after it's used for its intended purpose" which is a little wooly at best.

I'd therefore like to delete everything once a project is finished, but this has been met with pushback internally "in case clients as follow up questions", so I figure the next best way is to hash the data with a one way system, so, it's effectively anonymized, not even we'd know what it was, but, if supplied with an email address (for instance) to lookup, we could hash it and search for a match in our database.

I'd need something that non-technical users could use and wouldn't be overly onerous in time, as it's an uphill battle to get people compliant already.

Hoping for an excel solution, or something that could load an excel/csv in and spit out the hashed version, however everything I look at for PBKDF2 is for implementing in websites or similar, singular password use.

I managed to get SHA256 working in excel, but as there's no salt they can be reversed with some work, meaning our effort to make the data anonymised is disingenuous, which is where i came across PBKDF2.

As you can tell be reading this far, I'm a bit out of my depth and would like to appeal to those who know more than I for any help!

Even with PBKDF2, You wouldn't be able to use salt anyways, because salting relies on a one-to-one mapping between the salt and a user identifier (email). You cannot keep the email, so you wouldn't know which salt to use when a user comes back with his email.

Simply iterating SHA 256 for a large number of times is a way to discourage preimage searching. Other (more solid) cost-incurring algorithms include scrypt. Although time-space balance attacks still work if you don't have salt to work with. (Using SHA, possibly inserting large constant data after input string to further slow it down).


Why does ed25519 seem to accept and use 96-byte / 384-bit signatures? Why do ed25519 signature verify functions accept 96-byte signatures? Take this piece of code for one example: crypto_sign_ed25519_open() requires that signatures be at least 64 bytes (512 bits) but will accept longer ones, and get_hram() will include extra bytes at the end of the signature in its hashing step if they are present. Yet crypto_sign_ed25519() generates a 64-byte signature.

Is this some kind of legacy thing? Does it have any cryptographic implication?

This is likely an artifact of the API used in the specific piece of code you're using. This piece of code follows the NaCl API, which verifies the input as the concatenation of signature and message (sm) and copies the message out of sm into the message buffer m. The NaCl paper explicitly states on p. 5 et seq. that this is an intentional design choice. The reason why it "will include extra bytes at the end of the signature" is because these seemingly extra bytes are actually the message that was signed.

Thus they're not actually 96-byte signatures, but rather 64+$L$-byte signatures, where $L$ is the length of the signed message in bytes, and 64 is the length of the actual signature.

Note that it is theoretically possible to have 96-byte signatures specifically, by skipping point compression, as noted on the original Ed25519 paper, p. 15, but this isn't the case in the code you're linking as an example.


Is the concatenation of two one-way functions a one-way function? Suppose we are given two one way functions $f$ and $g$. We define a new function h that is the concatenation of f and g. That is, $h(x)=f(x), g(x)$, where the comma indicates concatenation. We want to figure out whether this is a one way function or not. My teacher tells me this is not true generally. I know it is true if $f=g$, but otherwise I am clueless. I'd love some help.

But is h invertible more or less often? That is how I was asked the question.

When mathematicians say "This statement is not true generally" (or similar wordings) they mean "There exist cases for which the statement is false". So your teacher is talking about the statement "For all $f$ and $g$ which are one-way functions $h(x)=f(x),g(x)$ is also a one-way function" and says that this general statement is false, even if it might be true for some choices of $f$ and $g$.

Looking at this specific statement:

There are choices where it's true. You already found the trivial $f=g$.
There are choices where it's false. When $g(x)=f(x)\oplus x$, $h$ is never a one-way function, since you can recover $x=f(x) \oplus g(x)$ from $h(x)$ (technically you still have to show that there exist $f$ and $g$ of with this relation that are both one-way functions).
In practical terms, if you don't choose $f$ and $g$ deliberately to produce a weak $h$, $h$ will normally also be an OWF, but mathematicians avoid such vague and difficult to formalize claims.


P2P encryption - Do I need a different session key each time? I am using AES128-CBC+HMAC for all encryption.

Currently I am using the same encryption and authentication/MAC key (Both derived from a master key with HKDF).

Assuming that forward secrecy is not a requirement for my project:

Is having a different session key each time strictly necessary and why?

No, having a different session key each time is not strictly necessary. The generic justification is that all modern ciphers and Message Authentication Codes, including AES128-CBC and HMAC, are specified to allow a key to be safely reused for multiple messages.

Note: the One Time Pad does not allow reuse of its pad/key for multiple messages, but is not an exception; it just does not match the modern definition of a cipher.

For CBC with a $b$-bit block, and fully random IV, the best generic attack (for chosen plaintext) requires that there is an accidental collision in the ciphertext blocks, and that has demonstrably odds less than $n^2/2^{b+1}$ to occur after $n$ blocks of $b$ bits have been encrypted. For AES, $b=128$, so if one enciphers less than $2^{60}$ octets (including padding) across all the sessions, residual odds of any attack due to CBC are demonstrably less than $2^{-17}$; and then that is only expected to compromise a few blocks of plaintext, or allow to test if the plaintext has some characteristic.

HMAC with any common hash (including the broken MD5) resists even better to multiple uses.

Still, there could be good reasons to change the key regularly, including being secure despite:

an insufficiently random IV for CBC (including, a narrow one, or one generated using a poor RNG, including a good PRNG that is poorly seeded);
leakage of key by some side-channel, including plain compromise of a machine using it;
guess of the MAC for a certain message that the attacker wants to be accepted, by some side channel like the archetypal timing attack allowed by comparison using memcmp;
a padding oracle attack.