XOR secret sharing scheme I was wondering how we can get a secret sharing of $a+b$ from the sharing of secrets $a$ and $b$ themselves by using an XOR secret sharing scheme, where $a_1,...,a_n$ and $b_1,...,b_n$ are the shares for $a$ and $b$ respectively. Can anyone give me any suggestion?

The answer is almost definitely no for what I think you want (question is still unclear). I was hoping someone else could give a definite no, but since they haven't I figured I'd write this up.

Your exact secret sharing method probably needs to be fully described in the question. I'm going to assume that $a=a_1\oplus a_2\oplus\dots\oplus a_n$ and similarly for $b$. Party $p_i$ is given $a_i,b_i$ and you want the parties to be able to compute shares, say $c_i$ of $c=a+b$ without reconstructing $a$ or $b$. I'll assume we are working in some finite field $\mathbb{F}$ and that $a_1,\dots,a_{n-1}$ are chosen randomly from the field and $a_n=a\oplus a_1\oplus\dots\oplus a_{n-1}$. The shares of $b$ are chosen similarly.

Note that this is basically additive secret sharing in a field of characteristic two. But, when you say you want to compute shares of the sum of $a+b$, I'm assuming you don't mean field-of-characteristic-2 addition (which is just xor). If that is what you mean, then the answer is simple (each party $p_i$ simply computes $c_i=a_i\oplus b_i$). I'm assuming you want something like 32 bit addition (i.e., addition mod $2^{32}$ or something very similar like addition in $\mathbb{Z}_p$ where $p$ is possibly the next prime after $2^{32}$).

To see why I don't believe it is possible, lets use $n=2$.

So, $p_1$ gets $a_1,b_1$ and $p_2$ gets $a_2,b_2$ where $a=a_1\oplus a_2$ and $b=b_1\oplus b_2$.

Therefore, the problem reduces to the following, we need some operation, say $\boxplus$, such that $(a_1\boxplus b_1)\oplus(a_2\boxplus b_2) = a+b$

So, what are the possibilities for $\boxplus$. If we allow for communication to take place between $p_1$ and $p_2$, then the answer is yes, it can be done. In this case, we can do multiparty computation in the characteristic 2 field and construct a 32 bit adder circuit. This should be possible as far as I understand MPC.

Now, assuming you do not allow communication between the parties after the shares are distributed (which I'm guessing is what you wanted), I just don't see a way to do it (though I haven't been able to fully prove it, if nothing else hopefully my answer will bring some good discussion). If we take the approach of MPC, all we can do on the shares is compute the xor and multiply by a constant. Given those operations I don't see how you would construct an adder.

Another temptation might be to simply add $a_i,b_i$ using regular addition. In which case you get $(a_1+b_1)\oplus(a_2+b_2)$ which will not be $a+b$. Really we need an operation $\boxplus$ which is commutative and associative with $\oplus$ in which case you could do $(a_1\boxplus b_1)\oplus(a_2\boxplus b_2)=(a_1\boxplus b_1)\oplus(b_2\boxplus a_2)=a_1\boxplus (b_1\oplus b_2)\boxplus a_2=a_1\boxplus b\boxplus a_2$. It is unclear where to go from there. This is where I ended up and couldn't go any further and why I believe the answer  is no in the case of no communication.


Is it possible to make use of a pseudo-random permutation to construct a one-way compression function? Let $f_k(B)$ denote the underlying function (a pseudo-random permutation) of a block cipher: it uses an $x$-bit key $k$ to encrypt an $y$-bit block $B$.
The question: is it possible to make use of $f_k(B)$ to construct a cryptographically secure One-way compression function that transforms any sequence of $y$ bits to a sequence of $y/2$ bits? If yes, then what is an example of how to do it? If no, then why?
For example, consider the following construction. Let $V$ denote a sequence of $x$ zero bits: $$V = 0^x.$$ Then $W$ denotes the inverse of $V$: $$W = 1^x.$$ Consider a function that outputs the first half of a bitstring $T$, where
$$T = f_V(b) \oplus f_W(B),$$ assuming that $B$ denotes the input, $b$ denotes the inverse of $B$ and $\oplus$ denotes a standard XOR.
Can we use such function as a compression function?

This is possible in the ideal cipher model, and is the basis of the Davies-Meyer and other hashes; see https://en.wikipedia.org/wiki/One-way_compression_function. There has been a lot of work looking at this, but I think a good place to start is the paper Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. It is important, however, to be aware that the ideal cipher model is very strong. For example, AES suffers from related-key attacks and so is not a good basis for such constructions. In addition, due to DES weak keys, some of these constructions are completely broken with DES. However, it does explain the rationale behind the SHA256 and other SHA constructions that essentially construct a type of block cipher and apply a Davies-Meyer type transformation.


Some Questions about the Veracrypt hash functions Veracrypt has always been my favourite encryption tool since it came out .
But still there are some things about the tool I don't understand .

Why is there the possibility to use sha256 or sha512 .
This one does not make sense to me at all . As far as I know the output size of the Veracrypt KDF will always have the same length .... so why give the possibility to use a shorter or longer hash ? does it have any advantages ?
Why does Veracrypt use such strange hashes ? sha512 , Whirlpool , Streebog , etc ... Whirlpool is ( as far as I know ) not even officially a KDF . All thes hashes are rather collison resistant , but not one of them is suited as cryptographic strong hash function . Why not Argon2 , scrypt , bcrypt , ..?
Why is Veracrypt GPU resistant ? Attacking a VC hash with a GPU is slow . Why ? I don't see any GPU attack countermesures . All the hashes are well implemented in GPU . they pass through PIM which ( I think ) rehashes the output of the last hash with the same algo . And then they pass through PBKDF2 at some point . But even PBKDF2 is rather GPU friendly .

These hash functions are also used for the key derivation function. Both are roughly equally secure for a KDF in the sense of collision resistance etc., but SHA512 offers a bit more security as countermeasure for custom hardware attacks, since the memory requirements are a higher than for SHA256 and custom hardware to crack the passwords like FPGAs is more expensive. So there is a small advantage using SHA512, even if the output is truncated at the end.
Although I can’t explain VeraCrypt’s selection of hash algorithms, it is not a bad idea to offer a variety of functions as a countermeasure to custom hardware attacks with ASICs, as these chips must be produced for each algorithm. This could also be a reason for using different SHA variants.
I agree with you, that Argon2, scrypt, bcrypt would be better than PBKDF2, which remains vulnerable to custom hardware attacks even at high iterations.
But VeraCrypt took the poor design of TrueCrypt, where all possible combinations of key derivation are tested in a trial and error process (see chapter 3 of VeraCrypt encryption scheme). This limits the amount of time for all key derivation functions (see Bill Cox's Responses). So if it would test PBKDF2, Argon2 and scrypt in sequence, the latency would increase drastically.
I don’t know if or why VeraCrypt is GPU resistant. hashcat supports GPUs to crack VeraCrypt volumes, but I don’t know anything about the performance.


Safety of DSA key parameters sharing I'm looking for a solution to use in a context where I need to be able to generate new asymmetric key pairs quickly (using a widely recognized algorithm, and EC-DSA is not applicable). It sounds like DSA would be the adequate solution.

According to the documentation, just generating DSA parameters once allows then to generate a large number of separate keys pairs only requiring the step of selecting a random private key 'x' for each of them. FIPS 186-3 says :

  the intended signatory shall first obtain appropriate domain
  parameters, either by generating the domain parameters itself, or by
  obtaining domain parameters that another entity has generated

Is there any security issue I'm missing before reusing the same domain parameters for a large number of keys ? How frequently ought the domain parameters be changed ? (There's some reference around to the possibility for a CA to use the same domain parameters for all the certificates it issues)

In DSA (and ECDSA), it is possible and common to share the same domain parameters, across multiples users. AFAIK (and according to common wisdom, including FIPS recommendations) this introduce no known security weakness. The only common reasons to change domain parameters are to increase key size, or purposely introduce on interoperability barrier (e.g. to force an upgrade).

One advantage of fixed domain parameters $(p,q,g)$ in DSA is that it simplifies the choice of a user's key: basically one selects a random private $x\in[1, q–1]$ and computes the public $y=g^x\bmod p$.

As pointed in this other answer, sharing domain parameters increase odds that several users share the same key. However, for a good RNG, $2^n$ users and the lowest security level in FIPS 186, odds that it happens are less then $2^{160-2⋅n}$; that's negligible even for one key per day per human on our planet during a century. And if the RNG is flawed, all bets are off anyway.


Collision Resistant Hashing from One-Way Functions? In general, can we construct a collision resistant hash function from a one-way function?

Simon [Sim98] showed that is not possible to build a collision-resistant hash function from a one-way permutation (which is a stronger statement) in a black-box manner .

The main idea is to use the so-called oracle-separation technique. You can read more about it either here or in this survey.

[Sim98]: Daniel Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? Eurocrypt'98.


Maximum secret key length from a time series shared signal Alice and Bob share a common time series signal.

1. What can be the largest possible secret key?

2. Will the entropy and secrecy of system depends on this length?

Ideally if after passing though analog to digital converter(ADC) number of bits a signal gives depends on $N_S$ sampling rate. Suppose I had s 1 second window of signal. Through ADC I got $N_S$ samples. I apply threshold on these samples and generate keys. Maximum length hence is $N_S$ bits of secret keys.

Is this the best key? I mean is there any relation between entropy/secrecy of the key vs length I choose from $N_S$?

What can be the largest possible secret key?

Any size. You can use the entropy as input for a DRBG (deterministic random bit generator) or KDF (key derivation function) and generate as many bits you want out of that.

  Will the entropy and secrecy of system depends on this length?

No.

  Assumption: Maximum length hence is $N_S$ bits of secret keys

No, it isn't. That's just the input data that contains a certain amount of entropy - or at least that's what we'll assume for the sake of argument.

  Is this the best key?

No $N_S$ (or any specific part of $N_S$) is not the best key. You want to explicitly extract the randomness from your data. $N_S$ may be biased.


PKCS1 v 1.5 Signature questions I'm crash studying the public key cryptography topic and I have a few questions about how signatures are created.

So are digital signatures just encrypted hashes? If that's the case then I can hash my symmetrically encrypted message, pass it with the signature maker with my private key, then it can promise authenticity and its data to be untampered (cause you'll have to recompute the hash on the other side)? Will the same private key and same hash give the same signature? On the other side what the verifier does is to create its own version of the signature and matches it with the received signature or does the public key have the ability to decrypt a message encrypted using the private key?

Sorry for all the questions i just started on this last night. Thanks in advance!

PKCS #1v1.5 signatures are basically signed hashes. Therefore, it is possible to extract hash and applied hash algorithm (in ASN.1 DigestInfo format) from properly signed signature.

In some old terminology, this operation may have been referred to as "encryption with private key". However, this terminology should be deprecated as the private key operation does not provide security you would expect from encryption (confidentiality) but instead it allows to ensure that signing has been made with private key matching public key used in verification (authenticity).

See RFC 3447 / PKCS #1 v2.1 for new version of PKCS standard. It calls the underlying signature primitive RSASP1.

Quoting that document:

  The main mathematical operation in each primitive is exponentiation,
  as in the encryption and decryption primitives of Section 5.1. RSASP1
  and RSAVP1 are the same as RSADP and RSAEP except for the names of
  their input and output arguments; they are distinguished as they are
  intended for different purposes.


Where to find a comprehensive content on security proof systems in cryptography Proof systems (provable security) are seen in many research papers related to cryptography and security. Where would I be able to find a comprehensive resource covering the purpose and the fundamentals of proof systems, and its common approaches such as the random oracle model method?

First, as a heads up "approaches to provable security" or "approaches to security proofs" (which it sounds like you are interested in) means something different than "proof systems" in cryptography. Proof systems are a specific construct that are studied within cryptography (similar to encryption or signatures), of which zero-knowledge proofs are the best known example. The fact that there is a naming collision here is unfortunate, but its best to just keep it in mind and sometimes uses more awkward phrasing to avoid the collision.
There are a number of slightly different competing notions of "proof systems". I don't know a resource that collects them all into one document, but two popular ones are:

Bellare and Rogaway's "Game-playing" model, which you can find exposition on here

The "simulation" proof technique, which you can find exposition on here

As for the random oracle model, I believe chapter 6 from Katz's book Digital Signatures is probably a good pointer, although if you do not have institutional access it may not be freely available.
EDIT: Browsing eprint, I found this chapter on hybrid arguments, which also may be interesting.


Can we calculate AES-CBC-PKCS7 ciphertext length based on the length of the plaintext? I am currently using AES256 in CBC mode with PKCS7 Padding to encrypt some data. It seems like the output size is not always a power of two, which was what I expected.

Is it possible to calculate the size in bytes of the output, knowing only the input data?

PKCS7 uses mandatory padding. Even if the length of your data is a multiple of your block size, it will pad.

output_size = input_size + (block_size - (input_size % block_size))


Obfuscate an "I'll reveal if you do" function Is there any cryptographic obfuscation scheme that will let me obfuscate a program that reveals my secret, if you reveal yours?

Formalization.  Let $C(\cdot),V(\cdot)$ be a secure commitment scheme.  In other words, $C(x,r)$ is a commitment to $x$ under randomness $r$, and $V(\cdot)$ is the corresponding verification function, so that $V(C(x,r),x,r)=1$ and $V(C(x,r),x',r')=0$ if $x\ne x'$.

For instance, one example commitment scheme is $C(x,r) = H(x \;||\; r)$ and $V(c,x,r)=1$ if $H(x \;||\; r)=c$, $0$ otherwise; where $H$ is a cryptographic hash function.

Suppose Alice has a secret $x$, and she publishes a commitment $c=C(x,r)$ to her secret.  Suppose Bob has a secret $y$ of his own.  Can Bob build a obfuscated program $P$ so that, when you run $P$ on input $x,r$, it outputs Bob's secret $y$, but the source code of $P$ doesn't reveal anything about Bob's secret to someone who doesn't know Alice's secret?

To make this precise, we can define the function $f$ by $f(w,q) = y$ if $V(c,w,q)=1$ and $f(w,q)=0$ otherwise (in fact I don't really care what the output is, in the latter case, as long as it doesn't reveal anything about $y$).

My question. Can Bob obfuscate $f$ to get a program $P$ that computes the same functionality as $f$ (so $P(w,q)=f(w,q)$ for all $w,q$), but where the source code of $P$ reveals nothing about $y$?

Can this be done in a way that is efficient enough to be practical?  I am fine with a solution for any commitment scheme of your choice: you can co-design the commitment scheme and the obfuscation method.  I am fine with the random oracle model and any plausible cryptographic hardness assumptions you might want to make.

Motivation. This would help with the construction of cryptographic fair exchange protocols, where intuitively we want Bob's secret to be revealed if Alice's is (except there are many more details I'm omitting that are out of scope for purposes of this question).

One thing that makes me think it might be doable is that this is a lot like a point function, which we do know how to obfuscate.  The difference here is that the obfuscator (Bob) does not know Alice's secret $x$ -- he only knows the commitment $c$ -- whereas the standard methods for obfuscating a point function would require Bob to know the secret value $x$.  So, the standard methods for obfuscating point functions do not immediately solve this problem... but can they be adjusted or extended somehow?  Alternatively, I know there have been recent breakthroughts in indistinguishability obfuscation; might those help with this obfuscation task?

If there is _______________ obfuscation scheme for such $\hspace{.03 in}f$s then there is a scheme

that does what you describe, where _______________ is either "a differing-inputs"

or "an extractability", depending on how you define "doesn't know Alice's secret".

Note that if there is no a-priori bound on the length of $x$, then the $\hspace{.03 in}f$s will have to be Turing machines with unbounded input length rather than just circuits. $\:$ In order to obfuscate such programs with the latter paper's candidate construction, one needs (publicly verifiable) SNARKs instead of just SNARGs.

However, if there is an a-priori bound on the length of $x$ or the commitment scheme's

verification function is sufficiently parallelizable (for example, if it follows a Merkle tree),

then one can replace the FHE scheme with a leveled FHE scheme.

On the other hand, this paper gives an argument against

the plausibility of the types of obfuscation that I linked to.

I see a lot of papers mentioning that standard assumptions suffice for the existence of a pseudorandom generator with linear stretch in NC1, although I cannot actually find any good candidate for that. $\:$ If there is one, then by chaining it to make the stretch sufficiently large and applying Naor's construction to the resulting PRG, one gets a commitment scheme whose verification function is in NC1. $\:$ Observe that

the $\hspace{.03 in}f$s are computable by just ANDing the output of the verification function with each bit of $y$.

Thus, if there is a pseudo-random generator with linear stretch in NC1 and a

_______________ obfuscation scheme for NC1, then there is a scheme whose

commitment is slightly interactive but otherwise does what you describe.


AES plaintext is smaller than 128 bits I'm currently developing a AES implementation in a graduation project at university.
As far as I know, AES uses a 128 bit block length as input .
if the entered string to encrypt is not 128 bits such as 32 bits .
what should be done for data that is less than 128 bits ? What's the best solution ?

It really depends on the block mode that you are going to use. If you want to use something like CBC, have a look into PKCS#7. If you were to use CTR mode, then you do not require any padding, as the input will always be in chunks of 16 bytes, and you use as much of it as you require.


Encryption algorithm with shortest ciphertext for long strings EDIT:
My original problem was that if I have to encrypt large amounts of data, AES would expand the data even more, but this is not the case. This question states that AES does not expand data at all.
ORIGINAL QUESTION:
I have a list of data URIs containing image data that I need to encrypt and save to a file. On average, the data URIs I need to save are thousands of characters in length and may get longer depending on how I configure my system. Currently, I am using the AES encryption algorithm.
What encryption algorithm would provide the shortest resulting ciphertext for strings of this length?

The general method for shortest ciphertext goes

Compress [but see cautionary note], perhaps using a general-purpose lossless compression such as (among many) Deflate or LZFSE; or some context-aware compression.
Encrypt, using authenticated encryption such as (among many) AES(-256)-GCM-SIV.
If the context requires, reformat to fit requirement, e.g. as Base64.

Decryption undoes each layer in reverse order. It is critical to use authenticated encryption or (much preferably, and) a robust de-compressor to avoid all kind of attacks, or crashes when deciphering an invalid ciphertext or decryption key.
For “a list of data URIs (that) are thousands of characters in length”, compression in step 1 will I guess reduce size by more than 1/4. It can outweigh the (small, constant) expansion in 2, and the ≈1/3 expansion of Base64 in step 3.
CAUTION: with compression, the size of ciphertext will reveal something about the size and compressibility of the plaintext, when normally encryption reveals only the size. This is known to be an issue in some contexts (including, digitized voice). Knowledge about the nature of the URI and what's confidential in them would be required to determine if that's an issue . If in doubt, don't compress.
Note: if size is paramount, and it is not an issue (or perhaps, if it is desired) that encryption of the same data with the same key always yields the same ciphertext, then it is safe to use a constant (e.g. all-zero and implicit) Initialization Vector in an authenticated encryption with the aforementioned AES-GCM-SIV.


Which is the fastest way to find a member of a subgroup with known size modulo prime $P$, with know factorization of $P-1$?->$x$ with $x^s \mod P = 1$ Assuming you know the factorization of used prime $P-1$
$P-1 = s \cdot f_2\cdot f_3...f_i$
Now you want to find a member of a subgroup $\mathbb{Z}_s$.
This means any $x$ with
$x^s \equiv 1 \mod P $

Naive way whould be selecting a random value $x$, compute $x^s$ and check if it is equal to $1$.

Another way I found online:
transform to disc. log
This first first computes a prime root $g$ of $P$. With this you can rewrite the equation:
$x^s \equiv (g^k)^s \equiv  (g^s)^k \mod P$
And computes a $k$ with Shanks' baby-step giant-step algorithm.

Is that the best/fastest way to go? Does it help if $s$ is a prime?
Is there a faster way if you are allowed to change $s$ and $P$ as well?
e.g. instead finding $x$ look for a fitting P' instead. For this fix $x$ to any number of choice $x_{const}$ and search for a  $P'=s \cdot f +1$
$x_{const}^s \equiv 1 \mod P' $

(Trivial $x$ like $x = 1+n \cdot P$ do not count here)

Is that the best/fastest way to go?

Well, unless you give some criteria, whether it's the best is unanswerable.  However, it might not be the fastest; you could just note that $k = f_2 \cdot f_3 \cdot … \cdot f_i$ and skip the baby-step-giant-step algorithm entirely.

In addition, if all you want is a random element of the subgroup, you don't need to find a generator.  Instead, all you need to do is select a random value $r \in [1, P-1]$, and compute $x = r^k \bmod P$ (using the above definition of $k$); if $x \ne 1$ (true with probability $1 - 1/s$), that's what you're looking for.

BTW: why do you think you need $x$ to be a prime?


Do I need to encrypt the IV? For example, I'm using AES-CTR.

I use fixed (random generated) key and random IV. I know that I have to encrypt key but I don't know about IV.

If I will encrypt 1 block of data with fixed key and first IV then encrypt another block of data with fixed key and second IV - does this violate the security of AES-CTR?

AES-CTR uses a nonce - a number used once - rather than an IV for creating the initial counter value. This nonce is actually just an octet stream / byte array rather than a number; you could think of it as an encoded unsigned number.

So in principle, CTR mode doesn't require an IV. However, as there are many ways of creating the initial counter value, most implementations simply allow the user to provide it for them. This then is usually called "the IV", as it is called that in other modes of operation such as CBC.

Generally however the full IV is not random; only the first (leftmost) bytes that are part of the nonce are random, if the a random nonce is used at all.

  For example, I'm using AES-CTR.

As each mode uses the IV differently, I'll just focus on AES-CTR.

  I use fixed (random generated) key and random IV.

So that's a bad idea, I would only randomize part of the IV if CTR mode is used. Using a random key is fine of course.

  I know that I have to encrypt key but I don't know about IV.

You only encrypt a key if you need to establish a key with a receiver and store it with the ciphertext, or to protect it locally. But in the end, you cannot encrypt all keys as every encryption will require another key...

You should never ever encrypt an IV and include it in your question. In AES-CTR the encrypted IV would be identical to the first block of the generated key stream that is XOR'ed with the first plaintext block. If you XOR the encrypted IV with the first ciphertext block you would get back the plaintext block. Never-ever encrypt the IV with the key used for the cipher mode itself.

  If I will encrypt 1 block of data with fixed key and first IV.

For AES-CTR the IV will be the first counter block, as indicated in the first part of my answer. There is only one Initialization Vector per message. So there is no such thing as a "first IV" - and definitely not a "second IV".

  then encrypt another block of data with fixed key and second IV

The definition of AES-CTR is that you encrypt the next block of data with the second counter block value, and then XOR it with the plaintext.

If you mean a block of data from a second message, then encrypting with a second random IV is likely secure, but see the description above w.r.t. creating the IV values and remind yourself that collisions may occur if you encrypt many messages this way, as random IVs are vulnerable to the birthday problem (i.e. you may get a collision sooner than you would generally expect).

  - does this violate the security of AES-CTR?

So no, unless...


Off-the-record communication Is my protocol correct?

For fun, I tried to design a protocol that would allow off-the-record communication. I'm not sure it works, I have a feeling there might be a problem with it that I'm not seeing. Please tell me whether you see a problem with it.

Here's a dramatization of the protocol I'm imagining:

  Alice wants to send a message to Bob such that Bob would know it was sent by Alice, but couldn't prove it to Dan.

  Alice creates a disposable persona Charlie (an RSA keypair) and talks to Bob using Charlie.

  Charlie: "Hello Bob! I wish to send you a message that you'll know is from Alice, but couldn't prove to anyone else!"

  Bob: "Okay, here's a string X, it's the public key out of an RSA keypair I just randomly created, which I know for a fact you didn't tamper with."

  Charlie: "Cool, I got X, but I'm not including it in this message. Here's Z, a random string I just came up with, which I know for a fact that you didn't tamper with."

  Bob: "Cool, here's Y, which you can verify is the private key of X. Now let's take (Y xor Z) to be our W, which is a number we both know is random, but that none of us can prove to outside parties that it's not random. We're not sending W over the line because we both know what it is."

  Charlie: "Here's the message M I want to prove to you is sent by Alice. I'm sending you (SHA1(M) xor W) signed by Alice's private RSA key."

From Bob's prespective, everything's legit. He knows that no one could know what the number W was before he revealed the private key Y. Thanks to RSA, he knows that Alice made the message (SHA1(M) xor W), meaning that Alice intended to send the message M.

But if Bob were to show these messages to Dan, he couldn't be sure that Alice indeed sent M; perhaps Bob is trying to cheat him? Perhaps Bob composed message M himself, with no connection to Alice, and built the Charlie persona himself just to make it look like Alice sent the message? Let's see how Bob could have done that.

Maybe Bob obtained, in some way, an arbitrary string F signed by Alice's keypair from a past communication with her. He calculated (SHA1(M) xor F) and called it W, so now he can say he has Alice's digital signature on (SHA1(M) xor W), which is just (SHA1(M) xor (SHA1(M) xor F)) which is just F. He created the random keypair X and Y, and calculated Z, which is (Y xor W), which makes W be (Z xor Y). Then he created the disposable Charlie persona and constructed the entire fictional thread of conversation between them which includes all these numbers.

Bob knows he didn't do all of that, but Dan can't be sure, and thus our objective is reached.

Are there any problems in this protocol that I didn't think of?

Both Ram's and Ilmari's protocols allow forgery.

(The "other party" is either Charlie or Alice, depending on

whether Ram's or Ilmari's protocol is being attacked.)

Mallory receives either "Alice" or $m_{real}$, and sends to Bob either "Alice" or $m_{fake}$, respectively.

Mallory receives from Bob either an RSA public key or

a hash, and sends the same thing to the other party.

Mallory receives a random string the other party, and

sends $\:$ that_string $\oplus \hspace{.02 in}H(m_{fake}) \oplus H(m_{real}) \;$ to Bob.

Mallory forwards the next two messages (without changing them).

(Incidentally, I came up with that attack when I was formalizing the content-deniability proof.)


Key exchange resilience to DoS attack I am designing a user registration protocol for a system where I control both clients and servers.  The aim is to establish a symmetric key for subsequent authentication, while minimizing the work load on the server side.  The security concerns are less about privacy than about integrity of the system and resistance to DoS attacks.  I thought about doing something like this:

Client generates an RSA public-private key pair
Client sends public key to server
Server returns randomly generated key, encrypted in the public key

Is there any risk that malicious clients may choose public keys that cause undue work load on the server?  Or, other problems?  Is there a better way to minimize load on the server in the face of malicious clients, while still insuring the security of the key exchange for cooperative clients?

Steps 5 and 7 remain very important even when one ignores DoS attacks.

$\;\;\;$ The RSA key-pairs use   e = 3

$\;\;\;$ Server signs $\: \langle \hspace{-0.03 in}$ RSA_modulus , RSA_ciphertext $\rangle \:$ and returns that to Client in step 3

$\;\;\;$ If computation is significantly more of a bottleneck than communication,

$\;\;\;$ then Client computes a sufficiently accurate estimate of its modulus's

$\;\;\;$ reciprocal in step 1 and sends that estimate to server in step 2

$\;\;\;$ In general, if step 6 is used then its estimate may need to go into what gets signed

$\;\;\;$ in step 5. $\:$ However, I believe the most straight-forward way to use estimates from

$\;\;\;$ step 6 would have the property that if an adversary changed it to a bad "estimate",

$\;\;\;$ then Server will either detect that or get the right result anyway.

$\;\;\;$ If step 6 is used and the use of its estimates has that property and the key(s)

$\;\;\;$ is(are) only used as input to a secure MAC scheme and/or a stateless IND-CPA

$\;\;\;$ encryption scheme and those schemes are only used for authentication

$\;\;\;$ and/or (possibly-already-authenticated-)encryption respectively, then the

$\;\;\;$ estimate from step 6 does not need to go into what gets signed in step 5.

$\;\;\;$ (It's fine if the encryption is used in a way that keeps state, but I only see a proof for the

$\;\;\;$ cases in which the underlying encryption scheme is IND-CPA despite not keeping state.)

Explanation of what's going on in #7:
By changing the honest client's estimate to a bad one, the adversary might be able to make

the event "server aborts" depend in a useful(-to-the-adversary) way upon what the resulting

key would otherwise have been and the randomness that would've been used to encrypt it.

The assumptions I gave are enough to guarantee that subsequent

communication remains secure despite such any such dependency.


Simplified Example of ECC to use in the classroom I have come up with the following rudimentary example of how ECC relates to asymmetric keys.
Is this a valid explanation of ECC and its relationship to asymmetry?
To only be deciphered by the person with the private key, it is necessary to use methods nontrivial in cryptography. To randomize the key, a set would be required to contain multiple solutions of which only one is the key.  Primes are also used in ECC, so a useful approximation for implementation would be Gauss' approximation to primes.
$ x^2+xy+x−y^3$
will be used as the basis for this example.
A random point may be selected from within the area of the curve, generated by a set of functions and a rotating exchange of variables.
The shake in the cipher would be:
$k(n)+(−y^3)+x+xy+x^2=kG$
for:
$k(n)+(−y^3)+x+xy+x^2=k$
There are four solutions for $y$ which allows one to be a random key in this example.  The asymmetry comes from the rotation of solutions to $y$, coupled with having to know that $y$ is the variable to be solved for.
Is this a good basic example of ECC?
For proof let Alice create the message $k$, and then create $kG$.  Bob receives $kG$ and has been told by Alice in a separate message that the key is negative and a solution for $y$.  Thus Bob knows to decipher $kG$ he must use:
$$y = -\frac{2^{1/3} x}{(\sqrt{(-27 k(n)+27 k-27 x^2-27 x)^2-108 x^3}-27 k(n)+27 k-27 x^2-27 x)^{1/3}} - \frac{(\sqrt{(-27 k(n)+27 k-27 x^2-27 x)^2-108 x^3}-27 k(n)+27 k-27 x^2-27 x)^{1/3}}{32^{1/3}}$$

To summarize and make my question as explicit as possible, is this a workable example for how asymmetry relates to ECC?

In short: the question does not explain well the notion of asymmetry in ECC; and the exposition is not how Elliptic Curve Cryptography works. A reasoning sidestepping the notion of Discrete Logarithm Problem over a finite group can not really explain asymmetry as meant in ECC.

Asymmetry is in the knowledge Alice and Bob have about the key, not asymmetry of a curve, or even asymmetry in variables in the equation, or different forms of the curve's equation. Foremost, ECC does not work as explained. Among discrepancies:

The variables in the "curve" are on discrete sets like $\mathbb Z_p$ or $\mathbb Z_{2^k}$, not real numbers $\mathbb R$; that makes a hell of a difference to the appearance of the "plot" of a curve with a given equation. A plot using real variables is traditionally used to illustrate how the group law is built; but (since a curve is with real variables, and it is used discrete ones in actual use) this is not how things are actually being used in ECC. Update: The Ars Technica article (page 2) quoted in comment does a good job explaining this.
The curve/equation is there to define an appropriate finite group (typically: where the Discrete Logarithm Problem is hard), and the actual crypto is built on top of that. There's no viable exposition of ECC (that I know) short of building that finite group structure. Update: the Ars Technica article does not even mention group, or associativity of the "dot" law.
Typically, the asymmetry lies in the difficulty of

computing $G+G+\dots+G$ repeated $k$ times in the group defined by the curve, which is easy;
finding $k$ from $kG$ (that is, $G+G+\dots+G$ repeated $k$ times), which is believed intractable.

ECC encryption schemes (that I know) do not work as stated in the question. In particular $k$ is not a message, but is the private key; $kG$ is the public key, and is unrelated to the message. That's perhaps because the Ars Technica article does not explain ECC encryption (it introduces asymmetric encryption using RSA in a very naive setup, but there's no viable transposition of that to ECC).

In order to introduce "how ECC relates to asymmetric keys" to a classroom (if that must be done for some reason), I suggest:

introducing post-symmetric cryptography with Diffie-Hellman key exchange, defined on a finite group initially illustrated by the relatively familiar $\mathbb Z_p^*$, because that's by far the simplest example;
probably, using as the defining problem for asymmetric cryptography signature (illustrated by El Gamal signature or its common variant DSA) rather than encryption (illustrated by El Gamal encryption), because the former is simpler;
showing that an appropriate Elliptic Curve equation over a (finite commutative field) can be be used to define a finite group usable for the above purposes;
stating that this is computationally attractive for a given security level, hence the growing interest in ECC (a true justification requires examining the running time of various known algorithms for solving the DLP, as well as introducing as competitor factorization-based asymmetric cryptography, probably RSA).


What kind of machine can generate 100-400 digits prime number? RSA The 64 bit machine's biggest number can be 2^63 (9,223,372,036,854,775,807). So what kind of a monstrous machine can generate 100-400 digits prime number? I probably don't understand something, so that's why I am asking.

You can simply combine mathematical operations on 64 bit numbers to create mathematical operations on bigger numbers. Just like a computer can combine bit operations to create operations on bytes and - yes - 64 bit values. In the end it is all binary arithmetic, calculations in current computers are performed on values of just 0 and 1.


RSA - What's to stop someone from using the same ciphertext to mimic private key holder? I've recently looked into fundamentals of RSA and think I understand how it works. However, there's one basic problem I can't seem to figure out. If someone received ciphertext for a given message, what is to stop them from sending the same message/ciphertext to other nodes in a network and pretending to be the private key holder?

For example, suppose Alice is a general and commands soldiers Bob, Sue, and Jerry. Alice generates private key (n, d) and public key (n, e) and sends (n, e) to all soldiers. The soldiers wait for Alice's instructions every day, which is either "attack" or "don't attack". Alice sends encrypted message "attack" to the soldiers via RSA as ciphertext to all soldiers. Now suppose one of the soldiers is malicious and has hacked Alice's delivery method (e.g. email), but not her private key. And on a separate day sends the same "attack" encrypted cypher text to all other soldiers. What's to prevent this from happening (even if you use padding which will always result in decrypted message "attack")?

I suppose one way is to add a timestamp to all messages and soldiers must make sure the date matches with current day. But it still doesn't seem right that someone can send the same exact message to others by just having the cyphertext... Or am I missing something?

If Alice is sending the encrypted messages then her public key isn't involved at all. She encrypts the messages for each recipient's $(n, e)$ pair individually, and sends them tailored messages.

In reality she probably sends the message encrypted with AES and only uses RSA to send each recipient their copy of the decryption key, a la PKCS#7's EnvelopedData.

The recipients have no way of knowing that the message actually came from Alice in this scheme. What she needs to do is sign the message (post-encryption, for best results), which does use her private key.

At this point, as you observe, there's still a replay vector. So the message would need to contain some way of identifying its freshness. A monotonic time stamp is an easy way, a monotonic message counter is another, or some sort of pre-arranged keyword from a shared code book (if you like whimsey).

So the recipient does:

Verify the integrity of the ciphertext and encrypted key using Alice's public key. (Prove it was sent by Alice)
Decrypt/derive the message encryption key using their private key.
Decrypt the ciphertext to reveal the original message.
Verify the time stamp / counter. (Prove it isn't a replay)
Respond appropriately to the contents.

The time stamp could have been signed but not encrypted, it just depends on whether or not that is itself sensitive data.


Is there need for message authentication if a public key is transmitted and then used to encrypt a symmetric key? First I'd like to note that I'm really a beginner at cryptography, and while this interests me and while I have researched it in the past few months, there is still a lot of things that simply aren't clear to me, and I would like to have them clarified so I can move on.

Let's say (because this scenario is what I have pondered and have thought about it for a while) that a client has generated a temporary RSA key pair, knows a server's public RSA key beforehand and needs to transmit its own public key securely to the server, in order to agree on a mutual, secret symmetric key, resistant to both eavesdropping and MITM. (I'm not aware of another, better way of negotiating a key when a client has a server certificate beforehand, but that would have more to do with my crypto incompetence.)

So the client encodes its (n, e) in a series of bytes and encrypts the data using the server's public key taking care of proper padding (using, say, OAEP). The server receives this data, decrypts it, and then wants to send its part of the symmetric key to the client. So it chooses this random key, hashes it using a secure hash algorithm (say, SHA-2), encrypts it using the client's public RSA key and fires it off into the network along with the hash.

The client now receives a hash and RSA-encrypted data. It decrypts it using its private key, checking the padding, hashes it, and compares to see if the hashes match.

My question is, is there even need for the hash in the server response so the client knows it hasn't been MITM'd (because the server has proved it decrypted the client's public key)? Can an adversary which doesn't know the server's private key ever change the RSA ciphertext so it passes the OAEP check routines? Even if this happens in some way, the client will end up using a garbage symmetric key—is this dangerous i.e. could be exploited in some way? And if there is legitimate need for the client to know at this stage absolutely no one has tampered with the message, is my simple plaintext hash-based authentication secure? I feel it is pretty obvious but I haven't stumbled upon its use so far, so there may be a good reason. I've heard that MACs are a good, secure solution, but obviously there is no shared secret at this point in the negotiation so I don't see how they can be utilized.

Am I missing something painfully obvious?

Notice: This answer assumes the user doesn't encrypt the initial contact because I misread that part. Will update accordingly in due course.

  Is there even need for the hash in the server response so the client knows it hasn't been MITM'd (because the server has proved it decrypted the client's public key)?

Sharing the hash of a key is a bit risky in general so I'd say shy away from doing that. In your case there's another reason why you shouldn't: You are correct about MITM, anyone can generate a key and send it back to the user.

The server must sign its response so the user is sure of its origin.

  Can an adversary which doesn't know the server's private key ever change the RSA ciphertext so it passes the OAEP check routines?

The probability of that happening is negligible. Even if it does your security doesn't depend on OAEP's sanity checks, it depends on the strength of RSA. See next for details

  [...] will end up using a garbage symmetric key—is this dangerous i.e. could be exploited in some way?

No. There are two ways to spot the problem: One is by signing the message - if there's a mismatch between the signature and the message, you know you can stop there.

If there's no signature, the plaintext should conform to some format (which could be a checksum encrypted along with the plaintext). If your application decrypts an altered message which does conform to the format, you're either very lucky or the app doesn't bother checking, which would make it absolutely worthless.

In your case, let's say the client gets a garbled symmetric key. The server (conforming to the protocol) would expect the client to say Hello! and instead would decrypt something along the lines of £Gh^T-31j3mqjgeY, which is a strong hint that something's amiss.

  is my simple plaintext hash-based authentication secure?

No. See the answer to the first question. Anyone watching the user will see his public key coming along, generating a new keypair for every server won't help at all.


Perfect Secrecy with 1 Time Complex Secret Cypher Is it possible to achieve perfect secrecy, unbreakable, unguessable, uncrackable by using a totally secret cypher?

The following conditions must apply:

Using the secret cypher only 1 time, so that no correlation between outputs can be achieved
The cypher itself has to be selected from a big pool of possibilities and having a high complexity so that an attacker would not have the option to just run through all combinations of cryptological operations (XOR, NOR, ShiftRows, Shiftcolumns, etc..)
So the attacker only knows the OUTPUT, and doesn't know the private key, doesn't know the cypher, and doesn't know the input. The attacker also doesn't know the size of the input in relation to the output, other than the input being < or = to the output, but not the precise size. Also the cypher would not be shared, so 1 time use by 1 person, and no other user.

Now using the cypher only 1 time is self explanatory. If you use it multiple times, and the cypher turns out to be weak, then probaly some kind of correlation attack between multiple outputs could be mounted to recover the input.
Now the complexity of the cypher should also be obvious. Like if you just pick a simple cypher like one of those old cyphers from the cold war, or one of a similar structure, then the adversary can just run through the possible combinations of all cryptological operations and then brute force each. It would slow him down, but not stop him.

Then some people might say that this would violate Kerckhoffs's principle, but I disagree.

Because if the cypher is secret, then obtaining the cypher is equivalent to obtaining the private key. If the attacker can obtain the cypher through some side channel attack, then with the same effort he can just obtain the key altogether and decrypt the message.

So a secret cypher that nobody knows, and it's complex enough, would be like Navajo code that was used during WW2.

Furthermore of the input itself is unknown, like the attacker doesn't even know what to look for, then even if he break N rounds of the cypher, he has absolutely no clue what to look for, and doesn't know how many rounds are there left. It doesn't even know if the algorithm he used is correct at all.

So it's not even like searching for a needle in a haystack. It's like having a haystack and no needle, the attacker doesn't even know what to look for.

Is it possible to achieve perfect secrecy, unbreakable, unguessable, uncrackable by using a totally secret cypher?

There are two different questions: Can you obtain perfect secrecy, and can you obtain an encryption algorithm that cannot be broken.

Perfect Secrecy

The One Time Pad is already a well known construction; Supposing that any construction that provides perfect secrecy is effectively equivalent to a One Time Pad, then using a secret cipher to obtain perfect secrecy will not be possible.

Supposing you did develop some other algorithm that provided perfect secrecy, keeping the algorithm would not be necessary or improve anything: Proof of this can be demonstrated with the One Time Pad, in that it is information-theoretically secure, despite the adversary knowing that a OTP was used to encrypt the message.

Unbreakable, Unguessable, Uncrackable, etc

In theory, probably not.

In practice, yes. However, once again, this is something that can/is achieved without resorting to keeping the algorithm secret; It is usually accomplished by creating designs that understand how an adversary will attack.

Then some people might say that this would violate Kerckhoffs's principle, but I disagree.

This is the very definition of a violation of Kerckhoffs's principle: The cryptosystem should be secure even if the enemy knows everything about it except for the key. It appears that you are not disagreeing about whether or not this scheme violates the principle, but whether or not the principle is worth upholding.

The algorithm as a key

Keeping the algorithm secret means that the algorithm becomes the key material. We can (and do) quantify the size of keys in terms of bits; There is a minimum representation of your algorithm that requires a minimum number of bits to represent.

The real problem with this is that symmetric keys should be shared between two parties; A secret algorithm is a symmetric key which must be shared between all parties. This dramatically increases the chances of exposure of the "key" the an adversary.

Because you have to execute it physically somewhere, somehow, you will have to ensure that copies of your program never end up on disk, never hang around in memory, that nobody ever sees the source code, and that nobody can watch what the CPU is doing. It is hard to make these guarantees even when many eyes are scrutinizing the source for mistakes.

Creating a cryptosystem on the assumption that an adversary does not know a single bit of plaintext implies that you only ever encrypt fully random blocks of data. If you are encrypting anything other then random data, this assumption will not be met and any further analysis is a waste.

Keeping the algorithm (and all plaintext messages) a secret in an attempt to thwart cryptanalysis is effectively equivalent to "hoping" that the adversary does not discover any flaws in the algorithm. "Hope" is not what cryptography provides; Cryptography provides certainty, preferably using as few assumptions against as strong of an adversary as possible. Instead of hoping, it is a proven superior practice to understand and design algorithms that can offer provable security.


Fast crytographically secure Pseudo-Random number generator in software What are the methods for generating pseudo-random numbers in software? I have seen methods where people use SHA implementations from openssl to hash a random message as source of entropy, or using AES or Keccak. But I have done some experiments and found them quite slow. They take around more than 3 clock cycles in an intel 3.3GHz i5 processor to generate a random bit. Whereas pseudo-random generators like ISAAC are blazingly fast compared to other methods. Now my question is

Why don't people use ISAAC for their implementations?
Is ISAAC not secure enough for cryptographic applications?
What are the other methods available for fast pseudo random number generation?

Thank you for your help.

What are the methods for generating pseudo-random numbers in software?
What are the other methods available for fast pseudo random number generation?

If you don't need to be able to repeat the stream of numbers, there is little reason not to use the methods provided by the operating system - namely, urandom on linux, and CryptGenRandom in Windows. The RDRAND CPU instruction is another option, though it is often times combined with other sources of random number generation, as not everyone trusts it completely (you can ignore this unless you are dead set on obtaining absolutely secure random numbers).
Otherwise, assuming a modern CPU with AES-NI support, nothing will likely be faster then utilizing AES in CTR mode. There is no need to hash the output, this is just eating cycles for no statistical or security benefit.

Why don't people use ISAAC for their implementations?

We can only conjecture at the motivations of others. Some reasons might include:

ISAAC is not a hugely well known algorithm in the same tier as AES or salsa20

If they are not aware it's existence, they will not use it

Their requirements may be satisfied with simpler/more commonly used algorithms
Secure random numbers are not always required; Often times, numbers that look random enough work just fine.
On the other hand, sometimes security is required, as well as conformance to a particular security standard. ISAAC is not a standardized (read: officially prescribed) algorithm for use as a PRNG by any official organizations i.e. NIST.

AES-CTR-DRBG is a standards compliant PRNG.

Is ISAAC not secure enough for cryptographic applications?

The jury appears to be out on this one. There was a reason to prompt the author to design ISAAC+, so while there is no known attack that breaks it outright, it does provide less assurance then a thoroughly reviewed design such as AES or salsa20.


Why is the market for cryptographic primitives non-commercialized? There are not many successful companies in cryptographic primitives market. Certicom holds many patents attached to the ECC. RSA Security probably made some profits from the patent. Are there more examples?
Why do people, scientists not try to commercialize their achievements, despite the fact that they could do so, especially under patent protection? I know it's harder to sell a product when most solutions are free. I know that a patent can makes it difficult to adopt technology in this market.
Nevertheless, it is still not clear to me why such powerful and universally useful technologies are being developed and made available in a charitable way.

Are there more examples?

About the only other example I can think of is Cryptography Research Inc (now owned by Rambus); however what they sell is methods of implementing primitives (in ways that are resistant to side channel attacks); however those operate just like the standard primitives, so that might not count.

Why do people, scientists not try to commercialize their achievements, despite the fact that they could do so, especially under patent protection.

They could certainly try; however they are quite unlikely to succeed.  A large part of the crypto community is quite allergic to anything patented (unless that patented has been released for all uses); unless what they have is considerably better than the alternatives, it'll not be used at all (and so the patent fees will be for nothing).

I know that a patent can makes it difficult to adopt technology in this market.

Think: close to near impossible.  Consider the case of OCB; it might be a bit better than the competing competitors as a way to do authenticated encryption (e.g. GCM); however GCM was patent free and OCB was not, no one uses OCB.
Yes, if someone did have (say) a practical FHE method (say, with homomorphic multiplication only 1,000 times slower than an unencrypted multiplication), you could make a mint (because there is nothing else able to come close to that); however this side of such a radical improvement, people will look for unencumbered alternatives (and be able to find them)
And, while we're on the subject: I believe Certicom's patenting (and aggressive threats of lawsuits) on some implementation methods for ECC (they certainly did not own the concept of ECC) slowed down the adoption of ECC by several years; certainly, the company I was with refused to touch it until the patent scenario was resolved.  Yes, Certicom did make some money; however I don't believe this was a net plus for the crypto community...


What's dh-composite test on badssl.com? The site badssl.com provides examples of bad (red icon) and good (green icon) uses of TLS for the purpose of testing TLS implementations. I'm a bit confused by the test called dh-composite. This explanation is given for the test: "This site uses an ephemeral Diffie-Hellman key exchange over a composite group." What exactly is a composite group? How would I test if given parameter set describes a composite group?

TL;DR: It allows the parameters to be backdoored and the solution is a simple primality test.

  What exactly is a composite group [and why does it matter]?

First, we need to get a quick understanding of the Diffie-Hellman Key-Exchange. Diffie-Hellman (DH) works on a mathematical construct named group, which is a set and an operation which adhere to some basic requirements. You can call any set with an operation that adheres to these requirements "group". Now the idea of DH is that you have two parties pick positive integers $x,y$ and let them compute and exchange $X=g^x,Y=g^y$ for some agreed-upon group element $g$. In practice this means that $g$ is an integer such that $1<g<n$ for some $n$, which we call modulus and the actual operation is $X=g^x\bmod n$ (same for $y$), using modular arithmetic which basically means "if you get beyond $n$, subtract $n$ from the number until it's smaller than $n$ again". Now it can be shown that multiplication with modular reduction ("applying the $\bmod$ operation") and the set of all integers $<n$ form a group, which we typically call $\mathbb Z_n^*$. What this is about is the case where $n$ is composite, ie not prime.

  "So why is a composite group bad?"

Well, it turns out that the security of DH relies on the fact that given $X,g,n$, you can't recover $x$ from $X=g^x \bmod n$. Now when we apply some special precautions to the structure of $n$ and the choice of $g$ this is actually assumed to be secure for sufficiently large parameter choices. However, when $n$ is large and composite and you now the factors of $n$ (and they're sufficiently small) you can in fact recover $x$. "Good, then I have a solid key-backup system now", you may think, but in fact such backdoored parameters have already been exploited in other cases, where an attacker replaced these parameters with their own, so they could eavesdrop on communication.

  "OK, so how does this work then?"

There's a mathematical trick, called the Chinese Remainder Theorem (CRT) which allows you to split your instance of $\mathbb Z_n^*$ into several smaller groups like $\mathbb Z_p^*,\mathbb Z_q^*$. Now if you can do an operation in all these groups you can transfer the result back into the larger group with minimal effort. So let's just for the fun of it suppose we wanted to do this. We'd pick an $n=a\cdot b\cdot c\cdot d$ where $a,b,c,d$ are 512-bit long each and $n$ is 2048-bit long. Factoring $n$ or taking the discrete logarithm in $n$ would take on the order of $2^{112}$ operations using the best known algorithm (the GNFS), but computing the discrete logarithm in $\mathbb Z_a^*$ (and the other three groups) takes a week of pre-computations for each group, followed by a few seconds to minutes per group and discrete logarithm (PDF), which is definitely feasible.

  How would I test if given parameter set describes a composite group?

In theory it's simple: You run a standard primality test against the parameters you receive and deny the connection if a composite modulus is used and accept the connection if the modulus is prime. The cost of this however is several times more expensive than not bothering and just accepting the parameters...

  [T]he modulus is a prime in this case

In this case we need a bit of background on group theory. Especially the fact that there are $\varphi(p)=p-1$ elements in $\mathbb Z_p^*$ and the fact that each subgroup has $q$ elements where $q$ divides $\varphi(p)=p-1$. This means that you have at least one subgroup with two elements (because primes $> 2$ are odd and $p-1$ is thus even) and one with $(p-1)/2$ elements. Ideally you want this number to be a prime (and thus $p$ being a safe prime) to avoid the Pohlig-Hellman attack. If it is not a prime, then you can split the (full, "composite") group into (many) smaller groups and solve the discrete logarithm problem in all those subgroups (which can be significantly faster than in the full group) and recombine the result using the CRT again. Now if you pick $(p-1)/2$ to be composite consisting of let's say 128-bit primes it's gonna be hard for other people to find these factors, especially if you use 16 und it's easy for you to compute discrete logarithms, having only a cost of about $2^{70}$ (which should be feasible) instead of $2^{112}$. So again it allows parameters to be backdoored and can be prevent with a "simple" primality test on $(p-1)/2$


What is a tweakable block cipher? Pretty simple question - but I can't seem to find much information about it.

What exactly is a tweakable block cipher?
How do they differ from traditional block ciphers?
What is the 'tweak'?  Is it just a sequence of bytes? Does it have any special qualities?
Are tweakable block ciphers more suited to any particular situation?
How does Twofish (a traditional block cipher) compare to Threefish (a tweakable block cipher)?

A block cipher is a family of permutations where the key selects a particular permutation from that family. With a tweakable bockcipher both key and tweak are used to select a permuation. So tweak and key are pretty similar.

The main difference are the security and performance requirements for a tweak:

Changing a key can be expensive, changing a tweak must be cheap.
Being secure when using attacker chosen, or at least related keys are not primary security properties of a cipher. Typically they're analyzed assuming a randomly chosen secret key. Related key attacks are rather academic. For example AES is still considered secure despite related key attacks against it.

Related or attacker chosen tweaks must still be secure. The tweak is often a counter, so tweaks are often related.

If you look at Threefish, tweak and key are pretty much treated in the same way. Changing either is cheap, and it doesn't suffer from related key attacks.

If on the other hand you'd take AES-256 and use part of the key as tweak, that wouldn't work well. Rekeying AES has a cost, and it suffers from related key attacks.

One application of tweakable block ciphers is disk encryption. You encrypt each block with the same key, but a tweak that corresponds to the block index. Currently we usually don't use a tweakable block cipher for this, but rather XTS mode, which turns a normal block cipher into a tweakable block cipher.

Such a tweak counter mode(not sure if it has a standard name) is generally nice. It's quite simple, similar to ECB. It's parallelizable and doesn't suffer from ECB's weaknesses. It also doesn't fail as catastrophically as CTR mode when a key(or key-iv pair) is reused.


Hash function such that fx(hash(s1),hash(s2)) = hash(concat(s1,s2)) First, I'm not a mathematician, so I may express this question awkwardly. Feel free to chuckle.

I'm wondering if there exists a hash function h such that for given strings s1 and s2, and string s3=concat(s1,s2), the hashes of s1 and s2 may be combined with a "hash combining function" g to give the hash of s3. That is g(h(s1),h(s2)) = h(s3).

For example, the string length function (as h) and addition function (as g) illustrate the property I'm after (even though string length would be a terrible hash function). For s1="abc" and s2="1234", s3="abc1234", h(s1) = 3, h(s2) = 4, and h(s3) = g(h(s1),h(s2)) = 7.

Merkle trees are similar in spirit to what I seek, except that I'd like the the intermediate hashes to be equal to the hash of the concatenation of underlying data (rather than a hash of child hashes).

For my intended uses, it is imperative that the hash function have an extremely low collision probability (akin to md5 or the sha series).

For what it's worth, the idea I'm considering is whether such a hash could be used to refer uniquely to a segment in graph of DNA sequence. Initially, the contiguous segment would be merely the hash of the segment, such as chromosome 1. As more is learned about large-scale genome variation, the contiguous segment might be decomposed into concatenated constituent segments, each of which is hashed. Users would refer to variation in sequence using the hash as an identifier, regardless of whether the sequence was contiguous or a virtual assembly of constituents. In this way, the hash value would effectively refer to both a path through these segments as well as the actual sequence of the concatenated fragments. For an example of such segments, see http://www.ncbi.nlm.nih.gov/assembly/GCF_000001405.28.

I'll consider only a non-adversarial model for the requirement of a low collision probability; that is, we are considering naturally-occurring strings only (which implies they are of bounded size; I'll limit it to $2^{64}-1$ bits, over 2305 Petabyte). However I'll consider that we need to reliably detect strings that differ only in a small consecutive segment. Caveat: in the following, hash is thus not used in its default meaning in cryptography.

My (new) proposed $h(s)$ is $256$-bit ($32$ bytes), among which the first $64$ bits are the number of bits in $s$ (truncated to the lower $64$ bits); and the $192$ last bits are a $192$-bit Cyclic Redundancy Check (CRC) of $s$, that is as the coefficients of $s(x)\bmod p(x)$, where $s(x)$ is the binary polynomial with coefficients the bits of $s$, and $p(x)$ is a fixed $192$-bit primitive polynomial. Conversions from bitstring to integer or polynomial, and back, are big-endian (the last bit corresponds to the least significant bit of integer or constant term of polynomial).

We define $g(h_1,h_2)$ as follows:

from $h_1$ and $h_2$ we get the integers $l_1$ and $l_2$ as the first $64$ bits, and build the first $64$ bits of $g(h_1,h_2)$ as $l_1+l_2$;
from $h_1$ and $h_2$ we get the polynomials $m_1(x)$ and  $m_2(x)$ which coefficients are the last $192$ bits, and build the last $192$ bits of $g(h_1,h_2)$ as the coefficients of
$$m_1(x)\cdot x^{l_2}+m_2(x)\bmod p(x)$$

The desired $g(h(s_1),h(s_2))=h(s_1\|s_2)$ holds, and its computation is fast, independently of the length of the original strings, noticing that $x^{l_2}\bmod p(x)$ is quickly computed by pre-computing $q_j(x)=x^{2^j}\bmod p(x)$ for $0\le j<64$, and multiplying modulo $p(x)$ those $q_j(x)$ corresponding to the bits set in $l_2$.

The hash of any bitstring $s$ of at most $192$ bits is its length $l$ (in binary over $64$ bits), followed by $192-l$ 0 bits, followed by $s$. For longer bitstrings, we can either use the definition, or use $g(h(s_1),h(s_2))=h(s_1\|s_2)$; both allow computing the hash of an arbitrary bitstring in time roughly proportional to its length.

A practical implementation of $h$ on a modern $64$-bit CPU can use a table of $2048$ pre-computed $192$-bit values ($8$ tables each $256$ entries each $3$ words of $64$ bits), and each additional $8$ bytes of $s$ will require only $8$ fetches of $3$-word entries, and few simple operations dominated by $24$ wordwise XOR. That's very fast.

It is trivial to make collisions, but that can not occur between bitstrings of different length, or which differ only in a small segment (of size no more than $192$ bits).

One suitable $p(x)$ is $x^{192}+x^{149}+x^{97}+x^{46}+1$, taken from Jörg Arndt's Table of weight-5 binary primitive polynomials with (roughly) equally spaced coefficients. We might however want to use a random primitive polynomial, which gives even better insurance that no collision occurs between naturally occurring strings (argument: with neither knowledge of the polynomial nor example hashes, it is computationally impossible to find distinct strings with sizable odds of hash collision).

My original (and in retrospect overly complex) proposed $h(s)$ is $256$-bit ($32$ bytes), among which the first $64$ bits are the number of bits in $s$, and the $192$ last bits are $2^s\bmod p$, where $p$ is a fixed $192$-bit prime such that $(p-1)/2$ is prime and $2^{(p-1)/2}\bmod p=p-1$.

Because $2^s\bmod p=2^{s\bmod(p-1)}\bmod p$, we can compute the hash of a string in time about proportional to its length, by first reducing $s$ modulo $p-1$.

We define $g(h_1,h_2)$ as follows:

from $h_1$ and $h_2$ we get the integers $l_1$ and $l_2$ as the first $64$ bits, and build the first $64$ bits of $g(h_1,h_2)$ as $l_1+l_2$;
from $h_1$ and $h_2$ we get the integers $m_1$ and $m_2$ as the last $192$ bits, and build the last $192$ bits of $g(h_1,h_2)$ as
$$m_1^{2^{l_2}\bmod(p-1)}\cdot m_2\bmod p$$

The desired $g(h(s_1),h(s_2))=h(s_1\|s_2)$ holds, and its computation is fast, independently of the length of the original strings.

A suitable choice of $p$ is $\lfloor325\cdot\pi\cdot2^{182}\rfloor+78356$, that is in hexadecimal ff41208fd469fe8cfdcfdb1b1a977095890fed10d7b6f8a3 (Note: $325$ was selected so that the leftmost byte of $p$ is FF, $78356$ is the lowest integer so that $p$ matches the other requirements).

Examples (with this choice of $p$)
The hash of the empty string is
0000000000000000000000000000000000000000000000000000000000000001
The hash of the one-byte string 00 is
0000000000000008000000000000000000000000000000000000000000000001
The hash of the one-byte string 4c is
0000000000000008000000000000000000000000000010000000000000000000
The hash of the one-byte string bf is
0000000000000008800000000000000000000000000000000000000000000000
The hash of the one-byte string c0 is
000000000000000800bedf702b960173023024e4e5688f6a76f012ef2849075d
The hash of the one-byte string c1 is
0000000000000008017dbee0572c02e6046049c9cad11ed4ede025de50920eba
The hash of the two-byte string c0c1 is
0000000000000010f4cf3a34057419042ee1a3d61690616770b8532f43255211

It is easy to find a collision, but it won't occur by accident, and only for strings of equal length. For example, the $24$-byte strings
000000000000000000000000000000000000000000000001 and
ff41208fd469fe8cfdcfdb1b1a977095890fed10d7b6f8a3 both hash to
00000000000000C0000000000000000000000000000000000000000000000002.

The above has the property that it is slightly difficult to come up with a string having a given random value in the right part (first preimage resistance); that's the discrete log problem. By making $p$ much larger, or using a group derived from point addition on an elliptic curve of known order, we can make that very difficult. This is nice to have, but not useful in the context of the question.

The idea in that other answer as modified per this comment also works, but is prone to collisions for messages differing by few consecutive bytes, contrary to all the methods considered in the present answer.


Current Status of mixnets for voting I am currently doing some research on universally verifiable mixnets, but it seems to me that there are too few papers about them after 2006 or so and most of them come from the team of Douglas Winkstrom.
Is this correct?

Can anybody point me to current references about mixnets and their use in voting protocols?

I found a few for shuffles.
The papers below will be good pointers for recent results.

Stephanie Bayer and Jens Groth: Efficient Zero-Knowledge Argument for Correctness of a Shuffle. EUROCRYPT 2012.
Melissa Chase and Markulf Kohlweiss and Anna Lysyanskaya and Sarah Meiklejohn: Verifiable Elections That Scale for Free. PKC 2013.
Melissa Chase and Markulf Kohlweiss and Anna Lysyanskaya and Sarah Meiklejohn: Succinct Malleable NIZKs and an Application to Compact Shuffles. TCC 2013.


Is it possible to sample HE ciphertexts using pseudo-random generator? I'm trying to sample HE ciphertexts which serve as ciphertexts encrypting some random values. I have realized a example program using Microsoft SEAL, which implements a variant of BFV scheme. Unfortunately, the ''noise budget'' of these uniformly-distributed ciphertexts is zero and thus they cannot support any further homomorphic evaluation. However, when I draw these ciphertexts from discrete Guassian distribution (with mean = 0), they have non-zero ''noise budget'' and work fine.

I'm quite confused about this result. Since BFV scheme is IND-CPA secure, its valid fresh ciphertexts should be indistinguishable from malformed ones (i.e., drawn from uniform distribution). However, the experiment result shows that a uniformly-distributed ciphertext does not form a valid ciphertext of BFV scheme with overwhelming probability.

Is there something wrong? Many thanks.

Since BFV scheme is IND-CPA secure, its valid fresh ciphertexts should be indistinguishable from malformed ones (i.e., drawn from uniform distribution).

IND-CPA says that someone who doesn't know the secret key cannot distinguish those two distributions.

  However, the experiment result shows that a uniformly-distributed ciphertext does not form a valid ciphertext of BFV scheme

You can only check whether a ciphertext is "valid" if you have the secret key. So there is no contradiction.

An analogy is a length-doubling PRG $G: \{0,1\}^n \to \{0,1\}^{2n}$. The output of the PRG is indistinguishable from the uniform distribution over $\{0,1\}^{2n}$. That doesn't mean that most strings in $\{0,1\}^{2n}$ are "valid outputs" of the PRG. In fact, only a negligible fraction ($2^n$ out of $2^{2n}$) of them are.


Is entropy being lost when the hash of a secret has a specific format? Bitcoin's mini private key format works by brute forcing random data to produce a secret so that when appending ? and then hashing with sha256 it will produce a hash that starts with 0x00. This way the user knows the secret is well formed and can proceed to hash it without appending ? to produce their private key.

This technique could be extended to include useful data in the hash "header", up to 2 bytes could be brute forced in a second or two.

However it seems that this scheme is reducing entropy of the secret i.e. if the attacker knows that a key is not valid by using a cheap sha256 hash, she will skip the expensive private to public key calculations. When the hash header is 1 byte around 99.6% of the random candidate keys were rejected, for 2 bytes it was 99.9983282%.

So does this scheme reduces the entropy of initial secret? If so how much?

From the linked page, a minikey is a 30-character string over the base58 alphabet with the first byte fixed to 'S', so effectively 29 characters. This gives a space of $log_2(58^{29}) \approx 169.88$ bits. Assuming that SHA is a random function, the probability of the hash starting with an 0-byte after appending a ? is 1/256, so this check loses 8 bits of entropy giving just over 161 bits of security.


Zero knowledge proof of exponents Assume a cyclic group $G=\langle g\rangle$ of order $q$ and $g_1,g_2$ are two generators of $G$. Alice computes and sends to Bob

$m_1=g_1^{a_1}g_2^{x_1}, a\gets R $ is a uniformly random element

$m_2=g_1^bg_2^{a_2x_2}, a,b\gets R $  are uniformly random elements

A malicious Alice selects $a_1 \ne a_2$ and $x_1 \ne x_2$ while a benign one chooses $x_1=x_2$ and $a_1=a_2$.

Is there a way to prove to  Bob that in $m_1,m_2$: $x_1=x_2$ and $a_1=a_2$ in a zero knowledge manner? Recal that $a_1,a_2,b,x_1,x_2$ should be kept secret to Bob the verifier.

On assumption $x_1 = x_2 = x$ and $a_1 = a_2 = a$, introduce linear polynomials over $F_q$: $X(z) = x z + \eta_x$, $A(z) = a z + \eta_a$, $B(z) = b z + \eta_b$. Consider two group elements: $g_1^{A(z)} g_2^{X(z)} m_1^{-z}$ and $ g_1^{z B(z)} g_2^{A(z) X(z)} m_2^{-z^2}$. First element is a constant (zero degree in $z$) if and only if the assumption holds. Nothing unusual/new at this point yet. Second element is linear in $z$ if and only if assumption holds, and this might look like an extension of Schnorr protocol. Now evaluate polynomials at some $z$ chosen as a challenge and invoke Schwartz-Zippel lemma for a bound on soundness error. At last, Alice must not be able to solve DL in this group (computational soundness) and must not know linear relation with $g_1$ and $g_2$ (setup).


Can Fully Homomorphic Encryption do comparisons? I encountered a simple function that even FHE cannot solve. Here's it:

int f(a,b,c,d){
   if(a+b>c+d) return a+c;
      else return b+d;
}

Since FHE is not order-preserving, one can't figure out whether a+b>c+d without the decryption key. That means even if practical FHE was implemented, f(a,b,c,d) cannot be computed in the Cloud independantly and securely. Not to mention linear regression, or more complex functions.

So I wonder with such an obvious limitation, why is FHE called "the holy grail of cryptography"?

This is simply not true. The above function can perfectly be homomorphically computed on FHE ciphertexts encrypting the inputs. There is no such "obvious limitation", and I wonder where your certainty comes from.

Asking whether FHE is Turing complete does not really make sense: FHE is a cryptographic primitive, not a general computing device. If this is what you meant, yes, we can evaluate any (polysize) function on encrypted inputs using the FHE evaluation algorithm. More precisely, we can evaluate any polysize boolean circuit on the input, in a private way (i.e. the inputs and the outputs are not leaked). If you want to evaluate Turing machines, it is more complicated in general (and you must give up on hiding the exact running time of the computation for this to be interesting), but it can also be done.

EDIT: from your comments, I now understand your question more clearly. Yes, FHE will never reveal the intermediate computation in the clear. This means that when you run a program on encrypted values, the computation pattern will have to be oblivious of the exact data. This does not make such computation impossible, as you seem to believe, but simply less efficient.

For example, suppose that you must evaluate the following program: if $a > b$, output $f(x)$, otherwise, output $g(x)$. Using FHE, you would proceed as follows: compute the bit $\beta$ which is $1$ if $a > b$, and $0$ otherwise, and output $\beta\cdot f(x) + (1-\beta)\cdot g(x)$. You can compute this on encrypted data, and you never need to know the exact value of $\beta$ to evaluate this program with FHE.

The FHE computation does not need "the plaintext result", it simply must rely on an algorithm which works obliviously of the exact inputs, and it is usually not hard to convert a computation in an oblivious computation (although it's not always obvious either).


Is factorization modulo a product of primes an NP-hard problem? For example, let, $p$ and $q$ be two large prime numbers. We set $n = p \cdot q$.
Now, let $a \cdot b = c \pmod n$.
Given $c$ and $n$, is finding the factors $a$ and $b$ computationally difficult?

I can alternatively ask, is integer factorization modulo a product of primes an NP-hard problem?

Your question has not a unique answer. In general case, finding $a,b$ is very simple. In this state, we can choose an arbitrary $b$(can be a prime number) and find the $a$ as follow:
$$a=c\cdot b^{-1} \pmod n.$$
Unfortunately, if you need that $a$ be prime, your question has no unique answer again. As an example, let $n=33$ and $c=20$. So we have:
$$7\cdot17=23\cdot31=20 \pmod{33}.$$


Can we solve the Hidden Number Problem in $GF(2^n)$? Is it possible to solve the Hidden Number Problem in extension fields? In particular in $GF(2^n)$?

Let's suppose an attacker knows some least/most significant bits of $r_i = a_i \times k$ in a given field $GF(2^n)$, for many uniformly distributed and known $a_i$ and a fixed and unknown $k$. Is it possible to recover $k$ ?

This is, as far as I know, an instance of the Hidden Number Problem originally introduced by Boneh and Venkatesan, used mainly to break digital signature schemes provided several signatures and partial knowledge of the respective nonces.

As far as I know HNP has always been applied in $GF(p)$, and furthermore the technique used to solve it, through Lattices and Closest Vector Problem, can't be easily adapted, IMHO, to $GF(2^n)$.

Rationale behind the question (not required for answering it):

I was comparing the authentications of GCM and Poly1305 in a specific, purely hypothetical, scenario where the attacker gets some knowledge of bits of the result of the authentication function, prior to the final addition of the encrypted nonce.

Let's assume we have single block messages.

Poly1305 authentication (without addition of encrypted nonce) is just:
$(c\times r)\mod {2^{130}-5}$ where $c$ is the message block and $r$ is the authentication key. I can see how to apply HNP to solve for $r$ in this case.

But GCM performs (I'm assuming to use an HW accelerator so that I can cheat in providing the final message with the aad and payload sizes):
$ (c\times h) \mod {x^{128}+x^7+x^2+x+1}$ where $h$ is the GHASH key. I don't see how to solve for $h$, having several partial information of the result for different and known $c$.

Yes, it appears that it can be solved in practical time in $GF(2^n)$, if the attacker gets $n+\epsilon$ random $a_i$ values, even if he gets a single bit of the $a_i \times k$ values.

The chief observation is that the mapping from $a_i$ to bit $j$ of $a_i \times k$ (which I'll refer to as $bit_j(a_i \times k)$) is bitwise linear (for constant $j$, $k$).

So, assuming that we have $a_i$ and the corresponding $bit_m(a_i \times k)$ values (for some known $m$), our first step is to find $n$ linear independent $a_i$ values (which, given $n+\epsilon$ random $a_i$ values, we'll have with good probability); we view this as a set of $n$ linear equations, and solve them in $O(n^3)$ time, giving us the mapping between any value $a$ and $bit_m(a \times k)$

Now, for polynomial representations of $GF(2^n)$, for every $i, j$ pair, there is a constant $c_{i,j}$ where $bit_i(a) = bit_j(a \times c_{i,j})$ for all $a$.

This observation allows us to find the linear mapping of $bit_n(a \times k)$ for any $n$, as $bit_n(a \times k) = bit_m(a \times k \times c_{n,m}) = bit_m( (a \times c_{n,m} ) \times k )$; in other words, to perform this mapping, we multiply the vector by the constant $c_{n,m}$, and then apply the mapping we already know (both of which are linear operations).

The result of this are $n$ linear maps giving us all $n$ bits of the product.  Then, we can solve these $n$ linear maps for the input that gives a 1 bit for the lsbit map, and 0 for the rest; the solution for this is $k^{-1}$, which immediately gives us the value for $k$.

I suspect that there are signficantly more efficient ways to solve this; however this algorithm should be enough to answer the question.


One Time Pad Low Bandwidth Doubt from the book Following is a sentence from the book "Cryptography and Network Security - Principle and Practices" by William Stallings [Fourth Edition]
Sentence -
"
... the 'one-time pad' is of limited utility, and is useful primarily for low bandwidth channels requiring very high security.
"
Can anyone please elaborate on low bandwidth , because I thing low bandwidth will make transfer of the key and ciphertext slower instead they should use high bandwidth isn't?
Book Link - http://uru.ac.in/uruonlinelibrary/Cyber_Security/Cryptography_and_Network_Security.pdf
Page Number - 79/983

For an OTP you need to distribute the OTP key stream out of band. That can be performed by e.g. bringing a data storage device to the other side. Let me explain.
The problem with an OTP key stream is that you cannot transport it over a secure transport channel without removing the claim of theoretical security. Similarly, you cannot simply distribute a seed for a PRNG, because the PRNG would have similar security as a stream cipher.
Because you cannot distribute an OTP without compromising its security it is limited to the amount of information that you distributed out of band.
How limiting this is depends on the application of course. Nowadays you can store several TB in a tiny flash disk. That's enough for many, many hours of video. Still, securely distributing such a disk would be troublesome; just sending it by regular post is obviously not a good option.
Another option would be to use quantum key distribution. However, implementations of quantum key distributions are not necessarily secure, and the speed may be a severe limit.
Fortunately, we've got a lot of ciphers that we don't know how to break, key ratchets and whatnot to give us practical security even for much smaller key sizes.


Confused with 128-bits AES round numbers The key size used for an AES cipher specifies the number of repetitions of transformation rounds that convert the input, called the plaintext, into the final output, called the ciphertext. The number of cycles of repetition are as follows:

10 cycles of repetition for 128-bit keys.
12 cycles of repetition for 192-bit keys.
14 cycles of repetition for 256-bit keys.

  Each round consists of several processing steps, each containing four
  similar but different stages, including one that depends on the
  encryption key itself. A set of reverse rounds are applied to
  transform ciphertext back into the original plaintext using the same
  encryption key.

So 10 cycles of repetition for 128-bits keys. This are the rounds:

KeyExpansions—round

keys are derived from the cipher key using Rijndael's key schedule. AES requires a separate 128-bit round key block for each round plus one more.

InitialRound

AddRoundKey—each byte of the state is combined with a block of the round key using bitwise xor.

Rounds

SubBytes—a non-linear substitution step where each byte is replaced with another according to a lookup table.
ShiftRows—a transposition step where the last three rows of the state are shifted cyclically a certain number of steps.
MixColumns—a mixing operation which operates on the columns of the state, combining the four bytes in each column.
AddRoundKey

Final Round (no MixColumns)

SubBytes
ShiftRows
AddRoundKey.

So my question is: it says 10 cycles, but does that mean that the initial round is performed once, the normal rounds 9 times, and the final round also once? Because the expanded key is 176-bytes, so the addroundkey function can be used 176/16 = 11 times.

Can someone give me help on the correct division of cycles on the 3 times of rounds (initial, normal, final)?

So my question is: it says 10 cycles, but does that mean that the initial round is performed once, the normal rounds 9 times, and the final round also once? Because the expanded key is 176-bytes, so the addroundkey function can be used 176/16 = 11 times.

For the 128-bit AES, that is correct.

InitialRound, which consists of AddRoundKey is performed once.

Rounds, which consist of SubBytes, ShiftRows, MixColumns, AddRoundKey is performed nine times.

Final Round, which consists of SubBytes, ShiftRows and AddRoundKey is performed once.

Also, you might want to check out this two flash animations which offer great insight into how 128-bit Rijndael (the cipher AES is based on) works and also allows you to view the intermediate results as the cipher progresses.


NIZK proof for randomization of DLOG One can have a NIZK proof for DLOG by applying Fiat-Shamir heuristic to Sigma protocol, such that one can prove non-interactively that $x$ is discrete logarithm of $X = g^x$. Then, in simulation based proofs, the simulator can extract the witness $x$.

What interest me is whether a party $P_2$ given $X = g^x$ and DLOG proof $\pi \gets (\{ \exists x' \mid X = g^{x'} \}, x)$ from a party $P_1$, can give another proof for the randomization of $X$. More precisely, $P_2$ samples a random $r$, calculates $X' = X^r$, and then gives a proof like $\pi' \gets (\{ \exists r' \mid X' = X^{r'} \}, r)$ or any other proof, such that the simulator simulating $P_1$ can later extract the randomized witness $x \cdot r$ either from the proof $\pi'$ received from $P_2$ or from the combination of both proofs $\pi$ and $\pi'$?

Please note that when I talk about proofs here I mean always non-interactive version.

NOTE: I know that Sigma protocol cannot be re-rerandomized. But, is there any other type of proof that will let you to prove this re-rerandomization and extract the witness?

Yes $P_2$ can generate $\pi' \gets (\{ \exists r' \mid X' = X^{r'} \}, r)$, which proves that he knows $r$ that is the Dlog of $X'$. Since $r$ is chosen by him and $X$ is public, he can do this just as any normal DLOG proofs.

However, $P_2$ cannot generate $\pi'' \gets (\{ \exists xr' \mid X' = g^{xr'} \}, xr)$, which I guess is what you actually want. This would require $P_2$ to know $xr$, instead of just $r$.


Does WEP protect message authenticity? The WEP secure channel works by sending $$IV||(m||CRC(m) \oplus RC_4(K,IV)$$ where IV is an asynchronous initial vector, K is an encryption key and CRC is a cyclic redundancy check function.

I know there are lots of attacks on this scheme. I also know that this scheme does not protect confidentiality, integrity or sequentiality. However what is meant when we say that in certain way it protects authenticity? The text I'm reading says:

  Message authenticity in WEP is not specically protected by a message
  authentication code. It is protected in the sense that an adversary
  cannot push a message which makes sense with an unused IV without
  knowing K. It is enough to know one plaintext and ciphertext to reuse
  the IV.

Why is authenticity protected in some sense but not integrity? To be honest the last two sentences of the last quotation make no sense to me.

It makes no sense since its nonsense. Let me explain why. Consider an attacker who captures a message of the form $(IV,c)$ for a plaintext $m$ that is not known to the attacker. The aim of the attacker is to "push" the message $m\oplus\Delta$ (e.g., the attacker wishes to flip some bits of $m$. Then, since CRC is linear, the attacker can compute $c'=c \oplus(\Delta,CRC(\Delta))$ and "push" the message $IV,c'$ which will decrypt to $m\oplus\Delta$.

Technically, one could argue that the text is just arguing that you can't push a message with an unknown IV and here I am reusing the IV. However, who cares if the attacker reuses or not; the recipient will accept reused IVs so the attack works.


Proving HMAC collision probability bounds? Could someone point to results or proofs about the probability of $$HMAC(k, m_1) = HMAC (k, m_2)$$ assuming the underlying hash function is SHA-256? Would those probabilities be higher/lower if $m_1$ and $m_2$ are not independent?

Please don't point to birthday attack results. I am only interested in the probability that the tags are equal given two messages (random or not) and a single key.

The following is a method of calculating the probability using the random Oracle model, where the random Oracle is substituted for the HMAC function:

$\mathcal{A}^{\mathcal{O}}$ works as follows:

Generate $m_1$ and $m_2$ in whatever way

set: $tag = \mathcal{O}(m_1)$

output: $[m_2,tag]$

and observe that $\mathcal{A}^{\mathcal{O}}$ has trivial runtime and makes only one query to the oracle. $\:$

This leads to:

$\operatorname{Prob}(m_1 ≠ m_2 \text{ and } \operatorname{HMAC}(k,m_1) = \operatorname{HMAC}(k,m_2))= \operatorname{Prob}(\mathcal{A}^{\text{HMAC}(k,\cdot)} \: \text{succeeds})$


Alternatives to FHE for secure function evaluation As a followup to a previous question I asked which was more related to Fully Homomorphic Encryption (FHE), what other cryptographic methods are available for computing a private function on public and/or private input? And, what are the benefits/limitations when compared to FHE?

In specific I am interested in Yao's Garbled Circuits construction and a newer publication I recently came across due to Parno et al., which uses functional encryption (aka attribute based encryption). If there are any others, I'd be interested in them too.

Yao's garbled circuit is simple to understand. First of all, note that if we can securely compute $\mathsf{NAND/NOR}$ of two input bit, we can perform any boolean operation. Yao's garbled circuit tries to achieve the same. Lets look at scrambled $\mathsf{OR}$ gate.

Alice creates a set of four keys, $K_{x=0},K_{x=1},K_{y=0},K_{y=1}$
She then creates 4 “boxes” for each of the table entries, $B_{00}=0,B_{01}=1,B_{10}=1,B_{11}=1$.
She then encrypt each box with the corresponding keys, for example, $B_{00}$ is encrypted with $K_{x=0},K_{y=0}$, permutes the box and send the box to Bob.
Bob gets the key corresponding to Alice's input from Alice and the key corresponding to his input by using $\mathsf{OT}^2_1$.
Bob computes the output by decrypting the only box he can.

NOT gate is even simpler and I leave it for exercise for you. Else, you can always fall on the famous GMW paper, "How to play any mental game."

For attribute based cryptography, you can have a look at the bibliography at the webpage of Liang. There is a good talk given by Waters at MSR website on his work on Unbounded HIBE and Attribute based Encryption.

Now to include few questions later asked by Mike,

Computation overhead: a lot of overhead, for sure. Theoretically, you are fine as long as the overhead is polynomial which is the case in Yao's garbled circuit. But in practice, it is a lot.
Any circuit: yes, as long as they are boolean circuit. NOR and NAND are universal gates.
Interaction is a requirement if you are trying to do Secure party computation. If you are fine with Secure function evaluation, then you can do away with interaction. All you need is a non-interactive zero knowledge proof. The drawback is that that NIZK is proven zero knowledge only in random oracle model. Recall that NIZKP helps in proving to the other party that the gates are constructed properly without any interaction. This will work fine if you are doing SFE because there is no binding on the second party to share the output to the first party.
The result are in clear, but here you are assuming authenticated secure channel. If you are in standard model of communication, there are ways to go around this as well in a very standard way.
Reusuability of the garbled circuit is a different issue. You can use proactive cryptosystem to make it reusable. Stand-alone Yao's garbled circuit is not reusable. (Proactive cryptography works in the scenario where you don't change the shares after some time epoch. It is first studied in the realms of secret sharing, where the first share are formed as in normal SS, but later on, when you need to redistribute the share for same secret, you construct a polynomial with constant 0 and redistribute the share as in normal SS.)
Jarecki and Shmatiko made a garbled circuit secure against active adversary by incorporating that the first party proves in ZK-way the correctness of every gate. Note that in garbled circuit, one party construct the circuit and other computes. It thereby, does not prevent against unfair adversary. Till now, there is no way to get fair computation using Yao's method
They can be made verifiable by a very standard way. I am not sure if all the standard methods can be applied or not.

The advent of FHE helps in most of these areas, but at the moment FHE is still in a baby-stage. I cannot wait for it to become very efficient.

Summary

|System | plaintext output | Circuit size | Reusable          | Verifible | Currently Practical | 1 block of AES |
------------------------------------------------------------------------------------------------------------------
|FHE    |       N          |      Any     |     Y             |     N?    |          N          |     1 week     |
------------------------------------------------------------------------------------------------------------------
|GC     |       Y          |      Any     | Y (special        |     Y     |          Y
|       |                  |              |    constructions) |           | (with caveats)      |    0.2 sec     |
------------------------------------------------------------------------------------------------------------------
|FE     |       Y          |       ?      |         Y         |     Y     |          ?          |       ?        |
------------------------------------------------------------------------------------------------------------------


Hash Function Formating Question If a hash function is written:

Hash(Hello||World)

Is that equivalent to Hash(Hello) +  Hash(World) or Hash(HelloWorld) ?

Similarly, is there any difference between Hash(Hello||World) and Hash(Hello,World)?

Typically, the notation || means concatenation, which is to say Hello||World is equivalent to HelloWorld.

Is that equivalent to Hash(Hello) +  Hash(World) or Hash(HelloWorld)?

So Hash(Hello||World) is equivalent to Hash(HelloWorld).

Is there any difference between Hash(Hello||World) and Hash(Hello,World)?

This depends entirely on what Hello,World is defined to mean.

Notation does not have absolutely defined meaning - what a symbol means in one context can be different from what that symbol means in another context.

The only way to know for sure is to check the definitions of the notation from wherever you found this.

If there are no such definitions, then it is safe to assume the most common/obvious meaning for the notation. However, if the notation is non-standard, then there may not be a common and obvious meaning for it.