Does absence of second pre-image resistance infer absence of pre-image resistance? Talking about hash functions, I know the hierarchy is as follows:

Pre-image resistance
Second pre-image resistance
Collision resistance

Where each property implies the one before it so 2nd pre-image resistance implies pre-image resistance.. But is this also true the other way around?

Can we infer from the absence of second pre-image resistance, that there would also be the absence of pre-image resistance?

No, it is easy to show that (assuming that there are preimage-resistant functions at all) there are functions that the preimage-resistant, but not second-preimage resistant.

If we assume that SHA512 is preimage resistant, one such function is:

$$H(x) = SHA512(Trunc(x))$$

where $Trunc(x)$ just returns $x$ with the last byte removed.

$H$ is not second-preimage resistant; given $H(x)$, we can change the last byte of $x$ to another value that hashes to the same value.  However, given a target hash value $z$, we can't find a value $x$ with $z = H(x)$; if we did, then we could find preimages to SHA512.

And, in practice, it doesn't only come up only in artificial hash functions (as above); in real hash functions, we can often come up with a way to 'tweak' the message in such a way so that the intermediate state of the hash function happens to be unchanged after the tweak (which would imply that the hash value is unchanged).


RC4 - Key scheduling Algorithm I'm trying to understand the KSA algorithm of RC4 which apparently scrambles the array which will later be used by the PRGA to generate the keystream. My question is, does the seed used by the KSA have to be kept secret?

Yes, the seed to the KSA in RC4 is essentially the secret key for the stream cipher. With the secret key (the only input to the KSA) an adversary can recreate the keystream, and thereby recover any information encrypted under that key.


Is it safe to use fast/small hash for key identity? I have to roll database access keys often, but it's important to know which key each system is using in order to avoid unavailability. I want the systems to report that without exposing the key itself, of course.

I'm using randomly-generated 512-bit keys, and from each key I'm planning to make a 32-bit hash. I only need to compare a handful of keys each time, so it's ok to have $1 - \frac{1}{2^{32}}$ of comparison confidence (which gives more than 99.99999%).

If the attacker sees the hash and knows the key size, he/she can filter out keys that produce a different hash. However, he/she will still have $2^{480}$ keys to brute-force access the database.

Does that make sense or is there a better solution? If this will work, which hash function should I use for the 32-bit hash? CRC/Checksum/something else?

In general, you never want to use CRC/weak checksum for any computations on secret material (like keys). CRC is a linear function and by showing CRC of a key, you reveal a lot of equations that hold among the key bits. This is equivalent to showing the same number of bits of the key as the length of the checksum.

The proper way of doing it has been suggested by @puzzlepalace: Take a cryptographic hash function (like SHA-2), compute the hash of the key and take only 32-bits of the digest.

Key fingerprint of 32-bits may be too small: if you have ~2^16 keys, you will get different keys that give the same fingerprint. You need to take this into account when designing your system.


Is there any functional encryption scheme whose key generation circuit is in NC1? To my best of knowledge, I have kown there exists randomized encoding scheme whose encoding circuit is in $NC^1$, fully homomorphic encryption scheme whose decryption circuit is in $NC^1$, and functional encryption scheme for $NC^1$ functions. Now I'm curious about is there any functional encryption scheme whose key generation circuit is in $NC^1$ ?

Attribute-Based Encryption schemes (ABE) are definitionally a sub-category of FE. Furthermore, non-monotonic ABEs (NM-ABE) can encode decisions from $NC^1$, so yes, there are FE-schemes that are restricted to $NC^1$.

There are both ciphertext-policy ABEs (CP-ABE), key-policy ABEs (KP-ABE) and mixtures of them (dual-policy, or DP-ABEs), so it is possible to embed the circuit of desired complexity into both ciphertext and key (or key generation).

The most general FE schemes can encode decisions from the whole of $NC$, so they are also able to encode circuits in $NC^1$. FE-schemes also exist in both KP- and CP-flavors.


What information is signed by a Certification Authority? What data does a CA sign?
I know that in a certificate there is plenty of information such a the serial number of the certificate itself, the X.509 version number, the user public key, the asymmetric algorithm to which the key belongs and its size, the user ID, the validity of the cert (both beginning and expiration day), CA ID and finally the digital signature and the algorithm used to generate it..
What information is signed with the CA private key? Is it just the (user ID || user public key) or something else?
I don't know if I need to specify that, but I man concatenation with the || symbol, but I don't know if the data is simply appended in sequence.

The information that is signed may differ by certificate, but basically the procedure can be found by looking at RFC 5280 and working downward:

4.1.1.3.  signatureValue

   The signatureValue field contains a digital signature computed upon
   the ASN.1 DER encoded tbsCertificate.  The ASN.1 DER encoded
   tbsCertificate is used as the input to the signature function.  This
   signature value is encoded as a BIT STRING and included in the
   signature field.  The details of this process are specified for each
   of the algorithms listed in [RFC3279], [RFC4055], and [RFC4491].

   By generating this signature, a CA certifies the validity of the
   information in the tbsCertificate field.  In particular, the CA
   certifies the binding between the public key material and the subject
   of the certificate.

Note that signature value is the signature put over the certificate by the CA here, it's not a digital signature over a document.

The next section contains a content description:

4.1.2.  TBSCertificate

   The sequence TBSCertificate contains information associated with the
   subject of the certificate and the CA that issued it.  Every
   TBSCertificate contains the names of the subject and issuer, a public
   key associated with the subject, a validity period, a version number,
   and a serial number; some MAY contain optional unique identifier
   fields.  The remainder of this section describes the syntax and
   semantics of these fields.  A TBSCertificate usually includes
   extensions.  Extensions for the Internet PKI are described in Section
   4.2.

TBS in TBSCertificate stands for To Be Signed which makes things pretty clear.

To be more precise, the contents of the TBS certificate are

TBSCertificate  ::=  SEQUENCE  {
     version         [0]  Version DEFAULT v1,
     serialNumber         CertificateSerialNumber,
     signature            AlgorithmIdentifier,
     issuer               Name,
     validity             Validity,
     subject              Name,
     subjectPublicKeyInfo SubjectPublicKeyInfo,
     issuerUniqueID  [1]  IMPLICIT UniqueIdentifier OPTIONAL,
                          -- If present, version MUST be v2 or v3
     subjectUniqueID [2]  IMPLICIT UniqueIdentifier OPTIONAL,
                          -- If present, version MUST be v2 or v3
     extensions      [3]  Extensions OPTIONAL

subjectPublicKeyInfo above contains the encoded public key.

And the list of extensions can be found by looking at the index:

    4.2. Certificate Extensions ....................................26
           4.2.1. Standard Extensions ................................27
                  4.2.1.1. Authority Key Identifier ..................27
                  4.2.1.2. Subject Key Identifier ....................28
                  4.2.1.3. Key Usage .................................29
                  4.2.1.4. Certificate Policies ......................32
                  4.2.1.5. Policy Mappings ...........................35
                  4.2.1.6. Subject Alternative Name ..................35
                  4.2.1.7. Issuer Alternative Name ...................38
                  4.2.1.8. Subject Directory Attributes ..............39
                  4.2.1.9. Basic Constraints .........................39
                  4.2.1.10. Name Constraints .........................40
                  4.2.1.11. Policy Constraints .......................43
                  4.2.1.12. Extended Key Usage .......................44
                  4.2.1.13. CRL Distribution Points ..................45
                  4.2.1.14. Inhibit anyPolicy ........................48
                  4.2.1.15. Freshest CRL (a.k.a. Delta CRL
                            Distribution Point) ......................48
           4.2.2. Private Internet Extensions ........................49
                  4.2.2.1. Authority Information Access ..............49
                  4.2.2.2. Subject Information Access ................51


Is a random permutation "hiding"? Let's say I tell you $G: \mathbb{F} \rightarrow \mathbb{F}$ is a random permutation (some finite field). Does that mean:

$G$ is one-way, so that if I give you $G(x)$, it is infeasible to determine the pre-image $x$?
Is $G$ hiding in the sense that you can't figure out anything about $x$ given $G(x)$? For example, you could determine if $x$ were even/odd?

If the second question is true, how do I capture this in a game?

If $G$ is only known to be a random permutation, and one $G(x)$ is given, that gives no information whatsoever about $x$ (it can be any element of $\mathbb F$ with equal likelihood if $G$ is uniformly random). So I would say $G$ is one-way and hiding in the sense of the question.

Things change when for the same $G$ it is considered several given $G(x)$ and perhaps $x$. In particular, knowing $G(x)$ and $G(x')$ we can tell if $x=x'$, since that is equivalent to the testable $G(x)=G(x')$.

Capturing the first situation in a game is easy: change the permutation whenever its input or output changes. But that's bound to give dull results: we're not using most of what the permutation is good for.

To capture the second situation, define the permutation early in the game, and make several rounds with $x$ or $G(x)$ varying. It's possible to establish things like: for appropriately large $\mathbb F$, given a $G(x)$ that was not previously disclosed, the computational advantage in predicting $x$ is negligible.


Salt and pepper at both client and server sides? Putting aside that it may sound paranoid.

I know that many users tend to use the same password on many sites. Then, from an ethical point of view, I should not only be concerned about security breaks that affect my own system, but also how my system might facilitate breaking the security of other systems.

Suppose that an attack allows a third party to read (but not modify1) the communication, including the password exchange during login. If they can read the user's name and password, they could gain access to the account of that person on other systems if they used the same name and password there.

To avoid that, I was thinking about doing hash(system_public_pepper+username_as_salt+password) at client side, along with bcrypt (which includes salt) with a secret system pepper. Both peppers would change at each server (randomly generated on install).

But then my new concern is whether this client-side hash could weaken the password (example: limiting the entropy).

And then:

What hash should I use to make sure there is no significant entropy loss? Is MD5 ok?
Can the pepper and/or salt weaken the entropy, considering it is of public knowledge (although salt changes between users)?
Does it make a difference whether the salt (username) or pepper (public) are prepended or postpended? Which order is best?

I think that if the salt or pepper are prepended, one can take the state of the hash algorithm at that point as a start, and then computing the hash of every password would cost less (as if there were no salt and pepper).

But, also, one could apply the same to common passwords if they are at the beginning.

Is there anything else I should consider?

Edit: I think that there is a misunderstanding from what I proposed. So, I will put an example. U is user, C is cliente, S is server, D is database (just pseudo for clarity, we can use PDO for prepared statements and so).

SIGNUP EXAMPLE:

C>S: I need to signup, send me the public pepper.
S>C: {"system_public_pepper":"Potts"}
U>C: {"username":"johndoe","password":"IWasBornOn1987"}
C: P=system_public_pepper+username+password; //P="PottsjohndowIWasBornOn1987"
C: H=md5(P); //="28d36f3969e05dedb5f9ba20acd3842a"²
C>S: {"username":"johndoe","hashpass":"28d36f3969e05dedb5f9ba20acd3842a"}
S: private_pepper="GwynethPaltrow";
S: new_pwd=private_pepper+hash_pass; //"GwynethPaltrow28d36f3969e05dedb5f9ba20acd3842a";
S: pwd_bcrypted=bcrypt(new_pwd); //"$2a$04$qh7z5sSkMCrLq6mrpdOwM.ohlvCKWvU3vQm.CrjrxcQc6otwByBle"³
S>D: INSERT INTO users ('username','password') VALUES ('johndow','$2a$04$qh7z5sSkMCrLq6mrpdOwM.ohlvCKWvU3vQm.CrjrxcQc6otwByBle')

SIGNIN EXAMPLE:

C>S: I want to sign in, send me the public pepper.
S>C: {"system_public_pepper":"Potts"}
U>C: {"username":"johndoe","password":"IWasBornOn1987"}
C: P=system_public_pepper+username+password; //P="PottsjohndowIWasBornOn1987"
C: H=md5(P); //="28d36f3969e05dedb5f9ba20acd3842a"²
C>S: {"username":"johndoe","hashpass":"28d36f3969e05dedb5f9ba20acd3842a"}
S: private_pepper="GwynethPaltrow";
S: attempt_pwd=private_pepper+hash_pass; //"GwynethPaltrow28d36f3969e05dedb5f9ba20acd3842a";
S>D: SELECT 'username', 'password' FROM users WHERE 'username'='johndoe'  //'$2a$04$qh7z5sSkMCrLq6mrpdOwM.ohlvCKWvU3vQm.CrjrxcQc6otwByBle'
S: password_verify(attempt_pwd,stored_hash)

Footnotes:

I know that it would be odd, since usually if you can sniff an HTTPS
communication, you can also run a MitM attack. But I was thinking
about a generic attack only aimed at reading because it may work on
a massive amount of sites. While modifying them would require more
work. So, at least I can prevent those. Also, I suppose it could be
a specific attack to the OS or HTTPS deamon that allows to read
communications.
Here is the key, the user password does not leave the client.
Let's say there is a bug at the server, and the received communications
get logged: you can't get the password logged, just the hashed version.
The stored hash is neither the original password, nor the received one.

I think the detailed approach you have given can work. To address your specific point:

Rule of thumb: No md5 is never okay, for anything.
I'm not sure what you mean but pretty sure that the answer is: No.
The order doesn't really matter although your point is correct and you should probably add field separators instead of just concatenating.

I think proposing this kind of change requires a consideration of the attacker model. Your connection should be secured by TLS and all this becomes moot.

You can do more advanced things, they are great but work a little different. Maybe looking Password Authenticated Key Exchange (PAKE) will give you some inspiration.


Secure Cipher Suites supported by JDK versions I'm a n00b to cryptography.  I've been searching through oracle's java docs, ssl labs, googling and more googling attempting to find an up to date list of cipher suites considered secure for the latest updates of Java SE 6 (I know its old), Java SE 7 and Java SE 8. I've found plenty of outdated info which is not useful to me.

I understand the basic concepts and ciphers that together make a cipher suite- key exchange, bulk encryption and MAC. I also have a high level understanding of the TLS protocols.

If someone can point me to an up to date resource(s) I'd really appreciate it. Deadlines are looming.

To clarify- This isn't a programming question. It is strictly focusing on secure cipher suites. I'm not implementing any of this in code. It is simply a list of secure ciphers related to Java that I'm compiling.

(Meta: if we're going to improve formatting might as well improve content too. However, I haven't looked at at 10 yet; I'll try to come back and re-edit when I have time to do so.)
Java Cryptography Architecture (JCA) is designed around the concept of replaceable providers. Originally (in the 1990s) this was necessary to easily support US and limited 'foreign' versions with a single codebase.
(This applies to all crypto: codesigning and other things as well as SSL/TLS.)
If you use the Sun-now-Oracle providers (which is the case if you use the 'standard vanilla' JRE or JDK packages from Sun-now-Oracle) or if you use the open-sourced equivalent OpenJDK packages in at least some Unix distros, then the official documentation is at http://docs.oracle.com/javase/8/docs/technotes/guides/security/SunProviders.html#SunJSSEProvider -- and has been there or the corresponding 7 and 6 and 5 directories for a long time.
(Update: Java 9, Java 10.)

In summary, and expanding a bit on some points that may be unobvious:
Protocols

Java (JSSE) 6 implemented only the SSLv3 and TLSv1 (meaning 1.0) protocols. There is also a protocol name SSLv2Hello but this is not an actual protocol, rather the option to use backward-compatible negotiation as per rfc2246 or rfc4346 E.1.

Java 7 and 8 implemented SSLv3 through TLSv1.2, but SSLv3 was disabled in updates beginning Dec 2014 because of POODLE. (6 was past end-of-life and so was not updated, at least not in public/free versions.) Although 7 implements 1.1 and 1.2, on client side it does not enable them by default; 8 does. 7 and 8 still implement SSLv2Hello, but do not enable it on client by default.

In the 2000s there were still some SSL2 servers around, and using SSLv2Hello allowed you to get a more specific error when encountering them, but by now they should all be gone (and SSL3 as well) so there is no good reason to enable SSLv2Hello. If you are stuck running on Java 6, it may be worth the trouble to disable it, because modern systems may implement a rigid no-SSL rule that prohibits any SSL2-format hello, even when it would allow negotiation to an otherwise acceptable TLS version. Plus, if you want to enable ECC on 6 (see below), ECC negotiation may not work (or not well) without extensions while SSL2-format doesn't have.

Cipher suites
JSSE 6 and 7 implement (AFAIK all) public key and Kerberos cipher suites from TLS1.0 and 1.1 (which are the same), although the EXPORT and NULL (!) and anon and KRB5 ones, plus in 7 those using original (single) DES (versus 3DES), are disabled by default. The first three were designed to be insecure, and the last has become so, and they should not be enabled. Suites using Kerberos for key-exchange can be secure but it requires special infrastructure, so if you don't already know about Kerberos you probably can't use it.
But the ECC suites can actually be used only if the JVM has a (separate) cryptoprovider for the needed ECC primitives, which Sun/Oracle JRE/JDK 6 does not but 7 up does (SunECC). You can add a third-party ECC provider to 6; my favorite is BouncyCastle. OpenJDK may be more variable; in particular RedHat (hence CentOS, Fedora, SL, etc) packages used to exclude ECC crypto from (AFAIK all) crypto/security programs even when it was provided upstream, although I believe these have now been fixed.
Also, the cipher algorithm RC4 has become seriously weakened by attacks in recent years and since 2015 is officially prohibited although not everyone implemented this change promptly -- or at all. 8u60 and up disable it using a setting configured in JRE/lib/security/java.security which you can change if you need to, and 9 similarly in JRE/conf/security/java.security.
TLS 1.2: SHA2 and GCM suites
JSSE 7 also implements the CBC-SHA2 suites in TLS1.2; 8 adds the GCM suites in TLS1.2. GCM is one form of AEAD (Authenticated Encryption with Additional Data) which is now considered superior to all former TLS cipher suites, which combine a cipher with separate HMAC in the more vulnerable order MAC-then-Encrypt. GCM suites should be preferred when possible (in 8 up).
SCSV
In addition, 6 starting with 6u22, and all versions of 7 and 8, implement a cipher suite name TLS_EMPTY_RENEGOTIATION_INFO_SCSV which is not actually a cipher suite, but an option to implement rfc5746 using the (registered) pseudo cipher suite value; if 'disabled' JSSE client still supports rfc5746 but uses the extension field instead. In 2010 the SCSV was slightly more interoperable/robust than the extension; today it usually doesn't matter.
Strength Policies
Sun-now-Oracle JREs and JDKs until 2017 install with a default 'policy' that prohibits symmetric encryption over 128 bit strength; for SSL/TLS this has the effect of disabling cipher suites using AES-256 (in either CBC or GCM). To use AES-256 on these you must download and install the Unlimited Strength Jurisidiction JCE Policy applicable to your major version. Only 8 is still on the download page (but may not be much longer); older versions used to be in the archive but I no longer see them. Update: 8u161 and 8u162 in 2018, and 9.0.0 in 2017, remove this obsolete policy restriction, and allow AES-256 out of the box; OpenJDK (AFAIK all versions) never had this misfeature in the first place.
Server keys limit available cipher suites
On server side, of course, a public key suite can be agreed only if the server's keystore (or more precisely keymanagers, normally derived from a keystore) contains a privatekey with certificate (chain) for the applicable publickey algorithm. For example, using an RSA-based cipher suite requires an RSA key and cert. In particular, keytool by default generates a DSA privatekey and selfsigned certificate; this supports only ciphersuites with DHE_DSS key exchange. JSSE supports keymanagers containing multiple key+cert pairs of different types, although some applications configure only a single keystore entry (alias) and can't benefit from this.
For ECC (if supported, per above) in addition the curve used must be among those offered by the client; this is rarely a problem for keytool generated keys since it uses the widely supported curves P-256 P-384 P-521, but may matter if you generate your key by other means.
Other providers
IBM Java replaces the Sun/Oracle providers with IBM providers, and I don't have relevant experience with them. And of course you (or anyone) can write your own provider(s) and substitute it(them) in which case you are on your own.
Update: recently BouncyCastle releases began including a provider BCTLS which is an alternative to JSSE, and provides a modern set of features, depending (only) on the BC version, that work the same on all Java versions back to 5. (BC had implemented TLS
years earlier, but using a separate and incompatible API; with BCTLS you just instantiate your SSLContext from BCTLS instead of JSSE and the rest of your code can stay the same.)


Building adversary to show a PRF is not secure Let $F(k,x)$ be a secure PRF over $(\mathcal{K},\mathcal{X},\mathcal{Y})$ where $\mathcal{K} = \mathcal{X} = \mathcal{Y} = \{0,1\}^n$.

Let $F'(k, x) = F(F(k, 0^n), x) \; \Vert \; F(k, x)$.

$a \; \Vert \; b$ means $a$ concatenated to $b$.

How can I show that $F'$ is not a secure PRF? I've been trying to build an adversary that could find some pattern but I couldn't. My  best guess was to initially use $x = 0^n$, so the output would be something like $F(k', 0^n) \; \Vert \; k'$ (where $k' = F(k, 0^n)$, which is the key of the left side) and I would be able to use $k'$ for the next calculations, but it didn't seem to be enought to find any pattern in the sequence of outputs.

Query $0^n$ to your oracle, receive $a\Vert b$ as a response.
If $F(b,0^n) = a$ output $1$, otherwise output $0$.

In the case that the oracle is $F'$, since $F'(k,x)$ is defined as $F(F(k,0^n),x)\Vert F(k,x)$ your response will be $a\Vert b = F(F(k,0^n),0^n)\Vert F(k,0^n) = F(k',0^n)\Vert k'$, it will always be true that $F(b,0^n) = a$. I.e.
$$\Pr_k[\mathcal{A}^{F'(k,\cdot)}(1^n)=1] = 1.$$

In the case that the oracle is a truly random function $g : \{0,1\}^n \times \{0,1\}^n  \to \{0,1\}^n$, $a$ is distributed uniformly and independently of $b$. Therefore the probability of $F(b,0^n) = a$ is $2^{-n}$. Thus,
$$\Pr_g[\mathcal{A}^{g(\cdot)}(1^n)=1] = 2^{-n}.$$

And therefore

$$\left|\Pr_k[\mathcal{A}^{F'(k,\cdot)}(1^n)=1]-\Pr_g[\mathcal{A}^{g(\cdot)}(1^n)=1]\right|=1-2^{-n},$$
which is clearly non-negligible.


SHA-512 partial preimage I was looking at how SHA-512 works, and I have a question. Imagine I want an input $N$ of 512 bits whose hash in hexadecimal starts with the digits 12345678. How could I determine an input $N$ to get that hash output?

As far as we know, SHA512 acts like a random function.  So, the only way we know to find a preimage whose hash starts with 0x12345678, is to go through distinct preimages, and hash each one until we find one that starts with 0x12345678.

If the output of SHA512 is equidistributed (and we have no reason to believe it isn't), then the probability of any hash starting with 0x12345678 is $2^{-32}$, hence the expected number of hashes you would need to perform is $2^{32}$, which is an achievable work effort.


How to prove the pseudorandomness of CryptoPAn in my cryptography course, we are learning about pseudo randomness and the prefix-preserving function known as CryptoPAn invented in 2002. It is said that the scheme is highly insecure. So in that case, i am leaning towards disproving the pseudorandomness of cryptoPAn. But i am struggling to put it into words.
for your kind information, this is crpytopan : https://handwiki.org/wiki/Crypto-PAn

Since you're still learning, I would give you an answer; however consider the encryption of the IP addresses 10.0.0.1 and 10.0.0.2; how would those two ciphertexts be related?  How could you use that as a distinguisher from a random permutation?


Clarifications regarding ciphers and Nmap scan I'm running the below Nmap command to test the strength of the cipher suites I have used in my host

nmap -sV --script ssl-enum-ciphers -p 443 <host>

The Nmap doc says that Each ciphersuite is shown with a letter grade (A through F) indicating the strength of the connection and the output line beginning with Least strength shows the strength of the weakest cipher offered

When I ran the command against the host I got the output as shown below

| ssl-enum-ciphers:
|   TLSv1.0:
|     ciphers:
|       TLS_DHE_RSA_WITH_3DES_EDE_CBC_SHA (dh 768) - E
|       TLS_DHE_RSA_WITH_AES_128_CBC_SHA (dh 768) - C
|       TLS_DHE_RSA_WITH_DES_CBC_SHA (dh 768) - E
|       TLS_RSA_WITH_AES_128_CBC_SHA (rsa 2048) - A
|       TLS_RSA_WITH_RC4_128_MD5 (rsa 2048) - C
|       TLS_RSA_WITH_RC4_128_SHA (rsa 2048) - C
|     compressors:
|       NULL
|     cipher preference: client
|     warnings:
|       64-bit block cipher 3DES vulnerable to SWEET32 attack
|       64-bit block cipher DES vulnerable to SWEET32 attack
|       Broken cipher RC4 is deprecated by RFC 7465
|       Ciphersuite uses MD5 for message integrity
|       Key exchange (dh 768) of lower strength than certificate key
|   TLSv1.1:
|     ciphers:
|       TLS_DHE_RSA_WITH_3DES_EDE_CBC_SHA (dh 768) - E
|       TLS_DHE_RSA_WITH_AES_128_CBC_SHA (dh 768) - C
|       TLS_DHE_RSA_WITH_DES_CBC_SHA (dh 768) - E
|       TLS_RSA_WITH_AES_128_CBC_SHA (rsa 2048) - A
|       TLS_RSA_WITH_RC4_128_MD5 (rsa 2048) - C
|       TLS_RSA_WITH_RC4_128_SHA (rsa 2048) - C
|     compressors:
|       NULL
|     cipher preference: client
|     warnings:
|       64-bit block cipher 3DES vulnerable to SWEET32 attack
|       64-bit block cipher DES vulnerable to SWEET32 attack
|       Broken cipher RC4 is deprecated by RFC 7465
|       Ciphersuite uses MD5 for message integrity
|       Key exchange (dh 768) of lower strength than certificate key
|   TLSv1.2:
|     ciphers:
|       TLS_DHE_RSA_WITH_3DES_EDE_CBC_SHA (dh 768) - E
|       TLS_DHE_RSA_WITH_AES_128_CBC_SHA (dh 768) - C
|       TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256 (secp256r1) - A
|       TLS_RSA_WITH_AES_128_CBC_SHA (rsa 2048) - A
|       TLS_RSA_WITH_RC4_128_MD5 (rsa 2048) - C
|       TLS_RSA_WITH_RC4_128_SHA (rsa 2048) - C
|     compressors:
|       NULL
|     cipher preference: client
|     warnings:
|       64-bit block cipher 3DES vulnerable to SWEET32 attack
|       Broken cipher RC4 is deprecated by RFC 7465
|       Ciphersuite uses MD5 for message integrity
|       Key exchange (dh 768) of lower strength than certificate key
|_  least strength: E

My questions

As per the doc, the Ciphers marked as "E" is the weak cipher and in another way can I consider the cipher marked as "A" as the strong cipher?
TLS_RSA_WITH_AES_128_CBC_SHA is marked as "A" here, but in some discussions, I have observed it is mentioned as WEAK. Is it because of the SHA1 usage? if so why this is rated as "A" in NMAP?
I have configured the below cipher list on my server.

  ciphers="SSL_RSA_WITH_RC4_128_MD5,SSL_RSA_WITH_RC4_128_SHA,SSL_DHE_RSA_WITH_DES_CBC_SHA,SSL_DHE_RSA_WITH_3DES_EDE_CBC_SHA,TLS_RSA_WITH_AES_128_CBC_SHA,TLS_DHE_RSA_WITH_AES_128_CBC_SHA,TLS_RSA_WITH_AES_256_CBC_SHA,TLS_DHE_RSA_WITH_AES_256_CBC_SHA,TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA256,TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256"

but the ciphers such as SSL_RSA_WITH_RC4_128 is not available in the Nmap output, instead, there are ciphers like TLS_RSA_WITH_RC4_128, what is the reason for this? Can we use SSL and TLS interchangeably in the Ciphers?

Even though I have added the TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA256 as a cipher in my server, it wasn't available in the Nmap results, what might be the reason for this?

PS: I'm using JDK 1.7 as the underlying JDK version for the server

Even though I have added the TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA256
  as a cipher in my server, it wasn't available in the Nmap results,
  what might be the reason for this?

Your server probably uses a RSA-based certificate and the second part of the name states "ECDSA" which means that this ciphersuite indicates an ECDSA-based certificate. As none has been found, the server didn't actually offer this ciphersuite.

  As per the doc, the Ciphers marked as "E" is the weak cipher and in
  another way can I consider the cipher marked as "A" as the strong
  cipher?

It would appear that "E" means "practically exploitable if you have enough money / time", as example issues seem to include the use of 3DES which is bad for the small block size or the use of DES which has a easily brute-forced keylength.

"A" here probably means "not practically exploitable if decently implemented", which is the only thing I can come up with as the use of CBC and non-DHE suites have been flagged "A".

  TLS_RSA_WITH_AES_128_CBC_SHA is marked as "A" here, but in some
  discussions, I have observed it is mentioned as WEAK. Is it because of
  the SHA1 usage?

This suite has two main issues. The use of SHA1 (which is used in HMAC), is not one of them.

It uses CBC mode which has been a major cause of worry in TLS in the past and gave rise to many attacks on TLS implementations.
It uses key-transport RSA, that is if your private key leaks from your server (eg because of something like heartbleed), all transcripts of past sessions can be decrypted. This is not the case if a (EC)DHE suite is used.

  if so why this is rated as "A" in NMAP?

Apparently the nmap developers chose a different notion of "good" as most cryptographers / Google did, in that they define anything as "good" that is "effectively unbreakable if decently implemented" whereas cryptographers want more fancy properties like "hard to get wrong" and "still somewhat secure if compromised in the future".

  but the ciphers such as SSL_RSA_WITH_RC4_128 is not available in the
  Nmap output, instead, there are ciphers like TLS_RSA_WITH_RC4_128,
  what is the reason for this?

This is a naming difference. Your implementation chose the prefix to be SSL_, nmap chose it to be TLS_, the objects identified are still the same.


Is there any valuable Cryptography certification for working in the field? I'm an amateur math/crypto/CS passionate, but I find myself without any degree or certification that gives credit to my skill-set, specially on math and crypto. Currently I'm designing cryptosystem on non-commutative cryptography, trying to cryptoanalise my own trapdoor functions, measuring security parameters, testing new platform groups, etc. Eventually I write down all my investigations and write a paper if it's something to take into consideration.

I think that a professional on the field would classify my work as pure recreational, but I'd like to dedicate my working life as someone who uses math/crypto at computer security level.

Is there any degree/title/certification that is respectable and valuable enough? By "valuable enough" I mean that does not just cover the basics and that must be updated to nowadays times.

Cryptography is a quite academic field. Outside of universities, practice of cryptography tends to be "applied crypto", which feeds on academic papers while contributing its own perspective on things, in particular with regards to implementation issues. In any case, this means that whatever you do in cryptography will involve reading a lot of research papers, and, correspondingly, the formal degrees about it are academic. If you want to go that road and be recognized as a "cryptographer" through certifications and degrees, then go get a PhD or at the very least a Master's degree in cryptography.

There are alternate roads to building your crypto street cred:

You might demonstrate your deep knowledge of the field by flooding some well-known public forums or Q&A sites (e.g. this very site, crypto.stackexchange.com) with hundreds of well-researched and explained answers that make people instinctively think of you as "that guy knows his stuff".
While paper publication in peer-reviewed conferences or journals is a difficult art, "publishing" software implementations is simple; you just have to create a free GitHub account, and roll with it. If you manage to write some kick-ass piece of crypto software, that people find useful and appears to be of high coding quality, then you could also gain some reasonable level of recognition.
There occasionally are some "cryptographic competitions" (some are referenced here; an ongoing one is the NIST call for Post-Quantum algorithms) in which anybody can submit a "candidate". This is substantial work, and little glory is achieved if it gets broken right away. But if a candidate survives one or two rounds, then it can lend some credibility to the authors.

The common theme in all of these is that you should show, at all times, that you understand the academic side of things, and you know not to make unsubstantiated outrageous claims of security.


Does MD5 generate 128 independent bits? I heard that there are 128 stochastically independent bits in an MD5 output. Is that true?

If so, are there any citations or proofs for that?

No, there are expressions relating input values which demonstrate extremely strong correlations between output bits. The output bits of of MD5 are not independent, particularly if the party supplying the input to MD5 chooses for them not to be.

These correlations are sufficiently powerful to enable the generation of completely identical output values rapidly on ordinary desktop systems. This would otherwise require a challenging amount of work (2^64), were MD5 an ideal random function.

Consider this visualization of an MD5 collision. Observe that even towards the end of the computation, near the output, the differences (red and green colors) have been largely confined to long vertical columns (which correspond directly to the output bits). Even after just one input block, a change to 3 input bits results in no change at all in 125/128 output bits rather than the 64/128 that would be expected by chance alone.


Serpent block cipher : S0 to S7 functions unclear I am presently implementing the serpent block cipher in C++ following the specifications. It's important to mention that I'm implementing the cipher in bitslice mode. You'll need the The full submission package of Serpent which contains the specification of the algorithm and the source code in C and Java.

Lets start with the key schedule algorithm at pages 6 and 7 of the paper. You'll see ${k_0 , k_1 , k_2 , k_3} = S3(w_0 , w_1 , w_2 , w_3)$ and the following equalities for k. $S_i$ is a S-Box for $i = 0,\ldots, 7$. Notice that those S-Boxes take 4 32-bit integers as input parameters and return 4 32-bit integers. This confuses me, because on page 3, they write that those S-Boxes take a 4-bit integer as input parameter and return a 4-bit integer.

If someone can help me to understand those S-Boxes, it will be very appreciated. I need to know how to build them by using the ones mentioned at page 21 (A.5).

Also, in the serpentsboxes.h file given in the package, I saw the following code :

/* S0:   3  8 15  1 10  6  5 11 14 13  4  2  7  0  9 12 */

/* depth = 5,7,4,2, Total gates=18 */
#define RND00(a,b,c,d,w,x,y,z) \
{ register unsigned long t02, t03, t05, t06, t07, t08, t09, t11, t12, t13, t14, t15, t17, t01;\
t01 = b   ^ c  ; \
t02 = a   | d  ; \
t03 = a   ^ b  ; \
z   = t02 ^ t01; \
t05 = c   | z  ; \
t06 = a   ^ d  ; \
t07 = b   | c  ; \
t08 = d   & t05; \
t09 = t03 & t07; \
y   = t09 ^ t08; \
t11 = t09 & y  ; \
t12 = c   ^ d  ; \
t13 = t07 ^ t11; \
t14 = b   & t06; \
t15 = t06 ^ t13; \
w   =     ~ t15; \
t17 = w   ^ t14; \
x   = t12 ^ t17; }

Here, w,x,y,z are the output and a,b,c,d are the input integers. If I well understood, the RND00 function is equivalent to $S_0$. If it's true, how did they get that code working ?

Define 16 functions like this make the code longer and not really understandable. Is there another way to code those functions with clearer instructions more like what's explained in the paper ?

Another question : What's the difference between bitslice mode and non bitslice mode in terms of performance and utility ? Why should one will prefer one instead of the other one ?

As you can see, I really don't want to copy the code. My objectives are to understand every step of the cipher and write my own readable code (optimized in C++11) in which it'll be easy to understand and follow.

The reason it is taking 4 32-bit integers into the round function is because it IS a bitsliced implementation.

It bitsclices 32 4-bit sboxes into 4 32-bit inputs and uses standard logical operations on the words to get the job done.
The sbox you posted was not generated by Osvik, but he generated a set of optimized blitsliced sboxes for 32-bit implementations of Serpent. His sboxes use only 5 registers, and are faster even though they use more logical operations because data does not need to be moved out of cache. I would suggest using his sboxes, unless better ones are now available. Osvik's sboxes are generally 25% faster on modern processors, and much faster on older ones.

Non bitsliced mode will be extremely slow in software, unless it is on something like a 8-bit cpu.


HMAC ipad and opad choice It is written in the HMAC paper that the ipad=0x36 and opad=0x5C were chosen such that it maximize the Hamming-Distance of the part of the key used in the inner and outer part of the HMAC process.

Since 0x36=0b0110110 and 0x5c=0b1011100, it seems that the Hamming distance is 4, but I would expect that ipad and opad with Hamming distance of 8 would have been used.

Do you know how does those exact ipad and opad values make the scheme stronger?

To quote from the paper you linked:

  The above particular values of $\mathrm{opad}$ and $\mathrm{ipad}$ were chosen to have a very simple representation (to simplify the function’s specification and minimize the potential of implementation errors), and to provide a high Hamming distance between the pads. The latter is intended to exploit the mixing properties attributed to the compression function underlying the hash schemes in use. These properties are important in order to provide computational independence between the two derived keys.

Note that a "high" Hamming distance is not exactly the right term: In fact, $4$ is the mean Hamming distance, i.e., half of the bits are flipped.

For lower distances, we have $\mathrm{opad}\approx\mathrm{ipad}$, thus the keys fed into the compression function are very similar: Those seem more likely to trigger some vulnerability of the underlying compression function than keys without such a simple relation.

Similarly, high Hamming distances imply that $\mathrm{opad}\approx\overline{\mathrm{ipad}}$ (and in the extreme case $8$ we have equality), so there is again a nice relation between the two pads, falling under the same reasoning.
(For example, even though not a hash function, DES has the complement property $E_k(x)=\overline{E_{\bar k}(\bar x)}$, showing that such things can indeed happen in cryptographic primitives.)

Thus, it seems like a reasonable choice to select pads that have the most "non-regular" Hamming distance: This means flipping not too few and not too many bits.

And indeed, it turned out later that those values do matter in some situations: The 2012 paper Generic related-key attacks for HMAC presents a related-key attack on HMAC that depends on the values of $\mathrm{opad}$ and $\mathrm{ipad}$.
The authors state:

  In the case of HMAC this is possible only when $k=m$ or $k=m-1$ since the last bit of ipad and opad are equal (otherwise, for a smaller key the attacker can not build a proper related-key). This shows that the choice of ipad and opad is not anecdotal. For example, if ipad and opad were very similar, then our attacks would work for basically any key length.


How to determine if a hash is pre image resistant or collision free Let $H : \{0,1\}^*\to \{1,\dots, 2^{256}\}$ be a hash function.
Let $p > 2^{256}$ be a safe prime, and $\alpha$ a primitive root for $p$.
Define:
$$H'(m) = H(m || m),\quad H''(m) = \alpha^{H(m)}\bmod p$$
Where $m||m$ is the concatenation of $m$ with itself.

I am confused how when given hash functions like this, how to explain or tell if they are preimage resistant or strongly or weekly collision free? I also am confused on how the hashes, such as $H,H'$, and $H''$ connect to each other in that respect?

Name and exact definition of security properties of hashes vary, depending on level of formalism. Refer to your reference material. However the general idea always is:

preimage resistant (or first preimage resistant): given $h$, it's infeasible to come up with $m$ having hash $h$.
second preimage resistant (or weakly collision free): given $m$, it's infeasible to come up with $m'\ne m$ such that $m$ and $m'$ have the same hash.
collision resistant (or strongly collision free): it's infeasible to come up with $m$ and $m'\ne m$ such that $m$ and $m'$ have the same hash.
indistinguishable from a random member of a Pseudo Random Function family (or indistinguishable from a PRF; or secure in the Random Oracle Model) meaning that lacking some fragment of the definition of the hash, it's infeasible to distinguish it from a random function with the same domains.

Some of these properties are stronger than others. Finding implications involving (3) and those involving (4) is easy, and highly recommended to help grasp these properties. With appropriately large input domain of the hash, (2) implies (1), see this.

On relation between security properties of different hashes: the general idea is to assume an algorithm that can break one security property of one of the hashes, and use it (as a subprogram) to build a new algorithm that breaks one property (often, the same) for another hash. This proves that the second hash is no stronger than the first (or equivalently that if the first hash is secure, then the second is) w.r.t. the security property/properties considered.

For example, take preimage resistance for $H'$. Assume an algorithm $\mathcal A'$ breaking that. It is one which, given $h\in\{1,\dots, 2^{256}\}$ as input, outputs¹,² $m\in\{0,1\}^*$ with $H'(m)=h$; that is an algorithm¹ such that² $H'(\mathcal A'(h))=h$.

By definition of $H'$, for the $m=\mathcal A'(h)$ that this algorithm produces, it also holds $H(m\mathbin\|m)=h$.

Therefore we can devises an algorithm $\mathcal A$ breaking preimage resistance for $H$, as follows:

accept input $h\in\{1,\dots, 2^{256}\}$
compute $m=\mathcal A'(h)$ by invoking the hypothesized algorithm breaking preimage resistance of $H'$
compute and output $m\mathbin\|m$

We see that² $H(\mathcal A(h))=h$ (and the runtime of $\mathcal A$ is only slightly/linearly higher than that of $\mathcal A'$).

We conclude that if $H$ has preimage resistance, then $H'$ also has.

It is possible to make similar demonstrations for other security properties and other pairs of functions in the question.

Hint: In the problem at hand, the function $h\mapsto\alpha^h\bmod p$ is used in the construction of $H''$. Given the stated properties of $p$ and $\alpha$, this function has one demonstrable property and one conjectured property, which can be put to use to derive security properties of $H$ or $H''$, or relations between these properties.

¹ With running time polynomial w.r.t. the width of the output of the hash, but that formalism is not in the question, and can be omitted to some degree.

² With non-negligible probability, though that's sometime left implicit.


Understanding padding oracles - is an attack plausible in my scenario? I have a scheme that, long story short, uses AES in CBC mode to encrypt third-party credentials for user accounts with a password-derived key. It's been mentioned that the use of CBC mode is a vulnerability because it is susceptible to "padding oracle attacks"; the cipher, after being initialized by the legitimate user with the proper key/IV, can be used by an attacker to execute a chosen-ciphertext attack to recover the plaintext without ever discovering the key.

The question is, do I actually have to worry about this type of attack given the way my system uses the cipher, specifically the fact that the cipher instance is only in existence for some seconds before its internal state is erased and it goes out of scope?

Perhaps more background is necessary. The basic scheme is that the user enters their username and password. The password is "stretched" by hashing it with SHA-512, and then that digest is split in half; one side is BCrypted for password verification by the server, the other half is the AES key used to decrypt the user credentials retrieved from the server.

So, the AES cipher isn't being used to maintain an open secure channel with a remote party; it's created, initialized, does its job on one message, and is then cleaned, disposed and garbage collected. This takes less than a second. To my way of thinking, this would make a POA infeasible, because the attacker would need an open, initialized instance of the cipher to bounce his chosen ciphertexts off of, which would take far longer than the second or two that the cipher instance is doing its job. Further, the cipher instance isn't being exposed to anyone outside the computer; if an attacker's in the computer, he has the user's password plain and simple, but an attacker can't even make a network request of the client computer that would involve the cipher in any way.

There are much easier attacks on this scheme as implemented, perhaps the simplest being that the AES key is derived rather simply from a user-chosen password (and we know how much entropy those have).

So, should I worry about the vulnerability of CBC mode to padding oracle attacks in my specific circumstance, or am I reasonably safe from that particular vector and should concentrate on other areas of weakness?

If I understand your scenario correctly, padding oracle attacks are probably not a massive concern, but not for the reasons you seem to believe. Padding oracle attacks have nothing to do with maintained open channels, lack of garbage collection, or time the cipher is kept in memory.

A padding oracle attack requires two things: a ciphertext whose contents you wish to read, and a "padding oracle": more or less, a way to tell if a ciphertext that you've forged passed through the decryption algorithm successfully. If you never decrypting information directly received from users, then you are probably not significantly vulnerable. If users can supply ciphertexts to be decrypted, you are probably vulnerable. If an attacker can write to your database through something like SQL injection, you retrieve and decrypt ciphertexts from the database, and your service can be instructed to decrypt something stored in the database, you have bigger fish to fry, but you are probably also vulnerable to padding oracle attacks.

Long story short: if it is at all plausible that an attacker can feed you ciphertexts to decrypt, you should authenticate ciphertexts. Consider also if the contents of your ciphertexts should remain secure even in the face of other exploits. Since it's very hard to reason about what a motivated attacker might be able to do if given access to your system, you should absolutely default to using an AEAD mode unless you have a overwhelmingly compelling reason not to.

With that out of the way, you should highly reconsider how you handle passwords and encryption keys. SHA-512 by itself is not "key stretching", and the left half of SHA-512 plus bcrypt for digests, plus the right half for keys is tantamount to sprinkling cryptography around like magic pixie dust, expecting it to magick away security concerns.

For password digests, you should use BCrypt. SHA-512 plus BCrypt is probably not worse, per se, but it's unnecessary, and gains you nothing.

Your key derivation, however, is extraordinarily weak. SHA-512 is fast, and an attacker can trivially brute force his way through common passwords and use trial decryption to expose ciphertexts of users with weak passwords. You should use an actual key-stretching function such as PBKDF2. For each user, generate a cryptographically random 128-bit value. Compute the PBKDF2 of the user's password using this value as the salt, SHA-256 as the PRF parameter, an output length corresponding to the key length of your encryption algorithm (16 bytes for AES-128, 32 bytes for AES-256), and a number of iterations calibrated to take around 0.1s on your server hardware. Store the number of iterations and the salt. The output of this function should be used as your encryption key.

And, of course, don't overlook generating unique IVs for each encryption with a given key.


How was the GCM polynomial found? As far as I understand, there is no general way to enumerate irreducible polynomials in a particular finite field, which are similar in nature to prime numbers over the integers.

The GCM mode finite field has order $2^{128}$, which matches the block size of AES, and uses the irreducible polynomial (see source page 8)

$$x^{128} + x^7 + x^2 + x + 1$$

Why does the source PDF not go into any detail regarding the choice and how was it found? It does not even give proof that the polynomial is irreducible.

For the GCM mode polynomial, it's likely that they simply looked it up in a table.  Low-weight irreducible polynomials over ${\rm GF}(2)$ are useful enough that people have spent time compiling lists of them; the one I linked to above (Seroussi 1998) is fairly often cited, and indeed contains the GCM polynomial.

Of course, this just changes the question to how such lists are compiled in the first place.  As the paper linked above notes, the basic procedure is to simply generate successive low-weight polynomials and test them for irreducibility.

The specific test that Seroussi used to generate the linked table was apparently based on Victor Shoup's NTL library, which nowadays can be found here; the GF2XFactoring module in that library provides an IterIrredTest() function that implements "an iterative deterministic irreducibility test, based on DDF."  Conveniently, there are also BuildIrred() and BuildSparseIrred() functions for finding "canonical" irreducible polynomials of a given degree over ${\rm GF}(2)$.

For more details on how irreducibility testing actually works, you might want to take a look at e.g. this answer on math.SE and these slides linked from it (Brent & Zimmermann 2008).  In particular, according to the slides, it would seem that for most practical purposes (i.e. for polynomials of degree less than 100 million or so), a perfectly good way to test if a polynomial $p(x)$ of degree $d$ is irreducible over ${\rm GF}(2)$ is to simply use repeated squaring and modular reduction to test whether $$x^{2^d} \equiv x \pmod{p(x)}.$$

(Ps. There's apparently also a Wikipedia article on factorization of polynomials over finite fields that you might find useful.)


Single theorem adaptive vs non-adaptive non-interactive zero-knowledge proofs I am trying to understand non-interactive zero-knowledge protocols (NIZK). But, I encountered single theorem adaptive and non-adaptive NIZK protocols. According to my understanding,

In adaptive NIZK protocols, simulator ($S$) is divided into two stages ($S_1,S_2$) where in first stage it generates the common reference string and in second stage, it generates the proof for any input using common reference string generated in first phase.

In non-adaptive NIZK protocols, given an input, simulator outputs common reference string along with the proof.

Is this understanding correct?

Is there any way to covert a non-adaptive NIZK protocol to adaptive NIZK?

What is difference between single-theorem and multi-theorem NIZK?

It seems to me that the term "adaptive NIZK" is unclear. Where did you encounter it? If you give me the context, I can probably tell you what it was suppose to mean in this context.

Specifically, adaptive NIZK could refer to:

NIZK with adaptive soundness, where the malicious prover first receives the crs as input, then produces a word and a proof, and wins if the word is not in the language yet the proof is accepted;
NIZK with adaptive zero-knowledge, which matches what you mentioned: the simulator is divided into two parts, and first return a simulated crs, then outputs simulated proofs;
NIZK secure against adaptive adversaries in the UC model, which is more complex.

Assuming you meant "adaptive zero-knowledge", I don't think there is any generic way of transforming non-adaptive NIZKs into adaptive NIZKs; in fact, it's an open problem to build adaptive perfect NIZK arguments from standard assumption (those we have are from non-standard "knowledge-of-exponent-type" assumptions, or satisfy only a weaker property, called adaptive culpable soundness).

For your third question, I don't know if there are group signatures that use non-adaptive NIZKs.

For the last question, in a single-theorem NIZK, the zero-knowledge property is only guaranteed for provers that send a single proof after the crs is generated - to perform more proofs, new crs must be generated. Put otherwise, the length of the crs must be proportional to a bound on the number of proofs that will be executed with this crs. In contrast, in a multi-theorem NIZK, the same crs can be reused an arbitrary (polynomial) number of times for generating proofs. There is a generic transformation from single-theorem to multi-theorem NIZKs that uses only one-way functions, see this paper.


Hashing SHA-512 1000 times SageMathCloud security (http://goo.gl/dCujW1) is as follows:

  Only the hash of your password is stored by the server, which uses 1000 iterations of the sha-512 hash function, with a salt length of 32.

While that does sound like a nice salt, I am a bit doubtful of the 1000-iteration idea. While this does make brute force attacks 1000 times slower, isn't it true that every extra iteration squares your chances of collision?

Baring an improbable tremendous theoretical breakthrough, any odd of any kind of collision among SHA-512 hashes, for any cause except identical input or computing failure, is negligible in practice; we'll thus handle this from a theoretical standpoint.

Let $s=512$ be the hash width; $k=1000$ the number of hash iterations; and $q>0$ the number of stored iterated hashes.

The question worries about chances of collision, I assume in the stored hashes. Such collisions, even if they occurred, have little potential to help an adversary to get access or recover a password, but for the sake of the argument let's consider them anyway (say, the login system searches among all iterated hashes without using the salt as primary index).

If there was no iteration, odds of collisions would be $\approx q\cdot(q-1)/2^{s+1}$. That's also about the odds considering iterations if the salt is rehashed at each step (which is common and would match the question's statement).

With iteration and just re-hashing the previous hash, we have to worry that collisions among the result of the $q\cdot k$ total hashes could also cause a collision of the stored hashes. Because we can neglect that a cycle also gets involved and has just one of the few length that could matter, only collisions occurring after the same number of iteration need to be accounted for, and the odds of collisions among stored hashes are $\approx q\cdot(q-1)\cdot k/2^{s+1}$.

Thus with the worse possible interpretation of the question's quote, odds of collision among stored hashes grow only about linearly with the number of iterations.

The main issues to worry about:

1000 iterations is MUCH insufficient; that might have been useful when PBKDF2 was created, but no longer provides adequate protection against brute force password search in the event of a leak of the password hashes.
Better slow key derivation functions provide much better protection at equal computing cost, see scrypt.


Fully Homomorphic Encryption - state of the art What are the latest advances in fully homomorphic encryption? First of all, I am interested in cryptosystems based on LWE / RLWE and NTRU problems.

I guess the latest real production grade homomorphic library is Microsoft SEAL, which implements the BFV and the CKKS encryption schemes.

I'm not a big MS fan. There are other options to explore:

HELib implements the BGV scheme with GHS optimizations.

NuFHE implements a GPU reference of fully homomorphic encryption on torus

Also checkout the open group site for homomorphic encryption.


What are some approaches to attack an triple key polyalphabetic cipher when the IV key and PT key are known? The cipher is an triple key polyalphabetic cipher also known as an Quagmire IV by the ACA. An example would be here: Quagmire IV example and info (pardon the ads)
I posses the IV key and the PT key. The IV key runs vertically and sets the shifts of the lookup alphabets for the ciphertext. The IV key is the length of the PT and is an plain English phrase. The PT key sets the shifts of the plaintext lookup alphabet. The length of the PT is ~120 characters, is in plain English and I possess an crib consisting of 4 letters and it's location in the ciphertext.
I have read and tried to adapt this method of solving a Quagmire IV but it deals with recovering the PT without the PT key but it does give insight. E.g. if we know the CT key and the IV key, the PT can be reduced to an simple substitution cipher.
I have attempted to attack the cipher using other methods used to solve polyalphabetic ciphers like Kerckhoff's principle and Kaliski but these and other methods I have used to solve simpler polyalphabetic ciphers have not yielded anything.
The question is what is the best manner of attack for this sort of cipher? Even the smallest bit of info about the CT key would be useful. E.g. if I found that the CT key length was 6, I could brute force it. I am not looking for solutions but more techniques/attacks that have some validity to them.
Edited for cipher details (below)
CT

JOZIPMTOHWBFAZPACLRKOHOYSVHLKKRCQTUKJGBGKLCPRFOOACGCFTTDSIQPQRAFKDPMTRXSFOGTKMJRIJGNUTUCVAZNGNNMKAAAMXPLTQCXNQPDJPOKPFA

IV Key

THERESAVOICETHATKEEPSONCALLINGMEDOWNTHEROADTHATSWHEREALWAYSBEEVERYSTOPIMAKEIMAKEANEWFRIENDCANTSTAYFORLONGJUSTTURNAROUND

PT Key

UPSTAIR

Crib

RXSF == THEY

I can't comment yet and have no solution, but I still wanted to post my own analysis and hope it'll get you a bit further. BTW, the site you linked to with the info about Quagmire IV is mine and yes, sorry about the ads! I haven't updated it in many, many years, so I was surprised to see it pop up :)

The first thing to do is try to find plausible candidates for letters in the keyword. I'm absolutely assuming the CT key was produced in the same way the PT keyword was, i.e. a keyed alphabet and not a completely random one. The latter case will require hill-climbing algorithms and is not in scope at this time.

From the crib I could deduce:

P and R are 3 letters apart (2 between them). Since in the regular alphabet there's only one between them, I think both are used in the keyword. PxxR. If you put the R in front, the P ends up at the back of the alphabet and this is unlikely, since that would require almost every letter after the P in a regular alphabet to have been used in the keyword.
I and X are 13 letters apart. I think the I is not part of the keyword, because if you put the I at the front somewhere the X is totally out of place somewhere in the middle and it could only be the 11th, 12th or 13th letter in the keyword and I assume the keyword is shorter.
However, the X may be part of the keyword, since the I ends up near its original location when the X is put at the front, but this requires that at least 5 letters that normally come after the I appear in the keyword, plus one extra letter for every position that X moves to the back. This makes it more likely that the X is the first or second letter in the keyword, than any other.
The M and S are 10 letters apart, where normally they are only 6 letters apart. This implies that either one of them was used in the keyword. Both are possible, since the other letter would end up reasonably close to their original positions in the alphabet. If the M was used, it is most likely one of the last letters in the keyword; if the S was used it is likely one of the first three or four.
The A and F are 24 letters apart, as opposed to the original 5 letters. From this it is highly unlikely that the A alone was used, since that would leave the F way at back of the alphabet. Either both were used in the order of FxA, with one letter between them, or the F alone was used as the second to last letter of the keyword and the A is the beginning of the padding.

Putting this all together, I believe the keyword definitely contains P??R, S or M, and F?A, not necessarily in that order. It may contain an X at the beginning as well.


Where can I find information on the speed of basic hand-operated ciphers? I have a science fair project coming along, and I'd like to focus on a basic cipher (something simple, like a substitution cipher) and how I could make a similar system that would be about equally secure but would be faster to decode. Is there anywhere I could find information beforehand on deciphering speeds or would I have to try get my own results?

You’ll likely have to do your own analysis.
First of all, most of existing literature focuses either on asymptotic speed or specific implementations (such as in the case of hardware based encryption). Neither of which will be very useful to your pen-and-paper scenario.
Second of all, coming up with your own “similar system” implies it is a “new” system and no existing analysis would’ve been done on it.
I recommend that you create a set of “basic operations”, such as lookups in a table, arithmetic operations, copying intermediate result to another piece of paper, etc. This way you can estimate the number of operations the original decipher takes and compare it with that of your new algorithm.
(As this is for a science fair project, I'm leaving out any considerations for the actual security implications.)


How does tls 1.3 cope with man in the middle (in key exchange) in case i cannot do PSK (give the same key to both sides via physical means).
i saw tls1.3 still support DH (doesnt matter that it is DHE or ECDH).
isnt that makes it a weak key exchange?
do they rely on seperate key exchange algo.? (like PAK - x.1035)

TLS 1.3 without PSK (i.e. the usual use-case of TLS) uses a certificate which verifies the authenticity of the service, just like all the other versions of TLS (and SSL). For most typical uses in web browsers, the server's certificate is signed by a certificate authority (CA). It doesn't matter what key exchange algorithm is used as long as it is strong (DH and ECDH are considered strong).

See also The New Illustrated TLS Connection: Every byte explained and reproduced for TLS 1.3.


Where is the key in white-box AES cryptography? After an initial study of white-box cryptography, specially around the first article (Chow et. al.), I understood each step of transforming the lookup tables of AES into new ones.

If I understood it correctly, the purpose is to redefine the AES algorithm to propose new tables in each step and to perform lookups into different tables in order to obfuscate the key.

I have trouble understanding where the key is supposed to be in the white-box version of AES. During the AES development into code, is the key defined statically or it is diffused into tables in a "pre-calculated" manner always before the AES execution?

In whitebox cryptography the attacker is supposed to have access to every detail of the computation and the goal of this implementation is to protect the key, to -usually- avoid it is used on a classical no-whitebox implementation on a different platform.

The goal is that an attacker having access to the whole computation and intermediate values cannot achieve a bigger knowledge of the encryption key as he would have a black-box access (only input/output for all input of his choice).

The perfect way to create a whitebox implementation would be to tabulate the AES: for a given key, one takes all the possible input blocks, compute the encryption on a trusted machine and put the output on a table. In this scenario an attacker would have access only to the input/output and the computation has been done elsewhere. But, of course, this table would be ${HUGE}$ (e.g.: for the AES: $2^{128} \times 128$ bits, I don't even know how to write this quantity, but could be approximated by $2^{92}$ Terabytes). So, a typical solution is to use several lookup tables (noted as LUT) in a networked way. This allows to build an implementation in a less of a Megabyte (700k), even if this size is quite a lot in respect to a standard, no-whitebox implementation. Resume of white-box applied in AES algorithm (slides 18 - 24).

So you are not going to see the key in a whitebox implementation, the key is cut, smashed, embedded in all the tables used to compute a single encryption.

That also means that the key is not loaded somewhere during the computation but has to be embedded before shipping the implementation, and that when one needs do change/update the key, he has to ship another implementation (or on other set of tables).


Security of password hash with known prefix and appendix Assume I have a password that is exactly 32 characters long. I hash it the following way:

Prepend 1524 bytes (known to an attacker)
Append 3356 bytes (known to an attacker)
Do the checksum

It is clearly visible that only a tiny part of the plaintext is variable.

Assume the attacker stole the checksum from a DB. How difficult would it be for them to recover the password or create a collision? What checksum algorithms are more resistant against that?

Yes, I know that one cannot recover a password from a 16-bit CRC-16. Let's assume that the checksum is at least 128 bits long.

What would change if one of pads would disappear?

Except against rainbow tables, it makes no difference whether you've prepended or appended any bytes if they're known and static. Both may as well not exist.

So the scenario is reduced to "doing a checksum of" (presumably trying to hash) a 32-byte password.

There isn't a CRC-128 in common use, but if you extended the CRC algorithm to 128 bits, you'd get a completely insecure transformation. CRC was designed for simplicity and low collision probability, making it reversible. There's a paper specifically on reversing CRC - https://sar.informatik.hu-berlin.de/research/publications/SAR-PR-2006-05/SAR-PR-2006-05_.pdf - and the process can be implemented by a decent high school student.

Algorithms resistant to that - producing a true one-way transformation - are called hashing algorithms, not checksums. Popular examples of hashing algorithms include SHA-3 and SHA-2.

For passwords specifically, an even higher level of security is often called for, such as using key derivation functions (PBKDF) - bcrypt, scrypt, argon2. In addition to the quasi-randomness property that hashes have and CRC don't, PBKDF deliberately tie up additional computer resources to somewhat improve their brute-force resistance.


How many keys does the Playfair Cipher have? I was just studying the Playfair cipher and from what I've understood, it is just a slightly better version of a Caesar cipher, in that it isn't actually mono-alphabetic but rather the 'digrams' are mono-alphabetic. I believe that since it offers a larger combination i.e 26*26=676 digrams, it is better than a Caesar Cipher which would give us a maximum of twenty-six keys. So does this mean that the Playfair Cipher have 676 keys including the duplicate or is it larger than that ?

When we consider that a Playfair key consists of the alphabet (reduced to 25 letters) spread on a 5x5 square, that's $25!$ keys (another formulation consider any string to be a key; then strings leading to the same square are equivalent keys).

The rules of Playfair are such that any rotation of the lines in the square, and any rotation of its columns, lead to an equivalent key (in other words, the square reduce to a torus). It can be proven conclusively that there are no other equivalent keys (note: a transposition of line/columns leads to a key such that 200 out of 600 digrams with distinct letters are mapped to the same diagram as for the original key, and the other 400 are mapped to the digram obtained by exchanging the two letters in the digram mapped by the original key; also, an horizontal or [resp. and] vertical mirroring of the square leaves 500 (resp. 400) digrams invariants; these are near-equivalent related keys, but not equivalent keys).

I conclude Playfair has $25!/{5^2}=620448401733239439360000\approx2^{79}$ distinct keys classes (a 79-bit-key cipher). At least another source agrees.

This is much less than an arbitrary permutation of digrams with distinct letters, which allows $(25\cdot24)!\approx2^{4678}$ keys.

If that's a homework question, I find it excellent to illustrate the notions of equivalent keys, key space, and why a big keyspace is not sufficient for security.


Why is EdDSA collision-resilient with SHA-512? In the Bernstein et al. paper about EdDSA, the authors claim EdDSA is resilient against collisions (i.e. it can still be secure even if the hash function used isn't collision-resistant), drawing on a result from Neven et al. that says that Schnorr signatures are secure when used with a hash function that is random-prefix preimage resistant and random-prefix second-preimage resistant. Bernstein says that

  Neven, Smart, and Warinschi in [60] proposed taking advantage of collision resilience by choosing $H$ to output only $b/2$ bits, reducing the size of compressed signatures by 25%

and then makes the following claim:

  Our verification equation is the same as Schnorr's verification equation with
  double-size hashing instead of half-size hashing, with $\underline{A}$ inserted as an extra hash input, and without Schnorr's compression of $\underline{R}$. These modifications obviously do not compromise security.

However: In Neven, one mention of halving the hash length occurs at page 8, where they note that the herding attack from Kelsey and Kohno allows one to use a lack of collision-resistance for a Merkle–Damgård hash functions to break the random-prefix preimage and second-preimage resistance requirements, and so recommend not using a Merkle–Damgård hash function as-is, and instead truncating it. They present this not as a convenience thing, but a security thing (so that even if collision-resistance is compromised, the two properties needed for Schnorr signatures to be secure aren't necessarily compromised by the herding attack). SHA-512, of course, is a Merkle–Damgård hash function.

Here's my question: I'm pretty sure I didn't catch something the authors of the EdDSA paper somehow missed. There's probably something I'm missing here. What is it?

The relevant part of Neven et al is this:

  What this means for practice is that one should not instantiate the hash function with a Merkle-Damgård iteration of an $n$-bit compression function. Instead, one should probably simply truncate the output of a $2n$-bit hash function to $n$ bits. (Such a method would in our situation be reminiscent of Lucks’ wide-pipe hash [Luc05].) Therefore, using for example the first 128 bits of the SHA-256 hash should in practice provide a security level of 128 bits.

Ed25519 uses SHA-512, a 512-bit hash function. If the herding attack applies but the hash function itself is secure, its security level should be at least about 256 bits (the collision resistance of the hash function). That is way more than the security of the overall algorithm and so not relevant here.

Even if some collision attack on the ~256-bit number that results from the multiplication (after reduction modulo $l$) would allow breaking the signature scheme, that would still not break the claimed ~128-bit security level.

I.e. rather than running into problems due to using a half length Merkle–Damgård hash, Ed25519 uses a conservative double length hash and should not be affected.


Strict Avalanche Criterion and Avalanche criterion? What is the difference between Strict Avalanche Criterion(SAC) and Avalanche criterion?

The definition of avalanche effect is given in the paper of Webster, A. F. "On the design of S-boxes". Advances in Cryptology - Crypto '85 as :

  For a given transformation to exhibit the avalanche effect, an average of one half of the output bits should change whenever a single input bit is complemented.

It is also seen as each bit should have 50% chances to change if you change 1 bit of the input. (strict avalanche)

In the avalanche criterion you look at the output as a whole (average 50% of the bits changes).

In the strict avalanche criterion, you look at each bit one by one and you verify that what ever the other bits will change, it will have a 50% probability to switch.

Related questions:

Hash functions and the Avalanche effect
Calculation of the avalanche effect coefficient


Use of crypto on QR codes for access control I want to create a process whereby registered users receive a QR code on their phone and then they present this code to a camera. The camera should scan the QR code and then decide if the QR code is legitimate, in which case access is granted.

According to my very basic understanding, the camera would be equipped with a "public key" and the QR codes (sent to the users) should all be generated using a matching "private key". The camera then performs a basic decode and allows/denies access.

What cryptographic techniques are suitable? How are they used?

EDIT

The core behind the question is around the event where the web-cam needs to validate a random QR code. This should be achieved using local keys/hashes without the web-cam having to connect to some database in order to validate the QR code. So my question, I suspect, is a very basic one around cryptography: Can the camera have some key stored in memory (typically on a Rasberry Pi) and be able to validate the QR code (again without connecting to the internet). If my question is nonsense then please discard altogether.

The question is about using digital signature for signing access-control 2D-barcodes.

In the simplest form, some authority will generate and hold a private key, with the corresponding public key stored in the access control systems. A message with access rights (e.g. time interval and location for authorized access) will get signed by the authority using the private key, and encoded with (or in) the signature as a 2D-barcode. The access control system reads the 2D-barcode, thus obtaining the message and signature. It then verifies the signature against the message and the public key (that's the signature verification step of digital signature), and (only if the verification succeeds) allows access or not according to the access rights in the message.

It is cryptographically impossible to make an acceptable 2D-barcode without knowing the private key, other than by duplicating verbatim the content (message and matching signature) of a known one. In particular, any attempt at the alteration of a message will cause the signature verification to fail, and access won't be granted. This is obtained with a purely local verification process, as could be carried by almost any CPU.

The use of digital signature starts to make sense when the access control system is distributed: even reverse-engineering a device can't let one make a forged 2D-barcode that gets accepted. That's because the reverse-engineering can not get at the private key, for it's not there.

Among the most common signature standards usable (and routinely used) for this application are DSA, ECDSA, and EdDSA. The signature will add like 64 bytes for 128-bit security. A Raspberry Pi is powerful enough to perform an ECDSA or EdDSA signature verification step in a small fraction of a second.

If we want to make the size overhead incurred by signing as small as possible¹ (because the less information in a 2D-barcode, the easiest it is to read), there is also the short/original Schnorr signature scheme (48-byte for 128-bit security), but AFAIK it is not standardized². There also are BLS signature schemes, but good luck figuring out safe parameters, and I'm not even sure there's any gain.

Digital signature with message recovery could help a little: it embeds some of the messages in the signature. For short messages (below about 192 bytes) the best standard such schemes are the DLP based ones³, which achieve about the same size overhead as the aforementioned Schnorr scheme, with a better security justification and a standard to boast. For larger messages, an RSA/Rabin based scheme⁴ lowers the overhead to 34 bytes, and also greatly reduce the computational overhead of verifying a signature.

An obvious issue with the system is that signed 2D-barcode can still be duplicated, including captured as screenshots and sent electronically.

Notes:

¹ Of course the message size should be as low as possible. The best is using a compact encoding, or when that's not possible after-the-fact data compression to compensate for a lousy encoding. That's independent of crypto.

² Perhaps because simple security arguments for short Schnorr signature are not rigorous, and the latest developments are complex to the point of being hard to interpret.

³ Some standards are ISO/IEC 9796-3 and X9.92-1, see this for bibliography; beware of the patent minefield.

⁴ ISO/IEC 9796-2 scheme 3. It is not patent-encumbered AFAIK, but the standard itself is not legally available online for free.


Are there any practical ways to transfer random data securely? The owner of the random.org service recommends that you do not use randomly generated numbers from their website in cryptographic keys. This makes sense, but it got me wondering. Is it possible to securely transfer random values in such a way that they are still viable for use in cryptography?

They can be trivially transferred with a physical cable, but what about when such an instance is impossible? For instance, when a true random number generator is physically separated from the client which needs random numbers, and both machines are in control by the same person.

Is this practical to do securely?

Is it possible to securely transfer random values in such a way that they are still viable for use in cryptography?

Yes and this is done all the time.

If you use a TLS_RSA cipher suite, the client uses RSA to encrypt key material, i.e. random values, and transfer that securely to the server for key derivation.

  The owner of the random.org service recommends that you do not use randomly generated numbers from their website for use in cryptographic keys.

The reason for this is not the security of transferring the random numbers (random.org is available through TLS), but the fact that you cannot be sure they are not storing or manipulating the numbers:

  We should probably note that while fetching the numbers via secure HTTP would protect them from being observed while in transit, anyone genuinely concerned with security should not trust anyone else (including RANDOM.ORG) to generate their cryptographic keys.

So it is possible, but you would have to trust the one generating and sending the random numbers.


CryptoJS.AES result always has same first few bytes? When using this very minimal CryptoJS AES example:

(Live demo here: http://jsfiddle.net/RwnYL/)

Note that the Key, IV and Salt are always different. But the output (here displayed as Base64) always starts with the same 10 characters. I'm probably missing something, but why is this?

If you decode the resulting cipher text with a base64 decoder it says:

Salted__XXXXXXXXXXX

Where XXXX changes, but "Salted__" doesn't. So I guess it is a prefix added to the ciphertext to define its format.


rotational cryptanalysis on modulo multiplication? I saw the paper 'Rotational Cryptanalysis of ARX', it is effective against design primitives using XOR, addition, and rotation.

http://www.iacr.org/archive/fse2010/61470339/61470339.pdf

However about those that use modulo multiplication (e.g. Multiplication modulo $2^{16}+1$, where the all-zero word (0x0000) is
interpreted as $2^{16}$ (denoted by a circled dot ⊙))?

The rotational cryptanalysis considers applying the transformation $E$ to both $X$ and $\overrightarrow{X}$, where
$$
\overrightarrow{(x_1, x_2,x_3,\ldots, x_n)} = (x_{r+1},x_{r+2},\ldots, x_n, x_1,\ldots, x_r)
$$
for some integer $r$. You know that $\overrightarrow{X} \oplus \overrightarrow{Y} = \overrightarrow{X\oplus Y}$ always, and
$$
\overrightarrow{X} \boxplus\overrightarrow{Y} = \overrightarrow{(X\boxplus Y)}
$$
with quite high probability.

For the modulo multiplication the property does not seem to hold.  I guess you were thinking of applying it to the IDEA block cipher. However, in some situations a modified property holds. For instance, if $X = q2^l$  and $Y = p2^t$ for some small $q,l,t,p$, then
$$
\overrightarrow{X} \odot \overrightarrow{Y} = (q2^{l+r}) (p2^{t+r}) = (pq)2^{t+l+2r} =
\overrightarrow{\overrightarrow{(X\odot Y)}},
$$
i.e. you have double rotation (again with some probability). I wonder if you could exploit in the attacks, because generally we want the same rotation distance $r$ in all internal variables.

To summarize, no one has yet applied rotational cryptanalysis to the multiplication, though there are hopes.


Why do we need to hash both the message and the $h$ value in ElGamal signature? The professor left us a question on ElGamal signatures:

  Given the hash function $H$ and message $M$, choose a random $r$ and compute $h=g^r$ and $H(M||h)$. Show that, if $H(M)$ is used instead of $H(M||h)$, the signature can be existentially forged.

I am struggling with the problem, and I think that maybe we can get one known message signed twice with different $(M, c_1, h_1)$ and $(M, c_2, h_2)$, and then use that to sign some other messages $M'$, but I have no idea how to proceed. Can anyone give me some hints?

It's not a complete answer because an adversary needs control on the random choice of a signing algorithm.

First let me define ElGamal signature to not get lost in notation.
$x \in N$ is the secret key.
$p$ is a prime, it defines $Z_p^*$.
$g$ is a generator of $Z_p^*$.
$y=g^x$ and the public key is $(p, g, g^x)$.
Then $k$ is picked at random from $0<k<p-1$,
$r = g^k \bmod p$, $s = (H(m) - xr)k^{-1} \bmod (p-1)$ and the signature is
$(r,s)$.
Suppose we know two signatures of the message $m$ for different $k$-s:
$\sigma_1 = (g^{k_1} \bmod p, (H(m) - xr)k_1^{-1} \bmod (p-1)) = (r_1, s_1)$ and
$\sigma_2 = (g^{k_2} \bmod p, (H(m) - xr)k_2^{-1} \bmod (p-1)) = (r_2, s_2)$.

Let $\sigma_3=(r_1r_2 \bmod p, s_1 + s_2 \bmod (p-1))$.

Verification of $\sigma_3$ leads us to an equation $(k_1+k_2)(k_1^{-1}+k_2^{-1})\equiv 1 \bmod (p-1)$. If an attacker can choose $k_1, k_2$, then he can probably find proper $p$ and $k_1, k_2$. Otherwise - still a problem.


Decryption a chunk of file with AES We are having a requirement to store large files (~1GB) encrypted and decrypt them when reading. We are looking to use AES-CTR or AES-GCM mode to encrypt the data. There are scenarios where we want to divide the files into chunks/blocks and then decrypt these chunks in parallel. So my question is that is it possible to do it with these algorithms? If yes, what are considerable points while doing it. If no, how best to achieve it (the main requirement is to achieve parallelism).

With AES-CTR, it is trivial; it's actually one of the advantages of using the scheme. In AES-CTR, there is a counter which is incremented for each block, encrypted, and then XOR'ed to the ciphertext in order to obtain the plaintext. To parallelize the decryption of, e.g., 100 blocks, you simply encrypt the counter for the 1st-50th blocks in one thread and the counter of the 50th-100th blocks in another (simply add 50 to the initial counter value and start from there).

AES-GCM is more or less the same, since it also uses something like CTR internally for encryption. You will have to also check the authenticity, but this can also be done in parallel. (Some people are not confortable with starting decryption before checking the authenticity, but that's another discussion...)


NIST security categories (post quantum) Here (https://www.safecrypto.eu/pqclounge/round-2-candidates/) are collected all the proposals which passed the first round of NIST Post-Quantum Cryptography Standardisation process. What does the abbreviations in "NIST security categories" column mean? Where can I find a formal definition of them?

A copy and paste from page 16 of NIST document Submission Requirements and Evaluation Criteria
for the Post-Quantum Cryptography Standardization Process;

Any attack that breaks the relevant security definition must require computational
resources comparable to or greater than those required for key search on a block
cipher with a 128-bit key (e.g. AES128)
Any attack that breaks the relevant security definition must require computational
resources comparable to or greater than those required for collision search on a
256-bit hash function (e.g. SHA256/ SHA3-256)
Any attack that breaks the relevant security definition must require computational
resources comparable to or greater than those required for key search on a block
cipher with a 192-bit key (e.g. AES192)
Any attack that breaks the relevant security definition must require computational
resources comparable to or greater than those required for collision search on a
384-bit hash function (e.g. SHA384/ SHA3-384)
Any attack that breaks the relevant security definition must require computational
resources comparable to or greater than those required for key search on a block
cipher with a 256-bit key (e.g. AES 256)


Using key derived using HKDF or NIST sp800-108 with AES-CCM/GCM Is it safe to use keys derived using HKDF or NIST sp800-108 with AES-CCM/GCM ? The NIST SP800-108 and SP*00-56C spec says "To comply with this Recommendation, the derived keying material shall not be used as a key stream for a stream cipher". AES-CCM/GCM using AES in CTR mode which is a stream cipher. Given the construction of the "expand" portion of HKDF and NIST SP800-108 is very similar/same, is it safe to use the key stream derived from these key derivation functions with these modes of AEAD ?

... the derived keying material shall not be used as a key stream for a stream cipher

Using the derived keying material as a key for AES-GCM is not the same as using the derived keying material as a key stream.

The quote means "don't xor the key material with the plaintext" as your entire encryption process.

AES-GCM does not xor the key with the plaintext. It uses it as the key for AES to generate a key stream, which is completely secure.


What are the pros and cons of Pedersen commitments vs hash-based commitments? Obviously, it's possible to create a commitment scheme comm(r, S) by using a hash function H and computing H(S||r). This scheme is secure under the assumption that H is collision and preimage resistant, which (IMO) is a lighter cryptographic assumption than the discrete log assumption.

So I guess my question is, why are commitment schemes like Pedersen commitments used which do require the latter assumption? What efficiency or security benefits they bring? And are there still any benefits to using hash commitments?

The hash-based commitment scheme you are sketching is in fact not secure under collision resistance and preimage resistance of the hash function. For hiding, you need to assume that the hash function you are using behaves like a random oracle (i.e., whenever queried on a new value it returns a uniformly random value from the output domain of the hash function, and for every repeated query it answers consistently).

The random oracle assumption is an idealizing assumption which is considered to be a rather strong assumption compared to the discrete log assumption.


One way communication with forward secrecy? Is it possible to achieve forward secrecy using a one way communication channel with pre-shared secret?

I have a setup where I need to send some information across a unsafe channel between server A and server B. This communication can only go from A to B so no handshake or two way key exchange is possible.

I could simply share a key between the two servers and use symmetric encryption. But I would like to get forward secrecy if possible so that if the shared keys are compromised in the future the old communication is not compromised.

Is there a known protocol that can do this?

I guess the problem is its impossible to share random session keys like you can in say diffie-hellman and then have to rely on deterministic key generation such as TOTP which derives from the shared secret.

The data to be transmitted is less then 2 kb, all the usual stuff about authentication, replay, tampering etc. still applies.

Is there a known protocol that can do this?

It's easy to see that forward security is impossible with the constraints you have.

Suppose an attacker breaks into B to create a B' with the exact same state.

Then, from now on, when A sends a message to B, the attacker takes that message and also submits it to B'.

B and B' are essentially identical; if B can understand the message, so can B'.

This remains true even if B can generate some local entropy (e.g. has an entropy source whose output the attacker cannot predict); as B cannot send its entropy back to A, it has to understand the message from A no matter what the entropy is (and hence B' can as well, even if its entropy sample is different).


Parallel authentication of encrypted data. What AE type to choose? I've got a system with a slow data transfer channel. Transferring a message through several channels does increase the transfer speed significatnly.
 AES-CBC+HMAC is good except that verifying the MAC cannot be done in parallel.  Encryption can be parallel by using CTR, but MAC calculation still needs to be sequential.

I looked at some AE modes like GCM, CCM, EAX, OCB, etc (actually I'm reading this document: http://www.fi.muni.cz/~xsvenda/docs/AE_comparison_ipics04.pdf ), but still cannot find one that meets all my needs.
Here're the main requirements:

The decryption and verifying integrity must be parallelizable.
The encryption is not required to be parallelizable.
The Message can be of any size. Well, at least up to 100 TBytes.
When encrypting data, the message size may be unknown. So "online  processing" is required for encryption.
High performance is not required, because the data channel speed is the bottleneck.
No patents.

It seems that GCM mode is a way to go, except that it doesn't meet the requirement #3. According to NIST 800-38D GCM supports messages only up to 2^39-256 that is ~512 GB only. However the doc I referenced before states that GCM supports online message processing (without knowing the length of the whole message). Am I missing something? Because having length limitation seems to imply inability of online processing.

Use AES-OCB.  It is patented, but now has a free license for any non-military software use.  Unlike most other CAESAR candidates, OCB has been scrutinized for a while now, and meets all of your criteria other than 6 (assuming you have a good AES implementation).

If the patent is simply too much for you, then use a heavily scrutinized patent-free tweakable block cipher like Threefish in a patent-free mode like Tweakable Authenticated Encryption (TAE) mode.

But, as CodesInChaos points out, you should also break up the message into several pieces and authenticate each piece independently, so you don't waste all day downloading 100 Terabytes that you have to throw away because a single MAC tag at the end doesn't match.  Remember, there are other ways to attack you than just message forgery or breach of privacy - maybe a hacker would be satisfied just wasting your time.


Trapdoors for lattices I refer to an article https://eprint.iacr.org/2011/501. I focus on (a bit modified) Algorithm 1 which runs as follows (in my understanding):
For given $n, m\in \mathbb N$, $q=2^k$ and a distribution $\mathcal D$, algorithm chooses a uniformly random matrix $\overline {\mathbf A}\in \mathbb Z_q^{n\times m-nk}$ and a matrix $\mathbf R \in \mathbb Z_q^{m-nk \times nk }$ from the $\mathcal D$ and outputs a matrix $\mathbf A=[\overline {\mathbf A}\| \mathbf G - \overline {\mathbf A}\mathbf R] \in \mathbb Z_q^{n\times m}$ and a trapdoor $\mathbf R \in \mathbb Z^{m-nk\times nk}$.

If $\mathbf G$ is public and $\overline {\mathbf A}$ can be derived from $\mathbf A$ since $\mathbf A = [\overline {\mathbf A} \| \mathbf A_1]$, why one can not obtain $\mathbf R$? It is important due to $\mathbf R$ contains all information about short basis of $\mathbf A$, which usually treated as a private key, while $\mathbf A$ is a public key.

It is computationally infeasible to find $R$ (or any other short matrix that satisfies the relation) because solving $A R = V \pmod{q}$ for uniformly random $A, V$ is the SIS problem (in its inhomogeneous version).  SIS is provably as hard as solving worst-case approximation problems on lattices.

(Also, for the parameters considered in the paper, $[\bar{A} \mid -\bar{A}R]$ is very close to uniform, so finding a valid trapdoor given $A$ really is equivalent to the SIS problem.)


Brute-forcing Symmetric Keys Random keys are often produced using high-quality random generators. Assuming a key produced for a symmetrical cipher, this means that the number of zeros and ones in the key will, on average, concentrate on about half of the key's length.

Having this in mind, is it anywhere more profitable to start a brute-force attack from bit patterns with similar population counts (that is, with similar counts of ones and zeros)? Will this increase the probability of success?

No, it doesn't help.  It doesn't hurt either; as long as you don't repeat keys, the probability of success is always the same.  That is, if there are $2^n$ possible keys, and you test $\lambda$ of them, the probability you hit the right one is always $\lambda / 2^{n}$.

A key generated by a high quality random number generator (or a good key derivation function) is equidistributed; every possible value has an equal probability of being the correct one.  Yes, most keys will have approximately the same number of 0's and 1's; but that's because most possible values will have approximately the same number of 0's and 1's.


AES key length greater than 256 bits - is it dangerous to do an implementation outside of the standard? I'm making a digital-asset manager written in ActionScript 3, it will be used to manage highly sensitive information.  I'm using the AS3Crypto library (which has quite a good reputation) to implement AES encryption.

When I encrypt data using the AS3Crypto library, using AES-CBC, and a 256-bit key, I'm able to successfully decrypt it with php/mcrypt using the same key/iv.  That is to say, the AS3Crypto implementation seems fine.

When I use a key longer than 256-bits, I'm able to successfully encrypt it and decrypt it with the AS3Crypto library.  Changing just 1 character in key causes the decryption to fail, indicating that the full key is indeed being used, and not truncated to 256-bit.  However, when I try to decrypt the cipher with mcrypt, it fails (unsurprisingly, as the specification for AES states a maximum key-size of 256-bits).

My questions are, taking the below assumptions into consideration, will using a key longer than 256-bits introduce some sort of vulnerability into the encryption?  And if not, will using a longer key theoretically increase resistance from brute-force attacks?

Assumptions:

I understand that a 256-bit key is sufficiently strong
encryption will only take place client-side with the AS3Crypto library, and hence doesn't necessarily need to be compatible with other implementations
the key is a string containing random alpha-numeric characters, and is not derived from a PBKDF
even if using a key longer than 256-bit is overkill, the extra security that it might offer would be appreciated

There is no obvious extension of AES for larger key sizes. At best, AS3Crypto may be hashing the key to 256-bits for you, but the risk that AS3Crypto is doing something horribly insecure in that case is astronomically larger than any benefit that you could gain by having a larger key size.

$2^{256}$ is so huge that the only way that it could ever be brute-forced is by finding a significant AES weakness that would likely make all AES key sizes vulnerable in any case.

Even though you currently don't have any need to use anything other than AS3Crypto, that might change and it would be nice not to have a non-standard cipher in place.

Lastly, if you really do want to exceed AES-256 security (and you are probably fooling yourself, as I think you know), you would be better off XORing with a completely different cipher like Salsa20. Tahoe-LAFS (which is written by people who know what they are doing, crypto-wise) has taken this approach as they are aiming for 100 year security: https://tahoe-lafs.org/trac/tahoe-lafs/wiki/OneHundredYearCryptography.