In "Lecture Notes on Cryptography" what does "PTM" mean? I came across a handbook named "Lecture Notes on Cryptography" from Shafi Goldwasser and Mihir Bellare and I read their definition 3.1 about poly-time indistinguishability:

  Let $X_n,Y_n$ be probability distributions on $\{0,1\}^n$ (That is, by $t\in X_n$ we mean that $t\in\{0,1\}^n$
  and it is selected according to the distribution $X_n$).

  We say that $\{X_n\}$ is poly-time indistinguishable from
  $\{Y_n\}$ if $\forall \text{PTM } A, \forall \text{polynomial } Q, \exists n_0, \text{s.t. } \forall n>n_0$,

  $$\left|\Pr_{t\in X_n}(A(t)=1)-\Pr_{t\in Y_n}(A(t)=1)\right|<\frac1{Q(n)}$$

What I don't understand is what "PTM" means, can you please explain it to me?

As pointed out by hakoja in the comments:

  It means Probabilistic Turing Machine, see Section B.2.1.

where the following is written (emphasis mine, this is the full section B.2.1):

  Let $M$ denote a probabilistic Turing machine (PTM). $M(x)$ will denote a
  probability space of the outcome of $M$ during its run on $x$. The
  statement $z\in M(x)$ indicates that $z$ was output by $M$ when running on
  input $x$. $\Pr[M(x) = z]$ is the probability of $z$ being the output of $M$ on
  input $x$ (where the probability is taken over the possible internal
  coin tosses made by $M$ during its execution). $M(x; y)$ will denote the
  outcome of $M$ on input $x$ when internal coin tosses are $y$.


DSA authenticity/integrity Does checking sig with DSA implies both that the sender is verified , and the msg is original without change of any bit?
(case i dont have a reference HASH for that file, only public key)

If you know the sender's verification key previously: Yes, it does prove the authenticity and integrity of that message. No one else could have created a matching signature - for any message under that public key.

As a side note: hashes of files are in theory a good idea to check that it was not changed. But when you get the hash from the same source as the file itself (e.g. the webserver offering a file for download), then that's utterly worthless. Anyone able to manipulate the file can also just replace the hash (doesn't matter if he has access to the file server or if it's a man-in-the-middle attack).


What's up with unnamed elliptic curves in e-passports? At my work I deal with the cryptographic aspects of the international E-Passport specification (the crypto chips embedded in your passports, the kiosks at airports that talk to them, and the certificate authorities that issue their certs).

The relevant standards document is BSI TR-03110-3.

Section A.2.1.1. Standardized Domain Parameters provides a list of NIST and Brainpool curves that are allowed. Cool. Section A.2.1.2. Explicit Domain Parameters provides a mechanism for you to use any domain parameters you want.

My question is: Are they on drugs? Coming up with safe domain parameters is non-trivial. I suppose some countries' passport offices have cryptographers on staff who know what to look for in parameter generation, but not all. That seems like an awful lot of rope to hang yourself with for no real gain. Can anyone shed more light on why they would allow this?

I don't have any visibility into the BSI standardization process, and so this is a guess; I suspect one of two things happened:

This is a potential way to deal with someone figuring out how to break both Brainpool and NIST curves (but not arbitrary elliptic curves; if they managed that, this hook won't help).  In that case, if someone did that (or if we suspect they might have), we can update the passports without modifying the spec or the readers.
This is a political compromise; some entity with political power pushed it into the BSI spec; possibly because they were card manufacturers that were already using other curves (and BSI decided they didn't want to endorse those curves for whatever reason); possibly because it gave someone a competitive advantage (our password validation equipment does it, our competitor's does not; forcing this in will delay our competitor) or possibly because some bureaucrat got it into their head that this was a good idea.

As for whether coming up with safe domain parameters is non-trivial, well, yeah, it's not something you'd want to hand off to an intern; however the known potential attacks against elliptic curves are well documented; it's not that difficult for someone who knows what they're doing to come up with curve parameters that make all known attacks infeasible.  In fact, there's this paper where they suggest literally creating a fresh elliptic curve for every single key exchange.


Confused by the definition of Linear Complexity of an LFSR sequence? The Linear Complexity of a sequence is defined as the length of the shortest LFSR that produces this sequence. It also corresponds to the degree of the minimal polynomial ( i.e. the smallest reccurence produce the sequence) of the sequence.

Now consider the sequence {0,1} the degree of the minimal polynomial is equal to 1 therefore the LC must be equal to 1, but we need an LFSR of length 2 including both 0,1 (an arrow going out from stage 0 box, to backward feedback itself). No need a  connection coefficient for stage 1 box. Thus LC is equal to 2 according to this definition.

So there must be a problem in the definition of LC being equal to the length of smallest LFSR? It looks like if the definition would be the "length of the LFSR for the periodic part or nondegenerate part of the sequence" then the two definitions would coincide.

Which definition is correct? What is the Linear Complexity of this sequence; 1 or 2, and why?

By the way both definitions are from Rueppel's book.

Length 2: one tap at the rightmost cell, going back into the left side without further additions. Starting with initial filling $01$ we get the sequence $101010\ldots$. The same sequence can also be achieved with two taps on both cells and the xor of them going in the left and the same initial filling. With register length $1$ only constant sequences are possible in Rueppel's definition: I don't think he even really considers such trivial cases.

So (10)* has linear complexity 2.


Can a message be encrypted with BOTH mono-alpha and poly-alpha ciphers? For my class assignment, I was given this text;

  Qpuvu vo vv stazpuykzh Hhycmlmv asb. Ad dhyaqva wh uyo uzb jpwww Avlw.
  Tkpjllfdmbp zoatz vzjavfvna ZLHqh. Amva luy yyvlz yu bhk zua zlhvvalaz
  yow llh uldu llzy yzlvao. Hzk caslyv kfzounf zayy sh pvsv. Uopz ala
  yrvhbhm tk ppp Thlll jya. Blz o bblw tol Lsjay hba ljw oro lp nta
  avlnktn.

There is more than one cipher method used, with one of their keys being 'ANNIE'

POSSIBLE METHODS: Caesar, Vigenère, One-Time Pad, Columnar Transposition, Railfence Transposition...

Using Cryptool 1 to analyze the histogram, I figured out that there's a Caesar shift 7 cipher, which decodes the text to:

  Jinon oh oo lmtsinrdsa Aarvfefo tlu. Tw wartjot pa nrh nsu cippp Toep.
  Mdiceeywfui shtms osctoyogt SEAja. Tfot enr rroes rn uad snt seaootets
  rhp eea newn eesr rseoth. Asd vtlero dyshngy strr la iolo. Nhis tet
  rkoauaf md iii Maeee crt. Ues h uuep mhe Elctr aut ecp hkh ei gmt
  toegdmg.

I figured out the plaintext by using columnar transposition through a website.

  jamesisanundercoverinterpolcophereportstoouroldenemysuptshamshuddinusingencryptedsmsestheyareawareofallouractivitesforthelastfourmonthsthepolicesuspectthatweknowtheyareworkingtogetjamesoutsetatrapforjamesandgetridofhimtonight

Is there a way I can explain why it couldn't have been Vigenère or a one-time pad? Is my assumption that a mono substitution cipher cannot be combined with a poly substitution cipher correct?

I'm assuming that your Columnar Transposition Cipher (CTC) is as described as this site, since I found that the keyword ANNIE works.

OTP

First of all, the combined cipher (Caesar shift 7 plus CTC) can always be the OTP, as long as we don't require a truly random OTP. The simple reason; x-or the plaintext and ciphertext get the OTP keystream.

This is your OTP key;

  zpgzmdgvimgddgwmfdypurgdaagcgqhhulnohospvisfikencaiuspaplrpvdszgpjctgigfzmlrtuordrxzuzttzyllcyuvcdmzbsvnorznadqieerdcneslflvnqztpknyohgagorodtazczrdypyshyrolzigrnvtxaceufmrjusmyvtichxpdxsttpsousllyccusveqhodrnpfzrzuubmtjyvqag

And if you asked if OTP can replace the CTC, the answer yes again with the key;

  sizsfwzobfzwwzpfywrinkzwttzvzjaaneghahlioblybdxgvtbnlitiekiowlszicvmzbzysfekmnhkwkqsnsmmsreevrnovwfsuloghksgtwjbxxkwvgxleyeogjsmidgrhaztzhkhwmtsvskwrirlarkhesbzkgomqtvxnyfkcnlfrombvaqiwqlmmilhnleervvnloxjahwkgiysksnnufmcrojtz

Vigenère

In the Vigenère cipher, the password only affects $\operatorname{StrLen}(\text{password})$ characters whereas the CTC distributes the plaintexts implies they are not equal ciphers.

Note: If Vigenère is equal to CTC then the security will be the same as CTC.

Note: there may be a collision that is for some plaintexts a Vigenère Cipher will produce the same ciphertext as a CTC. This will have very low probability, and generating one is an interesting question.


How secure is a blind signature? From Wikipedia:

  Blind signatures can also be used to provide unlinkability, which
  prevents the signer from linking the blinded message it signs to a
  later un-blinded version that it may be called upon to verify. In this
  case, the signer's response is first "un-blinded" prior to
  verification in such a way that the signature remains valid for the
  un-blinded message.

This is a useful feature, no doubt.  Continuing on the Wikipedia article, it considers message $m$ and blinded message $m'$, and states that:

$$m' \equiv mr^{e} \pmod N$$

Which means that the $r^e  \pmod N$ part is what keeps the message a secret from the signing party.

How hard would it be for a signing party to link blind messages to later revealed un-blinded versions, by keeping a log of blinded messages that they sign.  The Wikipedia article states that this is hard but does not specify why.  It does however specify that an attacker could possibly use a blinded signature to get signatures for something different than what was signed, but that this could be mitigated by signing a hash instead.  Wouldn't that break the unlinkability, as explained in this accepted answer?

How hard would it be for a signing party to link blind messages to later revealed un-blinded versions, by keeping a log of blinded messages that they sign.

Assuming that the $r$ values are chosen uniformly from the values $[1, N-1]$ relatively prime to $N$ (and kept secret, for example, zeroized after use), and none of the $m$ values are relatively prime to $N$, then it's impossible to link them later (and this does not rely on a computational assumption, but an informational one).

For any such array of possible messages $m_1, m_2, ... m_n$ in any order, and blinded messages $m'_1, m'_2, ..., m'_n$, there is a unique set of values $r_1, r_2, ..., r_n$ with $m'_i \equiv m_ir_i^e$.  No set of values $r_1, r_2, ..., r_n$ are any more probably than any other, hence the server gets no information whether $m_1$ corresponds to $m'_1$ or $m'_2$ (or, for that matter, whether it was one of the values signed at all)

  It does however specify that an attacker could possibly use a blinded signature to get signatures for something different than what was signed

What the Wikipedia article is worrying about is that the attacker can do other things with the 'blinded signature' facility other than signing messages.  For example, if the RSA key is also used to encrypt messages, then the attacker could ask for a 'blinded signature', but instead decrypt a message.  This blinded signature method really is an oracle to the RSA private operation, and there is no easy way to limit it to only generating signatures.

  Wouldn't (signing a hash) break the unlinkability?

Yes (unless you do a lot of work with zero knowledge proofs).  This simple blinded signature scheme relies on the idea that the server gets no information on the message being signed; once you give it some, things start being linkable.  This could be worked around, however it's probably be easiest to use this RSA key for nothing other than signatures (and so there's nothing an attacker can do with the RSA oracle, other than generating signatures).


Calculating ECDSA m or k (k or d) when s1 = s2 I recently began to look into some information about obtaining the private key $k$ when two signatures have been produced using the same $m$ and $k$.
I've been using the well-publicised information about how the Sony PS3 private key was leaked, where:
$$m = \frac{e_1 - e_2}{s_1 - s_2}$$
$$k = \frac{e_1s_2 - e_2s_1}{R(s_1 - s_2)}$$
This has worked well and I've managed to use it to calculate $k$ (private key) in a few situations successfully.
However, I'm confused by what I should do with two different signatures ($e_1 \neq e_2$) with the same $s_1$ and $s_2$, because when I calculate $m$ or $k$ I get:
$$m = \frac{e_1 - e_2}{0}$$
$$k = \frac{e_1s_2 - e_2s_1}{R(0)}$$
Is there a way to calculate $m$ or $k$ in the situation where $s_1 - s_2 = 0$?

However, I'm confused by what I should do with two different messages ($e_1 \ne e_2$) with the same $s_1$ and $s_2$

Well, if we consider how $s$ is computed:
$$s_i = m^{-1} ( \text{hash}(e_i) + r \cdot k )$$
If $s_1 = s_2$, then (because the private key $k$ is the same in both cases, and $m$ (the secret nonce) and $r$ are assumed to be the same, we have $\text{hash}(e_1) = \text{hash}(e_2)$
If $e_1 \ne e_2$, that means that we have a hash collision on our hands; because the signature depends on the hash of the message (and nothing else about the message), that means that (as far as ECDSA is concerned) we're signing the same message twice, and so the attack isn't possible.


AUTHENTICATE MERKLE TREE: In the passage below how is A able to confirm YB in the public file only knowing R, log2 intermediate values, and YB itself? "If A wishes to confirm B's public
enciphering key, then A need only know
the first half of the public file,
(which is where YB appears) and H(second
half of public file) which is only 100
bits long. A can compute H(public file)
knowing only this information, and yet A
only knew half the entries in the public
file.
In a similar fashion, A does not
really need to know all of the first
half of the public file, for
H(first half of public file) =
F( H(first quarter of public file),
H(second quarter of public file)
All A needs to know is the first quarter
of the public file (which has YB), and
H(second quarter of public file).
By applying this concept recursively,
A can confirm YB in the public file
knowing only R, log 2 n intermediate
values, and YB itself. The information
needed to authenticate YB, given that R
has already been authenticated, lies
along the path from R to YB and will be
called the authentication path.

Alright past Ben listen up. What you are describing here is Tree Authentication ya dingus. Read a book once in a while - get some sun. To be fair to you it wasn't as well explained in "PROTOCOLS FOR PUBLIC KEY CRYPTOSYSTEMS," you had to read Merkle's Thesis, "SECRECY, AUTHENTICATION, AND
PUBLIC KEY SYSTEMS"... pages 41, 41a, 41b, and 42.

Initial Values & Assumptions:

YB = Y5

Log2 Intermediate Values = H(6,6,Y), H(7,8,Y), and H(1,4,Y)...these values are your authentication path

R (Merkle Root) = H(1,8,Y)

GOAL: Only use these initial values to get to the Merkle Root!

"Therefore, to authenticate
Y5 required only that we have previously authenticated
H(1,8,Y), and that we transmit Y5, H(6,6,Y), H(7,8,Y),
and H(1,4,Y). That is, we require 100 log2 n bits of information
to authenticate an arbitrary Y ..."

If you hash Y5 the output is H(5,5,Y). We can now use our first log2 intermediate value. The first one circled is H(6,6,Y). If we concatenate H(5,5,Y) and H(6,6,Y) and hash them together the output is H(5,6,Y). Now let's use our second log2 intermediate value, which is H(7,8,Y). We can now concatenate H(5,6,Y) with H(7,8,Y) and hash them together which yields H(5,8,Y). For the grand finale, we use out last log2 intermediate value which is H(1,4,Y). If we concatenate H(5,8,Y) and H(1,4,Y) and hash them together we should get the Merkle Root, which is H(1,8,Y).

See ya soon future Ben.


Confusion on Private Information Retrieval by Keywords PIR protocols retrieve an item from the database without the server knowing which item it is. But classic CPIR(Computational PIR) or IT-PIR (Information Theoretic PIR) protocols requires the user to know the location address of the object to be retrieved.

Major work on retrieving by Keywords is done here and subsequently here extended for SQL databases. An excerpt for more context.

  For B+ tree indices, however, the client uses PIR to traverse the
  tree. Each block can hold some number m of keys, and at a block level,
  the B+ tree can be considered an m-ary tree. The client has already
  been sent the root block of the tree, which contains the top m keys.
  Using this information, the client can perform a single PIR block
  query to fetch one of the m blocks so referenced. It repeats this
  process until it reaches the leaves of the tree, at which point it
  fetches the required data with further PIR queries. The actual number
  of PIR queries depends on the height of the (balanced) tree, and the
  number of tuples in the result set. Traversals of B+ tree indices with
  our approach are oblivious in that they leak no information about
  nodes’ access pattern; we realize retrieval of a node’s data as a PIR
  operation over the data set of all nodes in the tree.

A more general approach is like below

  The main idea in all of our subsequent PERKY constructions is the
  following: the databases insert $s_1, s_2 .. s_n$ into a data
  structure which supports search operations on strings. The user
  conducts an oblivious walk on the data structure until either the word
  $w$ is found, or User is assured of the fact that $w$ is not one of
  $s_1, s_2 .. s_n$. Typically, a successful search yields an address
  which contains data pertaining to the keyword.
  A typical search in the data structure involves a sequence of operations, where each operation consists of fetching the contents of a word from memory, performing
  a  "local" computation, which depends on the keyword and the fetched
  contents, and either determining a new address based on the
  computation, or terminating the search (successfully or
  unsuccessfully). This sequence of operations can be viewed as a $walk$
  on the data structure. We now describe a general outline of
  transforming this walk into an oblivious walk on the data structure,
  namely a walk where each server gets no information on the walk (and,
  therefore, on the desired keyword itself). For the sake of simplicity,
  we assume that the data structure has a fixed $root$, a word with
  known address that is always accessed at the first operation
  (regardless of the sought keyword).

But either i don't understand it or it seems to be weak. If a $walk$ ends after two iterations then an adversary is pretty sure that the retrieved element is in first two iterations right ? Or how does PIR by keywords in general work? any simpler explanations ?

The solution proposed in this (dated) work is an overkill considering more recent works on the subject. The simplest PIR by keyword construction I could think of is the one based on distributed point functions (DPFs).
see https://cs.idc.ac.il/~elette/FunctionSecretSharing.pdf

Distributed point functions are a special case of function secret sharing (FSS).
FSS is a primitive that is analogous to secret sharing for functions. A dealer shares a function $f:X\to Y$ by sending two shares $f_0$ and $f_1$ to two participants $p_0$ and $p_1$. Given a value $x\in X$ and his share $f_i$, every participant $p_i$ can compute a value $f_i(x)$. We require security: share $f_i$ does not reveal any information about $f$, and correctness: for every two shares $f_0,f_1$ and a value $x$, it holds that $f_0(x)+f_1(x)=f(x)$.

DPFs are FSS schemes for the class of point functions. These are functions that evaluate zero on all inputs, except one.

Now, to perform PIR-by-keyword over a databse, assume that every record in the data is of the form $(t_i,x_i)$ (a tag and a value). When the client needs to retrieve a value with the tag (or keyword) $t$, he secretly shares the point function $f$ for which $f(t)=1$ and $f(t')=0$ for any $t'\neq t$. He sends each of the shares $f_0,f_1$ to one of the servers. Server $i$, in his turn, computes $x^{(i)}=\sum_{j=1}^N f_i(t_j)x_j$. It is easy to see that from the security of the DPF, the scheme is secure, and from its correctness, the client can compute $x:=x^{(0)}+x^{(1)}$.

The DPF scheme proposed in the work mentioned above costs $O(n)$ bits of communication when the keywords are of size $n$ bits.

Notice that this construction assumes the keywords are all distinct.


Why doesn't steganography increase the size of an uncompressed image? So I have this question. I downloaded a .BMP off google due to .BMPs being not compressed. Just a 1024x768 .BMP image which its size os of 2.25Mb. I put the image in a steganography application.. inserted hidden text within it, encrypted and everything. How come the resulting image (Steganographied Image) is still 2.25Mb in size? Isn't it supposed to get bigger?

If you consider the mechanics of embedding the image in it's simplest form, then all you do is repurpose some of the existing bits.  The following is a Wikipedia extract from an article on steganography:-

  For example, a 24-bit bitmap uses 8 bits to represent each of the three color values (red, green, and blue) of each pixel. The blue alone has $2^8{}{}$ different levels of blue intensity. The difference between 11111111 and 11111110 in the value for blue intensity is likely to be undetectable by the human eye. Therefore, the least significant bit can be used more or less undetectably for something else other than color information. If that is repeated for the green and the red elements of each pixel as well, it is possible to encode one letter of ASCII text for every three pixels.

which kinda looks like this:-

except that your message is encrypted.  So the image remains exactly the same size.

The issue facing you (and your software) is how many bits can you alter and remain unnoticed?  One certainly.  The above example uses two and the altered image looks similar.  Could you use three then?  Clearly seven bits would totally destroy the image and tip off the attackers. It's a balance between leveraging the unavoidable noise introduced by the image digitisation process, the artistic scene and how dangerously you like to live.

Generally the blue channel is the noisiest from a CMOS/CCD sensor point of view.  You might be able to inject additional bits into that channel without significant human detection.

Note: There are more advanced embedding methods that can alter the discrete cosine transform coefficients inside a JPEG file.  This allows JPEGs to hide messages that would otherwise be impossible in this lossy format. There's a pretty good summary of advanced methods within the introduction to Data hiding inside JPEG images with high resistance to steganalysis using a novel technique: DCT-M3.


Curve25519 vs "Million Dollar Curve" Quoting from the Million Dollar Curve website:

By using publicly verifiable randomness produced in February 2016 by many national lotteries from all around the world, we propose to generate a cryptographically secure elliptic curve for the ECDH cryptosystem as an alternative to the NIST P-256 and the Curve25519 curves.
[...]
Today most of elliptic-curve cryptography relies on the same set of curves: ANSSI FRP256v1, NIST P-256, NIST P-384, Curve25519, secp256k1, brainpoolP256t1, Curve1174 and a few others.
However, most of these curves parameters generation processes contain unjustified choices, specific constants or specific hash algorithms. [...]

I understand the concerns over how NIST generated their curve parameters, and this does seem like a better approach.  However, I didn't think Curve25519 had any suspicious constants or design decisions.  What exactly is the benefit of using the "Million Dollar Curve" over Curve25519 (if there is a benefit)?

It's not related to the possibility of backdoors in curve25519, no one thinks that curve25519 can have backdoors.
It's related to having a trusted procedure to generate publicly verifiable random numbers, which is an interesting thing to have, not only related to elliptic curves.

There is the need for a way to generate curves, any possible way is arbitrary.
You can lower the number of degree of freedom (see the bada55 paper), but at the end some choices need to be made and people can have different preferences.
These are not only related to the (unlikely) possibility of having backdoors but mostly related to more or less conservative options for curves.

For example, taking the case of curve25519,
Bernstein made some choices with Curve25519 with the purpose of achieving efficient implementation, particularly with the choice of the prime $2^{255}-19$, which is a pseudo-Mersenne prime, and it is not congruent to $3 \mod 4$, which is a very common choice as these primes allow an efficient square root calculation and a better cofactor for the twist curve(see "twist security" in 6.1 of the million dollar curve paper).
Basically he says that the curve is rigid because it is the fastest among those with a similar security level. But speed depends on implementations and platforms and one might wonder if this is a good way to measure rigidity.

His method doesn't allow for an algorithm to generate curves at arbitrary security levels, therefore some people might prefer to have a procedure, more than a curve, that they can trust. I think this is one of the advantages of the "million dollar curve" project.

Others have argued that having a prime whose bitsize is not a power of two is strange because it doesn't meet the usual definition of security level. In fact, in the common definition of security level, curve25519 doesn't meet the 128 bit security level, see this answer.

That is why, for example, Microsoft NUMS curves requires a prime of 256 bit for a 128 bit security level.

Others, again, tends to prefer random primes (e.g. Brainpool), and not  primes of special form. Random primes have some advantages (over pseudo-mersenne prime) when protection against side-channel is required, and are considered a more conservative choice (because they don't belong to a family they are not subject to some possible attack exploiting properties of that family. Not that such an attack exists on Elliptic Curves, but it exists for multiplicative groups).

I think it is an interesting project, but it's not going to replace curve25519 or P-256 in implementations or protocols.


Intuitive explanation for key exchange with public/private keys I want to teach some people about crypto basics, and one of the topic will be key exchange with a public and private keys.
The audience is made of people working in InfoSec, but mostly junior fresh out of school.
I am looking for a visual/experimental way to show how we can achieve key exchange with both parties having a public/private elements.
The best thing I found was the example with color being mixed:

I like it, but it only shows the use of 1 secret key, there's no concept of public key.
Also, color may not be as intuitive as I like because people tend to think you can unmix (even if we made the hypothesis we can't.) And a real-world experiment would probably get messy.
Is there another example that would relay on 2 elements from each sides?
I made some attempts with pieces of paper, but alas, nothing came out. I would need a transformation that can be done with 1 piece of paper, and that can only be undone with another. Perhaps someone have a bright idea here.
PS: I introduce the concept of public/private key with the padlock/key analogy, which is very good. However this just depicts a 1way transfert of data, it is not a key exchange.

I like it, but it only shows the use of 1 secret key, there's no concept of public key.

The exchanged "mixed colors" are the public keys in the scheme.

Also, color may not be as intuitive as I like because people tend to think you can unmix (even if we made the hypothesis we can't.) And a real-world experiment would probably get messy.

Sorry, but you will have to make some assumptions when performing analogies. And a real world experiment seems useless; if people don't get above analogy then they won't be able to understand key agreement.

Is there another example that would relay on 2 elements from each sides?

If you are relying on an audience that needs to perform work with their bare hands to understand an idea, then you've already lost, as they won't get analogies either. Some abstract thinking is required.


What type of hash functions provides non-malleability of hash digests? I want to use a hash function for commitments. I don't want an attacker to construct a commitment related to a previously published (but still unopened) commitment.

A simple deterministic commitment scheme Commit(x) = Hash (x) may be insecure, since I read some time ago that this attack is possible:

Given y = hash(x) , the attacker finds z so that z = hash(f(x)). Here f() might be the addition of a suffix to the message or any other mathematical transformation.

None of the three properties of hash functions (pre-image resistance, second pre-image resistance and collision resistance) prevents this attack to be feasible.

I find keyed MACs (Message Authentication Codes) more suited for commitments. Setting Commit(x) = MAC(k,x) and opening the commitment by publishing k and x seems to prevent the attack, but I found no literature on this topic.

I also found Something called perfectly one-way hash function (POWHF), but I found no simple practical example of such a construction.

Commitment functions should be at least hiding and binding, and in your case, you want non-malleable.

Using a hash function as a commitment does require addition assumptions on the hash that are not covered by (second) pre-image and collision resistance for both non-malleability (as you point out) and hiding: the hash can be assumed to not reveal the entire pre-image but partial leakage is not covered by pre-image assumptions. See section 1.3, "a false solution" in this paper.

Non-malleability with hash functions like SHA256 (based on Merkle-Damgaard) can be defeated with a length extension attack. If you commit to $x$ with $Hash(x)$ it is possible for me to commit to $x'=x\|a$ without knowing your $x$ (technically it is a padded version of $x$). If you reveal $x$ first, then I can reveal $x\|p$.

Using a MAC does not provide hiding as MACs are not designed with this property.

All of this said, in practice with a hash function like SHA256, it will likely function ok if you are committing to fixed length messages. This is not provable but no known malleability is known and the hiding property of SHA256 is thought to be sufficient.


More rounds after AES related key attack? In his blog Schneier discusses that there is a new related key attack on 10 rounds of AES-256 "Another attack can break a 10 round version of AES-256 in 245 time, but it uses a stronger type of related subkey attack".

My question is how many more rounds would they have to use to keep this security margin on AES (other then adding a hash to AES 256 key schedule)? And would NIST actually change the standard again to something more secure such as Serpent?

Consider the number of rounds broken out of the total rounds for the security margin.

My question is how many more rounds would they have to use to keep this security margin on AES (other then adding a hash to AES 256 key schedule)?

When AES was standardized, the best known attack (pdf, page 19) in terms of rounds broken was a related key attack that broke 9/14 rounds of AES-256. The best attack on AES-128 broke 7/10 rounds.

Currently, the best attacks (pdf, paywall) are actually on full round variants. It's just that those attacks are only very slightly better than brute force. If you assume those attacks do not apply to increased-round variants, you would get the same security margin of unbroken rounds by defining AES-128 with 13 rounds and AES-256 with 19 – or maybe 14 and 20 for nicer numbers and in case an extra round can be broken with current attacks.

However, "rounds broken" is a rather crude measure. The best practical attack (in terms of computational cost) at the time of standardization was on six rounds for all variants. Now there are at least related-key attacks of practical complexity on 10/14 rounds of AES-256.

Either way, something like 14/20 rounds for AES-128/256 might be a reasonable number if the standard was revised, but attacks are still far from practical.

  And would NIST actually change the standard again to something more secure such as Serpent?

I doubt they would just change it to another existing cipher. Serpent may have more of a security margin, but it has also seen less cryptanalysis at this point. More likely would be another competition for "AES-2", like the one for SHA-3. Existing ciphers might be submitted, of course, but new ciphers would also be considered.


which exponent to be used for RSA e =3 or 65537 for RSASSAPSS signature verification I have the public key and I dont know how to obtain Modulus and exponent. After referring stack overflow, I have used below command line to obtain e and M finally as mentioned below.

openssl.exe rsa -pubin -inform PEM -text -modulus < key1024_pub.pem

Public-Key: (1024 bit)

Modulus:
    00:c4:bd:2a:41:92:5a:a1:0b:98:07:81:96:4f:9b:
    bc:ae:15:f9:01:b3:1c:37:df:9f:a0:a2:ab:0f:96:
    8f:cb:79:1a:21:31:49:ce:17:30:63:8f:7b:d5:24:
    96:e2:03:11:f8:fd:c2:20:62:13:e1:a1:b6:cd:73:
    58:c1:f0:67:56:57:d7:e2:88:ce:94:0d:8f:aa:ee:
    49:ac:cd:f7:37:57:47:1d:e6:00:76:c7:c9:1a:bb:
    46:29:31:6e:79:97:6e:c1:46:ef:38:b7:c2:ac:13:
    d5:ec:e1:98:94:ce:59:6e:a8:30:fd:25:26:69:f8:
    12:17:6b:9a:68:41:f0:cb:c5

Exponent: 3 (0x3)

Modulus=C4BD2A41925AA10B980781964F9B
BCAE15F901B31C37DF9FA0A2AB0F968FCB79
1A213149CE1730638F7BD52496E20311F8FD
C2206213E1A1B6CD7358C1F0675657D7E288
CE940D8FAAEE49ACCDF73757471DE60076C7
C91ABB4629316E79976EC146EF38B7C2AC13
D5ECE19894CE596EA830FD252669F812176B
9A6841F0CBC5

But now I am confused now which exponent to use either e=3 or 65537 Since i read Public exponent e - 65537 is default for 1024 bits of RSA. Could someone help me which value to use?

Use the value of public exponent $e$ that came with the public key, here $e=3$ according to the question. Otherwise, signatures won't check.

Common RSA public exponents include $65537$ and $3$, and more generally the Fermat primes $2^{(2^k)}+1$ with $0\le k\le4$; and $37$ (used by Putty).

$e=3$ leads to the fastest RSA public key operation, because we can compute $x^3\bmod n$ as $((x\times x\bmod n)\times x\bmod n)$; more generally, when using $e=2^{(2^k)}+1$, the public key operation $x\to x^e\bmod n$ requires $2^k$ modular squarings and one modular multiplication.

Using $e=3$ is believed safe when used with good padding techniques (including signature per RSASSA-PSS as in the question), but $e=65537$ is recommended by many authorities and can sometime act as an effective patch (for example, it has the potential to save implementations of PKCS#1 v1.5 decryption from disaster by side channel leakage thru error codes or timing attacks; and faulty implementations of PKCS#1 v1.5 signature verification that incorrectly validate the padding).


Burmester Desmedt Key agreement. Is the division a floating point one or an integer one As I look upon Burmester Desmedt algorithm:

I notice that the intermediate key $K_i$ is getting calculated as:

$K_i=(k_{i+1}/k_{i-1})^{x_i} \mod p$

Thus I wonder wheher the division $k_{i+1}/k_{i-1}$ should result an integer of a floating point number.

Thus I wonder whether the division $k_{i+1}/k_{i-1}$ should result an integer of a floating point number.

An integer.

Specifically, this computation is done modulo $p$; that is, the result of this division is the value $d$ such that $d \cdot k_{i-1} \equiv k_{i+1} \pmod p$.

One way to find this $d$ is to compute the multiplicative inverse of $k_{i-1}$ modulo $p$ (for example, using the Extended Euclidean algorithm, and then multiply that inverse with $k_{i+1}$ (again, modulo $p$)


Are zero-knowledge proofs quantum-resistant? Are zero-knowledge proofs quantum-resistant?

There is no generic answer to this question. Zero-knowledge proof (ZKP) systems can be post-quantum secure, but they need not be. It all depends on the cryptography on which the security of the ZKP rests.
There exist ZKPs that only use collision-resistant hash functions and hence are plausibly post-quantum secure. The most well-known examples are those using the FRI protocol: Aurora, Fractal, and zk-Starks [*].
Other notable ZKPs like Bulletproofs or Groth16 rely on cryptographic assumptions (e.g. hardness of discrete log in elliptic curve groups) for which it is known they would be vulnerable to quantum attacks, if such attacks became practical.
[*] "zk-STARK" refers both to a security definition and to a particular family of FRI-based proof systems that satisfies it. The security definition does not mention post-quantum security, so it is the latter that is meant here.


Mixing Autokey with Regular Vignere It seems to me that cryptanalysis of the autokey cipher relies on patterns being found in key attempts, easy when it's English you're looking for, but how can you do this if you're just getting further cipher texts?

How would someone decrypt a plaintext enciphered with an ordinary vignere followed by an autokey cipher, where the two keys are 10-20 characters long and random?

Presumably any solution would rely on a computer, but I'd also be interested if there was a method that could be done by hand.

Thanks

It can still be done, because some letters of the English alphabet are used more often. Analyzing a ciphertext based on the frequency of appearance of some characters is fittingly called Frequency analysis.

This method of cryptanalysis gets better, the more ciphertext you have. If the plaintext is in English, then you would know, that the most frequently used letter would be "e".

Because the Vigenère cipher is quite an old method of encoding something it can be (and has been) broken relatively easy by hand. The security relies on the keylength and the "randomness" of the key. 10-20 random letters is actually pretty good, but with a very long ciphertext you can ultimately still break the Vigenère method.


Condensed ElGamal + AES In normal ElGamal encryption, the encrypted message is a pair (gb, gabM) - that is, the actual "encryption" is simply multiplication by the shared secret gab.
A common pattern with public-key encryption is to encrypt a symmetric key using PK, and then encode the actual message with the symmetric key.

It seems to me that you could simply use the shared secret gab as your symmetric key instead - so your pair would be (gb, AES(M, gab)).  (This looks extremely similar to agreeing on an AES key via Diffie-Hellman.)  This would take up less space, putting it on even footing with RSA + AES for a given key-/group-size.

So: has anybody heard of a scheme like this?  If so, does it have a name, and is it actually used?  As for why I'm interested:

Possible advantage: semantic security without DDH?

In normal ElGamal, we lose semantic security if we don't have DDH (given ga, gb and c, we can test whether c = gab).  AFAIU, this is because the message is encoded as E = gabM mod p, so you can divide by your suspected message (c = gabM/Mguess), and test whether it matches gab.

It seems to me that if we use gab to provide an AES key instead, then recovering a candidate c is equivalent to recovering an AES key from a plaintext/ciphertext pair.  I understand that AES is not susceptible to known-plaintext attacks, so does this mean we have semantic security even without DDH?

Possible advantage: easier generation of private keys?

With RSA, it takes a reasonable chunk of computational effort to generate a new public/private key pair (because you have to find a probably prime).  With ElGamal, it seems much easier, which means you could rotate your short-term keys much more often, without draining a low-power device.

The more often you rotate your short-term keys, the "better" your forward secrecy is.  (After all, if you rotated your keys so often that each one was only ever used once, then you're basically doing Diffie-Hellman, just re-ordered a bit.)

What you are envisioning has basically been standardized as the integrated encryption scheme being a hybrid encryption scheme providing message authenticity (IND-CCA security).


What makes RSA secure by using prime numbers? I am just learning about the RSA algorithm. Looking at the first two steps:

Choose two distinct prime numbers $p$ and $q$.
Compute $n = pq$.

I have some probably stupid questions:

Why do $p$ and $q$ have to be prime numbers? Why couldn't they be any integers or odd integers? Or does that break the whole algorithm?
Because prime numbers are rare in comparison to regular integers, does restricting the algorithm to only prime numbers reduce security? It would seem easier to find the private key if an attacker knows it's only going to be some prime number?

In order to generate a RSA key pair, you are to find a public exponent $e$ and a private exponent $d$ such that, for all $m \in \mathbb Z_n^*$, i.e. $m$ is relatively prime to $n$, $(m^e)^d \equiv m \pmod n$. It is a consequence of Euler's theorem that if $e, d$ satisfy the equation $ed \equiv 1 \pmod {\phi(n)}$, they are such a valid public/private exponent pair.

The fundamental theorem of arithmetic says that every integer has a factorization into powers of prime numbers that is unique to the integer, save for the order of the factors.

The definition of Euler's $\phi$ function is that $\phi(n)$ equals the number of integers less than $n$ and relatively prime to $n$. In order to determine this number, you have to know the factorization of $n$.

Consequently, if you select a number $n = pq$ where $p, q$ are both prime, you will have selected a number you can factor, but, if it is large enough, no one else can factor. The reason for this is because, using known factorization algorithms for arbitrary integers, the running time of such algorithms depends on the relative size of the second largest prime factor of the input. This means that given the public exponent $e$ only you can determine the private exponent $d$.

(Note: The hardness of performing the RSA private key operation $m \equiv c^d \mod n$ given only the public key $e, n$ as above, is known as the RSA problem, which hasn't been proved to be as hard as factoring the modulus. The best known method is however by factoring the modulus $n$ in order to determine $d$ given $e$.)

It also means that if you were to select $p, q$ just as odd integers, you would make it harder for yourself to find $\phi(n)$, while at the same time decreasing the relative size of the second largest prime factor, and thereby making it easier for everyone else to factor $n$. In fact, it would be as hard for you to factor $n$ as it would be for everyone else, so you would completely loose the trapdoor component of your scheme (if not making it completely infeasible to find a pair $e, d$).

Regarding your second question, for large $x$, the number of primes less than $x$ equals $\pi(x) \approx \frac x {log(x)}$. Hence, the number of primes roughly equal to $\sqrt n$ is, for large $n = pq$, large enough to make factorization algorithms faster than a brute force search. Besides, by the arithmetic theorem above, the adversary is really only interested in prime numbers anyway, so the question is moot.


What is the current security level of an algorithm? I was reading a paper of some years ago about a cryptography and a phrase got my attention.

  We want to ensure a security level of at least $2^{80}$

I know that $2^{80}$ was used as rule of thumb rule, that's probably why they wrote that sentence.

But reading this I think that $2^{100}$ may also be too low.
Considering for example the resource that a state like US can have what is a reasonable security level?

EDIT:
I'm considering only the security level for a bruteforce attack, other algorithm can have a solution that require less computational force.

First of all: The security and the length of the key depends on the system you use. So e.g. RSA needs longer keys than AES-256 does, to ensure the same security.

Second: The level of security depends on the application and how secure it has to be. A important point here is: How long should it be secure. There are still security systems in use, that can be broken in days. That's however no problem when the information only has to be secure for some minutes/hours.

This question / answer about algorithms used for SSH keys on the Information Security site might also help you.


Would SHA-1 be safe for certificates with short validity? There are articles floating around the topic of SHA-1 deprecation. The gist of it is that in (mostly) developing countries, people are still using mobile/computing devices that are 5 years old (or older) and do not support SHA-2. As a consequence, the deprecation of SHA-1 would result in their being "cut off from the Internet as we know it."

Yeah, there are many problems with this oversimplification, but here's some questions:

There are estimates that it would cost something in the ballpark of several hundred thousand US dollars to create a SHA-1 collision. But how much time does that take?
Depending on the answer to the first question, why not extend client and CA support for SHA-1, provided that certificate validity periods are simply shortened to 6 months?  3 months?  One?  This seems especially more feasible with the kind of automation LetsEncrypt offers.

In my view, there's nothing wrong with the SHA-1 algorithm. No one has "broken" or is coming close to "breaking" the algorithm per se.  It is just becoming computationally more feasible to overcome its cryptographic strength over the typical course of a certificate's validity period. So long as that's the case, although it may be no longer well suited for year-long (or multi-year) certificate validity periods, it's still technically safe to use in more limited applications. After all... all forms of encryption are about time, not about impenetrability.

Would this proposal sufficiently eliminate known risks to make SHA-1 safe to use on older devices?

The short answer is that no, the length of validity would not help in a major way.

First you have to consider how the attack on the collision resistance of SHA-1 applies to certificates. The idea, and how it actually worked in the case of MD5, is basically:

Attacker finds a collision in the hash function that generates two certificates with the same hash.
They give1 the innocent one to a CA for signing.
Now they also have a signature for the malicious one, that e.g. allows them to claim to be Google.

A validity period of months would still allow them to make use of it for months. That may be less of a return for the attacker's resources than using it for years, but you would expect such an attack to eventually be exposed anyway. And if, like poncho mentions in the comment, the attacker can generate a malicious certificate with a different period of validity, then even that is not an issue.

Now, if you think that in the next year or so no-one will be able to generate a collision due to the expense or time it takes, then you can argue that certificates should be allowed for an extra year. However, the validity period itself does not really matter in this case.

1 Actually, the CA typically generates the certificate and the attacker must predict how and choose the information they give.


representing binary finite fields in ASN.1 In SEC 2: Recommended Elliptic Curve Domain Parameters two types of finite fields are utilized - $\mathbb{F}_p$ and $\mathbb{F}_{2^m}$. In the case of sect193r1, $\mathbb{F}_{2^m}$ is the finite field, where $m = 193$ and is defined by $f(x) = x^{193}+x^{15}+1$

In SEC 1: Elliptic Curve Cryptography, the following ASN.1 structures are presented:

FieldTypes FIELD-ID ::= {
    { Prime-p IDENTIFIED BY prime-field } |
    { Characteristic-two IDENTIFIED BY characteristic-two-field }
}
prime-field OBJECT IDENTIFIER ::= { id-fieldType 1 }
Prime-p ::= INTEGER -- Field of size p.
id-fieldType OBJECT IDENTIFIER ::= { ansi-X9-62 fieldType(1)}
ansi-X9-62 OBJECT IDENTIFIER ::= {
    iso(1) member-body(2) us(840) 10045
}
characteristic-two-field OBJECT IDENTIFIER ::= { id-fieldType 2 }
Characteristic-two ::= SEQUENCE {
    m INTEGER, -- Field size 2m
    basis CHARACTERISTIC-TWO.&id({BasisTypes}),
    parameters CHARACTERISTIC-TWO.&Type({BasisTypes}{@basis})
}
CHARACTERISTIC-TWO ::= TYPE-IDENTIFIER
BasisTypes CHARACTERISTIC-TWO ::= {
    { NULL IDENTIFIED BY gnBasis } |
    { Trinomial IDENTIFIED BY tpBasis } |
    { Pentanomial IDENTIFIED BY ppBasis },
    ...
}
gnBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 1 }
tpBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 2 }
ppBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 3 }
id-characteristic-two-basis OBJECT IDENTIFIER ::= {
    characteristic-two-field basisType(3)
}
Trinomial ::= INTEGER
Pentanomial ::= SEQUENCE {
    k1 INTEGER, -- k1 > 0
    k2 INTEGER, -- k2 > k1
    k3 INTEGER -- k3 > k2
}

$x^{193}+x^{15}+1$ is a trinomial but the "basis type" for it only consists of one integer? It seems to me that there are probably close to three integers - the exponents for $x$? eg. $193$, $15$ and $0$? idk - I guess it's just unclear to me how you're supposed to get $x^{193}+x^{15}+1$ from the ASN.1 or, conversely, how you're supposed to denote $x^{193}+x^{15}+1$ in the ASN.1.

Any ideas?

For a binary field $\mathbb{F}_{2^m}$, the polynomial necessarily has degree $m$ (otherwise the field would not have cardinal $2^m$), and its least significant coefficient must be $1$, not $0$ (otherwise the polynomial would not be irreducible, and the field would not be a field).

Therefore, for $\mathbb{F}_{2^{193}}$, if the polynomial is a trinomial, then it is already known that is is $x^{193}+x^j+1$ for some integer $1<j<193$. Only that integer $j$ needs to be encoded, which is why you only have one INTEGER. In other words, when trying to encode $x^{193}+x^{15}+1$, only the "15" needs to be encoded; the "193" and the "0" are implicit.

Similarly, for a pentanomial, you only have to encode three exponents, since the two extremes (0 and the field size) are implicit.


How much extra security does key wrapping provide? Wikipedia says:

  Key Wrap. Key Wrap constructions are a class of symmetric encryption algorithms designed to encapsulate (encrypt) cryptographic key material. The Key Wrap algorithms are intended for applications such as protecting keys while in untrusted storage or transmitting keys over untrusted communications networks.

Now key wrapping needs another key for wrapping. Isn't it like a chicken-egg problem. We now need to protect another key.

If someone needs to transfer key over network, wouldn't he/she use SSL/TLS rather than wrapping key?

For storing keys, wouldn't someone use the password protected keystore?

It all depends on the key wrapping used. Key wrapping is little more than encryption of a key with another key. Although key wrapping schemes certainly exist (and are considered rather secure in general) other key schemes may use common methods of encryption, both symmetric and asymmetric. And in the end, how strong the encryption is depends on the method used.

I've seen AES keys being encrypted using AES-CBC, which is perfectly fine for AES-128 and AES-256 keys. Wrapping an AES-192 key that way could already make it vulnerable padding oracle attacks. Encrypting a structured RSA key using CBC and an IV of zero bytes (as used by many HSM's) may even passively leak information to adversaries.

Encryption itself is already a chicken egg problem. You've got this data you want to keep confidential. Now you can encrypt it, but you'd need to secure the key now.

So why is encryption or wrapping useful? Well, not all keys have the same properties. Some keys such as public key for asymmetric systems can be distributed using a public key infrastructure, but they can perfectly use to wrap AES keys to perform key establishment. Other keys are distributed in advance, taking advantage of the moment in time that the key can be established. Yet others take advantage of hardware protection in HSMs or smart cards. So key wrapping is an important tool to perform key management. Note that one wrapping key can be used to wrap many other keys.

As for your examples: yes, a key can be transported over TLS. However, TLS is point to point transport security. After TLS is stripped you'd just have the key. It is much more secure to wrap the key and provide end-to-end security. With a bit of luck the key may be unwrapped directly within a HSM and never even appear in memory. Note that earlier forms of TLS, the TLS_RSA ciphersuites, actually perform a form of key wrapping to establish the master secret to derive the session keys from.

A password protected store can be used. Often the keys in those key stored can be protected separately as well. PKCS#8 could be seen as a high level form of key wrapping, for instance.

However, such key stores are not always useful. For instance, you may want to wrap a key in a HSM to sync it with another HSM. In that case you'll need a wrapping key in both devices. Generally HSM's cannot simply create a password protected key store for that.

Similarly, a device can offload wrapped keys if the memory is limited. This is a common method within TPM modules in PC's: instead of having a high end smart card chip, keys are wrapped with a TPM specific key and stored on the system's drive. When they are needed they are simply put back and used. This way the keys can be secure both at rest and when in use, even though they are not stored in the hardware device.

Wrapping / unwrapping a single symmetric key with another symmetric key that has the same access level probably doesn't make too much sense. But for key management key wrapping is a very important - if not essential - tool.


Confusion and Diffusion in the AES functions I am pondering, how each of the four functions that a full AES round does consist of (Add Round Key, Substitute Bytes, Shift Rows and Mix Columns) add to the confusion and diffusion of the full AES.

My understanding would be

Add Round Key: Confusion
Substitute Bytes: Confusion
Shift Rows: Diffusion
Mix Columns: Confusion and Diffusion

Is my understanding correct? There are actually two parts, where I am quite unsure:

Can confusion be introduced without a secret (subBytes)?
Can confusion be introduced from the state alone (Mix Columns)?

I am aware of that and that answer, but they don't go all the way.

I should start by saying that the notions confusion and diffusion can not provide an in-depth understanding of the design of the AES, simply because they are not specific enough. Instead, the key to understanding the choice of the steps in the round transformation is the wide trail strategy.
That said, we can of course try to understand the effect of each transformation with respect to the "confusion" / "diffusion" concepts. Needless to say, the outcome of such a thought experiment is at least somewhat subjective. In any case, a proper definition of "confusion" / "diffusion" is essential. Shannon wrote:

Two methods (other than recourse to ideal systems) suggest themselves
for frustrating a statistical analysis. These we may call the methods
of diffusion and confusion. In the method of diffusion the
statistical structure of $M$ which leads to its redundancy is
“dissipated” into long range statistics—i.e.,into statistical structure involving long
combinations of letters in the cryptogram. The effect here is that
the enemy must intercept a tremendous amount of material to tie down
this structure, since the structure is evident only in blocks of very
small individual probability. Furthermore, even when he has sufficient
material, the analytical work required is much greater since the
redundancy has been diffused over a large number of individual statistics.
The method of confusion is to make the relation between the simple
statistics of $E$ and the simple description of $K$ a very complex and
involved one. In the case of simple substitution, it is easy to
describe the limitation of $K$ imposed by the letter frequencies of $E$.
If the connection is very involved and confused the enemy may still be
able to evaluate a statistic $S_1$, say, which limits the key to a
region of the key space. This limitation, however, is to some complex
region $R$ in the space, perhaps "folded ever" many times, and he has a
difficult time making use of it. A second statistic $S_2$ limits $K$ still
further to $R_2$ , hence it lies in the intersection region; but this
does not help much because it is so difficult to determine just what
the intersection is.

The first comment I would like to make is that diffusion and confusion, if described using the intuitions above, typically only arise by repeated application of the round transformations. Shannon uses the following metaphor (for the construction of "mixing transformations"):

Good mixing transformations are often formed by repeated products of
two simple non-commuting operations. Hopf has shown, for example,
that pastry dough can be mixed by such a sequence of operations. The
dough is first rolled out into a thin slab, then folded over, then
rolled, and the folded again, etc.

For this reason, my answer will mostly be about how each transformation contributes to confusion/diffusion (rather than if these transformations contribute at all).
Diffusion
Paraphrasing to the context of the AES, one might say that diffusion means that the "statistic structure" (this is quite vague) of a plaintext block is spread out over the resulting ciphertext block. For instance, if the first input bit is zero which large probability, this should not be apparent in any small subset of the output bits. (Remark that if this was not the case, one would obtain a strong linear approximation.) This is unfortunately very vague and in fact not really helpful if you are designing a block cipher.
Note that the above interpretation of diffusion is somewhat different from Shannon's "long range statistics", because the latter might be interpreted as "non-neighboring/close bits" rather than "small subsets of bits". I would argue that "small subsets" is what is really meant because Shannon also talks about "long combinations of letters [~bits] in the cryptogram" (emphasis mine).
With this interpretation:

AddRoundKey does not contribute to diffusion. (Well... there are reasons why you could argue that they do, but let's not go into that.)
ShiftRows and MixColumns: these operations mix bits among rows or columns. Hence, you could say that this ensures "non-localized statistics" (again, somewhat vague). Again, the fact that the linear layer has to "mix" bits is not concrete enough to be very useful to a designer - maximizing the number of active S-boxes (cf. wide trail) is the real underlying idea.
SubBytes leads to diffusion at the byte level. If you think of the "symbols" as bytes then you can argue that SubBytes doesn't provide diffusion. I think it is more accurate to say that SubBytes does contribute to overall diffusion.

The last point may need some clarification. It is commonly said that the S-boxes provide confusion (this is correct by the way, see below) rather than diffusion. Nevertheless, consider a cipher such as PRESENT which uses a bitwise permutation for its linear layer. Clearly, if you remove the S-box layer of PRESENT then the result does not satisfy the intuition behind diffusion that was mentioned above. In this context, another answer of mine about statistical saturation attacks seems relevant.
Of course, if you remove SubBytes in AES, the whole cipher becomes affine over $\mathbb F_{2^8}$. More about that below.
Confusion
Confusion, according to Shannon, is all about the secret key. The idea is that the key is mixed into the output in such a "complicated" (this is again vague, for sure) way that a simple/reasonable test statistic $s$ only allows you to conclude that the key must satisfy some complicated equation $f(K) = s$. Shannon notes that if $f$ is sufficiently complicated, it should also be hard to combine the information provided by different statistics.
Now, what is a complicated $f$? This is difficult to formalize, but at least one can think of a few things that $f$ should not be. For example:

If we take $s$ to be the ciphertexts corresponding to one or more known plaintexts, then obviously $f$ should be nonlinear (otherwise one can just solve a linear system of equations). In fact, "nonlinear" is not enough by itself: there is a broad class of so-called algebraic attacks.
If we take $s$ to be the (estimated) bias of a sum of a few plaintexts and ciphertext bits, then the sign of $f(K)$ should not be (roughly) $(-1)^{\kappa}$ where $\kappa$ is some linear combination of key bits. Indeed, this is Matsui's first algorithm for linear cryptanalysis.
... (One can think about most other attacks from this point of view.)

That said, I would conclude the following about the steps in the AES:

AddRoundKey is essential for confusion because you need to have some way of mixing the secret key (which is what confusion is about) with the state.
ShiftRows and MixColumns: these operations are typically associated with diffusion, but they are also necessary to obtain overall confusion. Indeed, if you wouldn't mix columns (or rows), then the equations describing the AES would be easy to solve.
SubBytes are essential for the confusion. In particular, it is nonlinear. Note that SubBytes alone is clearly not sufficient.
The key schedule shouldn't be forgotten. It also contributes (or rather, can contribute) to confusion.

In modern cryptography, "confusion" is often used in a broader sense. For example, one can reasonably talk about confusion even in the absence of a key (e.g. in permutation-based cryptography). That's a different question though.
Conclusion
I should reiterate that "confusion" and "diffusion" are rather vague. At best, these concepts can give you some intuition about why it might be possible at all to construct a secure block cipher. They are not sufficient to really understand the design of modern block ciphers such as the AES.
Just to make sure you get a clear answer to your specific questions:

Can confusion be introduced without a secret (subBytes)?
Can confusion be introduced from the state alone (Mix Columns)?

The answer to the first question is no, but I must remark that SubBytes is not a secret in the AES. (But if "AddRoundKey" was intended, the answer would still be no.)
The second question must also be answered in the negative, see the comments about nonlinearity above.


Is the Couvreur et al. polynomial time attack on McEliece practical? There's a new e-print out on arXiv titled "A Polynomial Time Attack against Algebraic Geometry Code Based Public Key Cryptosystems" by Alain Couvreur, Irene Márquez-Corbella and Ruud Pellikaan:

  "We give a polynomial time attack on the McEliece public key cryptosystem based on algebraic geometry codes. Roughly speaking, this attacks runs in $O(n^4)$ operations in $\mathbb F_q$, where $n$ denotes the code length. Compared to previous attacks, allows to recover a decoding algorithm for the public key even for codes from high genus curves."

Is this a practical attack against currently used implementations of the McEliece cryptosystem, with security parameters such as those recommended by Bernstein, Lange and Peters (2008)?

If the answer is yes, then how much do we need to increase the security parameters $n, k, t$ to be safe?  Or do we need to switch another code / curve entirely?

My understanding is that the attack only works against McEliece with algebraic geometry codes. The paper by Bernstein, Lange and Peters recommends parameters for McEliece with binary Goppa codes, so the attack does not apply against those parameters.


Should Increment functions be near-constant time? When operating a block cipher in CTR or GCM mode, should the function used to increment the counter or initialization vector be near-constant time? Here, I'm wondering about the "addition with carry" that often occurs. For example:

void IncrementCounterByOne(byte *inout, unsigned int size)
{
    for (int i=int(size-1), carry=1; i>=0 && carry; i--)
        carry = !++inout[i];
}

In the function above, processing terminates when carry is 0.

While not readily apparent, some protocols treat the counter or initialization vector as secret or private data (like TLS). That appears to beg a near-constant time function to avoid leaking information.

I realize there will likely be CPU micro-code variations, and there's probably nothing that can be done about it. (Corrections, please).

A related question is, should the Increment function be near-constant time when it increments the seed to an ANSI X9.17 or X9.31 generator.

And a question I am not asking: should a counter or iv be considered public or secret information. Some projects, like TLS, have already made that decision.

Actually, Maarten isn't quite correct; in most cases, the counter doesn't have to be updated in constant time (because it's not secret); however in one case it does: GCM with an IV size that's not 12 bytes.

The reason the counter needs to be secret in this case is not because how it is used, but how it is generated.  It is initialized to $GHASH_H(IV||0^{s+64}||len(IV))$; if the attacker can learn the lower bits of this value (based on whether or not an internal carry has occurred), he can gain information on the internal value of $H$, and if we can fully recover that, then he can forge.

In this (admitedly obscure) case, it would be wise to fully disguise whether the carry occurred.  Here is some code that should be safe on most processors to do that:

void IncrementCounterByOne(byte *inout, unsigned int size)
{
    for (int i=int(size-1), carry=1; i>=0; i--) {
        int t = inout[i] + carry;
        inout[i] = t & 0xff;
        carry = t >> 8;
    }
}

It runs slower than your code (because it reads and writes every byte); however it avoids data dependent operations (on most CPUs and compilers)


Attack on DSA modification with bad hash function Given a (bad) modification of DSA where the hash function is the identity ($H(m)=m$), I am now supposed to design an attack. So $(m, (r,s))$ are given and I should be able to create a legit signature $(r',s')$ for a chosen $m'$ (of course $m'\neq m$).

Since retrieving the private key $x$ doesn't work. My new approach is to choose $m'$ as a modification of $m$ such that $m'=t \cdot m$. Then I want to calculate $(r',s')$ to be a legit signature of $m'$. So I was doing the verification step with $m'$ in order to see how to modify $r'$:

$v'=g^{m' \cdot w} y^{r \cdot w}=g^{m' \cdot w + xrw} \mod q$ now $v'$ is supposed to equal $r'$. This means $g^{m' \cdot w + xrw}=g^k$ so $m'w+xrw=k$. But I can't just choose k, can I (because it's already $k=mw+xrw$ ? And I don't know to modify $r$ in order to make this work...

With my new idea I seem to solve the problem and answer my question, so I'll go ahead and post it as the answer. I choose the new $m'$ as $m'=t+m$ with $t>0$.
Now the verification works like this:

$v'=g^{m'w} y^{rw}=g^{m'w+xrw}=g^{tw+mw+xrw}=g^{tw} \cdot g^k=r' \mod q$

So my new $r'=g^{tw}r=g^{ts^{-1}}r$

This means I can create a legit signature to any $m'=t+m$ which is $(r',s')=(g^{ts^{-1}}r, s)$. Correct?


Advanced Encryption Standard I had done an example on AES-128 bit.But while doing AES-192 bit,i am facing below problem.
what is the order of the matrix after mixed column step in 192 bit AES?

what is the order of the matrix after mixed column step in 192 bit AES?

The only differences between AES-128 and AES-192 are

the key scheduling is different
AES-192 has two more rounds.

There is no difference in any of the steps.

What you might be trying to look at is Rijndael with a 192 bit block size; there are differences in the shift row steps, which might be what you are looking at.  However, that has little to do with AES, which always has a 128 bit block size.


How long should the salt be for PBKDF2? In order to complicate rainbow table attacks, salt must be provided as input to PBKDF2 when a key is derived from a low-entropy password.

I have decided on my algorithms and key lengths to achieve certain bit strength. How long salt should I use for PBKDF2?

PBKDF2 defines, that the salt is concatenated with the numbers of iterations (in 32 bit big endian) as 2nd input to the PRF. If you use HMAC as PRF (as suggested in the wiki article), the 2nd argument can be of arbitrary length.

On other SE sites, you can find these questions and answers to cryptographic salts in general:

What is the optimal length for user password salt?
How big should salt be?

The main aspect of salts is that they are unique. So it comes down to how many different keys you want to derive with your KDF. As a rule of thumb, 32 or 64 random bits should be enough and you will most likely never exhaust those numbers. If you just want to derive a couple of keys from the master secret, you can get away with an even shorter salt, e.g. 2 byte. Even if you set the salt length "too short" and want to derive more keys later, you can always use the same salt and a different number of iterations. That will also result in different derived keys, because the number of iterations is embedded in the input of the first iteration of the PRF already.


Comparison on Ciphertext with Helib Is it possible to do a greater than homomorphic comparison in the form ($c_1 < c_2$) on two ciphertexts using Helib?

The equal comparison ($c_1 == c_2$) can be done in modulus 2 by adding both ciphertexts. Does it give any multiplication and/or addition combination to obtain the greater than comparison ( $<$) on binary numbers?

On the paper Low Depth Circuits for Efficient Homomorphic Sorting (page 5), the authors present circuits to homomorphically evaluate comparisons.
Their "Less Than Circuit" compares $\ell$-bit integers in the following way:
They define a bit level "less than": $f(x, y) = y \cdot (x + 1) \mod 2$  (where $x$ and $y$ are encryptions of bits).
They define a bit level "equal to":  $g(x, y) = y + x + 1 \mod 2$.
Then, the less than circuit for two encrypted $\ell$-bit integers is
$$C_{LT}(X, Y) =  \sum_{k=1}^{\ell} (f(X_k, Y_k) \cdot \prod_{k<t<\ell}g(X_t, Y_t))  \mod 2$$
where $X = (X_1, X_2, \cdots, X_\ell)$ is a vector of ciphertexts in which each $X_k$ is the encryption of the $k$-th bit of the first plaintext (and the same for $Y$ regarding the second plaintext).
Since the only thing it requires is the ability to encrypt bit a bit and to homomorphically operate $\mod 2$, it seems you can evaluate this circuit using Helib.


What does "message schedule" mean in SHA-256? I am trying to understand the sha-256 algorithm from FIPS 180-2. I understood the padding and parsing of the message string. However after that it states (page 15):

  For $i = 1$ to $N$:
     {

  Prepare the message schedule, ${W_t}$:
  $$ W_t= \begin{cases} M_t(i) & 0 \leq t \leq 15 \\
     ROTL^1( W_{t -3} \oplus W_{t-8} \oplus W_{t - 14} \oplus  W_{t-16} ) &
     16 \leq t \leq 79 \end{cases} $$
  ...

But I am unable to understand what $W_t$ is in the first place. Could someone please help me out?

I know it states on page 3:

  $W_t\qquad$ The $t$th $w$-bit word of the message schedule.

But what is the message schedule and how is it generated?

What this does is expand the 16-word (512-bit) input message block (to the compression function, i.e. one "chunk" of the complete message) into an 64-word array W[t]. The definition of this array is recursive. What it tells you is that the first 16 words of this 64-word array are just the words of the input chunk:

W[t] = M[t]   for 0 <= t <= 15

In other words, for t between 0 and 15, W[t] is equal to M[t].

Then, for 16 <= t <= 63 (the remaining 48 words) the following recurrence is used:

W[t] = MIX(W[t - 2], W[t - 7], W[t - 15],  W[t - 16])   for 16 <= t <= 63

Such that W[t] depends on W[t - 2], W[t - 7], W[t - 15] and W[t - 16] and MIX is the message schedule function (composed of exclusive-or and bit shifts/rotations). Note that words are guaranteed to have been defined previously as the first 16 words have already been initialized, and the remaining values are then successively calculated.

Here W[t] is just a temporary variable just like any other and is used to improve the compression function's quality, and is called the "message schedule" since it preprocesses the message block.

EDIT: I changed the description to SHA256 as @Henno noted you were actually describing SHA1 (though as he correctly observes, the overall structure remains the same for the two hash functions)


Why not just encrypt the message and the hash of the message to achieve cryptographic integrity? I've always seen MACs as a way to provide integrity and authentication. You would just append it to some message in clear.

But this is clearly not the case when you're doing Encrypt Then Mac. When you do that you provide authentication to something that already has authentication (to decrypt we need to know the key). So why use a MAC when we can use a hash instead: $E(m | h(m))$? (i.e., encrypt the message appended to a hash of the message)

I'll take this in parts:

  But this is clearly not the case when you're doing Encrypt Then Mac. When you do that you provide authentication to something that already has authentication (to decrypt we need to know the key).

Encryption, by itself, does not provide authentication.

  why use a MAC when we can use a hash instead: E(m|h(m))?

Here is a simple counter example to your proposal. Say I know that m="Transfer \$1000 to Mikeazo", and you use a stream cipher (or stream like mode) to encrypt that and the hash of the message. I know how to compute h(Transfer $9999 to Mikeazo). I also know what bits to flip in the encryption to get everything to check out okay.

Now, you may be thinking that this attack is only valid since I assumed a stream cipher and how about other modes (e.g., CBC). Well, here are the details on an attack with CBC.

When we design cryptographic primitives, we want them to be as secure as possible, and even provably secure (given a reasonable set of assumptions) if possible. That is why we do things like Encrypt-then-MAC as opposed to your proposal. Encrypt-then-MAC is provably secure.


Why is SKEYSEED derived using the nonce as a key? In IKEv2, SKEYSEED, which is used to as a seed for generating the rest of the keys, is generated as
SKEYSEED = prf(Ni | Nr, g^ir)
In other words, we invoke a pseudorandom function with the concatenation of the initiator and receiver nonces (that are sent in the clear) as the secret, and the Diffie-Hellman shared secret g^ir as the seed.
What is the rationale for this? Shouldn't the arguments for prf be reversed so that the secret is actually, well, secret?

The reason why the nonces are used as key is that there are some legacy PRFs, RFC 7296 mentions two, AES-XCBC-PRF-128 and AES-CMAC-PRF-128, that use a fixed key length (128-bit in this case, so only 64 bits of each nonce are used). Any DH key exchange that produces a longer shared secret would be rendered ineffective if its output was used as key with such PRFs.
So the nonces, which must be long enough to serve as half the key for any negotiated PRF (at least 128-bit each, most IKE implementations currently use 256 bits), are used instead to initialize the PRF and the DH shared secret as variable length seed to derive pseudorandom output from it.


How does failing to square a value in this version libcrypt++ cause a timing attack vulnerability? I'm a crypto beginner and reading about blinding, and my fundamental understanding about preventing timing attacks is that you need to sort of process information in a way that will produce similar processing times for each set of operations.

In CVE-2015-2141 something as simple as failure to call r = modn.Square(r); in a single func seems to have caused a timing attack vulnerability in libcrypt++ in 2015.

I have a multi part question about this:

First it seems like you'd need some special helper func designed to produce random timing results called in each subroutine to blind a func, why is the process of squaring a value sufficient?
Second, surely this algorithm has many hundreds of routines that get called every single time it's used - it seems like if nearly all of the subroutines are blinded, the failure to blind just one wouldn't leak enough timing information to cause the entire function to be vulnerable to a timing attack, can someone explain this?
Is the goal to make every subroutine take exactly the same amount of time to complete, or a random unpredictable time? Why couldn't we paste a helper function call into every module that runs in a securely random amount of time so the timing information released becomes useless?

In CVE-2015-2141 something as simple as failure to call r =
  modn.Square(r); in a single func seems to have caused a timing attack
  vulnerability in libcrypt++ in 2015.

Actually no. That's not what CVE-2015-2141 is about. What it is actually about is that the loop originally did not have the squaring and this would result in sometimes not having the blinding removed in a later step after the private key operation which would leak enough information in about 2 signatures on the same message to recover the private key.

  First it seems like you'd need some special helper func designed to
  produce random timing results called in each subroutine to blind a
  func, why is the process of squaring a value sufficient?

The blinding here is achieved by the fact that computing a signature in rabin-williams is "effectively equivalent" to computing a square root of the message. So it kinda works like this:

Pick $r\gets_\$ \{1,...,n-1\}$, compute $r^2\bmod n$ and $r^{-1}\bmod n$
Let $m$ be a message, compute $m'=r^2\cdot m$
Now compute the signature on $s'=\sqrt {m'}\bmod n=\sqrt {r^2\cdot m}\bmod n=r\cdot\sqrt {m}\bmod n$
Finally unblind the signature to recover the actual signature $s=r^{-1}\cdot s'\bmod n$

Now what this achieves is prevent an attacker from knowing on which value exactly the private key operation was applied, which should thwart quite a few timing attacks.

  Is the goal to make every subroutine take exactly the same amount of
  time to complete, or a random unpredictable time?

The standard strategy to thwart timing attacks is to either

ensure the timing doesn't actually depend on the private value in question or
ensure the timing doesn't actually correlate to known inputs and / or the private key in a meaningful way.

Randomizing the input to the private key operation is part of the second strategy.


Adding a Random component to CBC MAC in order to enlarge the tag space CBC MAC that is using AES as the underlying block cipher, has tag space of 2^128. If we add a random single block, concatenating it with the tag, and encrypt it again in AES CBC mode, with additional key, we get a 256 bit tag of 256 bits space:

TAG = CBC_MAC(K2,CBC_MAC(K1,M)||r) || r

(where r is 128 bit random number) This is a randomized MAC generating tags in the space 2^256. In the same way we can easily generate tag in any size. Is there any standard that is using this method?

Thanks

First, don't roll your own crypto.

Second, why would you want to use CBC-MAC, if you have GMAC (GCM-mode) and CMAC and even better HMAC? (all of which are better than CBC-MAC)

Third, don't try to fix problems that have been fixed. (see second)

Fourth, I'm not aware of this construction being standardized and I'd doubt it has been. (see points 1 to 3)

Fifth, in fact there's a proposal that is similar to yours. Look here


Software Security Impossible in Non-Trusted Hardware? Fundamentally it is impossible to protect software if you can't trust the execution platform (e.g. using a TPM), so what is the point of software security then?

With vendors claim that their white-box crypto / obfuscation technique are the best, is there a methodology or a way to assess the strength of software security?

Recently, ECRYPT CSA organized a white-box challenge where you can publish your white-box implementation for AES-128 without exposing your design and the chosen key.

As a result, all the submitted challenges have been broken in less than one month, which further proves that "obscurity" is never sufficient to protect your assets.

To the best of my knowledge, there are no formal methods to measure the obscurity strength achieved in a software.


Easy explanation of "IND-" security notions? There are many schemes that can advertise themselves with certain security notions, usually IND-CPA or IND-CCA2, for example plain ElGamal has IND-CPA security but doesn't provide IND-CCA security.

The most common ones are the "IND-" ones, advertising security against specific classes of attackers.
Now these notion may not be that well-understood by many people so I ask hereby for a canonical answer, that explains what the following security notions mean. A (simple) description of the formal attack scenario is preferred.
Please don't restrict the answer to "you can chose this and if you can break it with this it isn't IND-CCA2". Please at least outline the formal attack (like f.ex. real-or-random). Relations between the "IND-" are explained (f.ex. IND-CCA implies IND-CPA).
The notions in question are:

IND-CPA
IND-CCA
IND-CCA1
IND-CCA2
IND-CCA3

The ideal encryption scheme $E$ would be one that, for every ciphertext $C=E(K, M)$, if the key remains secret for the adversary, the probability of identifying $M$ is negligible. Since that is not possible in practice, the second most reasonable approach is to define constraints strong enough to satisfy some definition of security. The $\operatorname{IND-}$ notation provides such definitions in terms of games, where a challenger keeps his key secret, and an adversary has certain capabilities and his target is to break the encryption system.

To keep it general, an encryption scheme will have a key generation algorithm $KG$, which will generate a key pair $K_E$, $K_D$, an encryption algorithm $E$ and a decryption algorithm $D$. Encryption is always revertible, but the encryption and decryption key can be different (covering public key crypto): $D(K_D, E(K_E, M))=M$

  IND-CPA: INDistinguishability under Chosen Plaintext Attack

In words: the adversary generates two messages of equal length. The challenger decides, randomly, to encrypt one of them. The adversary tries to guess which of the messages was encrypted.

Algorithm:

Challenger: $K_E, K_D$ = KG(security parameter)
Adversary: $m_0, m_1 = $ choose two messages of the same length. Send $m_0,m_1$ to the challenger. Perform additional operations in polynomial time including calls to the encryption oracle.
Challenger: $b=$ randomly choose between 0 and 1
Challenger: $C:=E(K_E, m_b)$. Send $C$ to the adversary.
Adversary: perform additional operations in polynomial time including calls to the encryption oracle. Output $guess$.
If $guess=b$, the adversary wins

Further comment: the main concept introduced by this scenario is the polynomial bound. Now, our expectations from crypto are weakened from probability of winning is negligible to probability of winning within a reasonable timeframe is negligible. The restriction for the messages to be of the same length aims to prevent the adversary to trivially win the game by just comparing the length of the ciphertexts. However, this requirement is too weak, especially because it assumes only a single interaction between the adversary and the challenger.

  IND-CCA1: INDistinguishability under Chosen Ciphertext Attack

In words: the target of the game is the same as in IND-CPA. The adversary has an additional capability: to call an encryption or decryption oracle. That means: the adversary can encrypt or decrypt arbitrary messages before obtaining the challenge ciphertext.

Algorithm:

Challenger: $K_E, K_D$ = KG(security parameter)
Adversary (a polynomially-bounded number of times): call the encryption or decryption oracle for arbitrary plaintexts or ciphertexts, respectively
Adversary: $m_0, m_1 = $ choose two messages of the same length
Challenger: $b=$ randomly choose between 0 and 1
Challenger: $C:=E(K_E, m_b)$Send $C$ to the adversary.
Adversary: perform additional operations in polynomial time. Output $guess$
If $guess=b$, the adversary wins

Further comment: IND-CCA1 considers the possibility of repeated interaction, implying that security does not weaken with time.

  IND-CCA2: INDistinguishability under adaptive Chosen Ciphertext Attack

In words: In addition to its capabilities under IND-CCA1, the adversary is now given access to the oracles after receiving $C$, but cannot send $C$ to the decryption oracle.

Algorithm:

Challenger: $K_E, K_D$ = KG(security parameter)
Adversary (as many times as he wants):  call the encryption or decryption oracle for an arbitrary plaintext/ciphertext
Adversary: $m_0, m_1 = $ choose two messages of the same length
Challenger: $b=$ randomly choose between 0 and 1
Challenger: $C:=E(K_E, m_b)$Send $C$ to the adversary.
Adversary: perform additional operations in polynomial time, including calls to the oracles, for ciphertexts different than $C$. Output $guess$.
If $guess=b$, the adversary wins

Further comment: IND-CCA2 suggests that using the decryption oracle after knowing the ciphertext can give a reasonable advantage in some schemes, since the requests to the oracle could be customized depending on the specific ciphertext.

The notion of IND-CCA3 is added based on the reference provided by @SEJPM. I add it for completeness, but it seems important to point out that there are few resources about it, and my interpretation could be misleading.

  IND-CCA3: (authenticated) INDistinguishability under adaptive Chosen Ciphertext Attack

In words: It is not possible to create a valid forgery with non-negligible probability. The adversary is given two pairs of encryption/decryption oracles. The first pair performs the intended encryption and decryption operations, while the second one is defined as follows: $\mathcal{E}_K$: returns encryptions of random strings. $\mathcal{D}_K:$ returns INVALID. Instead of being presented as a game, it is presented using the mathematical concept of advantage: the improvement of the probability of winning by using the valid oracle against the probability of success under the "bogus" oracle.

Formula: $\mathbf{Adv}^{ind-cca3}_{\pi}(A)=Pr\left[K\overset{\$}{\leftarrow}\mathcal{K}:A^{\mathcal{E}_K(\cdot),\mathcal{D}_K(\cdot)}\Rightarrow 1\right] - Pr\left[A^{\mathcal{E}_K(\$|\cdot|),\perp(\cdot)}\Rightarrow 1\right] $

Further comment: the paper where IND-CCA3 is introduced a focus on one fundamental idea. IND-CCA3 is equivalent to authenticated encryption.

Note that in the case of public-key cryptography the adversary is always given access to the public key $K_E$ as well as the encryption function $E(K_E, \cdot)$.


Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks? Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?

I have been reading about homomorphic encryption and malleable cryptosystems lately and have found it fascinating. I still have a lot of reading to do, however, I came across a statement in my reading that suggested malleability is inherently counter to security against chosen ciphertext attacks.

While I read up more about this relationship, I am curious to learn if there a way to maintain malleability while making a chosen ciphertext attack computationally infeasible? Why or why not?

I know of two lines of work on this question. It is indeed possible to allow malleability but still make some guarantees in the presence of a chosen-ciphertext attack:

Manoj Prabhakaran & Mike Rosulek: Reconciling Non-malleability with Homomorphic Encryption.
Dan Boneh and Gil Segev and Brent Waters: Targeted Malleability: Homomorphic Encryption for Restricted Computations.

Both papers present encryption schemes (and security definitions) that allow malleability $\textsf{Enc}(m) \leadsto \textsf{Enc}(T(m))$ for some set of allowed transformations $T$ (as a feature), but where any other kind of malleability is infeasible.

As a concrete example, suppose the only allowable transformation is the identity transformation. Then it is possible to transform $\textsf{Enc}(m)$ into another "fresh" encryption of the same (unknown) $m$. But it is infeasible to transform $\textsf{Enc}(m)$ into any $m' \ne m$ that is related to $m$. This special case is called "rerandomizable RCCA" encryption.

The first paper is my work, a combination of 3 of our conference papers; the one most relevant to your question is this one. Our construction has additional security requirement: a "transformed" ciphertext obtained via $\textsf{Enc}(m) \leadsto \textsf{Enc}(T(m))$ should be indistinguishable from a "fresh" ciphertext (even to the private-key holder). We only consider the case of unary transformations, since n-ary transformations (i.e., combining several ciphertexts in a transformation) are impossible under these definitions.

The second paper does not have this extra requirement --- so "transformed" ciphertexts look different than "fresh" ciphertexts. They use an approach of appending a ZK proof that an allowable transformation was used on some original ciphertext.


Padding of Original Message in MD5 what should I do if my original message is greater than 64 bits? what is the process of padding in MD5?

As described in Internet Security: Cryptographic Principles, Algorithms and Protocols, page 138, the second step in MD5 is to append the length of the message:

Can someone help me understand exactly what happens when the message length is greater than $2^{64}$ bits?

If the original message length $N$ is $2^{64}$ bits or longer, you encode the value $N \bmod 2^{64}$ in the final padding block, rather than just $N$.  Alternatively, you can just always encode $N \bmod 2^{64}$; if $N < 2^{64}$, then they're the same value.

Now, this distinction between $N$ and $N \bmod 2^{64}$ doesn't happen at 64 bits, it's at $2^{64}= 18,446,744,073,709,551,626$ bits, or about 2000000 Terabytes.  No one has ever hashed a message that long with MD5; even if we assume an MD5 compression function can be computed in 1nsec (massively overoptimistic), it'd take over a year to hash a message that large (and parallelism doesn't help).


nonce of AES-GCM in SSL It seems that the nonce of AES-GCM in SSL has 3 parts:

salt, 4 bytes, generated in handshake, not changed in whole session
nonce_explicit, 8 bytes, chosen by the sender and carried in each SSL record
inner_counter, 4 bytes, used in AES-GCM internal

Is it possible to use a more simple method to construct the nonce:

generate a 16-bytes IV in handshake
use this IV as counter for each cipher block in the whole session life, ignore SSL record boundary

then the sender need not carry nonce for each record, saving the bandwidth.

===

I read the RFCs again and found I misunderstood something.

Let me make the question clear.

AES-GCM algorithm: require the nonce is distinct.
AES-GCM specification [RFC 5116]:

It gives an recommended format (not required):

" When there are multiple devices performing encryption using a single
key, those devices must coordinate to ensure that the nonces are
unique.  A simple way to do this is to use a nonce format that
contains a field that is distinct for each one of the devices, as
described in Section 3.2."     [ Fixed + Counter ]

" In some cases, it is desirable to not transmit or store an entire
nonce, but instead to reconstruct that value from contextual
information immediately prior to decryption."
[ Fixed-Common + Fixed-Distinct + Counter ]
It is defined for protocols that uses record. I missed this before:

"Each AEAD algorithm MUST accept any plaintext with a length between
zero and P_MAX octets, inclusive, where the value P_MAX is specific
to that algorithm.  The value of P_MAX MUST be larger than zero, and
SHOULD be at least 65,536 (2^16) octets.  This size is a typical
upper limit for network data packets."

QUESTION: However if we ignore the specification, is it possible to treat the whole SSL session as a stream (ignore the record bondary), and use only one nonce (and use the nonce as counter) ?

AES-GCM in SSL [RFC 5288]: it uses the recommended format.

QUESTION: since it generates master-secret in each SSL session, it would not hanppen that "multiple devices performing encryption using a single key". Why does SSL use the recommended format (the Fixed part)? What's the function of 'salt'?

I know that since specifications of AES-GCM and SSL have been defined, we should just follow it.
I just wonder why it was defined like this.

Besides, maybe we could define an SSL-extension, so that the SSL client and server could use record-seq as nonce_explicit, and do not send it with record.

This is a trickier question than you might think.

The first thing to note is that your scheme doesn't respect record boundaries. TLS 1.2 seems to have been rewritten to use a random IV for CBC mode encryption for each record (to avoid certain attacks). It is therefore likely that the idea of TLS 1.2 is to respect record boundaries.

The document "AES Galois Counter Mode (GCM) Cipher Suites for TLS" - RFC  5288 - mentions "An Interface and Algorithms for Authenticated Encryption" - RFC 5116. This document specifies the use of a 4 byte salt and 8 byte random. That means that the nonce is 12 bytes total, consisting of the persistent part of 4 bytes and 8 bytes random. The GCM specification strongly recommends a 12 byte (96 bit) nonce/IV. This specification in turn is based on GCM ESP, RFC 4106, which specifies the use of GCM for IPsec. So in general the use of GCM in TLS 1.2 seems to follow previously established standards.

The specification of a per record random (explicit) part is of course in line with the cipher suites that use CBC based encryption. In this case however the IV only has to be 8 bytes instead of 16, which saves some 8 bytes as overhead. That's still 8 bytes more than your proposed scheme - which, again, doesn't respect record boundaries - but it's better than CBC.

Notes:

If you would change to a fully implicit nonce you should still keep to 12 bytes to keep within the GCM specifications. If you would specify 16 bytes IV then the GCM specification requires an additional GMAC. There seems to be no way of specifying a 16 byte counter to be used; the 4 least significant (rightmost) bytes are set by the algorithm itself.
Related, in your scheme it is impossible to use a GCM API that only allows 12 byte nonces (i.e. without the counter included in the IV). You would need some way of keeping track of the counter and a method of instantiating GCM with that full 16 byte counter.
In your scheme it would be impossible to parallelize encryption/authentication and decryption/verification unless you had a way to pre-compute the record payload.

In conclusion, although your scheme could work (it's more efficient and isn't likely to be insecure), it doesn't respect record boundaries and it would put additional requirements on the GCM library. Finally, it would not follow pre-established standards for the use of GCM in a transport protocol.

In TLS 1.3 (under construction at the time of writing) it seems that the record number may be used instead of the explicit random, which would require less overhead in the record header and less calls to the random generator.

Note that Figure 2 in RFC 5116 "An Interface and Algorithms for Authenticated Encryption" includes the counter in the nonce specification. I've made a report for an ERRATA on this as the GCM specification and the ESP documents both treat the nonce as a 12 byte value (so without the counter).


Basic properties of some hash functions Let $b_1, b_2, \dots, b_n$ be blocks of a fixed size.
We take our hash function to be $H(x)$, for example SHA1.

What is the result of $H(b_1 || b_2 || \dots || b_n)$?

Edit:

Let me formulate it more clearly.
So I want to know if the following properties (or any other similar property) hold:

$H(b_1 || b_2) = H(H(b_1) || H(b_2))$
$H(b_1 || b_2) = H(b_1 || H(b_2))$
$H(b_1 || b_2) = H(H(b_1 || H(b_2)))$
Associativity (I assume it's not the case)
Commutativity (clearly not the case)

For any hash function like MD5, SHA1, etc.

Edit 2:

Okay, so how are large inputs treated by decent hash functions? Will the blocks be xored, then hashed. Is there a pattern or is it completely different from function to function?

The old hash functions you mention (MD5, SHA-1) are based on the Merkle-Damgård construction. SHA-3 uses a sponge construction instead. There are certainly more variations possible, but these are the popular ones.

There are multiple constructions possible but for most hash functions the input is indeed split in blocks. These blocks are directly put in some kind of compression / sponge function which is used to update the state of the hash function. A hash function also has an initial state provided for when zero blocks have been processed.

Generally the last block is padded and a length of the input is included to create the final state. In the case of MD5 and SHA-1 the state is directly output as the hash value, but in more modern hash constructions there may be more processing before the final output is produced. This happens for instance for SHA-3.

A hash function is required to always produce a different output for any different input. As they may process a virtually unlimited amount of input while producing a small amount of output there must of course be many messages that produce the same output; this is called the pigeon hole principle.

It is however computationally infeasible to find those input.at least when the hash function is not broken. MD5 is such a broken hash function for which this property is clearly not true anymore.

So lets visit your questions with this knowledge:

$H(b_1 || b_2) = H(H(b_1) || H(b_2))$ - clearly different inputs
$H(b_1 || b_2) = H(b_1 || H(b_2))$ - clearly different inputs
$H(b_1 || b_2) = H(H(b_1 || H(b_2)))$ - clearly different inputs
Associativity (I assume it's not the case) - clearly different inputs
Commutativity (clearly not the case) - clearly different inputs

So, no, hash functions do not possess any of these mathematical properties, which is not surprising if you consider that it should be infeasible to reverse a hash value.

It's much more interesting to have a look at how the internal compression function or sponge function behaves.