Do I have to know RSA padding scheme in advance when verifying signature with EVP_Verify*? Is there a way to figure out what RSA padding type was used on signature during verification (when calling EVP_VerifyInit, EVP_VerifyUpdate and EVP_VerifyFinal) or is it a matter of convention which has to be known in advance?

For this answer I'll be focussing on solely on RSA (the RSA tag is present, so I'll suppose that this question is just about RSA). It is also the most likely signature scheme that requires padding, I suppose.

TL;DR: you don't just need to know the padding scheme in advance, but also the other configuration options to be used, such as data hash method and MGF1 (configured with it's own hash), salt and label for PSS.

Yes, the padding scheme is something that needs to be known in advance during verification and of course signature generation. There is no easy way of verifying which padding scheme is used from within most signature schemes without first performing modular exponentiation yourself, after all.

If you'd allow both PKCS#1 v1.5 padding for signature generation and PSS during verification (and rely on the verification result to be true for either one of them) then your verification may fail if a successful attack is launched on either one of the two schemes. Besides that, it would require you to perform the signature generation twice.

The same goes for hash functions, where the acceptance of a hash from a weaker hash function may lead to insecurities. Even if these kind of insecurities are not directly visible or possible, in general the security proofs of the algorithms generally do now allow the key to be used for different schemes.

Sometimes there are indications that using keys for different schemes is problematic. E.g. for PSS the following can be found in PKCS#1 v2.2:

  This encoding method is parameterized by the choice of hash function,
     mask generation function, and salt length. These options should be
     fixed for a given RSA key, except that the salt length can be
     variable (see [JONSSON] for discussion).

Similarly, the withdrawn ISO 9796 specifications for signatures giving message recovery make it explicit that the configuration options need to be known in advance. It contains a section with three options in that respect:

  Use of the signature schemes specified in this standard requires the selection of a collision-resistant hash-function h. There shall be a binding between the signature mechanism and the hash-function in use. Without such a binding, an adversary might claim the use of a weak hash-function (and not the actual one) and therebyforge a signature.NOTE 1There are various ways to accomplish this binding. The following options are listed in order of increasing risk.

  Require a particular hash-function when using a particular signature mechanism. The verification process shallexclusively use that particular hash-function. ISO/IEC 14888-3 gives an example of this option where the DSAmechanism requires the use of Dedicated Hash-function 3 from ISO/IEC 10118-3 (otherwise known as SHA-1).
  Allow a set of hash-functions and explicitly indicate the hash-function in use in the certificate domain parameters.Inside the certificate domain, the verification process shall exclusively use the hash-function indicated in the certificate.Outside the certificate domain, there is a risk arising from certification authorities (CAs) that may not adhere to theuserís policy. If, for example, an external CA creates a certificate permitting other hash-functions, then signatureforgery problems may arise. In such a case a misled verifier may be in dispute with the CA that produced the othercertificate.
  Allow a set of hash-functions and indicate the hash-function in use by some other method, e.g., an indication in themessage or a bilateral agreement. The verification process shall exclusively use the hash-function indicated by theother method. However, there is a risk that an adversary may forge a signature using another hash-function.

I've included this mainly to show that when it comes to calling signature verification methods that the configuration options of the signature functions need to be known in advance. It makes sense that the signature algorithm itself and padding method should then also be known in advance.

For debugging or reverse engineering the methods used, it makes sense to perform modular exponentiation first. For PKCS#1 v1.5 padding the padding bytes will be immediately identifiable. If it just looks like random data then you are most likely dealing with a PSS signature scheme. Generally you can distinguish various initial and trailing bytes of the padding method as well. Unfortunately many different padding methods have been used in the past, more than you might imagine.


Size of Pre-Master Secret? I am implementing TLS 1.2 and using cipher ECDHE_RSA_WITH_AES_128_GCM_SHA256

According to RFC 5346 Section 8.1 length of premaster secret will vary depending on key exchange method.

So, what is the size of premaster secret according to above key exchange method?

Quoting from RFC 4492

  All ECDH calculations (including parameter and key generation as well
   as the shared secret calculation) are performed according to [IEEE 1363, 2000]
   using the ECKAS-DH1 scheme with the identity map as key derivation    function (KDF), so that the premaster secret is the x-coordinate of    the ECDH shared secret elliptic curve point represented as an octet    string.  Note that this octet string (Z in IEEE 1363 terminology) as  output by FE2OSP, the Field Element to Octet String Conversion    Primitive, has constant length for any given field; leading zeros found in this octet string MUST NOT be truncated.

More specifically, it is the byte count of the prime of the Elliptic Curve Field that you are using to exchange your keys.


Key Derivation Functions offering better than 2^hlen security? On page 21 of his HKDF paper, Krawczyk criticized one of the stated desirable features of KDFs from the paper “On The Security of Key Derivation Functions” (Emphasis mine):

  Due to the way the hash function is used by these schemes, their
  strength (measured by the work factor it takes to guess the output
  of the KDF) is never more than $2^k$ where $k$ is the output length of
  the hash function, and this is the case even when the entropy of the
  source key material is (much) larger than $k$. Indeed, in these
  schemes it suffices to guess $Hash(SKM)$ to be able to compute all the
  derived key material. While we agree with this fact, we do not agree
  with the criticism. If a work factor of $2^k$ is considered feasible
  (say $2^{160}$) then one should simply use a stronger hash function.
  Counting on a $2^k$-secure hash function to provide more than $2^k$
  security, even on a high-entropy source, seems as unnecessary as
  unrealistic.

This seems like good advice in general: If you want a KDF with a strength larger than $2^k$, then make sure the output length length of your hash is greater than $k$. (You should also, of course, make sure the SKM is stronger than $2^k$)

However, in some highly constrained environments the use of a hash with a larger output length (Like SHA512) is computationally infeasible due to a lack of a hardware implementation, such is the case on many smart cards.

Is there any formally-defined KDF which allows for an output strength larger than $2^{hlen}$ (where $hlen$ is the hash output length), while only using a common hash function like SHA1 or SHA256?

Note that Krawczyk's paper builds the extract-and-expand paradigm from a notion that he labels computational randomness extractor.  This is a modification of the concept of randomness extractor such that the output of the computational extractor need only be computationally near to a uniform random distribution, while a plain old randomness extractor needs to be unconditionally near to such a distribution.  So an extract-and-expand KDF is a combination of:

A computational extractor, which takes weakly random inputs and "condenses" it into a computationally-strong master key;
A pseudorandom function keyed off the computational extractor's output, which is used to produce expanded pseudorandom outputs.

So a KDF that can extract the maximum entropy that can be extracted from the source key material would replace the composition of these two submodules with a randomness extractor that's capable of producing output with the desired entropy from the source key material.  This is akin to the techniques used in true random number generators to produce full-entropy, uniform outputs from biased or correlated noise sources.

Randomness extraction is a big topic; searching the web for "randomness extractor" produces some technical introductory material.


How many different ciphertexts in repeated substitution cipher? Consider an alphabet with 26 letters. Then a substitution cipher has $26!$ possible ciphertexts (with every letter substituted). What about repetive substitutions on a 5 letter word for example? How many different ciphertexts will result? Like $\sigma(a)=b, \sigma(b)=c, \sigma(c)=a$, then $abc \rightarrow bca \rightarrow cab \rightarrow abc$ so two ciphertexts for $|A|=3$.But what about generally?

What you are asking is how many times do you have to apply the substitution on a plaintext to arrive back at the plain text. One observation is that it will depend on the order of the substitution as an element of $S_{26}$, the permutation group on 26 elements. If your permutation has order $n$, than applying it $n$ times is the same as the identity permutation. For a given substitution, it is not hard to determine its order.
Your question is a little different. For a given plaintext, it could take fewer iterations to return back. You are interested in the permutation's action on a subset of elements and not the full set. It is going to have to do with the orbits of each plaintext letter under the permutation. So for a plaintext "abcde", how long does it take each of a, b, c, d, and e to cycle back? The answer is the LCM of those lengths. In particular, notice that the answer might be totally different for plaintext "fghij".


How to know when decryption fails in Yao's Garbled Circuits I'm reading A Gentle Introduction to Yao's Garbled Circuits, and I came across this passage:

  Note that in order for this to work, Evan needs to know when
  decryption succeeds, and when it doesn’t. Otherwise, there’s no way
  for him to know which ciphertext yields the correct answer. So, simply
  XOR-ing the key with the encrypted value will not work here.

Essentially, Alice sent 4 values, each encrypted using different keys using symmetric-key encryption. Bob has one of the 4 keys and needs to know for which of the 4 values decryption succeeds. How does Bob accomplish this?

I figure since the unencrypted values are all either 0 or 1, the encryption could somehow be set up so that a failed decryption produces a non-0/1 value with really high probability, but I don't know if this is right.

How is failed symmetric key decryption detected in Yao's Garbled Circuits?

Your intuition is correct, the encryption is set up to indicate a failed decryption when an incorrect key is used with the ciphertext. A very simple way of doing so can be as follow: when encrypting the message $m$ with the key $K$, encrypt $m||0^{\lambda}$ ($\lambda$ is a security parameter, e.g. 80 or 128). When decrypting a ciphertext, check whether the last $\lambda$ bits are $0$; if this is not the case, decryption failed.

Note that the paper you are reading describes also the point and permute technique, which allows to find out which ciphertext we should decrypt, without having to try them all. This is an important optimization for garbled circuits.


Purpose of expanding then shrinking in SHA-1 What is the purpose of expanding then shrinking in SHA-1? Does it serves any security purposes?

Expanding then shrinking in SHA-1 refers to the process, performed for each round (each 512-bit block of padded message), of

message expansion from 512 bits to 2560 bits;
keeping only 160 bits of state for the next round.

The later directly follows from the construction of SHA-1 as a Merkle-Damgård hash of 160 bit. The former occurs because SHA-1's compression function is built from a block cipher using the Davies-Meyer construction, that is with the message entering the block cipher's (512-bit) key input; and, as most block ciphers do, the particular block cipher used in SHA-1 uses a key schedule, expanding the key to 80 subkeys (each 32-bit), one per round.

The expanding in SHA-1 is thus the key schedule of its block cipher, and is there to make SHA-1's internal block cipher secure, making SHA-1's compression function collision-resistant, making SHA-1 collision-resistant.

As an illustration that the key schedule/expansion plays a security role, the short-lived SHA (now known by the retronym SHA-0) differs from SHA-1 by a weaker key schedule (with one less word rotation), and is more badly broken than SHA-1 is (in particular, by  Yusuke Naito, Yu Sasaki, Takeshi Shimoyama, Jun Yajima, Noboru Kunihiro, Kazuo Ohta: Improved Collision Search for SHA-0, in proceedings of ASIACRYPT 2006).


Entropy estimation by Linux Kernel when adding entropy from TRNG As per resources given below, after adding the bits to entropy pool, the Linux RNG estimates the amount of entropy for "credit_entropy_bits" function. It is estimating the amount of entropy of an event as a function of its timing. Initially, the estimator calculates the jiffies differences on three levels. Then, estimator takes the minimum of the differences absolute values and finally, it assigns it a value between 0 and 11.

I am using a TRNG for supplying entropy to Linux entropy pool. The output of TRNG is 160 bits i.e. the entropy of source is 160 bits. In case of TRNG, What will be value of entropy for "credit_entropy_bits" function ? Will it be 160 bits ?

I have pointed the "rng_current" to "rng-caam". I am running "rngd" with r option i.e. "rngd -r /dev/hwrng".

https://hal.inria.fr/hal-00738638/file/rr8060.pdf
https://eprint.iacr.org/2012/487.pdf
https://github.com/torvalds/linux/blob/master/drivers/char/random.c

When you are adding entropy from outside the kernel, the kernel's entropy estimation functions are not used. Instead the entropy count is either not updated (e.g. if you just write data to /dev/random) or is updated according to the entropy count given to the kernel (e.g. through the RNDADDENTROPY ioctl).

Since you are using rngd, it will run some tests and assuming they pass ask the kernel to credit the entropy count with the full size of the data that was mixed in. I.e. 160 bits if you had 160 bits of data from the TRNG.


Improving Caesar Cipher security One of the weaknesses of Ceasar is that an attacker knows the order of my alphabet, IE ABC...Z

If I scramble this, then are there enough permutations to ensure my resultant ciphertext cannot be brute forced.
Does this then only leave me vulnerable to frequency analysis.

This is a monoalphabetic substitution cipher (with a mixed alphabet; in the first section of the article there is a paragraph about its security)

While the keyspace of this cipher is huge (relatively speaking for a classical cipher) with $26!\approx 2^{88.4}$ possible keys, it is still quite easy to break with frequency analysis.

Caesar is much worse of course, because you can simply try out all $26$ possible keys, and that is not possible for a simple substitution cipher (with arbitrary permutation).

  Does this then only leave me vulnerable to frequency analysis.

Well, that statement is true. But "more than almost nothing" doesn't mean much.


The Security of AES-N-GCM In the paper The Security and Performance of the GaloisCounter Mode(GCM) of Operation,it shows the AES GCM SECURITY in Corollary 1.

there are no distinguishing attacks against AES-N-GCM that work with distinguishing advantage greater than $A_{A E S-N}+q^{2} 2^{-116}-q 2^{-89.4}$

there are no forgery attacks against AES-N-GCM that work with forgery advantage greater than$A_{A E S-N}+q^{2} 2^{-116}-q 2^{-89.4}-q 2^{-128}$

But I can not get the same result (the right corollary) from the theorem 1 & 2 as the paper described when I plug in the value of parameters.
Here are the Theorem 1 & 2:

I presented my calculating process below.
$A_{E} \geq A_{G C M}-q^{2} 2^{-129}\left(94^{2}+2 \times 2 \times 95\right)-q \times 95 \times 2^{-96}$
$A_{E} \geq A_{G C M}-q^{2} \times 9216 \times 2^{-129}-q \times 95 \times 2^{-96}$
$A_{E} \geq A_{G C M}-q^{2} 3^{2} \times 2^{-119}-q \times 2^{-89.4}$
I notice that my result has a  $-q^{2} 3^{2} \times 2^{-119}$  item.However,the corollary in paper displays a $+q^{2} 2^{-116}$ .

You appear to have computed things correctly. However, you have quoted their Corollary 1 wrong: you've included an extra $-q^22^{-128}$ term in the confidentiality part  (don't know if that was what confused you though). To get their $2^{-89.4}$ instead of your $2^{-89.5}$ simply include more decimals of $\log_2(95)$.


What are the requirements from a Round function in Feistel network? Let's assume a balanced network with many (dozens?) rounds. And a simple (selecting key bits) key schedule.
What does it take from the round F function to make a secure block cipher? obviously we need non linearity and some avalanche. But is this sufficient, how can this still fail?
Does a high round count compensate for any mild weaknesses in the F function?

What does it take from the round F function to make a secure block cipher?

The ability of providing resistance to most common attacks like differential, linear, algebraic, slide and others mainly depend on the features of S-box (if used). * Simon does not use an S-box.
To design F-function, it depends on the structure of your Feistel
cipher Type I, II, III and others (which differ in term of number of
branches, number of F-function, internal structure of F-function).
The size of plaintext (64,128) could also influence the size of box
(4-bit or 8-bit), like piccolo vs Clefia. Therefore, the differential probability, linear probability and algebraic immunity differ, 8-bit S-box provide higher immunity features, therefore lower number of active S-boxes needed to provide minimum immunity, hence lower number of rounds.
The internal structure of F-functions such as SP vs SPS influences
diffusion (in term of number active-box). In addition, the use of
different MDS matrices in r-rounds (multiple round diffusion or
diffusion switching mechanism (DSM)) provide higher diffusion compared
to using 1 MDS matrix. CLEFIA employs DSM.
On the other hand, 8-bit s-boxes such as those in AES are expensive in term of
masking against side channel attacks. One way is to use smaller
s-boxes (easy to mask) to build larger s-boxes or using 4 bit S-box.

Does a high round count compensate for any mild weaknesses in the F function?

I don't think if you have self-similarity F-function, it will be
vulnerable to slide attack, increasing the number of rounds will not
providing compensate for weakness. To solve the self-similarity of F-rounds it is recommended to add constants. For how to chose round constants for simple key scheduling, I recommend to read

  Proving Resistance against Invariant Attacks: How to Choose the Round Constants

There are others structures of internal F-function (not only SP, SPS) such as ARX (e.g. the Simon cipher) that have been design in a triangle of security, performance and size, and resistance to both mathematical and implementation attacks (such as timing, DPA).


Can keys from Bitcoin's Hierarchical Deterministic Wallets be correlated (reducing privacy)? I'm trying to understand if the feature "Hierarchical Deterministic Wallets" in Bitcoin allows for complete privacy of all derived keys, and if any of those keys can be associated with each other after they are generated.

Knowing the answer to this will greatly impact the scenarios these keys are usable in.

I recently came across a paper that may interest you that I think answers your question. To quote from the abstract:

  Unfortunately, in all existing HD wallets---including BIP32 wallets---an attacker can easily recover the master private key given the master public key and any child private key. This vulnerability precludes use cases such as a combined treasurer-auditor, and some in the Bitcoin community have suspected that this vulnerability cannot be avoided.

Combine this with the fact that child private keys are generated from the master private key, and it appears the answer to your question is no, they do not offer complete privacy.


Seeking key stream as way to reuse a key In order to reduce the amount of key exchanges, I propose to encrypt messages using the same key stream, by selecting subsequent positions in the keystream for the separate messages.

I.e., message $M_1$ gets encrypted with the first $|M_1|$ bits of the key stream, message $M_i$ with bits $|M_1| + |M_2| + \dots + |M_{i-1}|$ to $|M_1| + |M_2| + \dots + |M_{i}|$ bits of the same key stream.

Observation: This way, I see it as if I encrypt a long message $M_1+M_2 \dots + M_i$ using said stream cipher.

Question: is this observation correct, for

all stream ciphers;
any specific stream cipher in particular, let's say Salsa20, and ChaCha20;

given that the time interval between messages is "large", and new messages might depend on different transmissions (possibly by an attacker)?

To address your bullet point directly, yes this will work for all generic key streams that only produce a sequence dependent solely on a key.
 However these are some real world problems.

Your scheme requires perfect synchronicity between a single pair of sender and receiver.  Otherwise the stream position will get lost as that is not part of the transmission.
You've specifically mentioned attackers.  Receipt of an attackers message will throw out the stream position and you'll never recover it without careful tracking of the number of characters received. Perhaps not even then.
Similarly, anything other that a single pair of sender /receiver will make stream position recovery extremely difficult. In the long term, impossible /impractical.
Salsa20 /ChaCha20 overcome this problem by use of a nonce that resets the key stream to an identifiable position.
If you don't exchange keys, how can new members join the party?

Key exchange is a part of cryptography and is well addressed.  Key stream positioning is the role of a nonce, and well discussed.


Cipher based message authentication (CMAC) and block reordering Is Cipher based message authentication (CMAC) susceptible to block reordering (just like CBC)?

No, CMAC is not susceptible to block reordering.

Unlike CBC, the attacker does not see the values of the intermediate encryptions (and because of the tweak applied to the last block, he can't find that out by asking for the MAC of prefixes).  Hence, the attack cannot modify the plaintext (including reordering blocks) in a way to make a predictable change to the hash output.


How to verify if g is a generator for p? For learning purpose, supposed I have a 16-digit prime which is 2685735182215187, how do I verify if g is a generator? (p is supposedly a special kind of prime)

Steps:

Factor $p-1$, that is, find the primes which, multiplied together, produce $p-1$.  In your case, $2685735182215186 = 2 \times 1342867591107593$
For each prime factor $q$ of $p-1$, verify that $g^{(p-1)/q} \not\equiv 1\pmod p$

If every such $q$ verifies (that is, they were all not 1), then $g$ is a generator.


Smallest Guaranteed hash collision cycle length If I take the sha-256 of an empty string, and apply the hash function $2^{256}!$ times, will I end up with the same hash that I started with?

Is the smallest required cycle equal to the LCM of $1$ to $2^{256}$?

In a uniform random function, which is a mostly reasonable model for SHA-256, you are not guaranteed that any particular element lies in a cycle: it could go $A \mapsto B \mapsto C \mapsto B$ and therefore never return to $A$.

In fact, only a tiny minority of elements are likely on cycles at all—the expected number of elements on cycles in a uniform function of $n$ elements grows with $\frac 1 2 \sqrt{2\pi n}$; for SHA-256, this is about $2^{128}$ of $2^{256}$ possible 256-bitstrings, i.e. the probability that any particular element is on a SHA-256 cycle is about $2^{-128}$.

However, if you just want to know how long you must pursue a hash chain before it cycles somewhere—not necessarily back to where you started ($A$), but somewhere you started going in circles lost in the desert trying to follow your own tracks like a pair of Belgian detectives ($B$)—the length of that chain turns out to have the same distribution as the number of elements on a cycle, with expectation $\frac 1 2 \sqrt{2\pi n}$, and the expected length of the cycle itself is $\frac 1 4 \sqrt{2\pi n}$.

So on average you'd have to follow $2^{128}$ elements before you ever come back upon your footsteps somewhere in a SHA-256 hash chain, and the average cycle length is about $2^{127}$, so you'd skip half your footsteps when you cycle back.

Here's an illustration that I stole from fgrieu of a 7-bit hash function—the vast majority of points, the grey dots, are not on cycles at all; only the red dots are on cycles:

Of course, in principle it could turn out that SHA-256 is actually a permutation of $\{0,1\}^{256}$ and is a single giant cycle, in which case you would actually have to tread $2^{256}$ steps—this, rather than the much larger $2^{256}!$, is the maximum number of steps before you are 100% guaranteed to have cycled back upon your footsteps.  But it is exceedingly unlikely that SHA-256 is a permutation, let alone a cyclic permutation—this would be an astonishing development if proven.

See Harris 1960 (paywall-free) for everything you need to know about statistics of uniform random functions, permutations, and derangements.


What motivated the creation of RSA and ECDH? Recently I've been learning about cryptography and so far I am loving it. However, there are some things I do not comprehend.

As far as I know, RSA was published in 1979 while New Directions on Cryptography by Diffie and Hellman was published in 1976. What I wonder is, what motivated the creation of RSA? Was it because they wanted to create something more secure than Diffie-Hellman? And if so, why is it more secure? Or was it because it was designed for other purposes which couldn't be accomplished with Diffie-Hellman?

On the other hand, it was not until 1985 that Neal Koblitz proposed cryptography based on elliptic curves. I've been told that elliptic curves offer more security than classic Diffie-Hellman but I'd like to understand and know how. I don't know much about security level. I've seen expressions like "$n$-bit keys give $m$-bit security" but I do not fully understand what do they mean. I see that ECDH offers more bit security than DH, but how can that be measured if attacks for both are not the same?

Thank you! And don't worry about throwing some math, I will probably understand.

What I wonder is, what motivated the creation of RSA? Was it because they wanted to create something more secure than Diffie-Hellman? And if so, why is it more secure?

The New Directions In Cryptography paper introduced the idea of public-key cryptography (though it had been proposed by Merkle before), and public-key cryptography was intended to solve two major problems: The key distribution problem, and the problem of authentication which is now referred to as "digital signatures".

Besides the general excitement of an entire new field of research being opened up, one of the motivations for RSA was to define a primitive that solved both problems of key distribution (or public-key encryption) as well as digital signatures. This is actually easy to see from just the title of the original RSA paper: "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems".

Their paper explicitly states this (emphasis mine):

  ... This method provides an implementation of a “public-key cryptosystem,” an elegant concept invented by Diffie and Hellman. Their article motivated our research, since they presented the concept but not any practical implementation of such a system.

Was it because they wanted to create something more secure than Diffie-Hellman? And if so, why is it more secure?

So as you can see, the answer to this question is "no" - it was simply a matter of accomplishing the feat at all, in general. The question of a given amount of security for a given amount of efficiency doesn't arise until after you at least have working examples of the concept.

Or was it because it was designed for other purposes which couldn't be accomplished with Diffie-Hellman?

As shown in the previous quotation, yes. Though, the world would later develop techniques that allow public-key encryption and digital signatures without requiring a trapdoor function/permutation.

As for the second part of your question, this other answer attempts to go into detail.

But basically, Diffie-Hellman works (as in correctness is guaranteed) for any finite cyclic group, (only a semigroup is actually required as inverses and identities are not used). There are generic attacks that apply irrespective of the actual group that you use, but for a given group there might exist attacks that are more efficient than the generic attacks. In finite field Diffie-Hellman (e.g. classic or "regular" Diffie-Hellman) there are non-generic attacks that do not apply or not known to have equivalents in the elliptic curve setting.


Why is Decisional Diffie–Hellman assumption harder than the Computational Diffie–Hellman assumption in cryptography? I did not understand why the decisional Diffie-Hellman assumption is harder than computational Diffie-Hellman assumption, I read that there are groups where DDH is known to be easy but CDH is still assumed to be hard.Please, could you explain this one, by using an example?

There are groups that allow a 'pairing' operation; that is, an efficiently computable function $e$ with the property:

$$e(x, y^a) = e(x^a, y)$$

for all group members $x, y$ and integers $a$.  Actually, the pairing operation maps the pair into another group, with the additional property $e(x^a, y^b) = e(x, y)^{ab}$; that's not important here (but is important for other uses of the pairing function).  We also assume that $e$ is nontrivial, that $e(x, y)$ doesn't uniformly map to the identity group member.

In any case, if we were given four values $g, g^a, g^b, g^c$, this function would allow us to check whether:

$$e(g, g^c) \stackrel{?}= e(g^a, g^b)$$

If this equation doesn't hold, then we know that $g^{ab} \ne g^c$ (and if we make some assumptions on $e$, then we can actually get equivalence).

However, this $e$ function doesn't give us any obvious way to recover the value $g^{ab}$, given $g, g^a, g^b$


How are recovery keys possible if something is encrypted using a password? I thought that encryption works as follows - it is about changing the thing we want to secure using an algorithm and using the password to mathematically change the secured content so it is unreadable.
If something is encrypted using a password then doesn’t it mean that the password is the only thing that can be used to mathematically change the encrypted thing so it becomes unecrypted?
I just have no idea how do recovery keys can even work!

Conceptually, a recovery key is usually like a second password.  The data is typically encrypted with a data encryption key and then the data encryption key is then encrypted twice, once with a key derived from recovery key and once with a key derived from the user password.  A significant point here is that the data encryption key never changes.  If you change your password then that just results in the data encryption key being encrypted with a new key derived from the new password.
The specifics depend on the exact product that you're interested in (e.g. Bitlocker or Apple or whatever).
By the way, the above (again at a high level) is very similar to how data is encrypted using PGP and I've read that it's similar to S/MIME as well (though I've never read that spec so cannot confirm that).


Why is CRC said to be linear? It is commonly understood that CRC satisfies the linear identity with respect to the $\oplus$ (XOR) operation:

$\operatorname{CRC}(a) \oplus \operatorname{CRC}(b) = \operatorname{CRC}(a \oplus b)$

But after some experimentation and research it appears that this is not generally true.

The particular algorithm in question is the one used in HDLC, ANSI X3.66, ITU-T V.42, Ethernet, Serial ATA, MPEG-2, PKZIP, Gzip, Bzip2, PNG (see Wikipedia) which uses the polynomial $\mathtt{0x04C11DB7}$.

In what sense is CRC linear? Is this a misconception?

In practice, CRC operations are often started with a nonzero state.  Because of this, the actual equation is usually of the form:

$$crc(a) \oplus crc(b) = crc( a \oplus b ) \oplus c$$

for some constant $c$ (which depends on the length of $a$, $b$).

An alternative way of expressing this is, for three any equal-length bitstrings $a, b, c$, we have:

$$crc(a) \oplus crc(b) \oplus crc(c) = crc( a \oplus b \oplus c ) $$

The technical term for this relationship is affine; in cryptography, we treat it as linear because, for attacks that assume linearity, affine works just as well.


Strength of block ciphers under attack [by government level attackers] So lets say the government has set their top priority to cracking a Veracrypt or Lukes or whatever volume containing highly confidential information.
It uses AES or AES(Twofish). How would they start an attack and how efficient would it be?

Ps: If most block ciphers really are so vulnerable to side channel attack why are most governments still using them for classified information?

Obligatory XKCD: coercion (or/and bribery) works. Other usual strategies are

Rigging the particular machine used by the data owner.
Otherwise spying key-presses on that machine to obtain the password.
Password search (including by compromising this user's other passwords and trying variations); that's an industry that has several professional-looking offers, targeting at least law-enforcement budgets (your guess of other users is as good as mine). It works for encrypted data at rest, as in the question.
Finding the desired data (or the password) in a non-encrypted area, such as swap space, sidestepping the question's problem.

Directly breaking AES (even AES-128) by brute force is so hopelessly hard that it is unreasonable to even attempt that.

Side channel attacks (like timing attack and DPA) are entirely useless for encrypted data at rest, because the key is not there to be extracted.

AES implemented with AES-NI or other hardware is immune to timing attack, and I believe is immune to DPA on today's mainstream CPUs, except perhaps with most direct access to the CPU using the key (as feasible in Smart Cards); that's a risk, but a manageable one.


In W-OTS, could you XOR all public keys? Since the signatures all generate the public keys, those can be derived from sig and proven by pre-commited XOR of every pub key compared with XOR of every signature end hash.

If I understand you correctly, you're proposing that we have a number of one-time-signatures (which, with the corresponding messages, hash to the corresponding public keys), and then we produce the xor of all the public keys.  Then, the receiver would validate all those signatures together (by computing the corresponding public keys, xor them together, and seeing if the result is the published xor).

If so, it doesn't work; an adversary could put together a forgery, that is, a series of messages and signatures that would evaluate to that same xor.  How he would do so is straight-forward; he would generate a series of messages and random signatures; he would then find the corresponding public keys.  Then, he would find a subset of those public keys that would xor to the published value - this can be done by solving a set of linear equations.  That subset would be the forgery.


Factorization for special primes $P$, $Q$, and $R$ Suppose that $p$, $q$, and $r$ are distinct $n$-bit primes, we define
$$
\begin{array}{rcl}
P & = & p \mathbin\Vert q \\
Q & = & q \mathbin\Vert r \\
R & = & r \mathbin\Vert p
\end{array}
$$
Where $\mathbin\Vert$ means concatenation of two integers. For example
$$1165993 \mathbin\Vert 1420831 = 11659931420831$$
We are given $N = P \times Q \times R$ and $P, Q, R \in \mathbb{P}$, that is they are primes too. Can we factor $N$ in polynomial time?
I have listed an example for this question too, we know that
$$\scriptsize N = P \times Q \times R = 12263640959607413166286548792372138857838409113471105337781351695720741222286495632687410855193016269011718576637693250596988228986909434347895553431945099$$
Can we factor it?

I don't think that we currently know how to exploit such structure.
The set-up immediately makes one think of Coppersmith's method for factoring RSA moduli with some bits of the factors known. This constructs a two-variable integer polynomial with an unusually small integer solution and uses lattice methods to find the solution.
In this case the polynomial $(10^cX+Y)(10^cY+Z)(10^cZ+X)-N$ has the solution $(X,Y,Z)=(p,q,r)$ with $p,q,r\approx N^{1/6}$. However this is a polynomial in three variables which is beyond our current knowledge of Coppersmith's method. The additional information that $p$, $q$ and $r$ are primes (and indeed that $P$, $Q$ and $R$ are primes) is not used by the methods, but I cannot see anyway to exploit this. If there are additional relationships between $p$, $q$ and $r$ that can eliminate on variable, more might be possible.
If you drop the polynomial-time requirement, then your example with $n=85$ can be solved in four hours for less than $100.


Differential cryptanalysis tutorial of Howard M. Heys I am currently working on some research about differential cryptanalysis. There is a lot of literature about that topic in the internet. One of the most known paper is the tutorial on linear and differential cryptanalysis by Howard M. Heys. May be some of you know that paper, if not have a look here:

https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf

In the meanwhile I got a good idea about the attack and how it can be practically done. In the most tutorials on the net the process works a little bit different as by Heys. My focus here is the extraction of the key bits. This part is described in section 4.4 in the Heys paper. Heys starts the extraction at the end of the cipher, he wants to recover the last subkey. He is doing it by trying to decrypt the last round (How can the other keys be obtained? Heys does not tell about). As far as I currently understand the differential cryptoanalysis, it is not possible to encrypt single rounds (until now I read the paper of Heys). Because: All I have are some plaintext / ciphertext pair which I could obtain from the user of the cipher. The user encrypts with the key which I want to recover by doing the attack. So it should not be possible to obtain single outputs of a specific round or decrypt a single round by the user. (Me as an attacker should not be able to interfere the decryption and get input / outputs of a round while the user uses the algorithm)
Is my guess here wrong? How could the partial decryption could be done? I am referring to page 26 "A partial decryption..." and so on. Or what is Heys here doing?

Thanks for your attention and help.

There is no assumption of obtaining any outputs of an internal round at all.

Having done the analysis, the attacker submits enough plaintext pairs with fixed difference $\Delta P$ so that he can be sure with high probability that the most common ciphertext difference is $\Delta C$.

Note that in his example, the 2nd and 4th Sboxes are active, so the target key bits are those at the output of Sboxes $S_{4,2}$ and $S_{4,4}$.

Now he can do a loop where he tries all the $2^8$ possible key bit hypotheses
$$(\widehat{K_{5,5}},\widehat{K_{5,6}},\widehat{K_{5,7}},\widehat{K_{5,8}},\widehat{K_{5,13}},\widehat{K_{5,14}},\widehat{K_{5,15}},\widehat{K_{5,16})},$$
and under each hypothesis (since he knows the ciphertexts) he can determine the hypothetical differentials (correct subject to the key guess being correct) at the output of the Sboxes $S_{4,2}$ and $S_{4,4}$ which by inverting the Sboxes can be converted to hypothetical input differences of the form $\Delta U_{4,5},\ldots,\Delta U_{4,16}$.

Whichever key combination gives the most likely differential $$\Delta U_4=[0000~0110~0000~0110]$$ is declared the most likely key guess for the last round.
So he would keep a count corresponding to each hypothesized round 5 key as the loop runs and check which value gave the maximum count.

Then the rounds can be peeled off one by one as in the comments.


RSA-FDH and random oracle query count I am now reading a paper 'The Exact Security of Digital Signatures - How to Sign with RSA and Rabin' and there is an equation e = (q_sig + q_hash) * e' on page 401.
(e : success probability of RSA, e' : success probability of RSA-FDH)

What I want to know is the relation between query count(q_sig, q_hash) and security parameter k.
Is query count is proportional to poly(k) or 2^k?

In case of RSA, k is the bit length of modulus. So I feel like it should be proportional to 2^k.
And if it is proportional to 2^k, how is e is guaranteed to be negligible in case e' is be negligible?

Thanks in advance.

It is proportional to $poly(k)$. Here $k$ is the security parameter (or more strictly speaking it should be $(1^k)$) and intuitively the adversary's can only be allowed to query polynomial times (since it is a PPT algorithm) bounded in terms of $k$. Then $e$ and $e'$ only differs by a polynomial factor, and thus allows you to reduce what you want to prove to the RSA problem.

The subtle technicality is that when modeling the adversary as a Turing machine and reasoning complexity (which is based on the size of input), the integer $k$'s length is only $log_2 k$, which will cause some formality problem. The more rigorous way is to supply $1^k$, a bit string of length $k$ that contains all 1s.


Secure way to transfer data over NFC? I am currently writing a payment system to accept payment details from an NFC enabled smartphone (BlackBerry 9900) to a Windows client (C#.NET)

I am currently having two issues relating to security:

What is a good way to secure the data for transmission over NFC? I'm thinking public key encryption so that it can be encrypted on the phone using the public key and then decrypted by the .NET on the other side using the private key.
How to secure the data so that the data can't be cloned by another reader i.e. another reader pretends the be the windows client and reads the secure data. This could then be played back to the windows client by the attacker at a later data to make a payment. I'm thinking that when the phone taps the client reader the client will send a token that must be present in the data returned from the phone that includes the sensitive data. I think that maybe the public and private keys should be created per each transaction request. The public key sent to the phone to encrypt the data. Maybe that would suffice as the token also as if it can't be decrypted by the client then it's an invalid request.

Please note that I have no experience in cryptography at all. I'm aiming to implement a solution that has libraries readily available in .NET 3.0 and BlackBerry SDK 7.0.

There is not much special about near field communication here - it is just like any insecure transport medium, which can be evesdropped on (with external antennas up to several meters in distance).

Because of the low distance limit, there is no way for a man-in-the-middle attack if you (the human operator) are sure that your device is communicating with the right reader, but there is the relaying attack (your blackberry communicates to a reader, which forwards the data to another device which communicates to the real reader), which also might including the replay problem.

I would recommend not to build a new protocol (especially if you are new to cryptography), but to reuse existing, generally known, protocols. In this case, the usual TLS (Transport Layer Security) protocol seems like a good fit, if you can provide your "server" with a private key which is kept secret, and whose corresponding public key could be certified by some certificate agency whose key (or root key of some chain) would be known to the "client".

In the usual way of SSL/TLS operating, client and server negotiate a shared secret, from which the session keys are then derived.

(I suppose it would be easier to let the Blackberry be the client and your windows machine the server, but it would work the other way around, too.)

I don't know anything about Blackberry programming (nor .NET), but I suppose that there are SSL/TLS libraries available for both.

Note that while this avoids replay attacks (the keys are individually creating depending for each session, and won't work later), this doesn't really help against the relaying attack - so make sure to only transmit your payment details to sellers you trust.


Hybrid encryption for MQTT payload? i've written a simple code for payload encryption, i'v done it with AES-128 CBC mode ,it works fine ,the senario is very simple : the publisher send a JSON payload format that includes the encryption key , IV (Initialisation Vector) and the encrypted data, the subscriber extract the key and IV then decrypt the data received, but i want to do a sort of hybrid encryption ,to encrypt the key with Asymmetric algorithm, i know the famous RSA, but after reading some articles, RSA is not suitable for constrained ressources devices, have you any idea wich algorithm can i use or somthing else that ensure the key transmission ?

I'm not endorsing your encryption scheme (because frankly it sounds dubious), but libsodium's Public-key authenticated encryption sounds like what you're looking for. It uses Curve25519 internally, which should be less resource-intensive than RSA. There are also bindings for many languages available.


How can I prove/disprove that a construction yields a secure PRG? Let $G:\{0,1\}^{*} \mapsto \{0,1\}^{*}$ be a secure PRG. Prove or disprove that the following construction also yields a secure PRG.
$$G'(k) = G(k||0),$$
where $||$ denotes the concatenation of two strings.

I understand that proving/disproving such constructions usually involves a proof by reduction or a counterexample. Intuitively, I would say that $G'$ is a secure PRG, since we only fix a bit of the input, which should not make the output distinguishable (in polynomial time). However, for some reason I can't finde the right reduction, since I don't see how a $w \in \{0,1\}^{*}$ and a distinguisher $D'$ for $G'$ can be used to construct a distinguisher for $D$ for $G$.

So is $G'$ a secure PRG? If yes, how can I construct a valid reduction and if no, how does a distinguisher for $G'$ work?

I don't know if it is appropriate, but I would prefer hints, which point me in the right direction instead of complete solutions.

If there exists a secure PRG, then there is a secure PRG

whose last bit of output is always equal the last bit of its input.

If the last bit of G's output is always equal to the last bit of G's input, then the

function G' constructed as described in the question will not be a secure PRG.


RSA signature signing For assymetric encryption such as RSA, I understand that Alice can sign a document with her secret key and send it to Bob, which he can then verify.

Sign: $\sigma=m^d \bmod N$

Verify: $v=\sigma^e \bmod N$

This may be a silly question, but what if it was the other way around, Bob wants to send a document to Alice. How would he sign it to say it was from him. Can he do it without introducing "Bob's secret key" and just use the scheme provided, or does he have to do that? or is there better way?

For Bob to prove that he signed the document, he needs to know something that other people do not.  In Alice's case, she knows her private key (we generally use the word private rather than secret when talking about signing keys), and we assume no one else knows it.

In Bob's case, everyone knows Alice's public key; hence if he used it somehow to sign a document, well, so could anyone else, and so that signature wouldn't prove that it came specifically from Bob.

There are other ways that Bob could try to prove authenticity (perhaps Bob and Alice share a symmetric key that no one else does; perhaps Bob has a secure connection with a Trusted Third party which is willing to vouch for Bob), however staying within the bounds of a simple asymmetric protocol, yes, Bob would need his own private key.


Vigenere ciphertext encrypted with another vigenere cipher I have been learning about Vigenere ciphers and then thought of this scenario: if a cryptographer encrypts a plaintext English message with a Vigenere cipher and then another cryptographer, who wants to ensure that the message is very secure, encrypts the ciphertext with another Vigenere cipher (with a different key length). Given only the ciphertext, how can you decrypt the message? A step by step explanation would be greatly appreciated.

Applying another round of vigenere would make the ciphtertext (in nearly every case) harder to break, yes. The problem is: This "new" algorithm is just a normal vigenere algorithm with a longer key (if the key lengths of both keys are not equal and not 1). You don't need to apply vigenere a second time, you can just calculate the new key in advance.

Example: We encrypt the plaintext "hello world hello world" with the key "ABC". (Encryption with A doesn't change the plaintext, it's like adding 0.)

hello world hello world
+
ABCAB CABCA BCABC ABCAB
=
HFNLP YOSND IGLMQ WPTLE

Now we encrypt the intermediate result again with the key "DDBC":

HFNLP YOSND IGLMQ WPTLE
+
DDBCD DBCDD BCDDB CDDBC
=
KIONS BPUQG JIOPR YSWMG

The length of the first key is 3, of the second key is 4. The least common multiple of both numbers is 12. If we now repeat the first key 4 times and "encrypt" it with the second key, we get a new key which eliminates the need for a intermediate result:

ABC ABC ABC ABC
+
DDB CDD BCD DBC
=
DED CEF BDF DCE

If we encrypt the plaintext with this new key we immediately get the final ciphertext:

hello world hello world
+
DEDCE FBDFD CEDED CEFBD
=
KIONS BPUQG JIOPR YSWMG

You see, double encryption (or more generally, multiple encryption) with vigenere doesn't add extra security by itself. You could just use a longer key from the beginning on. Search for generals attacks on vigenere to break this "double encryption".

What about the one-time-pad? You need a fully random, never before used key, which has to be as long as the plaintext for the one-time-pad. If you really use this scheme, you also don't need a double encryption: The one-time-pad is always fully secure if you tell nobody the key.


XEX mode - how to perturb the tweak The first part of the classical description of XEX is

$X = E_{k}(I) \otimes \alpha^j$

What I see a lot in sample code on the Internet is that you start with $T_ = E_{k}(I)$ and use that for the first block of the message. You then take $T$ and left shift it one bit. If the carry from that operation is a 1, then you XOR in 0x87 on the bottom byte. That becomes the pre- and post-crypto XOR material for the next block and so on.

This operation is exactly the same as the $K1$ and $K2$ derivation operations in CMAC. That's either an interesting coincidence or... well, I don't know.

Is that functionally correct?

You then take $T$ and left shift it one bit. If the carry from that operation is a 1, then you XOR in 0x87 on the bottom byte. That becomes the pre- and post-crypto XOR material for the next block and so on.

What's going on here is a finite field multiplication in the field $GF(2^{128})$, modulo the irreducible polynomial $x^{128} + x^7 + x^2 + x + 1$; if you look closely at the exponents of last four terms of that polynomial, they correspond to the positions of the one bits in 0b10000111 = 0x87.  This shift-and-conditional-XOR trick is a cheap way of "doubling" a binary string in $GF(2^{128})$, i.e., multiplying it by the polynomial $x$, whose binary representation is the numeral for two.  So sometimes you see the exact same thing notated as $2^n \cdot E_k(0)$, where the dot denotes multiplication in whichever finite field has been fixed for that context.


Has it become easier to pre-compute tables after MD5 collisions? Apparently it is not possible to compute all MD5 values from 0x00000000000000000000000000000000 to 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF.

As far as I understand this operation is hard because cryptographic hash functions make it difficult to calculate a message for a given digest (Pre-image resistance).

Storing all MD5 hashes requires $16 * 2^{128}$ Bytes, or $5.44 * 10^{39}$ Bytes, or billions of Yottabytes (1 Yottabyte = $10^{24}$ Bytes). This doesn't yet count the message(s) for each digest. To put this in context: 2011 it was estimated that the world wide storage capacity is "only" 295 Exabytes, ca. 0.0003 Yottabytes.

But MD5's collision resistance is broken. It doesn't take much time to create two different messages with the same hash.

Has the capability to provoke collision attacks in MD5 made it easier to create tables of pre-computed hashvalues?

Not really.
Finding distinct $m_1, m_2$ such that $H(m_1) = H(m_2)$ is a different problem than finding $m_1, d$ such that $H(m_1) = d$. If the first problem is hard it's called collision resistance, if the second problem is hard it's called preimage resistance.
MD5's collision resistance is practically broken - it's quite easy to generate a pair of $m_1, m_2$ that produce the same digest in a few seconds on a consumer CPU. However this result is not useful for creating pre-computed lookup tables at all, the contrary is true - you want as many different digests in such table, rather than collisions.
MD5's preimage resistance is theoretically broken (with a computational complexity $2^{123.4}$ according to Wikipedia), but that's not a practical result. So for example if I know that I still need a digest with value 0xFFFFA3BFFFFFFFFFFFFFFFFFFFFFFFFF in the table there is still no easy way to find an input for that digest.


Endomorphism ring of a Elliptic Curve and $j$ invariant I am reading Schoof's 1995 paper, Counting points on elliptic curves over finite fields, page 236, Proposition 6.1(i). I am trying to understand page 238 (second paragraph) of the proof: if the conductor is $1$ then $j$ invariant is $0$, or $1728$.

In Silverman's book, The Arithmetic of Elliptic Curves, Section III.10 on page 103, a relation between the Automorphism Group and $j$-invariant is given.
Is there any relation between the endomorphism ring of an elliptic curve to the $j$-invariant? When $j=0,1728$, how does the endomorphism ring look?

If the endomorphism ring is equivalent to the maximal order of the field, why is the $j$ invariant equal to $0$ or $1728$?

I know that given $E: y^2=x^3+Ax+B$, if $A=0$ then $j=0$ and if $B=0$ then $j=1728$. The endomorphism ring will be isomorphic to an imaginary quadratic field if $E$ is ordinary and to a quaternion algebra if $E$ is supersingular.

Please help me to understand the relation between the endomorphism ring and $j$ invariant.

If the endomorphism ring is equivalent to the maximal order of the field, why is the $j$ invariant equal to $0$ or $1728$?

The main source of all these theorems about endomorphism rings is in Deuring's Die Typen der Multiplikatorenringe elliptischer Funktionenkörper. Unfortunately, I can't find a free copy online, and I don't have a copy either. Another source besides Silverman's books is Washington's (not free) Elliptic Curves: Number Theory and Cryptography.

In any case, in those references, you can find a proof the following: The endomorphism ring of supersingular elliptic curves is a maximal order in a quarternion algebra. Silverman presents it as a starred homework assignment in the book you reference (problem 3.18), but I think going through it all is a bit too off-topic for this site.

As I mentioned in the comments, the $j$-invariant is useful in characterizing isomorphisms between curves, and if two curves are isomorphic (e.g., a curve and its quadratic twist), then they have the same $j$-invariant, but their associated endomorphism rings are isomorphic.

In general though, characterizing the endomorphism group is more complicated than the automorphism group. As Silverman notes in the section you reference:

  If an elliptic curve is given by a Weierstrass equation, it is generally a nontrivial
  matter to determine the exact structure of its endomorphism ring. The situation is
  much simpler for the automorphism group.

$j$-invariants are relevant for automorphisms because those contain invertible isogenies, but endomorphisms aren't necessarily invertible. $j$-invariants characterize isomorphisms between curves. Thus I wouldn't expect there to be a simple relationship between $j$-invariants and endomorphism rings.


Why is this hash function (based on a block cipher) insecure? I am new to hash functions and blockciphers and try to do some exercises to get a better understanding.

Considering the following block cipher if K is predefined value IV and the last ciphertext is the hash. I don’t really see how this hash function would be not secure but from what I heard block ciphers are only good hash functions if they use some sort of feed forward/backward with xor.

$C_1 = E_K(P_1)$
$C_i = E_{C_{i-1}}(P_i)$ for $i > 1$

Why is this hash function – which is based on a block cipher – insecure?

If you want a hint as to why your proposed hash function isn't secure (even against preimage attacks), I would note that block ciphers are invertible, that is, given $C_{i-1}$ and $C_i$, we can efficiently compute the value $P_i$ must be so that $C_i = E_{C_{i-1}}(P_i)$ holds.  Question for you to complete the answer: how can an attacker exploit this to create preimages?


Factor RSA modulus given many valid encryption decryption exponent pairs? I have read Is sharing the modulus for multiple RSA key pairs secure?, which explains an algorithm for factoring an RSA modulus n given only one encryption and decryption exponent tuple. Given multiple such tuples, is there a more efficient way to compute p and q? It seems like we could set up a system of equations using the Chinese Remainder Theorem and then could solve for Euler's totient directly. Once we have Euler's totient, we could solve a system of two equations with N and totient(N) to obtain p and q.

Given multiple such tuples, is there a more efficient way to compute p and q?

Possibly, however given how efficient the standard probabilistic method is, we generally don't bother.  Now, someone did find a nonprobabilistic algorithm to do so (proving that the problem is in P, not just in RP); however, it's less efficient in practice, and so that isn't used.

  It seems like we could set up a system of equations using the Chinese Remainder Theorem and then could solve for Euler's totient directly.

It's a little trickier than that; one issue is that we may have $ed \not\equiv 1 \pmod{(p-1)(q-1)}$; hence what such a series of equations would give might not be $(p-1)(q-1)$, but instead $\text{lcm}(p-1, q-1)$.  Now, in practice, $(p-1)(q-1)$ is extremely close to $N$, and hence it should be possible to give a good guess of $(p-1)(q-1)$ given $\text{lcm}(p-1, q-1) = (p-1)(q-1)/\gcd(p-1, q-1)$; however, it is nontrivial to write up an algorithm that will work in general.  In contrast, the standard probabilitic method always works (ok, half the time...)


Why can we ignore $y$ when using the extended Euclidean algorithm to calculate an RSA decryption exponent? I have a follow-up question about the extended Euclidean algorithm, as applied to RSA key generation, described in this answer.

Let us say we have $p=5$, $q=11$ and $e=17$, so that $N=55$ and $φ(N)=40$.

We can verify that $\gcd(e, φ(N)) = 1$, so $e$ is a valid encryption exponent.

Now the answer says we should use the extended Euclidean algorithm to find $x$ and $y$ such that $e \cdot x + φ(N) \cdot y = 1$, so that $e \cdot x \equiv 1 \pmod{φ(N)}$, and then let the decryption exponent be $d = x$.

By applying the extended Euclidean algorithm, we find that $x = -7$.

My first question is, how come $17 \cdot (-7) \equiv 1 \pmod{φ(N)}$?

Also, in the answer I linked to above, it says:

  "The value of $y$ does not actually matter, since it will get eliminated modulo $φ(n)$ regardless of its value. The EED will give you that value, but you can safely discard it."

I'm not sure what this is supposed to mean.  Could someone please explain it more clearly?

By definition of the notation $a\equiv b\pmod c$, this means $a-b$ is a multiple of $c>0$. Therefore, $17\cdot-7\equiv1\pmod{\varphi(N)}$ means that $(17\cdot-7)-1$ is a multiple of $\varphi(N)$.

Thus the answer to: "how come $17\cdot-7\equiv1\pmod{\varphi(N)}$" is just: because $(17\cdot-7)-1$ is $-120$, which is a multiple of $\varphi(N)=40$.

Addition trying to answer the question in the title: when you found $x$ and $y$ such that $e\cdot x+\varphi(N)\cdot y=1$ using the extended Euclidean algorithm, that implies $e\cdot x-1$ is a multiple of $\varphi(N)$, thus you have an $x$ with $e\cdot x\equiv1\pmod\varphi(N)$, irrespective of $y$.

Now how does it relate to choosing the private exponent in RSA?

Well you can use $d=-7$, it will work, but numerically computing $x^d\bmod N$ will require computing a modular inverse modulo $N$, and raising to the power $7$ modulo $N$ (in any order).

Or you can use that $-7\equiv33\pmod{\varphi(N)}$ and select $d=33$, obtained as $-7+40$; that would be a common $d$. More generally, any $d=x+k\cdot\varphi(N)$ will do from a mathematical standpoint (yet it is most common to restrict to $1<d<N$).

Or you can use $d=13$, which is the smallest positive private exponent possible, obtained by inverting $e$ modulo $\lambda(N)=\operatorname{lcm}(p-1,q-1)=20$ using the extended Euclidian algorithm and keeping the smallest positive representative; that's also common, and can save a little work: raising to power $13$ can be done with $5$ multiplications, rather than $6$ multiplications for power $33$.


Is the key deducible with AES CTR when we know about the plaintext, IV and the ciphertext? Simply as stated, with AES running in CTR mode, can somebody work out the key (without brute-forcing) given we know about the plaintext, IV and also the ciphertext.

Assuming we also know about the cipher block size & key length.

In other words, we have the pseudo random AES CTR stream + IV, can we work out what the key is?

No, that's not possible as long as the security of AES as a block cipher is not weakened.

In CTR mode a counter is encrypted using AES, and the result of that is XOR'ed with the plaintext. The counter actually consists of a nonce part and a counter part. Both the nonce and counter are known by a possible attacker.

If anybody would just be encrypting zeros the you would get exactly the key stream. This is still secure though, because the key used for AES is protected by the block cipher itself. And, as indicated by the comments of Dave Thompson, AES itself is secure against known plaintext attacks.

Basically the same reasoning can be performed for other (well known) block cipher modes of operation; the key is protected by the block cipher, how the result is used is inconsequential to security of the key.


Is this session start protocol secure? I am working on a password manager application that saves the user's passwords in a remote server. I need to use AES in CTR mode to encrypt the passwords before sending them to the server. The client is supposed to login/identify himself with a master password (which is already set in the server). This is what I've thought of until now:

Client connects to server.
Server sends a random value RAND1.
Client generates a random value RAND2, and calculates hmacKey = SHA1 (master|RAND1|RAND2).
Client calculates HMAC of RAND2, appends it to RAND2 and sends it to the server.
The server (who knows the master password) calculates its own hmacKey and verifies the client.

This hmac key would be used during this whole session. Is this secure?

You have the classic problem of establishing a common secret key between the two parties before they begin exchanging any sensitive information. Consider Diffie-Hellman or - since you're dealing with a client/server setup and the risk of a MitM - a private key on the server side and then use public key encryption to establish the session key before communicating the password. This can be achieved with RSA, authenticated DH, ElGamal, and a few other methods.


How can I generate a good password from a SHA512 hash? I have to change local administrator passwords on machines. I don't want to store password in a database. I have to generate a password that I can find later to connect to the machine again. So I periodically generate a secret random string (stored in a database) and make a hash of it with the machine  name. At this point I want to know how to generate a password from this hash (following current good practices) and I want to find the most secure way to do it.

So… I have to generate a password (in Python and following current good practices) from SHA-512. How can I do that? And what about security aspects concerning the password generation and the generated password?

So your idea is to effectively turn the password authentication into a key-based authentication by deriving the machine passwords from a single random key stored elsewhere. Assuming key storage is secure (probably encrypted with a strong password), this is sound.

It would be better to just use the asymmetric key-based authentication built into most remote access tools (like ssh), so that you don't mess up anything by rolling your own crypto. But if you need to use password authentication, your idea is not insecure either.

Actually generating the password / passphrase from a SHA-512 hash (or any seed material), it's a fairly mechanical process:

Choose the alphabet (or dictionary). For passwords you might use hex or base64, for passphrases any conveniently sized dictionary will do.
Choose the bit-strength. 128 bits is sufficient, but may result in quite long passwords. OTOH, there's no use making it longer than input entropy.
Consume the input bits to generate characters/words until you have a sufficiently long password. With a hashed input like SHA-512 you can just use the first bits from either end, with a non-mixed seed you should probably hash it first (with a strong password hash if entropy is low).


Last Sbox of a block cipher for Linear Cryptanalysis I figured I should try to learn about linear cryptanalysis with a super simple cipher with only one Sbox. The problem is that with that approach the last subkey bits seem to be involved in the linear approximation.

It looks like I need at least 2 Sboxes, keeping the last one to bring randomness in case of a bad guess on the bits of the last subkey. So obviously, the last one should also not appear in the linear approximation.

Is that understanding of Linear Cryptanalysis correct?

If you include a key addition layer ($K_1$) at the output as well the key addition layer ($K_0$) at the input of the Sbox then you can perform linear cryptanalysis on this simple cipher. You shall have access to $P,C$ pairs but no keys, of course, and the $P/C$ relationship is
$$C=K_1\oplus(S(P\oplus K_0))$$
and so your linear bias equations become something like
$$
\textrm{bias}(A,B)=\sum_{P} (-1)^{B \cdot (C\oplus \hat{K_1}) + A \cdot P}
$$
where  $A$ is the input mask, $B$ is the output mask, $P$ plaintext, $C$ resulting ciphertext and you choose the most likely key guess $\hat{K_1}$ which maximizes the observed bias. Before this, you choose the best mask pairs $(A,B)$ with $A\neq 0$ which give the best bias for the Sbox linear characteristics defined below
$$
\sum_{X} (-1)^{B \cdot S(X) + A \cdot X}
$$
where the sum ranges over the input set of the Sbox, and perform the attack for that $(A,B).$


Where would a "half round" come from? In the hierocrypt-L3 description, the cipher takes 6, 7, or 8 rounds.  Example source code also seems to follow this same specification of 8 rounds for 256-bit keys.  Wikipedia shows 8.5 rounds for 256-bits. I found it some other literature as well.

Where does this 1/2 round come from?

The following appears in the linked wikipedia article (emphasis mine):

  The Hierocrypt ciphers use a nested substitution-permutation network (SPN) structure. Each round consists of parallel applications of a transformation called the XS-box, followed by a linear diffusion operation. The final half-round replaces the diffusion with a simple post-whitening. The XS-box, which is shared by the two algorithms, is itself an SPN, consisting of a subkey XOR, an S-box lookup, a linear diffusion, another subkey XOR, and another S-box lookup. The diffusion operations use two MDS matrices, and there is a single 8×8-bit S-box.

So the final round operates differently, opting to replace the diffusion step with an add-key step.

It is not uncommon for block ciphers to skip the final linear diffusion operation, because it does not appear to improve security to include it. For example, AES skips the final diffusion step also. But they don't refer to it as a half round.

Salsa20

Salsa20 (and ChaCha) both use a double-round, which is counted as 1 round. So half-rounds appear again here in this context (scroll to FAQ), due to how the rounds are structured and counted.


Integrity or Confidentiality or Authenticity If a sender creates a hash H of message M and encrypts it using receiver's public key, what do we ensure of the above three at the receiver's end.

PS : I know this is not the right way to send messages but I'm just trying to learn how do things work in such cases.

You're sending a message without signing it, and without any element which can reliably identify you as the sender, so you're clearly subject to Man in the Middle (MitM) attack. An attacker can intercept your message and replace it by his, he only has to compute a hash, and encrypt it with the receiver public key.

The only thing is guarantied is the secrecy of your message, but the hashing was useless. Signing your message would have been a good solution since it implies a secret shared by the two parties.
An even better option would have been to use an authenticated encryption with associated data (AEAD) such as AES-GCM since it take care both of encryption and authentication, and asymmetric crypto is mostly use for signature and key exchange but not data encryption (I know it's not your point, but I had to say it ;-) ).


How do I get the equivalent strength of an ECC key? I know how to calculate the comparable symmetric strength of an RSA modulus: calculate the running time for a field sieve. This is how NIST gives approximate symmetric sizes for asymmetric algos in their publications: for RSA you can calculate running time of the field sieve:
$$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right)$$
What's the equivalent for ECDHE? Eg. what is the running time for the best known algorithm for attacking a given ECC curve?
RFC 4492 states:

the following table gives
approximate comparable key sizes for symmetric- and asymmetric-key
cryptosystems based on the best-known algorithms for attacking them.

Symmetric
ECC (binary curve)
ECC (prime curve)
DH/DSA/RSA

80
163
160
1024

112
233
224
2048

128
283
256
3072

192
409
384
7680

256
571
521 (not a typo)
15360

How can I replicate the ECC column's numbers?
Edit: some some research, the paper mentioned in the RFC now 404s but a copy found at http://infoscience.epfl.ch/record/164526/files/NPDF-22.pdf mentions:

2.6.3. Attacks. A DLNFS equivalent or other subexponential method to attack EC
systems has never been published. The most efficient method published to attack EC
systems is Pollard’s parallelizable rho method, with an expected run time of 0.88√q group operations.

However I still don't know how to replicate the results: an elliptic curve has P and Q but how do I know what Q is, for, eg, secp521r1?
Edit: Deirdre Connolly on Twitter mentioned an approximation:
$log_2(0.88 \cdot \sqrt{2^{n}})$
Which matches the RFCs results. Will do some more research and post it as an answer in the next few days if she doesn't.

The security level of an elliptic curve group is approximately $\log_2{0.886\sqrt{2^n}}$. You can use this to approximate the security level of a $n$-bit key, eg:

$\log_2{0.886\sqrt{2^{571}}} = 285.32537860389294$

The real computation (at least for curves over a finite field defined by a prime $p$) is $ \log_2{\sqrt{\pi/4}\sqrt{ℓ}} $, where $ℓ$ is the order (number of points) of the subgroup of points on the curve generated by the public base point. The size of $p$ determines the upper bound of $ℓ$, though it is not exactly the upper bound itself, it's generally pretty close. So for example, Curve25519 has an $ℓ$ of about $2^{252}$, so:

$ \log_2{\sqrt{\pi/4}\sqrt{2^{252}}} = 125.82537860389293 $

Our approximation based on the ECC key size gets us pretty close to this:

$\log_2{0.886\sqrt{2^{256}}} = 127.82537860389293 $

As otus notes below, Koblitz curves are slightly different.

The strength of any ECC key is bound to the strength of the underlying curve and domain parameters, and in general all the valid keypairs generated for a specific curve should have the same size/strength. There are some points that are invalid and should not be used, but your ECC implementation should handle that for you.

More info on determining the runtime of Pollard's Rho and thus the theoretical security level of various curves at SafeCurves: http://safecurves.cr.yp.to/rho.html


What is the maximum length of a X.509 OID? I'm working on a feature for a project to determine if a given X.509 certificate is an EV Certificate, and if so, who is the authority behind that certificate.

To do this, I grabbed the list of EV OIDs from Wikipedia, and keep them in a hash of OID -> Authority Name. I get the certificate policy OID and convert it into a char array that I can use in my hash.

However I'm unsure about what the maximum length of a OID can be. I'm having trouble locating that information in the spec or anywhere else online.

OIDs don't have a maximal length / depth specified. There is no real value where you can safely cut them off - or rather reject them (raise an exception or error). Anything over 20 bytes seems ridiculous, so that should be plenty. Limiting to a measly 1 KB of RAM should be fine on a non-embedded platform (desktop / server) as well, if you must set a limit.

When planning to protect against DoS attacks from certificates it is more useful to limit the amount of bytes of the entire certificate. It's not very efficient to limit each and every component within the certificate.

When programming in C/unmanaged C++ it is more reasonable to bother about ASN.1 based buffer overruns; those are common enough and extremely dangerous.


How much of Probability do I need to know to study Cryptography? I have just started MSc in Computer Security. I didn't study probability before. Now, I have some short time to complete my MSc semester.

What are the minimum topics from 'Probability' do I need to know to complete my Cryptography course?

Not much. All you need can be found in any "Intro. to cryptography" book such as Katz/Lindell. In particular, you don't need any of the fancy measure-theoretic stuff since in cryptography you only work with discrete distributions.


Is there a formal language to define a cryptographic protocol? I wanted to work on a personal project where I would attempt to identify the flaws in a cryptographic protocol. Now for that to work properly, the program should understand the syntax of protocol definition (if any). So I wanted to know if there is any formal language to define a cryptographic protocol.
I found a paper but I don't know if everyone actually follows this or not.

Disclaimer: I use Coq on daily basis...

About the tools

As you are looking for a formal verification, I would advise you to take a look at Coq. Even though mainly used by Academics, it provides a logical framework and an interface to write formal and interactive proofs.

Based this language there exists some libraries dedicated to cryptographic proof :

CertiCrypt
EasyCrypt (tutorial)

Example of proof :

Full Proof Cryptography: Verifiable Compilation of Efficient Zero-Knowledge Protocols
Formal certification of ElGamal encryption

PHD : Formal certification of game-based cryptographic proofs

Other formal tools (interactive provers) can be used such as Isabelle, Agda, Fstar and HOL.
And some more readings :

Computer Verification in Cryptography
Probabilistic Relational Verification for Cryptographic Implementations

As Mikeazo said, Cryptol might be an other possibility, but I can't say more on it.

About the formalizations

I would also suggest you to have a look at the $\pi$-calculus which is mainly used to explore the verification of concurrent programs, but could be applied in the case of protocols.

Because most of those proofs are game based, one of the notion applied in this case is probabilistic couplings.

Some interesting readings:

Introduction to Symbolic Verification Methods, David Basin, ETH Zurich
Computer-aided cryptographic proofs, Gilles Barthe, IMDEA
Human Errors in Security Protocols, David Basin, ETH Zurich

Given the nature of your project, I would strongly recommend you to have a look at the works of David Basin as they have a software that seems to do what you intend to work on (from what I recall).


Is it safer to use timestamp in REST authentication? I am working on a personal project to build a REST authentication system which authenticate clients via three parameters:

apikey = example-apikey-34433
hash = examplehash-notarealhash-a34io4oehosseesr
timestamp = 2000000000

Every client has a unique apikey and secret key, stored in a database.

Hash is a SHA256 hash of the secret key + timestamp. This is to generate a unique authentication hash for every request.

Would this be secure against brute forcing? Because when a client can supply any timestamp, is it true that multiple hashes can be correct?

Wouldn't it be better to just rely on the apikey and (plain text) secret key? Or do you know a better way to do this?

Might need some clarification, but it sounds like you are wondering how to 'salt' the hash. First if you intend to concatenate the secret key with anything else, the standard way to handle this is a HMAC. A common way to handle this is PBKDF2:

https://en.wikipedia.org/wiki/PBKDF2

Basically this does a secure combination of secret codes and the timestamp/salt. While the user can supply the timestamp, the probability that they could guess a timestamp that gives the same hash is very unlikely.

So PBKDF2 with a timestamp salt may be what you're looking for. Good Luck!


How is it possible to define differential privacy on two databases that differ more than a single entry? The original definition of $\epsilon-$differential privacy is for two databases $D_1$, $D_2$ that differ at most one entry and an randomized algorithm $A$.

We have a bound on the probability ratio
$\frac{Pr[A(D_1) \in S]}{Pr[A(D_2) \in S]} \leq e^\epsilon$ where $S$ is subset of range of $A$.

How do we define such thing for two databases that differ more than one entry?

One of the advantages of differential privacy is composition. That is, if $D_1$ and $D_k$ differ on $k$ entries, then $k\cdot\epsilon$ differential privacy is achieved. This is easily shown by writing a series of equations. Specifically, let $D_1$ and $D_k$ differ on $k$ entries, and let $D_i$ be a database that differs from $D_{i-1}$ on one entry (for $i=2,...,k$). Then,
$$
\frac{\Pr[A(D_1)\in S]}{\Pr[A(D_k)\in S]} = \frac{\Pr[A(D_1)\in S]}{\Pr[A(D_2)\in S]} \cdot \frac{\Pr[A(D_2)\in S]}{\Pr[A(D_3)\in S]}\cdots \frac{\Pr[A(D_{k-1})\in S]}{\Pr[A(D_k)\in S]} \leq (e^\epsilon)^k = e^{k\cdot\epsilon}
$$
where each
$$
\frac{\Pr[A(D_{i-1})\in S]}{\Pr[A(D_i)\in S]} \leq e^\epsilon
$$
by the assumption of differential privacy for databases that differ on a single entry.


Building a combined encryption scheme from two encryption schemes that's secure if at least on of them is secure Any thoughts on how this can be done?

  Let $\Pi_1 = (\mathrm{Gen}_1, \mathrm{Enc}_1, \mathrm{Dec}_1)$ and $\Pi_2 = (\mathrm{Gen}_2, \mathrm{Enc}_2, \mathrm{Dec}_2)$ be two encryption schemes for which it is known that at least one is CPA-secure. The problem is that you don't know which one is CPA-secure and which one may not be. Show how to construct an encryption scheme $\Pi$ that is guaranteed to be CPA-secure as long as at least one of $\Pi_1$ or $\Pi_2$ is CPA-secure.

Problem 3.21 - Jonathan Katz, Yehuda Lindell - Introduction to Modern Cryptography: Principles and Protocols.

You can generate a random string $s_1$ as long as the plaintext. Then XOR this value with the plaintext generating $s_2$. Now encrypt both parts using $\mathrm{Enc}_1$ and $\mathrm{Enc}_2$. You need to decrypt both to XOR the two parts together again. This is similar to secret sharing where you need two parts of a key to decrypt.

If $\mathrm{Gen}_1$ and $\mathrm{Gen}_2$ are two random generators then you may want to XOR those together as well when generating $s_1$. I presume however that they are used to generate the secret keys.


What authentication techniques can be used by QKD Systems? As it is well known that QKD systems are prone to simple MITM attacks… what authentication techniques are being used in QKD to prevent those attacks in practice?

The standard answer in the research literature is to use information-theoretically secure message authentication codes, typically universal hashing (aka Carter-Wegman authenticators).  Of course, you could use computationally-secure message authentication codes, like CMAC or HMAC, if you wanted, though that would partly defeat one of the reasons for using QKD.

That said, in practice QKD is a bit silly.  QKD solves a problem that most people don't have, so it is basically a fancy useless toy (albeit a very expensive one).  If you're considering using QKD in some practical deployment, my advice is: skip the QKD, and just use a TLS or IPSec VPN.  There, I saved you $50,000; don't spend it all in one place!


Suggestion : CRC vs SHA1 I need some suggestions about the use of the CRC in my application. I need to be sure about the BIOS run by the CPU. I have a FPGA between the BIOS flash and the CPU that sniff every read performed by the CPU on the BIOS memory. The initial idea was to compute the SHA1 of the data stream to authenticate and to be sure about the correctness of the BIOS. The resulting digest is stored inside the bitstream of the FPGA. Is it enough safe to use the CRC in this application ?

No, it is not safe to authenticate the BIOS in that way. CRC should be used as checksum only, i.e. to avoid random bit flips. For larger random changes you should use CRC32 at the minimum.

If you want to protect against malicious change you need a cryptographically secure hash. the reason for this is that any attacker can create a malicious BIOS that calculates to a particular CRC.

SHA-1 is under attack although it is not broken yet. If it is broken, it will be broken exactly for the purpose you are using the hash though. So it is better to upgrade to SHA-256 and/or SHA-512 (whichever is faster on your machine).

Note that cryptographic hash functions do not take a key. So for authentication you need additional measures. You could rely on signature generation (e.g. PKCS#1 v1.5 padding + modular exponentiation for RSA) or - for symmetric keys - a HMAC. Both of these rely on an underlying hash function for security. With HMAC you could use SHA-1 by the way.

As lightweight software hash Blake2b is often mentioned here, but this requires a bigger understanding of hash functions. If possible stay with SHA-2.


How to achieve identity authentication without revealing credentials I am looking at a scenario where I would like to claim to an authority (call it A) that I am indeed me without revealing my identity documents. I am guessing some zero knowledge protocol has to be used. We can assume a trusted authority where I will show my identity documents for authentication. But I do not want A to know these details. I also do not want A to be able to collude  with the trusted authority and gain information about my identity. What are the possible schemes/areas I should be looking at?
From some reading I see that there is a Brands scheme and pairing based crypto schemes. One is interactive and the other noninteractive. Are there any other differences? Are there other schemes?

The primitive you are looking at is called anonymous credentials. It deals exactly with your scenario, and there are dozen of papers on the subject. The introduction of this paper provides plenty of references to the literature on this subject.


Sigma protocol ZK-proof of a pair of pedersen commitments Let's say you are using a $\Sigma$ protocol ZK proof to prove knowledge of $x_1, x_2$ so that $Y = g_1^{x_1}g_2^{x_2}$. Of course $g_1$, $g_2$ are generators within cyclic group G of prime order q, with q of sufficient size.

My question is, if $z = dlog_{g_1}g_2$ is known to the prover, how would that affect the soundness of the proof? If the value of z is known to the verifier, how would that affect honest-verifier z-k property?

Intuitively it seems like knowing z would break things, but I don't see how.

The important thing to understand is that if the prover knows such a $z$, then the commitment is not binding. In particular, for any $Y$ and any $x_1'$ it can find $x_2'$ such that $Y=g_1^{x_1'}\cdot g_2^{x_2'}$. Thus, it can open the commitment to any $x_1'$ it likes. As such, it can also prove knowledge of any $x'_1,x'_2$ it wishes. This does not break soundness, since it indeed knows such an $x'_1,x'_2$ and so everything is true.

If $z$ is known to the verifier, then this actually makes no difference, because Pedersen is a perfectly hiding commitment.

In general, you should study more about Pedersen commitments, and then understand the $\Sigma$ protocol issue.


XOR and cipher stream I am new to cryptography and I am very confused. In fact, I am so confused that I have trouble providing a suitable title for my thread...

I know that a Substitution Cipher is designed to substitute one letter or character for another, to produce a ciphertext as shown in the picture below

With most symmetric cipher, the final step is to combine the cipher stream with the plaintext to create a ciphertext using XOR binary logic encryption.

My question is

why is the plain text, cipher stream and cipher text all in binary?
In the first picture, it is all in letters, now in the second picture, it is all in binary.
Where does the single key from the symmetric cryptography take place?

For #1, binary is used for a number of reasons. First, XOR is a logical operator, so it only operates on bits. Modern computers store everything as bits, too, so that makes XOR convenient.

As for why the first picture is not in bits, that is because no one uses (or at least should) use substitution ciphers such as the one proposed on modern computers. That substitution cipher is extremely insecure. Those sorts of ciphers were typically seen in the pre-computing age, so showing it with an alphabet instead of in bits makes sense. You could, however, show the same graphic with binary text. You'd first have to break up the binary into groups of values (maybe 4 or 5 bits per group) and show a substitution table for the 4 bit values.

For #2, the key is used to produce the cipher stream. That is not shown in the picture.


What effect does a salt have on attacks against hashes's fundamental properties? I am interested in analyzing how adding a salt to our hashed passwords affects the three types of attacks we can use. The three types of attacks against hashes are as follows:

We have the hashed output and we are looking for a matching input (pre-image).
We have an input (and implicitly the output) and we want to find another matching input (second pre-image).
We have the input and we want to find ANY output (collision).

My thought is that the addition of a salt to our output would only affect our ability to perform attack 1, because we are reliant upon the output to find a matching input. With the salt, our chances of finding a matching input becomes almost impossible because we have to check each output with every possible salt. Essentially, attack 1 is what's known as using a rainbow table.

I'm no security expert but I'll take a stab at this since it hasn't been answered.
Also, I'm answering as if you're asking about a Rainbow table or Dictionary attack for preimage and second-premiage attacks. Preimage being the rainbow table attack and second-preimage relating to getting similar encrypted values (cipher text) from the same password.
If you actually mean preimage and second-preimage, these attacks have nothing to do with password protection and more to do with the hashing algorithm's robustness.
Basic Salting Info
In the most basic sense, salting increases the amount of time and effort needed to crack passwords.
Salts are:

Unique
Random (GUIDs are not necessarily random. Look up CSPRNG)
Public (at least, it doesn't need to be a secret)

Also, make your salts robust. This doesn't mean that the password should be weak. The password itself should also be robust.
How Salting Effects Hacks
Unique salts ensure the same password will be hashed to a different cipher text.
Attack 1: Salting will increase the time needed to find other user's passwords. Because, the attacker would need to create a Rainbow Table for every salt used because salts change the output in unpredictable ways. Cracking the hash for one user wouldn't be much harder but cracking the hash for all users would be exponentially harder (I'm not sure if that's literally exponentially harder or if it just seems that way).
Attack 2: If the salts are unique then there is no matching input (idealistically. I know there's collisions). So, if you know the plain text (and salt) for one user, then that doesn't mean you'll know the cipher text for all other users with that password.
Side Note: I suppose if you had the whole database and knew every salt that was used then you could hash the known password against all the known salts and compare all of those hashes to all the values in the database. However, this is still a win for salting because that takes more time then being able to query the database with one value. Also, I think key stretching can be used to increase the amount of time needed to hash while increasing the entropy of the algorithm. All of these little things make it that much more impractical to try and decrypt large databases.
Attack 3: I don't think you need to worry about collision attacks. In a collision attack, the attacker is in control of the input. An example, the attacker presents Document 1 to Person A to sign. Person A signs it. Then the attacker puts Person A's signature on Document 2 and gives it to Person B. I think this mostly has to do with TLS (SSL) security. Salting has no explicit effect on a collision attack.
Conclusion
Salting will make Attack 1 and Attack 2 more difficult to complete by increasing the amount of time and/or resources needed to execute the attack. This is assuming the attacker is hacking to get information for many users as oppose to just one.
Don't forget, strong salts should be used in conjunction with strong passwords.


Keyspace in truncated MD5 hash? I have identified a password hashing algorithm that uses a truncated MD5 hash to compare user passwords.

This means that any password whose hash matches the same first 23 hex chars (11.5 bytes or 92 bits) will authenticate the user.

How big is this keyspace? I believe it is 2^92 which is still quite a large key space to bruteforce a valid password for.

Yes, given a random 92-bit string, you will on average need to perform $2^{92}$ MD5 calculations to find a password whose MD5 hash begins with that 92-bit string.

However, if the passwords are not salted before they're hashed, then attacking multiple password hashes in parallel is only slightly less efficient than attacking one hash.  Indeed, if you only care about finding one of the passwords, having $n$ different hashes to target actually makes the attack about $n$ times faster.

Also, if the passwords are chosen by users, simply generating and testing strings that resemble common password choices will likely turn up the correct password in far less than $2^{92}$ attempts.  While it's possible to generate and memorize a password with 92 bits of entropy*, few people will actually take the time to do that.

(If the hashing scheme is indeed just plain (truncated) MD5, you may also be able to just look up the prefixes in a precomputed table of MD5 hashes of common passwords, several of which can be found online.)

This, not the size of the theoretical keyspace, is the reason for the recommendation to use a key-stretching KDF (like PBKDF2 or scrypt or Argon2) for password hashing.  Basically, it doesn't really matter if the hashes are 92 or 128 or 256 or 512 bits long, if the passwords they're computed from only have less than 30 bits of entropy.

*) For example, a seven word Diceware passphrase would have a little over 90 bits of entropy, while adding an eighth word would push it well over 100 bits.


Can we use higher strength SHA along with lower strength RSA key in SSL? I have noticed when the RSA public key is 2048 bit, SHA-256 bit used for signatures. When the key is 3072 bit, SHA-384 bit used.  When the key is 4096 bit, SHA-512 bit used.

I have tried the following commands.

openssl genrsa -out my.key 2048
openssl req -new -sha512 -key my.key -out my.csr

It worked without any errors.

My question is that, will there be any issues when the SHA-512 is used with 2048 bit?

In general, no, there is no security problem with using overkill that fits in your budget.

Maybe there are constraints in your application or protocol that would prevent you from using SHA-512 with 2048-bit RSA moduli, but we can't say without more details about your application or protocol.


What are the pros and cons of deterministic site-specific password generation from a master pass? I've been reading up a bit on deterministic password generators. All the ones I can find basically do something like this:

Pick a master username and a master passphrase. The username could be your email, or a PIN, or something else. The master passphrase can be subject to stringent requirements to ensure sufficient entropy. The combination of these two factors needs to be ultra-secure and something you're reasonably certain that nobody's ever used before.
Enter the site name that you want a password for.
Generate the string $H^n\text{(passphrase||username||sitename})$, where $H^n(\cdots)$ is an n-fold iteration of SHA256 or some other sufficiently secure hashing algorithm and $||$ is string concatenation.
Make sure that n is sufficiently large such that n iterations of the hash generates a substantial amount of work and protects against brute-forcing.
Do a final deterministic mapping from this last string down to an n-character string where the individual chars of the string are in some set of "valid" characters (alphanumeric, alphanumeric+symbols, etc).

There are variations on the above, but that seems to be the basic idea.

Now, I'm curious how secure and trustworthy an algorithm like this really is compared to existing password managers.

For existing password managers, you have the same basic weakness - if your user+master pass is compromised, all of your passwords are also compromised. But does this system have any additional weakness on top of that?

It seems as though it'd be fairly resistant to the obvious things:
- If your plaintext pass for one site is compromised, it'd be very difficult to work out your pass for another site.

Furthermore, due to the fact that the hash function is iterated a sufficient number of times, it'd be difficult to brute force.
The best way to attack this seems to be a rainbow table approach with a bunch of common master usernames, master passphrases, and site names, but so long as your username+passphrase is of sufficient entropy, that'd be difficult to pull off.
Furthermore, if you want extra security for a certain site, you can increase the entropy of the sitename field a bit (example: eBay becomes 3b4Y@!#$% or something).

Seems reasonably secure, but I don't know if I'm missing something. Is there some well-known weakness with this system?

The above scheme does have a very important drawback against schemes that encrypt a password store. If you randomly generate the site  specific passwords then there is no relation to the master password. You would need the complete password store to perform e.g. dictionary attacks to find the master password. This is not true for the deterministic password generator you've described; one single leaked site specific password would enable an attacker to launch an attack on the master password. In the following two paragraphs I'll focus on the security without regard of this observation.

It seems that the scheme above is just an application of a Password Based Key Derivation Scheme (PBKDF), coupled with a deterministic method of mapping the result to a new password in step 5. As long as step 5 only maps to an array of characters in a specific alphabet without loosing entropy, the security of the scheme depends on the PBKDF used. KDF's commonly already include parameters specific to the secret that is to be generated (in this case that would be the site name).

So for the security of the scheme you should simply study security of PBKDF's and - if possible - the security of the specific PBKDF that is being used. Maybe you can compare the scheme against well known variants like PBKDF1, PBKDF2, bcrypt, scrypt or e.g. the proprietary OpenSSL PBKDF.