Can I jettison MAC if I already have SHA1(M)? I'm currently using SSL with AES-CBC and HMAC for a file transfer containing string M.  Now suppose Alice already knows SHA1(M) (and the adversary does not), and she downloads M from Bob using only AES-CBC without a MAC.

Normally this would be ill-advised, but since she can check SHA1(M) after the download completes, isn't this still secure?

The short answer: No.  It is not secure.

Details. To answer the question properly, we first have to decide what we mean by "secure".  In this case, I assume security means confidentiality plus integrity.  So let's talk about each separately.

Integrity: yes, this provides integrity, under your assumptions.  @poncho explained why.
Confidentiality: no, this does not provide strong confidentiality protection.  There are chosen-ciphertext attacks that may allow an active attacker to learn partial information about M.

The details and feasibility of such an attack will depend upon things like exactly what padding scheme you use, whether known plaintext is available, and so on.  However, the basic concept is: the attacker replaces Bob's transmission with a carefully constructed ciphertext, and watches Alice's reaction.  In many systems, Alice's reaction will reveal whether the decrypted message matched Alice's hash.  Thus, the attacker learns 1 bit of information from Alice's reaction.  And, in certain situations, an attacker can leverage this to learn partial information about M, by choosing his ciphertext cleverly.

Read about padding oracle attacks and that sort of thing to learn more.

Summary. Use a message authentication code in encrypt-then-authenticate mode, or use authenticated encryption.  This stuff is tricky and subtle.  Don't try to take shortcuts.  It is too easy to open up a non-obvious security weakness.

More details: (added 7/29) I see some folks don't believe that the confidentiality attacks are possible.  The misplaced confidence in the impossibility of such attacks is an interesting comment on how people's convictions about what is secure are not necessarily correlated to what is actually secure, but I guess I should give further references to demonstrate the possibility of such attacks, as they are non-obvious, counter-intuitive, and quite surprising.  To learn more, see, e.g.,

Attacking the IPsec Standards in Encryption-only Configurations, Jean Paul Degabriele and Kenneth G. Paterson, IEEE Security and Privacy 2007.
Problem areas for the IP security protocols, Steven M. Bellovin, Usenix Security 1996, Section 3.8.
Password Interception in a SSL/TLS Channel, Brice Canvel et al, CRYPTO 2003.
Intercepting Mobile Communications: The Insecurity of 802.11, Nikita Borisov et al, MOBICOM 2001, Sections 4.4.2, 4.5.

Pro tip: you might want to make sure you understand the attacks in those papers before feeling too confident that the scheme proposed here can definitely resist those kinds of attacks.

An example attack: For those who have read the papers, here's a sketch of an example attack against the scheme proposed here.

Let's make some assumptions to keep the example simple.  Suppose that, before encryption, the message M is padded out to a multiple of 16 bytes by appending arbitrary bytes and then a single byte indicating how many bytes of padding should be removed.  Suppose for simplicity of exposition that the message M is always exactly 1 byte long.  This means M will be padded before encryption out to 16 bytes by appending 14 random bytes and then 1 byte with the value 0x0F.  Suppose that the attacker has previously captured plenty of known plaintext and its corresponding encryption, and now the attacker has intercepted the encryption of M and wants to learn something about M.

Now, suppose the attacker has a guess G at the value of the message (G is a single byte), and the attacker wants to confirm whether M=G or not.  Here's how the attacker can confirm his guess.

Let $IV$ denote the IV used when encrypting M; note that $IV$ is known to the attacker.  The attacker looks through his collection of pairs $(P_i,C_i)$ of known input-output pairs for AES (each one is a block width); these can be derived from the known plaintext and ciphertext for a CBC-mode encryption.  The attacker looks for such a pair $(P_i,C_i)$ such that $IV \oplus P_i$ has G as its first byte and has 0xF as its last byte.  The attacker replaces the ciphertext that Bob sent by the ciphertext $(IV, C_i)$ and waits to see Alice's reaction.  If Alice rejects this message, then the attacker learns that $M\ne G$.  If Alice accepts this message, the attacker learns that $M=G$.

Therefore, the possibility of this attack means that the scheme proposed in this question does not provide semantic security: it is not IND-CCA2 secure.  Put in non-technical terms, it does not provide the level of confidentiality protection that we have come to expect from an encryption scheme.  In practice, such a vulnerability might be quite severe and might be readily exploitable by bad guys.

If you've read the research literature that I cited above, none of this is anything especially novel or new.  Of course, if you're not familiar with that research literature, this stuff is thoroughly surprising and unexpected.  So, take this as a lesson about the dangers of departing from accepted practice, even if everything seems fine to you.  If you're not an expert in this area, you probably aren't qualified to judge whether your scheme is secure -- and if you are an expert, I suspect you'll probably be especially leary of departing from accepted practice, given the number of surprising attacks that have been discovered in the past.


multiplicative inverse I actually do want to know how to generate the multiplication inverse (M.I) table, I mean the calculation how the M.I been generated.. such as the M.I of 22 is 5A regarding to the table.. Do you know how to calculate M.I how the 22 will become 5A

22 is the hex encoding of a binary polynomial $f = x^5 + x$ that is used to represent the element of the AES finite field (the field is defined as $F_{2^8} = GF(2)[x] / p(x)$) where $p(x) = x^8+x^4+x^3+x+1$ is the reduction polynomial.

Now, we need to find the multiplicative inverse of $f(x)$, i.e. another polynomial $g(x)$ such that
$$
f(x)\cdot g(x) \equiv 1 \pmod{p(x)}
$$
We can do this either by using extended Euclid algorithm for polynomials or using the fact that $f^{-1}(x) = f^{254}(x)$ because of the Little Fermat's Theorem.

Using a computational algebra package like e.g. GP/PARI we can compute

p = Mod(1,2)*x^8 + Mod(1,2)*x^4 + Mod(1,2)*x^3 + Mod(1,2)*x + Mod(1,2)
f = Mod(1,2)*x^5 + Mod(1,2)*x
g = Mod(f,p)^-1

and we get the result

Mod(Mod(1, 2)*x^6 + Mod(1, 2)*x^4 + Mod(1, 2)*x^3 + Mod(1, 2)*x, Mod(1, 2)*x^8 + Mod(1, 2)*x^4 + Mod(1, 2)*x^3 + Mod(1, 2)*x + Mod(1, 2))

so we get the reduced polynomial $x^6 + x^4 + x^3 + x$ and this encodes as 5A, the table entry that corresponds to 22.

The only element that does not have its multiplicative inverse is 00, so by convention we define that 00 is mapped to 00 again.


Why restricting SHA3 to have only two possible capacities? I just read the presentation slides of John M. Kesley (from NIST) for his invited talk at CHES 2013 about SHA-3 and learned that NIST is going to standardize Keccak with a possibly modified padding scheme. Ok, so far so good. But what I don't understand is why they thought it was a good idea to limit the possible capacity values to 256 and 512 when an implementation could easily support just about any value for the capacity that is a multiple of the word length of 64 bits.

Why did they restrict SHA3 to have only two possible capacities?

2 main reasons:

The 2 capacities match the collision resistance of SHA2 for 32-bit (C=256) and 64-bit (C=512) word sizes.
Simplicity, having only 2 capacity/rate combinations means that it does not have to be chosen or calculated from the digest size.

I have implemented Keccak in software, and forcing only 2 capacities means a lot less code in the absorb/squeeze functions. The idea of only 2 capacities with those values was suggested by the designers of Keccak themselves in section 6.2 of their Sakura tree hashing proposal:

Sakura: a flexible coding for tree hashing

Keccak's SHA3 submission originally specified C=512 for a 256-bit hash and C=1024 for a 512-bit hash. The reduction in the slides means 2 things:

Speed; it is 23% faster for 256-bit hashes and a whopping 89% faster for 512-bit hashes due to the corresponding rate changes
Security; resistance against preimage and collision drops from $2^n$ to $2^{n/2}$, where n is the digest size in bits, this would make SHA3 weaker than SHA2, which has preimage resistance of $2^n$

Keep in mind that SHA3 has not even reached draft stage yet, and there are plenty of people who disagree with the chosen capacities, so it may very well change prior to FIPS 202.


Are multi move proof protocols still "sigma protocols"? Conventionally, sigma protocols are defined as being a three-move protocol (1. commit, 2. challenge, 3. response). Reading papers like "Bulletproofs" (Bunz, Bootle, Boneh et al., 2018), it feels like the authors avoid to call their protocols "sigma protocols", although their protocols are always repeats of either 1, 2 and 3 or only 2 and 3; i.e., the verifier only issues (field element) challenges and the prover repeats a response and commit.

Is there a technical reason that the term "sigma protocol" cannot be generalised to multi-move protocols?

There is no technical reason while it couldn't - but the term $\Sigma$-protocol was specifically invented to mean three-round public-coin honest-verifier zero-knowledge proof system. Note that the very choice of the greek letter $\Sigma$ was made because it (kind of) picturally represents the interaction pattern in a three-move protocol (arguably, one could also kind of see a four move protocol in it :p).

Note that interaction is a big deal in cryptography: more rounds introduce more latency, and this is very often the main efficiency bottleneck in protocols (think of a protocol between London and Sao Paulo: a 30-round protocol would take 3 seconds counting solely the latency, and is doomed to take at least one full second unless the parties can send messages faster than light - this means that 1 second is here a strict physical efficiency lower bound, unlike communication and computation which we can always improve with more bandwidth or more processors). Hence it makes sense to distinguish, through a specific name, protocols which enjoy the very desirable feature of having only three rounds (which is the minimum we can hope for in the plain model, at least if we want honest-verifier zero-knowledge - of course, in the common reference string model or in the ROM, we can have non-interactive proofs, which are also a big deal in crypto).

For many-round generalizations of $\Sigma$-protocol, I'd recommend calling them by their natural name, public-coin HVZK proofs. Note that the form "commitment - challenge - response" is characteristic of public-coin proofs in general, not only of $\Sigma$-protocols.


How convert Point on Curve into AES key? I'm playing around with ECC, trying to encrypt traffic between my webapp and backend (its not a product, im trying to learn and understand more about ECC)
I managed to generate keys, successful run key exchange and got same point on both ends.
Now I wonder how I should convert my point which has 2 coordinates into AES key.

Most symmetric cryptographic algorithms requires a key that is indistinguishable from random. This means that the process used to generate the key must have a uniform, independent distribution over all bit-strings of the appropriate length. Using a non-uniformly-random key not only reduces the brute force needed to guess it, but may also open the door to related-key attacks.
The expressions “key agreement” and “key exchange” are often used to mean a mechanism like (elliptic curve) Diffie-Hellman, but (EC)DH itself does not produce a key, it only produces a shared secret. This secret is in some numerical range that depends on the curve: not all $2^n$-bit values are possible. Even within this range, it is not uniformly distributed (it can't be since there isn't the same number of private points and public coordinates).
To go from the shared secret to a key, you need to use a key derivation function. A KDF takes a secret which has a cryptographically high number of possible values but may not be uniformly distributed, and has output that is indistinguishable from random to anyone who doesn't know the secret.
In a pinch, if you only need one symmetric key from the key exchange, hashing the shared secret with a cryptographic hash such as SHA-256 or SHA-512 is fine. If you need more key material than one hash's length, or if you prefer to use a standard construction that may be more robust in case a partial weakness is discovered in a hash function, there are (too) many standardized key derivation functions, for example HKDF (robust and popular), the TLS 1.2 PRF (a variant of HKDF which is specific to TLS), the NIST SP 800-56C key derivation functions (some hash-based like HKDF, some AES-based), etc.


Finding $f^{-1}$ in the YASHE keygen algorithm In the YASHE (Yet Another Somewhat Homomorphic Encryption) algorithm, the beggining of the key generation step specifies:

Sample $\ f',g ← χ_{key}$ and let $\ f = [tf' + 1]_q$.
If $\ f$ is not invertible
modulo $q$, choose a new $\ f'$.
Compute the inverse $\ f^{−1} ∈ R$ of $\ f$ modulo $q$ and set $h = [t\ g\ f^{−1}]_q$.

The previous section of the algorithm descibres what each of these parameters are

Given the security parameter $λ$, fix a positive integer $d$ that determines
$R$, moduli $q$ and $t$ with $1 < t < q$, distributions $χ_{key}$, $χ_{err}$ on
$R$, and an integer base $w > 1$.

How can you tell if:

$f$ is invertible?

and if so

what $\ f^{-1}$ is?

To invert a polynomial in the quotient ring $F_q[X]/(\phi(X))$ there are two cases:

-> Either $\phi$ is irreducible modulo $q$, in which case every polynomial is inversible

-> Either $\phi$ is not irreducible, and one reasons with the Chinese remainder theorem.

In the first case, to find the inverse, just use Extended Euclides to find two polynomials $U,V$ such that

$$Uf+V\phi=1$$

(I'll let you deduce why $gcd(\phi,f)=1$) and therefore $Uf=1 \in R$.

For the YASHE parameters, $\phi$ is not irreducible, and therefore a quick answer to your question is

$\mbox{ if } gcd(f,\phi)\neq 1$ then $\phi$ is not invertible,
if $gcd(f,\phi)= 1$ use Euclides as before.


Raw public keys vs PSK in TLS Is there any advantage in using raw public keys (RFC 7250) in comparison with pre-shared keys (RFC 4279) in TLS, when I need client authentication and have an unique key per client deployed to them out of band?

I'll assume that you have many clients talking to a single server (having many servers would only tend to exacerbate the differences). With raw public keys, the server has to have the public key of each client handy. Exposure of these public keys may be a privacy violation, but does not compromise the confidentiality and integrity of the communication. With pre-shared keys, the server has to have the secret key of each client handy. Exposure of these secret keys makes it impossible to communicate securely with the clients (unless you have an out-of-band protocol to revoke the key and generate a new one). This gives public keys a huge security advantage.

I do not recommend using pre-shared keys except in a small network where the pre-shared key is generated during an enrollment phrase for very limited client devices on which asymmetric cryptography is unrealistic, and either the loss of a client is not a big deal or all the devices are in the same physical area so a physical compromise of a single client is not a relevant threat.


Secure Sketch Construction I would like a user to choose a point on an image which is represented by (x,y). This is meant to be a security token. When a user uses this location to login they are unlikely to to choose the exact same (x,y), rather they will choose a point nearby (x_g, y_g). The user may also be required to enter a password.

ATM I'm thinking of using a simple modulus function that will round (x,y) => (x mod 16, y mod 16). Other ideas include:

 multiplying x,y prior to applying the modulus function, (x,y) => x*y mod 16
 adding a salt to x and y prior to applying the modulus function, (x,y) => (x+salt mod 16, y+salt mod 16)
  adding the numerical representation of a hashed password to x and y. (x,y) => (x+pwordHash mod 16, y+pwordHash mod 16)

I'm also considering how this maybe extended to more than one point.

Problem

I wish to know if any of the above ideas are suitable or if there exists better better solutions for calculating a secure sketch. It is assumed that an attacker will have access to the salt and the secure sketch. The system will not store any record(i.e hash) of the actual point. The user will need to verify that the system has found the correct point.

One standard solution is described in the following research paper:

Robust discretization, with an application to graphical passwords.  Jean-Camille Birget and Dawei Hong and Nasir Memon.  eprint 2003/168.

That paper shows how to deal with the problem that the user's second point might be close to, but not exactly the same as, their original point.  In other words.... exactly your problem.

There might be more recent work on this problem.  You could do a literature search, starting from the above paper (e.g., looking at other papers that cite it) to see whether there are other better solutions.


Is there a known vulnerability when using identical key and salt with PBKDF2? For optimum security, a random salt should be chosen for PBKDF2.

I came across a scenario where I  produce a hash of a random file that serves as the "password". Due to the nature of files, this has similar entropy issues as a "normal" password.

What would happen now if I decided to take the same (low-entropy) hash as the salt, too?  Is there a known attack on this? Of course, in this scenario the salt would be kept secret. But still, since it is not entirely random, does this compromise the overall security, and if so, how badly? I know that for example "key as IV" severely compromises certain ciphers, so I'm afraid it could do harm in this situation, too.

Using the password itself (or anything similar predictable) instead of an independent random value as the salt denies the whole benefit of salt:

Same passwords (passphrases) give now the same key, instead a different one. So, if two users happen to choose the same favorite image as their password, they get the same key, and thus an attacker can use this fact to easier get the key.
If an attacker bruteforces your "password" database, he can attack multiple passwords in parallel, since they don't use different (independent) salts.

If you have a way to generate good quality random numbers (which should be the case on every normal personal computer), generate a random salt and put it at the start of your encrypted file (like a normal initialization vector).


How to perform the initial permutations 64-Bit DES to derive $K$? Perform DES encryption on the first 64-bit plaintext only, what are these 0's and 1's? Do they mean that I need to use this value 111101 to derive $K$?

I want to know how to use initial permutation to derive $K$ using permuted choice 1 and permute choice 2.

I want to know how to use initial permutation to derive $K$ using permuted choice 1 and permute choice 2

You start with the DES key $K$, usually expressed as 8 bytes. That's 64 bits. DES number these bits from 1 to 64, starting with high-order bit on the first byte in reading order, moving to lower-order bit, then after the 8th bit of a byte moving to the next byte in reading order, so that bit 42 is the second-highest-order bit of to the 6th byte in reading order, testable by binary AND of that byte with 40h.

From these bits 64 bits of $K$ it is extracted two 28-bit quantities $C_0$ and $D_0$ by picking bits per table $PC1$. The top (resp. bottom) of this table gives the bit numbers in $K$ of the bits forming $C_0$ (resp. $D_0$). You'll notice that $PC1$ contains no multiple of 8, meaning that the low-order bit of each byte of $K$ is ignored. This deliberately weakens DES.

Bits of $C_0$ are numbered 1 to 28, and bits of $D_0$ are numbered 29 to 56, in reading order of $PC1$.

For the first round of encryption, from $C_0\mathbin\|D_0$ it is extracted eight 6-bit quantities (the subkeys 1 to 8 for the first round) by picking bits per table $PC2$, which lines gives the bit numbers in $C_0\mathbin\|D_0$ of the bits forming each 6-bit quantities. Eight bits of $C_0\mathbin\|D_0$ are left aside, but will be used in the next round, after some rotation of $C_0$ (resp. $D_0$) yielding $C_1$ (resp. $D_1$).


How many required known plaintexts for an attack are considered insecure? I stumbled over this problem when looking at symmetrical block ciphers with a relatively small block size like 32 bit.

When I was looking at more common block ciphers with a 64 bit, I learned that they can be considered secure when the number of plaintexts required for a known/chosen-plaintext attack is relatively high ($~2^{40}$ - $2^{64}$).

I have two questions.

Firstly, is this a correct threshold for considering a cipher secure?
And secondly, does this mean that all 32-bit block ciphers are inherently insecure?

Another question that I asked after discussing my original post: Speaking in general terms, assuming that you have found an optimal attack for a block cipher that requires x known plaintexts or y chosen plaintexts. How large would x/y have to be so that the cipher could be considered secure?

Firstly, is this a correct threshold for considering a cipher secure?

Not exactly. Security is a spectrum, so what is secure for some applications may not be secure for others. Is a $2^{-64}$ probability of attack success too much? For some it is far too high. For others, even $2^{-32}$ is fine. In the case of known plaintext attacks, an attacker is usually assumed to have as much known plaintext as they want. In such cases, the bounds are placed on the amount of plaintexts that can be reasonably stored and processed. That is, a petabyte of known plaintext may be assumed (high-speed hardware that behaves as an encryption oracle may allow this), but $10^{90}$ exabytes? Usually not.

As stated, your question doesn't have an objective answer. You would need to append "when performing a specific number of encryptions" to get a real answer, in which case you consult the effects of block size on certain modes of operation. For example, Blowfish is a 64-bit block cipher and is considered secure when encrypting, say, one gigabyte of data under a given key. You can calculate the precise requirements for an attack under those conditions and show that the attack is not practical. If, on the other hand, you encrypt a hundred gigabytes, things will get nasty when using that block size.

A known plaintext attack for a given cipher is usually considered not to be a problem if either:

The specifications make it such that it is impossible to obtain enough known plaintext, or
The amount of known plaintext required would be so vast that no one could encrypt that much.

An example of the first reason for not worrying about known plaintext attacks is in two-level E0, as used in some older versions of Bluetooth. The E0 stream cipher is extremely vulnerable to known plaintext attacks. Rather than vastly modifying the Bluetooth specifications, an easier mitigation was to require rekeying before enough data is transmitted to provide enough known plaintexts to perform an attack.

It turns out that the best attack against E0 requires a bit of known plaintext from only $2^{23.8}$ frames, but the Blutooth protocol allows up to $2^{26}$ frames to be encrypted under a single key, rendering E0 more insecure than implied above.

An example of the second reason would be a 128-bit block cipher in CTR mode. The amount of data required to perform an attack on it is staggeringly huge. An online cost of $2^{64}$ is really quite massive.

  And secondly, does this mean that all 32-bit block ciphers are inherently insecure?

For the vast majority of uses, yes. For those asking if a 32-bit block size is too small, also yes. However there are a few edge cases when that block size is acceptable. This is only the case if truly minuscule amounts of data are being encrypted under a single key. Encrypting small session tags is one example.

The cipher Speck32/64, for example, is considered to be secure despite having a 32-bit block size and a 64-bit key size. It provides 64 bits of security under the constraints that only a trivial amount of data can be encrypted with it. But that doesn't mean you should be encrypting your hard drive with Speck32/64. That is because those parameters make it vulnerable to generic attacks under realistic conditions.

A generic attack is one that applies even to an ideal, perfect block cipher and is utterly independent of its internal workings. Brute force of the key and issues caused by the birthday bound when used with certain block modes are both kinds of generic attacks. A block cipher is not considered inherently insecure in the cryptographic sense just because a generic attack may apply to it, but it may be considered insecure by practitioners. After all, an attacker doesn't care that they broke something with a generic attack because you used a small key or a small block size instead of using some fancy and complex cryptanalysis.

Generally, you should assume the following statements about block sizes to be true:

256 bits is always safe from the limitations imposed by the birthday bound.
128 bits is safe for the vast majority of use cases with realistic amounts of data.
64 bits is worryingly small, but is acceptable if used carefully and not for a lot of data.
32 bits is only safe in extremely rare circumstances. For others, it is horribly insecure.


At what point does passphrase strength match the strength of the cipher? Let's say that I have an ordinary hard drive encrypted with VeraCrypt 1.0e full disk encryption and implementing:

-AES

-RIPEMD-160 Hash Algorithm

Now let's say that for an arbitrary machine, the amount time that it takes to make 1 guess at the master encryption key itself is equal to 1 unit of time. (I understand that, in practical terms, it is beyond infeasible to attempt to crack the master encryption key of AES-256. This is a purely theoretical question.) Knowing that VeraCrypt uses 327,661 iterations of PBKDF2-RIPEMD-160, how many units of time would it take to check 1 password?

What I am interested to know is, at what point K, where K is the keyspace of the randomly generated password, does the strength of the password match the strength of the cipher itself, knowing that the former will have to been run through 327,661 iterations of PBKDF2-RIPEMD-160 to arrive at the latter, where an equivalence of strength is defined as an equivalence of the amount of time that, on average, a brute-force attack would take.

Assuming that the amount of time that it would take for 1 iteration of PBKDF2 to occur = the amount of time that it would take to make 1 check at the master encryption key itself (which I DO NOT simply assume to be a correct assumption), then 327,661 iterations adds log(327661)/log(2) = 18.3 bits of entropy to the overall "strength" of the passphrase. It seems that finding an answer to my question would yield the logical upper-limit of password strength, the point after which it makes no sense to use a [password + key derivation function] whose average time to crack is longer than that of the cipher master encryption key itself.

If I'm not missing some important point here, that's rather trivial to calculate. As implicitly stated in your question, the attacker has two possible ways to brute-force the encryption key: either by brute-forcing the encryption key itself or by brute-forcing the user-entered password.

Given the numbers of iterations of the key derivation function n, the time per kdf iteration tkdf, the length of the encryption key b (in bits) and the time per invocation of the actual encryption algorithm tenc, the average time needed to crack the encryption key itself (by testing half of the available keyspace) is

1/2⋅2b⋅tenc.

The average time to crack the user-entered password is

1/2⋅K⋅(n⋅tkdf+tenc),

with K=cl being the entirety of all passwords available to the user (c: number of characters available, l: length of password).

In your scenario, tenc=tkdf=1, and n=327661. Assuming AES-256 is used (b=256), one has to solve the equation

1/2⋅2b⋅tenc = 2256 = K⋅327662 = 1/2⋅K⋅(n⋅tkdf+tenc),

which yields (approximately) K=5.9447⋅1035. Assuming an available keyspace of 90 characters (which most users aren't likely to even find on their keyboards), this translates to approximately l=36.

(Disclaimer: I'm neither a mathematician nor an crypto expert. In case of any mathematical or semantic error, please comment.)

Related: https://security.stackexchange.com/questions/74566/long-passwords-and-key-derivation-functions


SHA512withRSA - Looking for details about the Signature Algorithm I am trying to find information about the Signature Algorithm SHA512withRSA and have been unsuccessful so far.

In the current state, the signature is too long, so I would like to check the code for overhead and try to remove reduce the size.

Can anybody give me some pointers on how to achieve that.

References

Related to your reference request: SHA512withRSA points to the RSA Signature Scheme with Appendix based on PKCS #1 v1.5 with SHA-512 hash function.

This means you’re looking for reference documentation describing RSA PKCS1 v1.5 (see: RFC2313) signatures with SHA512 (see: RFC6234) hash and X.509 encoding format.

Removing “overhead” from code

As for the part of your question on how to achieve the removal of overhead in your code: diving into that could quickly become off-topic for Crypto.SE and it would probably be more suitable for StackOverflow anyway. Nevertheless – since your question indicates you’re new to the reference documentations and RFCs describing SHA2, RSA, etc. – I would like to add my two cents to your code-modification idea…

Cryptographic implementations rarely contain or produce (what you call) “overhead”. Therefore, I would like to strongly discourage you from stripping or modifying any part of code that represents, interacts, or relates to cryptographical algorithms or schemes. Doing so has a high probability of introducing issues – which might range from simple software bugs, up to a dangerous situation where the removal of code is equal to the voiding (= removal) of cryptographic security. You surely don’t want the later to happen. Instead of fiddling with the code, you should simply rely a tested and well-vetted implementation. There are many of them out there, available in almost every programming language you could wish for.


one-pass deterministic authenticated encryption suppose there is a router with limited storage but good network connection; it could be a good worker for deterministic authenticated encryption on streams; that means it receives data from another machine, encrypts and sends it back; however, siv algorithms need to calculate iv over the entire plaintext before that iv is usable in the encryption; that is a two-pass algorithm;

there are stream-able mac and encryption algorithms; but the stream does not come back again; and the router has too limited storage to buffer the entire stream; this effectively means the algorithm needs to be one-pass; are there any known solutions to this problem?

It is impossible for a one-pass algorithm to achieve the highest nonce-reuse security notion which only leaks equality of messages because the first few bits can't depend on the last few bits.
The best one could hope for is that the length of common prefixes between any two pairs of messages is leaked on nonce-reuse. One can strengthen this to only leaking the length of common prefixes for equal-length messages by prepending the message length before encryption.

If you want to achieve this strongest one-pass security notion, you can't use a paralellizable encryption algorithm because each bit / block has to depend on all previous ones which by definition is not possible for parallelizable schemes.

As for MACs, if you use a PRF-based MAC, like AES-PMAC (which is parallelizable) or AES-CMAC you should get plenty of robustness to nonce re-use, as these are deterministic MACs to begin with.

As for encryption, all the fancy modes are out of the question and I think the best bet you have is actually CBC. This is due to the fact that CBC does block-by-block processing which reduces the accuracy of the "common prefix" to number of totally equal blocks which should prevent an adversary from using an attack that guesses a small amount of bits at once until they get a longer shared prefix to recover a message as the smallest group for this would be 128 bit.

So in total, the best option you probably have is to use (AES-)CBC-then-PRF with AES-PMAC or AES-CMAC as PRFs.


Advantages of Pallier vs Goldwasser-Micali It is easy to see that both Pallier and Goldwasser-Micali are homomorphic addition schemes and are secure but what would be the advantages of choosing one over the other?

They're both additively homomorphic, but over different groups.

With Goldwasser-Micali, you can, given $E(x)$ and $E(y)$, compute $E(x \oplus y)$ (where $\oplus$ is exclusive or)

With Pallier, you can, given $E(x)$ and $E(y)$, compute $E(x + y \bmod n)$, where $n$ is a large integer; this implies that, given $E(x)$ and $k$, you can compute $E(kx \bmod n)$

Which is appropriate depends on what operation you need to perform on the encrypted data.

In my experience, we almost always want the operations that Pallier provides.


Multiple iterations of AES for key derivation? The keepass password manager uses multiple rounds of AES for its key derivation, as described here.  I was somewhat surprised that it wasn't using pbkdf2, bcrypt, or something more common.  Essentially, the key derivation is:

key = sha256(password)
cipher = AES(random_seed1, ECB)
for i in number_of_iterations:
  key = cipher.encrypt(key)
key = sha256(key)
key = sha256(random_seed2 + key)

Is there a name for this kdf?  Are there other systems that use something similar?  I'm mostly interested in general background info on the above approach.  Are there any weaknesses in this approach?  It seems considerably simpler than pbkdf2 and bcrypt.

One of the advantages of schemes like scrypt and bcrypt is that they are designed to be "hard" to brute-force. That is, the actual guts of the algorithm are designed to continuously use something that is difficult for a specialized implementation to speed up. For example, scrypt is based on sequential memory-hard operations, which makes sequential memory access a bottleneck of the computation process (meaning that the CPU is idle waiting on memory for some of the time).

This scheme doesn't leverage such a problem, and I would further argue that it's choke-point is pragmatically easy to brute-force due to the prevalence of AES-NI. For an attacker with AES-NI, a scheme like this would possibly the easiest type of scheme to brute-force because the choke-point uses the fastest cryptographic algorithm the attacker has access to.


Are CSPRNGs quantum-resistant? It's fairly well known that Shor's algorithm kills RSA, DSA, ECDSA, DH, ... and that symmetric ciphers (AES and 3DES) and hashes (SHA-2, SHA-3) are safe as long as you double your key size / output size against a Grover search. (See slide 3 in this NIST presentation.)

My question is: nobody has mentioned random number generators either way, safe or unsafe. (As evidence, the NIST Draft Report on Post-Quantum Crypto has 0 hits for "RNG"). Is this because it's obvious to the experts, or because the research has not been done yet?

My understanding is that CSPRNGs are built on top of hashes and block ciphers, which are quantum-resistant themselves, but I would really like a definitive statement that CSPRNGs are OK, or if not, then some issues that I should be aware of / concerned about.

The best generic attack against a PRG (i.e. an attack that does not use any internal structure of a construction and hence works for any PRG) is exhaustive search for a seed. I think this was not done yet but it is very likely that the optimality of Grover's algorithm carries over to this setting. This would mean that for $n$ bit seeds, the best attack requires $O(2^{n/2})$ evaluations of the PRG.

For PRGs build from hash functions and block ciphers this should be the case also for specific, non-generic attacks (assuming the used hash / BC is post-quantum). Of course, if you use a number theory based PRG like Blum-Blum-Shub Shor's algorithm kicks in.


Elliptic curve and embedding degree I am new to ECC. I am confused about what the embedding degree in an elliptic curve group represents and what is the impact of its values on the curve and security (small values or large values?)

What does the following mean:

  The elliptic curve group used has a 160-bit group order, the base field size is 512-bit, the embedding degree is 2

Informally, you can think of the embedding degree as the smallest integer $k$ that lets you transform or embed an instance of the elliptic curve discrete logarithm problem (ECDLP) over an elliptic $E(\mathbb{F}_p)$ into an instance of the discrete log problem (DLP) over the field $\mathbb{F}_{p^k}$.

Answering the specific question: we have an elliptic curve over a finite field $E(\mathbb{F}_p)$, where $\log(p) = 512$. There is a subgroup with order $\log(q) = 160$ bits. Finally, there is a transformation from the elliptic curve to $\mathbb{F}_{p^2}$, where $p^2$ has $\log p^2 = 1024$ bits. (The exponent "$2$" here is the embedding degree.)

Recall that the fastest algorithms known for solving the ECDLP are of order $O(\sqrt{p})$ steps for the ECDLP over $E(\mathbb{F}_p)$, whereas the DLP can be solved in subexponential time using, say, the index calculus. This transformation opens up the solution of the ECDLP to techniques from DLP, depending on the curve you choose.

Generally speaking, you want $k$ to be large to resist faster solution via transformation to the DLP.

I'm leaving out heavier details because the OP was new to ECC, but to be more precise, if you have a curve $E(\mathbb{F}_p)$, and one point in $E(\mathbb{F}_p)$ has order $q$ where $q \neq p$ is a prime, then the embedding degree with respect to $q$ is the smallest value $k$ such that $q | p^k - 1$, or $p^k \equiv 1 \bmod q$, assuming $p \not\equiv 1 \bmod q$.

I also left out that the Weil pairing does the embedding, and is used in the MOV algorithm. A similar attack is the Frey-Rück attack carried out using Tate pairings.


Prove that this protocol based on square roots modulo $n$ is zero knowledge Consider the following (zero knowledge) protocol based on the hardness of finding square roots modulo $n$. The Prover states that he knows a square root $x$ modulo $n$ of $y$, i.e., $y = x^2 \pmod n$.

The Prover randomly chooses $a \in \mathbb{Z_n^\times}$ and sends $r=a^2 \pmod n$ to the Verifier
The Verifier randomly chooses $b \in \{0,1\}$ and sends it to the Prover
The Prover sends to the Verifier the value $w=x^ba \pmod n$
V accepts if $w^2 = y^br$; otherwise the Verifier rejects

This protocol is repeated a sufficiently large number of times in order to convince the Verifier that the Prover really knows $x$.
This protocol is sound and complete (if the prover is dishonest, then he is detected with $1/2$ probability each time the protocol is ran.)

  How can we prove that this protocol is indeed Zero Knowledge?

Thanks in advance.

Here's the simulator $S$ to replace $P$ for challenge $y = x^2 \mod n$:

Choose $a$ randomly from $\mathbb{Z}_n$, draw a bit $b'$ uniformly.
Send $a^2 y^{-b'} \mod n$ to $V$. The inversion is done in $\mathbb{Z}_n$ of course.
$V$ replies with $b$:

If $b = b'$: send $a$ to $V$
Otherwise: abort

If $b'$ is drawn uniformly, then it doesn't matter how $b$ is chosen - the simulator always has exactly probability $0.5$ for the case $b = b'$ for a successfull verification.


Certificate revocation When someone claims that the private key corresponding to the public key  has been stolen, and sends to the CA a statement of this fact signed with respect to public key pk.

Why doesn't the CA need to check his identity in this case, and why is there no concern

that the person who has stolen his key can forge signatures with respect to pk?

There are two cases to distinguish: The attacker issues the revokation or the owner issues the revokation.

Attacker revoking the cert. In this case the attacker has the private key and uses this to issue a revokation. He thus effectively takes any use out he could get out of theh certificate and the certificate is revoked as it should be in such a situation."Thank you attacker, you just did my job  without me having noticed the breach!"
Owner revoking the cert. The owner wants to prevent missuse of the cert and thus revokes it. This stops the attacker. Everything as it's supposed to be.


How are primes generated for RSA? As I understand it, the RSA algorithm is based on finding two large primes (p and q) and multiplying them. The security aspect is based on the fact that it's difficult to factor it back into p and q. Now, since RSA keys are so large (often 1024 bits and above), the primes have to be at least half that (at least 512 bits then). Such large primes would be difficult to generate (you'd have to check many, many numbers and try to factor each of them), so I understand that the typical approach is to use pre-generated lists of large primes.

But doesn't that make the key very easy to crack? Even if the list container 1,000,000 primes (which I find unlikely), checking all the combinations would only take a couple of hours on a typical desktop computer.

Which part have I misunderstood?

You don't use a pre-generated list of primes. That would make it easy to crack as you note. The algorithm you want to use would be something like this (see note 4.51 in HAC, see also an answer on crypto.SE):

Generate a random $512$ bit odd number, say $p$
Test to see if $p$ is prime; if it is, return $p$; this is expected to occur after testing about $Log(p)/2 \sim 177$ candidates
Otherwise set $p = p+2$, goto 2

There are other methods to generate primes (e.g., do step 1, if step 2 fails goto step 1). The method I outlined is what OpenSSL uses though.

For an official, public standard on RSA key generation, see FIPS 186-4, section 5.1 and Appendix B.3.1.


What are the separate single DES keys from a triple DES key? Suppose my 192 bit triple DES key (in hex) is

0123456789ABCDEFFEDCBA987654321089ABCDEF01234567

What are the keys for the separate single DES operations? In this case the 168 bits triple DES key includes the parity bits to make the key size ($64 \times 3 = 192$ bits).

The single DES keys are commonly just split in three keys, where the first key is used for the first encryption of the message block itself, the second one for the decryption of the previous result and the third one for encryption of the decryption result.

So basically you'd have: $\newcommand{Enc}{\operatorname{Enc}}\newcommand{Dec}{\operatorname{Dec}}$

$$\Enc'_{(k_1, k_2, k_3)} \equiv \Enc_{k_3}(\Dec_{k_2}(\Enc_{k_1}(m)))$$

and of course

$$\Dec'_{(k_1, k_2, k_3)} \equiv \Dec_{k_1}(\Enc_{k_2}(\Dec_{k_3}(m)))$$

where $\Enc'$ and $\Dec'$ are the encryption and decryption operations of TDEA, commonly called triple DES or DES EDE after the order of encryption / decryption. Note that of course the inner functions are performed first, i.e. the functions are executed from right to left.

In pseudo code the encryption function:

c1 = DES_encrypt(k1, m)
c2 = DES_decrypt(k2, c1)
c3 = DES_encrypt(k3, c2)
c = c3;

The keys are defined as separate keys, but most - if not all - libraries simply take the concatenation $k = k_1 \| k_2 \| k_3$ as key input.

So in your case your keys would be k1 = 0123456789ABCDEF, k2 = FEDCBA9876543210 and k3 = 89ABCDEF01234567 (which have the parity bits correctly set).

Most if not all libraries only accept the keys including parity bits. Most libraries do not check the validity of the parity bit, but there may be some that do. The bits commonly do need to be present though; a single DES key can usually not be represented by just 7 bytes.

Note that the least significant bit of a byte is the parity bit over that byte, which should be odd number of set (or indeed unset) bits in the byte.  So both 00 and 01 would be equivalent byte values within the key, with 01 having correct parity. This means that each triple DES key with correct parity has $2 ^ {192 / 8} - 1 = 2^{24} - 1 = 16,777,215$ fully equivalent keys.

Sometimes key generators do act on the effective key size excluding parity bits, so you'd have a function such as $k = \operatorname{Gen}(168)$ to create a triple DES key rather than $k = \operatorname{Gen}(192)$, even though the output is 192 bits / 24 bytes in size.

For 2-key triple DES keys you'd have $k_3 = k_1$, so the key would be $k = k_1 \| k_2$ to get:

$$\Enc'_{(k_1, k_2)} \equiv \Enc_{k_1}(\Dec_{k_2}(\Enc_{k_1}(m)))$$

and to simulate single DES where only triple DES is available:

$$\Enc'_{k} \equiv \Enc_{k}(\Dec_{k}(\Enc_{k}(m)))$$

I'll spare you the decryption functions and pseudo code.

Neither 2 key triple DES or single DES is considered secure anymore, while triple DES still offers some security.

Sometimes the keys are lettered instead of numbered, in that case $k_A = k_1$, $k_B = k_2$ and $k_C = k_3$. So the concatenation of three keys is sometimes also called an ABC key, and the concatenation of two keys an ABA key.

If you don't want to deal with all this "complexity" then use AES instead, which has much better properties and speed compared to triple DES. A fast stream cipher such as ChaCha20 could also be considered.


Will ANY prior knowledge assist in determining contents of a SHA1 hash? I am working on a project testing a hash that protects some data, and I've already eliminated hash length extension attacks as a possible point of compromise, and I'm trying to educate myself on all the variables.

Say I have some data that is hashed via SHA1 - will knowing parts of that hash (the end piece - basically a known value with an unknown prepended salt) help in breaking the hash/finding the salt at all, other than speeding up a brute force?

By knowing a portion of the hashed data, and the hashed output, would that help in finding the missing, unknown portion of the hashed data? Would it matter if this was hashed using a nonce, and you have multiple versions of the partial data and ending hash? (For example, two hundred hashes, all with the same salt, same known data, changing nonce)

From everything I've read, I BELIEVE the answer to all of the above is "No, it's of no help, you still need to spend years brute forcing it", correct? I just want to cover all my bases before I put faith, and my I'm-no-expert-why-are-you-asking-me seal of approval on/in a security setup I don't have direct control over (If it were up to me I'd HMAC it - but it's not - and I cannot).

It all depends on whether the rest of the input is guessable.

The best attack we know for finding the input to SHA1, given the output and partial knowledge about the input, is a brute-force attack:

For each candidate at the full input, try hashing that input with SHA1 and see if it matches the known output.

So, the running time of the attack will be proportional to the number of candidates we need to try.  If part of the input is known, the running time will depend on how easy it is to guess/predict the rest of the input.

For instance, if the unknown part of the input is a 4-digit PIN, and the rest of the input is all known, then the system is definitely vulnerable.  There are only $10^4 = 10000$ candidates for the full input, so you can try each one of them.  This won't take very long.

As another example, if the unknown part of the input is a 128-bit secret value, and you have no way of predicting that input, and all 128-bit values are equally likely, then the system is safe.  There are $2^{128}$ candidates for the input, and you can't try them all.  Also, they're all equally likely, so you can't even get a speed-up by trying the most likely candidates first -- all the candidates are equally likely.

In general, if the entropy of the secret part is at least 128 bits, you should be good.


Why Authenticated Encryption the same message again is not secure? It is the Exercise 9.14 (9.1) from the book A graduate course in applied cryptography by Boneh and Shoup.

Let $(E, D)$ be an AE-secure cipher.

a. $E_1(k,m):=(E(k,m), E(k,m));$
  $$D_1(k,(c_1,c_2)):= \begin{cases} D(k,c_1) & &
    \text{ if } D(k,c_1)=D(k,c_2),\\ \text{ reject } & & otherwise \end{cases}$$

b. $E_2(k,m):=\{c \leftarrow  E(k,m),\text{ output } (c,c) \};$
 $$ D_2(k,(c_1,c_2)):= \begin{cases} D(k,c_1) & &
 \text{if }  c_1=c_2,\\ \text{reject} & &otherwise \end{cases}$$

Show that part (b) is AE-secure, but part (a) is not.

--

I know that the different of (a) and (b) is that $E(k,m)$ use again will product different cipher.

I do the follow:

let the algo use XOR,

let R is the random of algo,

$c_1 = E(m)\oplus R_1; c_2 =  E(m)\oplus R_2$

$c_1 \oplus c_2 = R_1 \oplus R_2 = R_3$

let $B=u \oplus v$, where u is the origin header and v is my header.

$c_1 \oplus B \oplus R_3 = E(m) \oplus B \oplus R_2$

then the message is changed by me, so it is not an AE-secure.

But my teacher ask me don't assume the algo, and I don't know how can I do now.

I guess the HMAC use same key twice maybe is point, but I still don't know how can I do now.

Can somebody please help me?

Thanks!

Recall the definition: a cipher is AE-secure iff it is secure against chosen ciphertext attacks and has ciphertext ingegrity. Try going through the attack games with $(E_1,D_1)$ and $(E_2,D_2)$: if the adversary succeeds, can he succeed for $(E,D)$?

It's fairly easy to see that $(E_1,D_1)$ and $(E_2,D_2)$ are CPA-secure. If the adversary can distinguish between the encryption of two messages under either cipher, then he can play the CPA game against the original cipher, submit all the outputs of $E$ from the original game, and win the CPA game against the original cipher. This means that the CPA security of $(E_1,D_1)$ and $(E_2,D_2)$ reduces to that of $(E,D)$.

Let's look at the ciphertext integrity game for $(E_2,D_2)$. If the adversary can craft a valid ciphertext $(c,c)$, then $(c,c)$ is not any of the previously obtained ciphertexts by definition of the attack game, which means that the adversary has obtained a new ciphertext $c$ for the original cipher $(E,D)$. So the ciphertext integrity of $(E_2,D_2)$ reduces to that of $(E,D)$.

Now let's look at the ciphertext integrity game for $(E_1,D_1)$. Suppose the adversary has obtained a valid ciphertext $(c^1,c^2)$ by encrypting one message $m$. Recall that the objective of the adversary is to create a valid ciphertext that he hasn't seen before. Can he do that?

   Yes, easily: $(c^2,c^1)$ is a valid ciphertext, and with overwhelming probability $c^1 \ne c^2$ so this is a distinct ciphertext from the one the adversary has already seen.

Now suppose the adversary submits $m$ again, and obtains a second valid ciphertext $(c^3,c^4)$ for the same plaintext $m$. Can the adversary create a new valid ciphertext?

   Yes: mix and match. For example $(c^1,c^3)$ is another valid ciphertext which is distinct from the previous ones with overwhelming probability.

The first counterexample is easily fixable: you could modify $E_1$ into $E_3$ which

   sorts the two ciphertexts, and $D_1$ into $D_3$ which checks whether the ciphertexts are in the correct order. The cipher $(E_3,D_3)$ doesn't suffer from the first counterexample, but is still vulnerable to the second counterexample (either $(c^1,c^3)$ or $(c^3,c^1)$ is a new valid ciphertext).

The second counterexample is more interesting because it shows that both $(E_1,D_1)$ and $(E_3,D_3)$ are fundamentally broken. Their weakness is that they allow the adversary to test whether two ciphertexts are the encryption of the same plaintext. Suppose that the adversary wants to know what a certain message $m$ is for a given ciphertext $(c^1,c^2)$, and they manage to guess that the message is in a small set $\{m_1,\ldots,m_n\}$. He can submit each of the $m_i$'s for encryption, getting ciphertexts $\{(c_1^1,c_1^2), \ldots, (c_n^1,c_n^2)\}$. If he can then test which of the ciphertexts $\{(c_1^1,c^2), \ldots, (c_n^1,c^2)\}$ (or the appropriate swapping of each pair for $(E_3,D_3)$) is valid, for example by observing the result or the timing of an attempted decryption, that lets the adversary find out what the message was.


How is OID 2a 86 48 86 f7 0d parsed as 1.2.840.113549? I saw that an RSA key, created by OpenSSL, contains the following HEX string:

  2a 86 48 86 f7 0d 01 01 01

that HEX string gets interpreted as Object ID:

  1.2.840.113549.1.1.1

It is obvious 01 01 01 is 1.1.1, but how does 2a 86 48 86 f7 0d get interpreted (parsed) as 1.2.840.113549?

The question's bytestring 2a 86 48 86 f7 0d 01 01 01 is the Value field of an ASN.1 BER/DER TLV with type 6, which is the Object IDentifier for an RSA key (the Type and Length just before are coded as 06 09, and won't be further discussed).
In order to parse that Value bytestring, we first separate the bytes into blocks ending after each byte in which the high-order bit is clear (in other words: blocks end after a byte in range 00h to 7fh). Then we paste together the low-order 7 bits of the bytes (in big-endian/reading order); so that
_____2a|_____86_____48|_____86_____f7_____0d|_____01|_____01|_____01   becomes
0101010|00001101001000|000011011101110001101|0000001|0000001|0000001
We then interpret each block of bits as coding a non-negative integer in big-endian binary. The question's example now comes out as the six integers: 42 840 113549 1 1 1
There's a special case for the first integer: it was built as $z=40x+y$, with $x$ encoding the top-level authority that assigned $y$. Integer $x$ is always one of $0$ (for ccitt), $1$ (for iso) or $2$ (for joint-iso-ccitt), and if $x<2$ then $y<40$.
We thus replace the first integer $z$ by $x=\min(\lfloor z/40\rfloor,2)$ and $y=z-40x$.
Note: when $x=2$, $y$ can be arbitrarily large. Assigned $y$ include 40 (exercising the $\min$ rule), 48 (requiring coding $z$ over more than one byte), and 999 (with $y\ge2^8$), which might not be correctly handled by some existing software.
The question's example now comes out as the seven integers: 1 2 840 113549 1 1 1
One practice is to format these integers in decimal without a leading 0 digit (with the exception of the integer zero represented as 0), separated by dots, as in
1.2.840.113549.1.1.1
or sometimes enclosed in braces with separating spaces, as in
{1 2 840 113549 1 1 1}
or sometimes (as shown by the OID Repository)
{iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) rsaEncryption(1)}
or in OID-IRI notation
/ISO/Member-Body/840/113549/1/1/1
The careful reader will notice that per the above conventions, different bytestrings can decode to the same OID; however the rule in crypto (for OIDs at least) is to stick to the unique DER encoding, such that (in the bitstring with the Value field of an OID) a byte 80h can only follow a byte which high-order bit is set (otherwise the 80h would encode leading zeroes of an integer, and must be suppressed).

Daniel Marschall's Study about OID encoding and size limitations was most useful in making the above (hopefully) correct; it also confirmed my intuition that OID decoding practices are chaotic. Microsoft has an explanation on OID format, which I found initially useful even though it turns out to be dangerously lacking.
The normative references for OID encoding are somewhere in IUT-T X.680 through X.695 Information Technology - Abstract Syntax Notation One (ASN.1) & ASN.1 encoding rules. They are also in its free ancestors IUT-T X.209:1988 Specification of Basic Encoding Rules for Abstract Syntax Notation One (ASN.1) in section 22 Encoding of an object identifier value, with definitions in IUT-T X.208:1988 Specification of Abstract Syntax Notation One (ASN.1) in section 28 Notation for the object identifier type and annexes B, C and D.


Is this ECC encryption key sharing method okay? Is this encryption key sharing okay to use?  Or is much better to use ECIES?

$G$ = base point
$a$ = Alice’s private key
$b$ = Bob’s private key
$A = aG$ = Alice’s public key
$B = bG$ = Bob’s public key
$C_x$ = x coordinate of $C$

Alice and Bob share an AES key:

Alice makes $C = aB$
Bob makes $C = bA$
The common encryption key is $C_x$

I can follow and have implemented ECIES.  But in the above method the common key can be computed locally leading to shorter message transmissions.  This could be a significant savings if most messages are short.  (I would use counter mode with the IV sent along with the ciphertext.)

But is there a problem using the above method?

To start things: Don't roll your own crypto.

What you're proposing is using standard static Diffie-Hellman for key-exchange, which by itself is a bad idea, as it will always result in the same key for each communcication between Alice and Bob. The key by itself should be safe, but as soon as it's broken all messages are as well. So if either the sender's public key is broken or the derived DH key is learned all communications are broken, whereas ECIES will still be safe (if the DH secret is learned one message is broken, if the public key is broken all messages to that person are broken and not all messages).

Next, ECIES provides authenticity and secrecy, meaning that if the message is altered in transit ECIES will output an error on decryption, using plain CTR + random IV doesn't provide this property.

So it's for these reasons (don't roll your own crypto, avoid static keys, think of authentication) that ECIES is the better choice.


In interactive proofs, do we assume that the prover can always solve the problem? I'm having a difficult time understanding a concept from interactive proofs:

A trivial interactive proof for the graph isomorphism problem is having the prover just send a permutation that shows an isomorphism between $G_1$ and $G_2$, and have the verifier check it.

But what happens when $G_1$ and $G_2$ aren't isomorphic? If the prover really does know a solution to the problem, he'll just say that they aren't and we'll move on. But what if he always says that they aren't isomorphic? We have no way of knowing whether they really aren't, or whether the prover is lying, right?

So the prover might just always answer "not isomorphic" for any problem given to him, and we'll have no way of knowing whether he's correct or not.

So when we discuss interactive proofs (and Zero-Knowledge Proofs especially) do we always assume that the prover is capable of solving the problem?

Thanks

No, but if the problem isn't known to be in promiseMA then

we do "assume that the prover can always solve the problem".

https://cstheory.stackexchange.com/questions/696/mip-with-efficient-provers

Graph isomorphism is trivially in NP, so for graph isomorphism, we just

"assume that the prover" has an isomorphism between the graphs.

Graph non-isomorphism is not even known to be in MA, so for graph non-isomorphism,

we do "assume that the prover can always solve the problem".


Why are elliptic curves better than cyclic groups? The set of points of an elliptic curve over a finite field is isomorphic to the direct product of two cyclic groups (i.e. $E(F_{p^n}) \cong Z_{s} \times Z_{t})$.
What is the advantage of representing or conceiving the group as an Elliptic Curve instead of as a product of cyclic groups?

The first assumption: $E(F_q) \simeq Z_s \times Z_t$ is always true!! (see Handbook of Elliptic and HyperElliptic Curve Cryptography)
It is never said that coordinates of points lie on $Z_s \times Z_t$ which has no sense except if $s=t$.

But the isomorphism is not trivial to compute (it is in fact hard to compute, since it is related to the discrete logarithm for the left-to-right part).

And working only with the representation $Z_s \times Z_t$ will weaken the discrete logarithm so useful for cryptographic purposes.

In brief, if you can exhibit a curve (or demonstrate that there is a NIST curve) for which the computation of the left-to-right part of the isomorphism is easy, then this curve MUST be considered as weak and must never be used for any cryptographic purpose.

Concerning quantum computers, EC-DLOG will be solved as easily as for any cyclic group, since the Shor algorithm can be adapted to solve it, but don't ask me about details, I don't understand them...


ECDSA key recovery - floating point values I'm currently attempting to recover an ECDSA key.

I have $m$, $m'$ and signatures $(r, s)$, $(r', s')$, and  I know that $k$ is constant, the curve is NIST P-192 and the hash function of the. As such, I'm attempting to compute $d_A$ as shown on the wikipedia page for ECDSA.

However, after recovering $k$ (on the stage where I am computing $d_A$), I get a floating point result for $d_A$. Is this to be expected? If not, what would be the correct way of handling it?

My code, if it helps:

#!/usr/bin/python
import hashlib
import ecdsa.util
import ecdsa
import sys
import base64

n = 6277101735386680763835789423176059013767194773182842284081
r1, s1 = ecdsa.util.sigdecode_string(open("sig1.bin", "rb").read(), n)
r2, s2 = ecdsa.util.sigdecode_string(open("sig2.bin", "rb").read(), n)
hash1 = hashlib.sha1('iSsuZJOq1FNKMuK4wm88UEkr21wgsypW'.encode('utf-8')).digest()
hash1 = ecdsa.util.string_to_number(hash1)
hash2 = hashlib.sha1('x3wqOnaetBPO66TrBaMyr3NQIDbhvK0w'.encode('utf-8')).digest()
hash2 = ecdsa.util.string_to_number(hash2)
print(r1 == r2)
#Much modulo N. Such wow.
#This totally didn't bite me in the ass for quite a while or anything <.<
top = (hash1 - hash2) % n
bottom = (s1 - s2) % n
print((top / bottom) % n)
k = int((top / bottom) % n)
print("Common constant k=0x%x" % k)
secret = (s1 * k) % n
secret = (top - hash1) % n
secret = (top / r1) % n
print(secret)

And the output:

True
6.337358414243492
Common constant k=0x6
50.34135291546233

This is not correct, the private key $d_A$ must always be an integer. Your mistake is that you are doing modular division e.g. $\frac{a}{b} \text{ mod } n$ incorrectly. You cannot simply divide the integers and then reduce by the modulus. The correct way to do this is to compute the modular inverse of $b$ i.e. $b^{-1} \text{ mod } n$ and then compute $a*b^{-1} \text{ mod } n$.


Simple explanation of sliding-window and wNAF methods of elliptic curve point multiplication I'm trying to understand the implementation of elliptic curve point multiplication.  I can easily understand the naive double-and-add algorithm, but I'm struggling to find a good explanation / example of the window method, or indeed of the wNAF method.
The canonical reference seems to be this Wikipedia page, in which is outlined all the various algorithms on a high level.
Does anyone know of any accessible explanations / examples of either the window method / wNAF method for point multiplication?  Alternatively, can anyone easily explain how these algorithms work?

To give you an example of how I'm confused by the Wikipedia article, the windowed method is listed as:
Q ← 0
  for i from m to 0 do
      Q ← point_double_repeat(Q, w)
      if di > 0 then
          Q ← point_add(Q, diP) # using pre-computed value of diP
  return Q

But it references the "point_double_repeat(Q, w)". method call.  But what is this method? What does this actually do?
With regards to the "w-ary non-adjacent form (wNAF) method", the algorithm seems simple to follow, but it's hard to be confident that I understand it properly without a simple example.
I understand that this is probably quite rudimentary to many people on this forum, but I would nonetheless greatly appreciate any help.

Update 10 Aug:
Reading Sam's answer below makes sense, and I was able to implement the wNAF method, but I'm still having trouble understanding how to implement the window method.
This is how I've tried to understand it:
Lets start with an example of a normal double-and-add for the scalar 2329.
2329 in binary is 100100011001, so going from right to left:
1   0   0   1   0   0   0   1   1   0   0   1
DBL DBL DBL DBL DBL DBL DBL DBL DBL DBL DBL START
ADD         ADD             ADD ADD         ADD
2048        256             16  8           1

As you can see there are 12 doubles and five additions.  Now I'm going to try to convert this to a window method so that there are less additions. Lets use a window size of 4:
1   0   0   1       0   0   0   1       1   0   0   1
DBL DBL DBL DBL     DBL DBL DBL DBL     DBL DBL DBL START
2048   +    256                 16      8     +     1
---------------     ---------------     ---------------
      2304       +        16         +        9

This means only three additions, a reduction of 40%, excellent.
Now for the algorithm itself, as per the description in Wikipedia:

One selects a window size $w$ and computes all $2^w$ values of $dP$ for $d = 0,1,2,...2^w - 1$. The algorithm now uses the representation $d = d_0 + 2^wd_1 + 2^{2w}d_2 + ... + 2^{mw}d_m$

In the example of using the scalar 2329 with a window size of 4, this means pre-computing a collection of 16 points, ($0 ... 2^4 - 1$ or $0 ... 15$).
For the scalar value, the algorithm then uses the representation $(9 \cdot 2^0) + (1 \cdot 2^4) + (9 \cdot 2^8)$. Simplifying: $(9 + 16 + 2304)$.  So in the algorithm below, this means that $d1 = 9, d2 = 16, d3 = 2304$, and "m" is 3.
This is the window method of the algorithm as per Wikipedia:
Q ← 0
  for i from m to 0 do
      Q ← point_double_repeat(Q, w)
      if di > 0 then
          Q ← point_add(Q, diP) # using pre-computed value of diP
  return Q

In this case, when it comes to adding the pre-computed point $d_iP$ There are three iterations, in which $d_i$ is either $9P, 16P, or 2304P$.  But our pre-computes are $0,1,2,...2^w-1$.  In order words, there is no "$9P$" in our pre-computes.  There is only $P,2P,4P,8P,16P,32P,64P....$
Obviously I have misunderstood either the algorithm itself or how I am supposed to compute the pre-computes that algorithm uses, either way I'm at a bit of a loss.

Suppose for simplicity we have an 4-bit key $k= (k_0,k_1,k_2,k_3)$, where each $k_i$ is a bit. To compute $kP$, we find
$$k_0P + k_1(2P)+k_2(4P)+k_3(8P)$$
But we could instead write $k=(k_{01},k_{23})$, where we separate it into 2-bit windows. Then we can write
$$ kP = (k_0+2k_1)P + (k_2+2k_3)(4P) = k_{01}P + k_{23}(4P)$$
Then one way to actually compute this is to compute $k_{23}P$, then double it twice to get $4(k_{23}P)=k_{23}(4P)$. Then we add $k_{01}P$ to this.
Extending the pattern, this is the same as double-and-add, except (1) we're doubling multiple times between each add; (2) in the add step, we don't just add $P$ or $0$, but a value in $\{0,P,2P,3P\}$.
For a window size of $w$, we split the key into $(k_0,\dots, k_{n/w})$, where each $k_i$ has $w$ bits. We start with $Q=0$, then repeat for $i=0$ to $i=n/w$:

$Q \leftarrow 2^w Q$
$Q\leftarrow Q + 2^{k_i}P$

In regular double-and-add for an $n$-bit key, we need $n$ doublings and $n$ additions. With this windowed method, we still need $n$ doublings, but only $n/w$ additions, plus whatever it costs to compute each value of $2^{k_i}P$.
If you just compute $2^{k_i}P$ with regular double-and-add, then there is no point to this windowed method -- it will cost more! But if you pre-compute a table of all the values of $\{0,P,\dots, (2^w - 1)P\}$, then you can look up the value in the table, which (depending on your cost model) is probably much cheaper. But the size of this table is exponential in $w$, so you save a factor of $w$ additions at the expense of an exponential amount of precomputation.
I haven't heard of the sliding window before, but it looks like it's exactly the same except you start your pre-computed table at $2^{w-1}P$, and then you don't bother adding a multiple of $P$ if the leading bit $k_i$ is 0 -- you just double $Q$ until the leading bit is 1, which shifts all the windows by the number of doublings.
Wikipedia says "In effect, there is little reason to use the windowed method over this approach, except that the former can be implemented in constant time" which to me seems like saying "there is little reason to use an elevator to get to the bottom floor of a building, instead of jumping out of the window, except that the former can be done without breaking your legs".
Edit: For wNAF, the main idea is that if you precompute $\{0,P,\dots, (2^w-1)P\}$, then you have $\{-(2^w-1)P,\dots,-P,0,P,\dots,(2^w-1)P\}$ almost for free, because you can just flip the sign of the $y$-coordinate (in Weierstrass form at least).
If you're careful about how you represent a number, then you should be able  to do something almost identical to windowed multiplication, except you use these negative multiples of $P$ and thus use fewer additions with the same amount of precomputation.
I am fairly sure (but not certain!) that you can represent a number $k$ by $(k_0,0,k_1,0,\dots, 0, k_{n/w})$, where each $k_i$ is in $\{-2^{w-1},\dots,2^{w-1} -1 \}$. That is, by using negative values, you can fit a 0 between each word (hence "non-adjacent form").
What the wNAF algorithm on Wikipedia is doing is similar to the sliding window: Rather than double exactly $w$ times between each addition, it checks whether the remaining value is even, and if it does, it does another doubling before the addition. This ensures it only ever adds odd multiples of $P$, which saves half the precomputation cost.
An important paragraph is:

One property of the NAF is that we are guaranteed that every non-zero element ${\displaystyle \scriptstyle d_{i}}$ is followed by at least ${\displaystyle \scriptstyle w\,-\,1}$ additional zeroes. This is because the algorithm clears out the lower $\scriptstyle w$ bits of $\scriptstyle d $ with every subtraction of the output of the mods function.

EDIT: It looks like the issue is that $0,1,2,\dots, 2^w-1$ is ambiguous notation. The pre-computed values are actually $0,1,2,3,4,\dots, 2^w-1$. That is, they are just incremented by 1 instead of doubling each time.
In your example, this means the precomputed values are $\{P,2P,3P,4P,5P,6P,7P,8P,9P,10P,11P,12P,13P,14P,15P\}$ (since $w=4$). Then the $d_i$ would actually be $d_1=9$, $d2=1$, and $d_3=9$ (that is, exclude the powers of 2), and so $d_iP$ is in the table for all $i$.
When you start the algorithm, $m=3$ and $Q=0$, and you add $d_3P=9P$ to $Q$ to get $Q=9P$. $9P$ should be in your table. Then you move to the next iteration of the loop, and double $Q$ for $w$ iterations. Since $w=4$, this means we get
$$(2^4)Q = (9\cdot 2^4)P$$
Then $m=2$, and you add $d_2P = 1P$, to get $Q=(9\cdot 2^4 + 1)P$. Then in the next iteration of the loop, double $Q$ another four times to get:
$$(2^4)Q = (2^4)(9\cdot 2^4 + 1)P=(9\cdot 2^8 + 1\cdot 2^4)P$$
Finally, $m=1$, and and so we add $d_1P=9P$ to $Q$ to get $(9\cdot 2^8 + 1\cdot 2^4 + 9)P = 2329P$.


RSA: select $e$ given $n$ and $\varphi(n)$ I have a question for a course I am doing. In an RSA question, it asks "Is it possible to select $e$ in such a way that it coincides with the corresponding private key $d$? If it is possible, provide a value for such an $e$.

So, this is only part of the question (last part really).

$$n = 22499$$
$$\varphi(n) = 22200$$

How would I go about this? I am completley lost. I have, by luck come across an answer of $149$. $149^2 = 1 \pmod{22200}$. This is because $ed = 1 \pmod{\varphi(n)}$. Is there a method to calculate such a number? [$a^x = 1 \pmod{\varphi(n)}$]

There are four different solutions, of which three have been identified as the "trivial solutions" in the comments to this question.

$e=d=1$ which is obviously fullfilling the condition that $1\cdot 1\equiv 1 \pmod{\varphi(n)}$ should hold.
$e=d=\varphi(n)-1$ which is fullfilling the condition that $(\varphi(n)-1)^2\equiv 1 \pmod{\varphi(n)}$ as $(\varphi(n)-1)^2=((\varphi(n))^2-2\varphi(n)+1) \bmod{\varphi(n)}=1$
$e=d=\sqrt{\varphi(n)+1}$ (if integer) which is also obviosuly true as $\sqrt{\varphi(n)+1}^2=(\varphi(n)+1)\bmod{\varphi(n)}=1$, this is the solution you stumbled across.
Use a full modular square root finding algorithm as documented as algorithm 3.44 in the Handbook of Applied Cryptography on page 102. (PDF version) However this requires you to know the prime factorization of $\varphi(n)$ which may be infeasible to obtain for sufficiently large $n$.


Statistical properties of hash functions when calculating modulo When using SHA-1 to hash an input, the result is a pseudo-random number in the numeric ID space $\{0\dots2^{160}-1\}$. Do I loose any statistical property in the result if I use modulo to restrict the key space? Obviously, the probability of collisions increases but is the randomness affected?

As an example, if I hash a string 'something', the result is pseudo-random:
$\operatorname{SHA-1}(\mathtt{"something"}) = \operatorname{pseudoRandom}$

So what happens when calculating modulo? Do the statistical properties still hold?
$\operatorname{SHA-1}(\mathtt{"something"})\bmod 2^{80} = \operatorname{pseudoRandom}$

Edit: What I actually want to achieve is a uniform distribution of the resulting, restricted ID space when feeding the $\operatorname{SHA-1}$ function with pseudo-random strings.

The question asks if $\operatorname{SHA-1}(M)\bmod n$ is random, giving the example of $n=2^{80}$.

I'll consider arbitrary $M$ (that is, determined without knowledge of SHA-1, or just of SHA-1's 160-bit initialization constant), and that it makes $\operatorname{SHA-1}(M)$ indistinguishable from $160$ random bits (which is true from a computational perspective, baring any huge theoretical progress).

When $n=2^k$ for $0\le k\le160$ (including $n=2^{80}$ in the question), $\operatorname{SHA-1}(M)\bmod n$ is simply the integer with binary representation the $k$ low-order bits of $\operatorname{SHA-1}(M)$, thus is indistinguishable from $k$ random bits (proof sketch: an hypothetical efficient distinguisher for $\operatorname{SHA-1}(M)\bmod n$ can be turned into an efficient distinguisher for $\operatorname{SHA-1}(M)$).

For other $n$ of interest, that is $n=s\cdot2^k$ with odd $s>1$ and $\log_2(s)+k<160$, the low-order $k$ bits of $\operatorname{SHA-1}(M)\bmod n$ are the low-order $k$ bits of $\operatorname{SHA-1}(M)$, and similarly indistinguishable from $k$ random bits. However $\operatorname{SHA-1}(M)\bmod n$ is not uniformly random over the set $\{0\dots(n-1)\}$: low values are more likely than high values. When $n=3\cdot2^{158}$, odds that $\big(\operatorname{SHA-1}(M)\bmod n\big)<{n\over3}$ are $1\over2$, rather than $1\over3$ for a uniform distribution. For example, the generator specified by FIPS 186-1 Appendix 3.1 has such bias (but it does not matter much in the application).

Update: a comment asks a simple algorithm based on SHA-1 that, given an arbitrary input $M$, outputs an integer uniformly random on the set $\{0\dots(n-1)\}$ for some parameter $n$ with $0<n\le2^{160}$.

As previously stated, when $n$ is a power of two, we can use $\operatorname{SHA-1}(M)\bmod n$. This is also the case when $n<2^{90}$ or so, because the adversary gets a negligible advantage for computationally reasonable effort.

Whatever $n$, we can use the following:

$r\gets 0$ ($r$ is expressed as a 16-byte string)
repeat $h\gets\operatorname{SHA-1}(r\|M)$ and $r\gets r+1$ until $h\ge(2^{160}\bmod n)$
output $h\bmod n$.

The output is uniformly random based on the fact that in the final step, $h$ is uniformly random on the set $\{(2^{160}\bmod n)\dots(2^{160}-1)\}$, which contains a number of elements multiple of $n$.


Perform calculation on encrypted numbers What i am trying to achieve ?

I am developing a carpooling solution powered by Blockchain and IOT. This one is supposed to be technically convenient and without compromising on the privacy part. Driver should be able to share his location on runtime. In order to remove the privacy issue i was wondering if this is possible :-

Driver has his private key on device and shares the location in encrypted format
Passenger requests for ride and queries server with its own encrypted location
Now we have list of active rides encrypted locations and one passenger encrypted location
Server performs haversine geolocation calculation over list of available active rides and figures out the best possible match along with the distance

I want to know if this is possible and if there is any efficient library available
Any other options to achieve the desired results are also welcome

Thanks in advance

No, that can't be done. There is no way that "Server performs haversine geolocation calculation over list of available active rides and figures out the best possible match along with the distance" but can't find driver's locations.

Worse, even if the server is trusted to internally know the location data, if it puts no limit to creating fake users and telling them what's the closest user, that allows to extract the location of any real user with arbitrary precision, by dichotomic search. That argument can be used to derive a rigorous proof of the above impossibility (sketch: there's nothing to stop a rogue server to use whatever computation it can make without implementing the necessary limitations).

Additionally, there is a possible inconsistency in "Driver has his private key on device and shares the location in encrypted format": the two things have no clear relationship. Fact is, it is never useful to encrypt with one's own asymmetric key, for only self could decipher. Remotely similar possibilities making sense include

Driver signs his/her location using his/her private key; that does not make the location confidential.
Driver encrypts his/her location with the server's public key.
Driver encrypts his/her location with public keys of some other users.

Note: variants of the last two involve establishing a symmetric key using the driver's asymmetric key, and using the symmetric key for encryption (perhaps authenticated), but that makes no functional change.

In the trusted server scenario, it is possible that users sign their location data with their private key and encrypt it with the server's public key; that keeps the location data from directly leaking to other users, and makes it necessary to use complicity of registered users to find a user's location. Further, the ability of a registered user to submit wildly different locations in a short period of time can be limited by the server. That's clearly feasible, including replacing the server by some secure "black box"; an HSM could do that.

Using Fully Homomorphic Encryption, it is theoretically possible that a non-trusted entity performs the distance calculation (including haversine), and I'm ready to admit it is possible to find the identity of the closest neighbor in encrypted form. But I see little point in that, for in the end deciphering distance and identity requires a trusted party / private key. Also, I'm afraid that, if security is required, the best FHE has to offer now would make computations slow (unbearably so for the encrypted identity).


In case M is small is it possible to recover the message In the plain RSA encryption, suppose $N$ is 1024 bits and the public key $e = 17$. Is it secure to use this setting to encrypt very small message, say $3 \leq m \leq 9$? In other words, is it possible for the attacker to recover the message $m$ given the public key and the ciphertext $c = m^e \mod N$.

No its not secure. As this is homework my hint is: Textbook (plain) RSA encryption is deterministic, and so encrypting the same message always gives the same...


What is the point of differential cryptanalysis when the amount of necessary plaintext is unrealistic? As someone with a non-crypto background, I learned that differential cryptanalysis is mostly weak against ciphers like DES because, being a chosen plaintext attack, for a state of art complexity of $2^{47}$ there is a need for $2^{47}$ plaintext bits to conduct this attack which is realistically infeasible.
So what's the point of this attack vector at all? If it has always been known that you need a huge amount of plaintext for these to work, why did people bother?

Differential cryptanalysis is a very powerful technique that permitted highly practical attacks on many ciphers that were not designed to resist it (e.g. FEAL-4).  DES, as it turns out, was designed to be pretty resistant to it, which is why it requires an essentially impractical amount of chosen plaintexts to implement a differential attack on DES.

However, I would note that $2^{47}$ is still significantly less plaintext than a generic codebook attack requires, and moreover the attack has a time complexity of only about $2^{37}$ DES calls (which is significantly better than the generic key-guessing attack).  As such, differential cryptanalysis counts as a 'break' of the cipher (anything that is better than generic attacks is a 'break').  It is only an 'academic' break, given the impracticality of so much chosen plaintext (which is why DES wasn't immediately deprecated once Biham and Shamir published their paper).  But it is a break nonetheless.

In general, people 'bother' with cryptanalysis because they want to evaluate the ciphers they use to protect lives and billions of dollars against all known attacks in order to understand how secure they are.  If you can show (for a cipher with sufficiently large parameters like key-size and block-size) that nothing beats generic attacks (i.e. that there are no 'breaks') then that gives people confidence in the security of the cipher.


How to make my hash more robust to the brute force? I'm using PBKDF2 SHA 256 with 100 000 iterations to generate a secret.

I want to increase the cost of brute forcing the passphrase I use to generate the secret.

I'm thinking of using scrypt after the pbkdf2 computation.

scrypt(pbkdf2(passphrase, salt))

Is there a better way?

I would recommend you use Argon2, which is both a slow KDF like PBKDF2, as well as a memory-hard function designed to improve resistance to GPUs and FPGAs like scrypt. You can select both the number of iterations and amount of memory used in Argon2, and they can be changed independently (unlike scrypt, where the memory and time difficulties cannot be modified separately, and high time implies high memory-usage). This can be done on existing password hashes to maintain backward compatibility, but I would suggest you convert the old scheme (PBKDF2 with scrypt) into one using just Argon2 as soon as a user next logs in and supplies their password.


How to securely use Elgamal encryption in libgcrypt? How secure is libgcrypt's Elgamal implementation of encryption (how different it is from textbook Elgamal), and how can I tweak padding and other preprocessing actions?

For example, I know that usign RSA I can use this S-expression to the function gcry_pk_encrypt:

(data
  (flags pkcs1)
  (value BLOCK))

And I can use oaep or pss instead of "pkcs1". But what do I use with Elgamal? I can encrypt and decrypt using Elgamal, using

(data
  (value BLOCK))

but then I have no idea if raw Elgamal was used or if it's actually DHAES or some padded-Elgamal variant.

What is the proper way to use Elgamal in libgcrypt, and what options can I pass? Or would it be better to switch to RSA?

edit: I think that what I wanted to ask is "what is the intended use of Elgamal as implemented in libgcrypt?"

I took the world's shortest look at the code, so please don't hold me to any of this. But it seems that the implementation is textbook. You provide a block of data, it gets encoded to an integer in the range 1,...,p-1 and then encrypted using standard Elgamal without padding.

There's does not seem** to be an encoding to the subgroup of quadratic residues, and this implementation is /not/ CCA secure. These probably aren't going to kill you if you're encrypting a large random key, but they're definitely not the right way to encrypt.

Rather than hacking Elgamal, I'd say you're better off encrypting with RSA-OAEP.

In the long term, libgcrypt should implement a secure KEM/DEM for Elgamal encryption. DHAES would be a great example. Alternatively the authors should give a proper (non-textbook) Elgamal implementation with a group encoding and protections against adaptive-chosen ciphertext attacks.

(Elgamal seems to be the forgotten primitive. pycrypto has the exact same problems. Nobody loves Elgamal, which is too bad because it's a great encryption scheme.)

** A footnote: I didn't look deeply into the encoding function (below), so I admit I could be wrong about this point. But I don't see anything obvious. Here's the code:

init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT, gcry_pk_get_nbits (s_pkey));
  rc = sexp_data_to_mpi (s_data, &data, &ctx);


Homomorphic decryption circuit in integer-based scheme I'm reading this excellent paper by Gentry as a smooth introduction to Fully Homomorphic Encryption. Most things are clear to me except from the way the homomorphic evaluation of the decryption circuit is described (which is after all the whole point).

If I understand correctly, we assume (for simplicity) 1 message $m$ encrypted as a ciphertext $c_1$ under the first public key $pk_1$ via $c_1=ENC(pk_1,m)$. Let's say this is a big $Q$-bit number.

Then Gentry suggests, that we double-encrypt this ciphertext, by encrypting each one of the $Q$-bits with a new public key $pk_2$, to obtain obviously a vector of $Q$ new ciphertexts, each one being $Q$-bits. Let's call this new ciphertext $\bar{c}$.

We also need an encryption of the $P$-bit secret key $sk_1$ in a similar fashion (i.e. encrypting each bit of it with $pk_2$ to generate $P$ vectors of $Q$-bit ciphertexts. Let's call this encrypted secret key $\bar{sk_1}$).

He now suggests, that we use the values $\bar{c},\bar{sk_1}$ (remember vectors of ciphertexts) as inputs to an evaluation circuit for the homomorphic evaluation of the decryption (this cleverly removes the inner encryption with $pk_1$ but still keeps the message wrapped under encryption with $pk_2$).

The scheme originally performs encryption of the form $c=pq+m$, where $m$ encodes 1-bit of the initial message as its least significant bit, so decryption is $(c \bmod p) \bmod 2$ ($\bmod 2$ obviously to retrieve the last bit). As such, the "default decryption" circuit accepts a $Q$-bit ciphertext and a $P$-bit secret key $p$ and outputs just one bit as the $\bmod 2$ operation dictates.

However, in the homomorphic case, the inputs are actually vectors and the output should be a fresh $Q$-bit ciphertext, that will be doubly-encrypted with a new key and so on. How then does this circuit look like? If it handles the vectors $\bar{c},\bar{sk}$ as huge integers it would still output 1 bit via the final $\bmod 2$ operation but this is not consistent with the concept of double encryptions.

Any idea?

The circuit looks like any homomorphic version of a usual circuit: you replace the inputs by the corresponding ciphertexts and the operations by the corresponding homomorphic operations.

That means that,

The decryption circuit has as input a ciphertext $c$, which is a vector of $Q$ bits, and the secret key $sk$, a vector of $P$ bits; and it performs a $\mod 2$ operation at the end.
But the homomorphic decryption circuit, let's call $HDec$, has as input a vector of $Q$ ciphertexts ($\bar{c}$) representing the encryption of each bit of $c$ and a vector of $P$ ciphertexts ($\bar{sk}$) (representing the encryption of each bit of $sk$. And $HDec$ does not perform the $\mod 2$ operation, but a homomorphic operation equivalent to the $\mod 2$. Since it is a homomorphic operation, it returns a ciphertext (so, a $Q$-bit value, as expected).

Thus, $Dec$ takes vectors $(c_1, c_1, ..., c_Q)$ and $(sk_1, sk_2, ..., sk_P)$ and returns one bit $b$, while $HDec$ takes vectors $(Enc(c_1),..., Enc(c_Q))$ and $(Enc(sk_1), ..., Enc(sk_P))$ and returns a $Q$-bit value $Enc(b)$.


If I have the unencrypted text and the encrypted text, can I calculate the key? If I have the unencrypted text and the encrypted text, can I calculate the key?  It seems logical based on my limited knowledge of encryption that I should be able to... but it also seems like too obvious of a vulnerability for it to be possible.

Could someone explain how encryption schemes prevent against this type of vulnerability?

It depends completely on the encryption algorithm in use - for some little examples have a look below the horizontal rule.

In general, this is called a Known Plaintext Attack. The attacker has access to a message $m$ and its encryption $c=E_k(m)^{[1]}$.
The stronger form of this attack is a Chosen Plaintext Attack (CPA), where the attacker gets to choose $m$ and have it encrypted for him.

Assuming you've observed at least one character, if the encryption is a caeser Cipher then yes: it would be sufficient to recover the key. This is because you can take the difference between the first character of the plaintext and ciphertext to find the key.

However, even with the Vigenère Cipher, which is a slight 'improvement' on the Caeser Cipher, this might not be sufficient. If the key is longer than the plaintext/ciphertext pair you have observed, then you will not learn anything about the latter part of the key.
Similar examples come from thinking simply in terms of information: if you only witness $b$ bits of output, no matter how useful they are you can only learn at most $b$ bits of the key$^{[2]}$. Thus if the key $k>b$ bits long, there is no way $b$ bits of output can be sufficient to discern it.

Notes:

Where $E_k(m)$ is the encryption of $m$ under key $k$.
I assume here that the key is in some sense minimal. That is, the bits of the key are randomly set, and we have no information about the form the key takes. For example, if we know the key is either $0000$ or $1111$, then even though the key is $4$ bits long, it is determinable from $1$ bit.


Why is this authentication protocol with a nonce and tree parties not secure? Why is the following authentication service not secure?

C⟶S: $I_C$

S⟶C: $N$

C⟶S: $E(K_{C,A}, N)$

S⟶A: $E(K_{S,A}, \{I_C, E(K_{C,A}, N)\})$

A⟶S: $E(K_{S,A}, N)$

where:

C = client
S = server
A = authentication service
$I_X$ = identification string of entity X
$N$ is nonce
$E(K, M)$ is the encryption operation using key $K$ and message $M$
$K_{X,Y}$ = symmetric key shared by X and Y

Suppose that the client and server were once connected by random number $N$, and adversary is eavesdropped these messages. So he has $I_C$, $N$, $E(K_{C,A}, N)$, $E(K_{S,A}, \{I_C, E(K_{C,A}, N)\})$ and $E(K_{S,A}, N)$. Now in the new session, the adversary can easily impersonate the identity of the server. To do so, just follow the steps below:

C⟶Adversary: $I_C$

Adversary⟶C: $N$

C⟶Adversary: $E(K_{C,A}, N)$

Adversary⟶A: $E(K_{S,A}, \{I_C, E(K_{C,A}, N)\})$

A⟶Adversary: $E(K_{S,A}, N)$

Note that in this protocol, the server can use $E(K_{S,A}, N)$ to verify client identity, but the client does not have any information about the identity of the server.

Edit: Also, an adversary cannot impersonate the client using $E(K_{C,A},N)$ because $N$ is generated by a valid server and will change in each session. Therefore, an adversary cannot find the valid $E(K_{C,A},N)$ using previous eavesdropped messages. To prevent this attack, you can modify the protocol as follows:

C⟶S: $I_C$

S⟶C: $N$

C⟶S: $E(K_{C,A}, N, M)$

S⟶A: $E(K_{S,A}, \{I_C, E(K_{C,A}, N, M)\})$

A⟶S: $E(K_{S,A}, N, E(K_{C,A}, M))$

S⟶C: $E(K_{C,A}, M)$

However, this is just a change, and the resistance of this protocol to other attacks should be investigated. "Cryptographic Protocol: Security Analysis Based on Trusted Freshness" By Ling Dong and Kefei Chen, is a valuable book on protocols that you can refer to for more information.


Can two different pairs of RSA key have the same modulus? Can $n=pq$ be part of two different pairs of RSA keys?

If such keys exist, say $(e_1,n)$ and $(e_2,n)$, how are they related?
What will be the security concerns for the two users?

The users will be able to read each other's messages (even though they can have different private keys, say $d_1$ and $d_2$). This is because knowledge of $d_i$ is sufficient to factor $N$, thus allowing that party to compute the other party's private key. This was detailed by Boneh in his analysis of RSA attacks.


Are the MD5 constants an S-Box? I noticed that several hash algorithms, in this case MD5, defines some constants.

MD5 defines 64 constant values (the shift count per round) which also gets expand (via sine) to a summand for a specific round. It is like a lookup table.

But I cannot see anything (no documentation, no implementation,...) that calls this table an substitution box (S-Box). But I saw some implementations that use a variable called "S" for this table. A hint?

So my question is: Is it valid to call this table an S-Box? Or is it only common to call this kind of table an S-Box when it's used into a real encryption/decryption?

Is it valid to call this table an S-Box?

Not really; at least, not with the meaning we usually give to "S-box".

The "S" in "S-box" stands for Substitution; we take the data, and replace it with a value from the S-box (using the data as an index into the S-box).  The classical (if not the original) example is the S-boxes within AES; at certain points within the cipher, we take each 8 bit value $V$ from the block, and replace it with $SBox[V]$.

We don't do anything like that in MD5; instead, the "S" constants stand for "Shift".  They don't replace anything; instead, they modify how much shifting (rotating in more common parlance) we do per round.


Why is OTP not vulnerable to brute-force attacks? I saw this question on the book Understanding Cryptography.

  At first glance it seems as though an exhaustive key search is possible against an OTP system. Given is a short message, let’s say 5 ASCII characters represented by 40 bit, which was encrypted using a 40-bit OTP. Explain exactly why an exhaustive key search will not succeed even though sufficient computational resources are available.

It puzzles me because I think that as far as I know that the key has only $40$ bits, I could try all the possible $2^{40}$ keys and XOR them with the ciphertext to recover the message... Is there something that I am missing? How can it not work if we are assuming the attacker has computational power to do the exhaustive search?

Brute force on OTP will give you all sorts of messages which are meaningful and not meaningful.

For example, you have a 4-character encrypted text: weaw. Now brute-forcing will give you all sorts of meaningful and not meaningful messages like:

erwe
hell
road
....

Now, which one was the real message? That would be difficult, rather impossible to guess.


Key exchange if forward secrecy is not an issue Let's say that we have a cryptosystem where Forward Secrecy and Man-In-The-Middle attacks are not an issue, purely hypothetically.

Would it be correct for a key exchange with any given public-key algorithm to simply work as follows?

Alice calculates public & private key
Alice sends the public key to Bob (and Eve intercepts it)
Bob encrypts a random session key with the public key
Bob sends the encrypted session key back to Alice (and Eve intercepts it)
Alice decrypts the session key using the private key, Eve cannot decrypt in any reasonable amount of time

And all future communications would be encrypted with the session key. Are there any glaring vulnerabilities in this, besides forward secrecy and man in the middle attacks?

No, because Bob cannot know for sure who send the public key in the first place. So impersonation may still be an issue, even if man-in-the-middle attacks are not possible.

If the communication is over a channel that can only be eavesdropped by Eve (i.e. Even cannot send anything to Bob within Bob knowing it is not from Alice), then this is secure. But that's a rather strong requirement.

In general, this is solved by a Public Key Infrastructure (PKI). The most well known one is the PKI based on X509 certificates used by internet browsers, which uses certificate authorities and browser organizations as trusted third parties as well as DNS to establish trust.


Help with AES decryption with AES-NI Instructions I am in process of implementing a AES 128 encryption in AVX2 assembly (using AES NI), and am having some problems with decryption logic. I have implemented the encryption sequence without any trouble. However, decryption has been giving many problems.So, my questions regarding the decryption are :

Are the keys identical for the encryption sequence and decryption sequence? If not, then, am I required to execute a VAESIMC instruction on the keys as generated for encryption to make those functional for decryption ? If yes, then must I skip this instruction for the Key 0 [the original Key] and for the Key 10 [the last in sequence to get generated] ? Please clarify...
Once the keys have been generated, the sequence of operation is to take the ciphertext, XOR with the Key 10 value, and apply VAESDECLAST to the result using Key 9, and VAESDEC for all other rounds? Or, alternatively, I must apply VAESDEC to result of the XOR from Key 10 step, and apply the VAESDECLAST to the last round (Key 1 ) ?

All help and advice is welcome.
Remain grateful..

This answer is based on Intel® Advanced Encryption Standard (AES) New Instructions Set whitepaper (Revision 3.01, September 2012) by Shay Gueron.

No, the keys are not identical (within order) for encryption and decryption. The first and last key used in decryption are indeed the last and first one used in encryption; but the other decryption keys are the encryption keys with an additional InvMixColumns applied (usually by way of the AESIMC instruction in a preparatory step), in reverse order.
No, the sequence of operations is not as described in the question; it shall be, for AES-128:

XOR with $K_{10}$ (the last and 11th key used in encryption);
for $j$ from $9$ downto $1$:

apply VAESDEC to the result using $K^\prime_j$ (the image by InvMixColumns of the $(j+1)$th key used in encryption);

apply VAESDECLAST  to the result using $K_0$ (the first key used in encryption).

Rationale: having InvMixColumns pre-applied to (the bulk of) the round keys allows to combine them in the decryption flow after InvMixColumns, rather than before in a realisation of decryption that inverts encryption step by step. Presumably, that's easing pipelining constraints. It works because InvMixColumns is linear, that is $\operatorname{InvMixColumns}(X\oplus K_j)=\operatorname{InvMixColumns}(X)\oplus \operatorname{InvMixColumns}(K_j)$.