Is authenticated encryption unnecessary if the message is digitally signed? Normally, it is necessary to use authenticated encryption if the message may be tampered with.  Can the authentecation be omitted if the message has been otherwise authenticated?

Yes, message authentication can be omitted when using an appropriate digital signature on the ciphertext.

A digital signature hashes the message, then encrypts the hash with a nonce and asymmetric key, which makes the security similar to HMAC.

The reason authenticated encryption is preferred is that it is generally less computationally expensive than a digital signature, and easier to build a MAC construct that is side channel resistant.


SHA-1 – Would using a SHA1 signature be a risk? If data (e.g. an e-mail, pdf file, xml content) is hashed using SHA-1 and then signed by a SHA-2 certificate, is this any bigger of a risk than using a SHA-2 hash with a SHA-2 certificate?

I assume in this scenario although the actual file content COULD be collided (as being hashed using SHA-1), in practice the risk is very small since the signature is made by a secure SHA-2 certificate.

In my question “SHA-1 – Why is it hard to find a certificate collision?” I stated colliding a certificate is harder than a PDF file. However, does this hold up for ANY kind of signed file? A certificate is basically a file with a signed hash. So what if I take a signed PDF? Or a signed e-mail? Would it still be hard to attack and why?

Yes, it is.

A chain is as strong as its weakest link. Strengthening one link, e.g. using a SHA-2 certificate instead of a SHA-1 certificate, will not strengthen any other link.

You cannot prevent someone tricking you into signing a SHA-1 collision, just by using a SHA-2 certificate. A SHA-2 certificate is a certificate that was signed using SHA-2 by the certificate authority that issued the certificate. Having such a certificate will not give you magic super powers. You will still have to use your own private/public key pair wisely.

Regarding the follow-up questions, you would of course have to generate the collision prior to signing it the first time. The second signature might be added in at least three different ways:

In parallel with the first signature, over the same data and consequently using the same hash. In this case you will obviously get a collision the second time as well.
Over the signed data including the first signature. It might be harder to generate an original collision that will still be collision for the second signer in this scenario. On the other hand, this doesn't matter unless the second signer gets the to-be-signed data with physical security directly from the first signer.
Counter signature of the first signature blob. Since the first signature blob is already compromised by a collision, the counter signature will by extension also be compromised.


Difference between Pure EdDSA (ed25519) and HashEdDSA (ed25519ph) My question refers to EdDSA as specified in RFC 8032.

I get from the RFC that ed25519 and ed25519ph are two different instances of EdDSA mainly differing in the fact that that in the case of ed25519ph the hash of the message is signed.

Step 2 of the Sign process is:

$SHA-512(dom2(F, C) || prefix || PH(M))$

where in the case of ed25519 the $PH$ function is the identity function and in the case of ed25519ph its for example an implementation of SHA512. However, the part I am curious about it that this isn't the only difference between the two.

According to the RFC $dom2(F,C)$ actually is also different:

  dom2(x, y):
  The blank octet string when signing or verifying
                    Ed25519.  Otherwise, the octet string: "SigEd25519 no
                    Ed25519 collisions" || octet(x) || octet(OLEN(y)) ||
                    y, where x is in range 0-255 and y is an octet string
                    of at most 255 octets.  "SigEd25519 no Ed25519
                    collisions" is in ASCII (32 octets).

What's the reason for that?
If this wasn't the case one could construct ed25519ph by simply hashing the message and passing it as input to an implementation of ed25519. The way its specified this construction wouldn't be compatible to an implementation of ed25519ph (because of the dom2 prefix).

This is just a preventive measure. Without this separation, an attacker knowing ed25519ph(m) would also learn ed25519(h(m)).

I'm not aware of any real-world protocol using both simultaneously and where that would be an issue, but it's not far-fetched to think that it could be the case.

Domain separation is good hygiene and has become very common in new designs.

The choice of dom2() being a blank string when using ed25519 was only made to remain compatible with existing implementations.


HMAC-SHA1 vs HMAC-SHA256 I have three questions:

Would you use HMAC-SHA1 or HMAC-SHA256 for message authentication?
How much HMAC-SHA256 is slower than HMAC-SHA1?
Are the security improvements of SHA256 (over SHA1) enough to justify its usage?

Would you use HMAC-SHA1 or HMAC-SHA256 for message authentication?

Yes.

That is a semi-serious answer; both are very good choices, assuming, of course, that a Message Authentication Code is the appropriate solution (that is, both sides share a secret key), and you don't need extreme speed.

  How much HMAC-SHA256 is slower than HMAC-SHA1?

Those sorts of crypto performance questions are quite platform specific, and so it's hard to answer definitively.  In my experience, I've seen SHA-1 (and hence HMAC-SHA-1) be about 30% faster than SHA-256; Your Mileage May Vary, of course.

Of course, the obvious comeback is "how much is this performance delta important to you?".  That rather depends on how fast you're adding/checking integrity tags.

  Are the security improvements of SHA256 (over SHA1) enough to justify its usage?

To the best of our knowledge, there is essentially no security difference between HMAC-SHA256 and HMAC-SHA1; with a sufficiently long key, both are impervious to brute force, and with a reasonably long tag, both will catch any forged messages with the expected probability.  There is a known weakness to SHA1 that allows someone to compute a collision in less time than expected; there is no known way to apply that to HMAC-SHA1, and so there are no known methods of attack (other than, as I mentioned just now, brute force, and guessing the tags randomly).


Application of Non-deterministic Processors in side channel attacks I was reading the abstract of "Non-deterministic Processors" paper by "David MayHenk L. MullerNigel P. Smart", in the abstract, they have mentioned the Kocher paper about "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems"

What is the application of Non-deterministic Processors on a side-channel attack?

Non-deterministic processors are generally sold as a method to vary processor timing and power.  To my knowledge they are theoretical as synchronous systems, as I have never seen any literature where one has actually been constructed.  The premise is that if you have varying instruction order, and completion time, you then have some level of robustness to side-channel attacks.  It is important to note that these are still synchronous systems.  The closest work that I know to this where hardware exists was body of probabilistic computing work by Palem, George and Marr.

You could easily make a non-deterministic system with asynchronous logic.  When I make asynchronous systems, creating noise is trivial because of the completion trees, and I do add random noise to the completion logic to slow it down as a verification of robustness against EMI.  This method would make the circuits robust to a side-channel attack due to random completion times for all logic.  Having said that, the dual-rail encoding of asynchronous circuits means that you cannot have a power attack, but only a timing attack.  You could size the completion trees so that they always required the same time; however, that would eliminate the speed gains of the asynchronous circuits.


Secure communication protocol for equality test I'm solving a theoretical problem with two entities, each having one secret number. They need to find out whether these number equal without disclosing their number when they differ.

Easy solution is to encrypt/hash both numbers and compare these encrypted messages/hashes. In this case, it is still, in theory, possible to compute/to guess the other secret number (even if is very improbable). For example when there is very limited number of possible secret numbers.

Is there any protocol that is 'totally safe' - meaning that an entity cannot guess the other secret number regardless of its computation power?

Equality of single bits is the XNOR function. There is no unconditionally secure protocol for XNOR in the presence of malicious adversaries. We prove this in:

  HK Maji, M Prabhakaran, M Rosulek: Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation, TCC 2009.

There is a simple protocol secure against semi-honest adversaries, but keep in mind that if you know your input bit, you know whether your bit is equal to the other guy's bit, then you know the other guy's bit. So the secure protocol is "just tell the other guy your input."

On the other hand, equality of strings 2 bits or longer does not even have a protocol secure against semi-honest adversaries. This follows from an old characterization of Kushilevitz: the function is not "decomposable".

  E Kushilevitz: Privacy and Communication Complexity. FOCS 1989

You can get equality test if you assume an ideal oblivious transfer. This is not unreasonable since you can get oblivious transfer from physical assumptions (like noisy channels). The private equality test described in this paper is pretty straight-forward, and unconditionally secure against semi-honest adversaries assuming an ideal oblivious transfer:

  B Pinkas, T Schneider, M Zohner: Faster Private Set Intersection Based
  on OT Extension, Usenix 2014


HMAC-SHA-512 with a 256-bit key I am implementing hmac-sha-512 in an integrated system. However, one subsystem is only supports the use of 256-bit keys.

I read in https://tools.ietf.org/html/rfc4868 that:

  However, note that [HMAC] strongly discourages a key length less
  than the output length.  Nonetheless, we describe handling of
  shorter lengths here in recognition of shorter lengths typically
  chosen for IKE or IKEv2 pre-shared keys.

And also:

  These key length restrictions are based in part on the
  recommendations in [HMAC] (key lengths less than the output length
  decrease security strength, and keys longer than the output length do
  not significantly increase security strength), and in part because
  allowing variable length keys for IPsec authenticator functions would
  create interoperability issues.

In what way does using a 256-bit key rather than a 512-bit key with HMAC-SHA-512 decrease its security strength? Is it not advisable to proceed with a 256-bit key?

In what way does using a 256-bit key rather than a 512-bit key with HMAC-SHA-512 decrease its security strength?

It doesn't, in any real sense.  With a 256 bit key, it can be broken by searching through a key space of size $2^{256}$; a simple computation on the energy required to do such a search shows that it is ludicrous (and is the source of the 'Dyson Sphere' comment made by CodesInChaos).

If we assume that the attacker had a working reliable Quantum Computer, he could, in theory, attack the system by performing $O(2^{128})$ HMAC-SHA512 evaluations, which is still not very practical, but not nearly as ludicrous.  However, to achieve such a 'low' number of computations, he would have to perform those computations serially (which would extend the total time taken to do the search to something longer than the current age of the universe).  Yes, he could speed things up by using multiple parallel Quantum Computers, but it turns out that drastically increases the already huge number of evaluations required.

There is no known way to attack the system with any less effort; hence the system is quite secure against any even remotely plausible attacker.


RAR brute force cracking speed I have been playing around with cRARk and was astonished by the low speed. On a 2015 high-end GPU (GeForce 980 ti), it took roughly 4h 50min to test all passwords composed of an 8-character prefix and 6 small latin alphabet letters (AAABBBCC $a * in the format cRARk uses). This is just over 300 million passwords, which corresponds to 18500 passwords per second.

The RAR file is 164 bytes long and has the identification string:

52 61 72 21 1a 07 00

Is it hardware limitation (I've had performance problem with the GPU), is it that cRARk is slow or is it the nature of RAR archives that they are this slow to crack?

Your file is in "RAR4" format (alternatively called 2.9). This means it is not using PBKDF2 as version 5 is, but it still uses an iterative hash. A custom one based on SHA-1, with $2^{14}$ "iterations" each feeding some amount of data into SHA-1. Depending on the length of the password and whether a salt is used, this may not correspond exactly to $2^{14}$ iterations of the SHA-1 compression function.

Assuming a one-to-one correspondence between iterations and SHA-1, your 185000 passwords per second corresponds to about 300 million SHA-1 hashes per second. According to what I can find online (e.g. this), the raw SHA-1 hash rate of your GPU should be about 10x that, but considering the somewhat special structure of the RAR hashing function, it is not obvious that it should reach that, especially with all password/salt lengths.

I.e. your result is not unreasonable, though there may be room to push it further by a factor of ten or so if the hardware is problematic or the software poorly optimized.

(There is no public format definition for RAR formats before 5.0. The above is based on reading the proprietary, but freely available UnRAR source.)


Proving that 2 numbers are different without revealing them Imagine that Alice generates a number $a$ and Bob generates a number $b$. Is there a way that they can check that $a \not = b$ without revealing any information on $a$ and $b$ (Alice must not know $b$ and Bob must not know $a$) ?

Yes, this is a standard secure two computation problem. There was a classic paper discussing this from many years ago called Comparing Information Without Leaking It. There are more efficient methods today (in fact, the oblivious transfer method today is very efficient using oblivious transfer extensions).


JSON AES-128: Security against known plaintext attack I have a system where I am transmitting JSON messages securely (using for example AES-128), where each message has the same format.

For example:

{"d":{"status":"success"}}

{"d":{"error":"Message length too long"}}

Where every plain-text message is guaranteed to start with {"d":{ and end with }}

Suppose the attacker knows this fact.

Does this reveal information that could lead to a security exploit (the attacker finding  the key)?  If so, what would prevent this?
If there is no security risk, what property of encryption prevents it from being an issue?

EDIT

This is related to my other question about the attacker knowing parts of the plain-text, but I would like to know why it isn't a problem.

Suppose the attacker knows [some part of the plaintext]
Does this reveal information that could lead to a security exploit

Given the rest of your notes, that you're using CBC mode (and depending on how you manage the IV), then yes, it can allow the attacker to modify messages such that the attacker can control the decrypted plaintext. For instance, an attacker could likely modify {"d":{"status":"success"}} to {"X":{"status":"success"}}. This could be a significant exploit or not.

(the attacker finding the key)?

Not directly. That isn't computable, even if you know the full plaintext and ciphertext. While the math is slightly different, this is similar to the problem of coming up with a plaintext that generates a given SHA-256 hash. AES is intended to make this computation no more efficient than a brute-force search.
However, if you are using a password to generate the key, and your KDF is incorrect, then there are definitely very good attacks against the password, and through it, the key. Knowing things about your data format will make these attacks faster (and if you fail to create a proper IV, they will be even faster). There are a lot of little pieces to correct AES encryption. If you get any of them wrong, then all the "AES is unbreakable" claims go out the window. Properly Encrypting With AES With CommonCrypto covers the main issues. They are the same for .NET as they are for ObjC.

If so, what would prevent this?

To the initial problem (data integrity / authentication), as Simon Johnson says, ideally use an authenticated mode such as CCM or GCM rather than CBC.
Alternately, if you do not have an authenticated mode available, use an HMAC to authenticate your data and demonstrate that it has not been modified. I would recommend draft-mcgrew-aead-aes-cbc-hmac-sha2 as a good approach to this. RNCryptor is similar and designed to address this issue, but there is not yet a C# implementation. (If you are interested in this problem, it is very easy to implement the RNCryptor data format in C#, and I'd be happy to work with you to build an open source version.)

If there is no security risk, what property of encryption prevents it from being an issue?

Let us consider the more basic version of this question. Get rid of block cipher modes, IVs, authentication, etc. Let's get back down to just AES. All AES does is transform 16 bytes into a different 16 bytes.
Encrypting with a key K and plaintext P yields a ciphertext C.
E(K, P) = C

For AES, there exists an efficient inverse of E called D such that:
D(K, C) = P

This just says that it is possible to encrypt something with a key, and then decrypt it with the same key. I.e.:
D(K, E(K, P)) = P

What you're asking for is some efficient function X such that:
X(P, C) = K

There are many functions E and D for which an efficient X exists. For example, if E is the xor function, then D is also the xor function and X interestingly enough is also the xor function. However, the AES function is such that there is no known efficient X (I don't believe that this is currently proven, but we certainly do not know what that X is).
This is a very long-winded way of saying that there is no known Known-plaintext attack on AES.
(I'm making a somewhat sloppy and broad claim here. There are some known attacks against AES that are not related to known-plaintext. There is a known attack that can recover an AES-128 key in complexity 2^126.1, which for cryptographers is a really powerful finding, but for most common uses is not a major concern.)


Transparent Voting and Advance Secret Code In the book "Introduction to the Theory of Computation", Michael Sipser writes

The field of cryptography, as this area is known, now extends well beyond secret codes for private communication and addresses a broad range of issues concerning the security of information. For example, (1) to allow electronic elections whereby participants can vote over a network and the results can be publicly tallied without revealing any individual’s vote, while preventing multiple voting and other violations; and (2) to construct new kinds of secret codes that do not require the communicators to agree in advance on the encryption and decryption algorithms.

(Chapter: Advance Topics in Complexity Theory,  section: Cryptography)
I am assuming that the example (1) refers to Blockchain technology. Are there any other ways of achieving the same?
For the example (2), I am not sure which technology is he trying to refer. Any idea?

I am assuming that [electronic elections whereby participants can vote over a network and the results can be publicly tallied without revealing any individual’s vote] refers to Blockchain technology. Are there any other ways of achieving the same?

Voting schemes using Blockchain technology mainly aim at avoiding a central authority. I doubt this is what's suggested, given the text, and it's age. I think it refers to voting remotely thru a network. A slightly later classic on this line of thought on electronic voting (among many) is Berry Schoenmakers' A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic Voting, in proceeding of Crypto 1999.

For [construct new kinds of secret codes that do not require the communicators to agree in advance on the encryption and decryption algorithms], I am not sure which technology is he trying to refer.

The author likely has used algorithm where he meant key. He would then be referring to Diffie-Hellman key exchange. The book has a mere 9 pages on cryptography (including 3 of exercises/problems), and it's section on Public-Key cryptosystems does not cover DH (only RSA). I would not recommend it as an introduction to cryptography.


Does CCA-security implies CPA-security While reading Katz & Lindell's textbook (2nd edition) if found three main security definitions: ING-EAV-Security, ING-CPA-Security and ING-CCA-Security. (From this forum I know there are more, but these are the most basic ones). I also read, that ING-CPA-Security implies ING-EAV-Security and that ING-EAV-Security is weaker than ING-CPA-Security which is weaker than ING-CCA-Security.
My question: Does ING-CCA-Security also implie ING-CPA-Security?

My Sketch on the reduction proof:

Basic Assumption: I got a Cryptosystem #1 that is CCA secure

Based on this Cryptosystem I can build a CPA secure Cryptosystem #2, and I assume, that an adversary can break it with non negligible probability

Therefore I can build a Reduction: R can simulate the CPA game with A and just gives the messages of A to his challenger and the response back to A. R then outputs the result of A.

Because A has a non negligible probability in breaking #2, R also has a non negligible probability in breaking #1, which gives a contradiction to the basic assumption

Therefore CCA implies CPA

I hope the basic idea is correct.


Is it possible to crack a LFSR encrypted file without using bruteforce? Let's say I was given a file from which I know that it is encrypted using a 5 bit LFSR with a given poly.

I already know that it is possible to deduce the state of an LFSR and thus all future outputs if you're given a certain length of the LFSR's output. But if that output is xored with a file, I would assume you can't, because of course you don't know the content of the file.

Am I right, or is there a way I havent't thought of?

First up: a 5 bit LFSR is horribly small, so getting the initial seed which was used is a piece of cake.

But indeed, it’ll basically boil down to a (rather quick) brute-force job where – unless that file contained purely random data – you’ld have good chances detecting the initial state (resulting in successful decryption) by just looking at the first couple of bytes.

Remember executable files, images, compressed files, and specific program files (like MS Word files) all come with specific headers. And text files can easily be detected too. UTF-8, UTF-16, etc mostly include BOMs (Byte Order Marks) and even if they don’t, they’re text – which greatly differs from random binary data. This makes "attacking" easier and can speed up things in scenarios where you’re facing multiple encrypted files each using different seeds.

That being said – never, ever, use a plain LFSR for encryption. If you really need speed, use a stream cipher (and don’t forget to use a MAC for authentication, as in "encrypt-then-MAC").


why AKS is so slow in practice? This note (http://maths-people.anu.edu.au/~brent/pd/primality4.pdf) states that AKS is not practical. However, it is known that AKS runs in polynomial-time, and I cannot understand where the slowness of AKS algorithm comes from? Brent, on the above link, justifies this to the high probability of hardware errors during the computation of the algorithm? can some one, either explain Bret's justification, or explain me other drawbacks?

Here is the issue about hardware errors that Brent is worried about on the slides (I'm not saying I agree; I just saying what the issue is):

Suppose we ran our algorithm, and it gave a result "it's prime"; how can we be certain that the algorithm didn't gave us the wrong answer because of an internal hardware error while running the algorithm?  This may sound like a trivial point, as the error probability on real hardware is actually quite small.  However the entire reason we're not running 100 iterations of Miller-Rabin is that we want to be certain; are we as certain we didn't run into an internal error within AKS as we would be that 100 iterations of Miller Rabin (which is a lot faster than AKS for any reasonable input size) didn't all lie?

Well, AKS just outputs an answer "Prime" or "Not Prime"; if you want to verify the result, we have no better way than to run AKS again.

In contrast, consider the alternative algorithm Elliptic Curve Primality Proving or ECPP.  This algorithm also always answers "Prime" or "Not Prime", and is always correct.  However, it also generates a "Primality Certificate"; this primality certificate can be rechecked with a separate fast algorithm.  No such primality certificate exists for a composite number; hence once we've run ECPP (and have generated a certificate), it is less important if we hit a hardware error during ECPP; if the primality certificate verifies, the number must be prime (even if ECPP did get a hardware error).

The above is the answer to the question; here is another point to consider.

ECPP is, in practice, considerably faster than AKS.  Hence, unless someone finds a further advance in AKS (and reduces its exponent), there's little reason to actually use AKS in practice; if you insist on a provable prime, you use ECPP; if probabilistic methods are good enough, you use Miller-Rabin (or similar algorithms); alternatively, if what you're doing is searching for prime numbers, you can consider provable methods of constructing prime numbers (such as Shawe-Taylor).

So, if AKS is not useful in practice, why are people so interested in it?  Well, while ECPP is faster, it's actually a Las Vegas algorithm; it's randomized, however, unlike Miller-Rabin, it'll never return an incorrect answer; instead, its low probability failure mode is that it might continue to run.  In contrast, AKS is a deterministic polynomial time algorithm.


Iterative hashing increases number of security bits? Whatsapp uses 5200 iterations of SHA-512 over user's public key and identity
according to WhatsApp Security Whitepaper.

I wonder why?

According to: Why iterate 5200 times when computing Safety Numbers in Signal?  this question on Information Security.SE: It is to increase security bits to 112.

I do understand why 30 digit number has $\approx 99$ bits entropy and so $\approx 99$ security bits.

$$\log_2(10)*30 \approx 99$$

But how does iterative hashing affects security bits? It does not affect entropy as far as I understand.

Math in the post indeed shows:

$\log_2(10^{30} * 5200) \approx 112$. Which is recommended number of security bits at keylength.com

Moreover, Signal source code comments state that too on the source code

Where can I read more on why '5200' iterations of hashing placed into the 'log' as multiplication and why does it affect security bits at all?

how does iterative hashing affects security (measured in) bits?

It does so by increasing the number of operations likely required to solve the problem by brute force, because an operation is what's iterated in each attempt of break.

  (iterative hashing) does not affect entropy

Indeed, iterative hashing does not increase¹ entropy. It can still increase security.

  $n$-bit security means that adversary needs to perform $2^n$ operations to break the system.

Yes, for some definition of operation, and certainty to break the system.

If there's an attack with $N$ operations that succeeds with probability $p$, and $p$ grows linearly with $N$ until $p=1$ as in key search, then the system has at most $$n=\log_2(N/p)=\log_2(N)-\log_2(p)\text{ bit security}$$

This formula works including for low $p$ and any $N\ge1$. Customarily, it is used also when $p$ only grows about linearly with $N$ until $p$ reaches a non-negligible value, e.g. because $p=e^{-N_0/N}$ as in preimage search.

The question's Whatsapp system re-formats 32-byte ECC public keys into 30-decimal digit strings that appear nearly uniformly distributed. The main design goal is to make it hard to generate a private key which matching public key re-formats to one (or more) given strings obtained by re-formatting one (or more) target public key(s); that is, make second preimage search difficult.

A brute force preimage attack against this system generates key pairs; hashes the public key 5200 times with SHA-512; and makes a test against the targeted value(s). Each private key test has probability $p=10^{-30}$ to match a given string. Each test costs 5200 iterations of SHA-512 and comparatively little else (an increment of the private key, an ECC point addition of a constant point to the previous public key, typically one (at most 6) comparison against 5 digits of the given string of the modular reduction modulo $10^5$ of part of the SHA-512 hash).

It follows that security is $\log_2(5200)+30\log_2(10)\approx112.00$-bit when the cost is counted in SHA-512 hashes, which is the natural metric here, and there's a single target key. For $s$ target strings/keys, the probability of success of each test is increased by a factor $s$, thus security is reduced by $\log_2(s)$ bit.

Notes:

A former version of this answer was about the security increase with increased iteration count in a cryptosystem where there are sizably much other operations beyond iterated hashing. That's not relevant in the question's context, thus removed.

¹ : The simplest forms of iterative hashing, including the one in the question's Whatsapp context even slightly reduce entropy; see this.


How to build a secure AE scheme with generic composition? I am actually looking for using a secure Encrypt-Then-MAC AE scheme , and consider using either an existing "ready-to-use" dedicated AEAD mode (GCM, OCB, CCM, EAX, etc ..) or an alternate composed CTR-Then-CMAC scheme (mainly in order to avoid apparent fragility of GHASH as to limit impacts of accidental IV reuse with gcm)

My questions are the following:

If for instance I plan to build a composed CTR-Then-CMAC scheme, I think to process as follows
derive two Authentication / Encryption keys from unique
input key
encrypt plaintext P using CTR mode & input
Initial counter block    (ICB)
lastly  authenticate the  sequence composed of IV, AD and
Ciphertext using CMAC.
Is is correct ?    where / how can we find rules to build   correctly a composed AE    scheme from input "secure"   Encryption & MAC/Authentication modes ?
the only standard which addresses such    AE generic
composition seems to be ISO/IEC 19772:2009 which includes
"Encrypt-Then-Mac" mode beside other AE/AEAD modes; but as such ISO
standard has to be ordered I didn't still get info about content of
"Encrypt-Then-Mac" mode section

You might look at EAX mode, which combines a block cipher in CTR mode with a CMAC.  However, EAX does differ from generic Encrypt-than-MAC in that EAX uses a single master key, which would be an absolute no-no for Encrypt-then-MAC.  Normally using the same key for both purposes is quite dangerous, but EAX is explicit about the use of the master key for the cipher and MAC, and EAX comes with a formal proof of security for that usage (and the entire mode).

Given that EAX (and CCM to a less flexible degree) provide a proven method for encrypting and authenticating data, for practical purposes my advice would be to just use one of the well known and trusted AEAD modes.

For theoretical purposes, the answers to Why choose an authenticated encryption mode instead of a separate MAC? and Should we MAC-then-encrypt or encrypt-then-MAC? should give you a good idea of the steps required to define a your own general composition, and how tricky it is to get all of those right.

The EAX paper also describes and proves the security of an EAX2 mode, which is a generic composition approach to create a two key AEAD mode based on a cipher and a MAC.


Difference between INT-CTXT and INT-PTXT I have read recently (here) about INT-CTXT and INT-PTXT and that INT-CTXT is strictly stronger than INT-PTXT. I wonder if there is any clear example of the situation when INT-PTXT is achieved but no INT-CTXT?

There are also examples of related situation in the original article (e.g. Encrypt-and-MAC and MAC-then-Encrypt schemes on pp. 25-31) but I haven't managed to understand them. How an adversary is able to produce a ciphertext which wasn't produced by the sender but is not able to produce a ciphertext decrypting to a message which the sender has never encrypted?

My answer is taken from the following paper http://cseweb.ucsd.edu/~mihir/papers/oem.pdf (it is a well-written paper, so if you are interested in this topic I highly recommend you to read it).

Suppose $\mathcal{SE = (K, E, D)}$ is INT-PTXT secure. From $\mathcal{SE}$ we create another scheme $\mathcal{SE}_2 = (\mathcal{K}, \mathcal{E}_2, \mathcal{D}_2)$ which is also INT-PTXT secure, but not INT-CTXT secure. The idea is to add to every ciphertext produced by $\mathcal{E}$ a redundant bit which will be ignored upon decryption. This allows us to easily create new ciphertexts from old ones which still decrypts to the same plaintext. Intuitively, an attacker cannot exploit this against INT-PTXT (which requires it to submit ciphertexts that decrypts to new plaintexts), but it will help us to break INT-CTXT security.

In detail, the definitions of $\mathcal{E}_2$ and $\mathcal{D}_2$ are as follows.

$\underline{\mathcal{E}_2(K, M)}:\\\quad C \gets \mathcal{E}(K, M)\\\quad \text{Return } 0 || C$

$\underline{\mathcal{D}_2(K, C)}:\\\quad\text{Parse $C$ as $b || C'$ where $b$ is a bit (return $\perp$ if the parsing fails)}\\ \quad M \gets \mathcal{D}(K,C') \\ \quad \text{Return } M $

I leave it to you to prove that $\mathcal{SE}_2$ is also INT-PTXT (the reduction can be found in the last paragraph before Section 4 in http://cseweb.ucsd.edu/~mihir/papers/oem.pdf).

Here is a simple attack that shows that $\mathcal{SE}_2$ is not INT-CTXT.

$\text{Adversary $\mathcal{A}$}\\ \quad \text{Let $M$ be any arbitrary plaintext} \\ \quad C \gets \mathbf{EncryptOracle}(M)\\  \quad \text{Parse $C$ as $0 || C'$}\\ \quad \mathbf{VerificationOracle}(1 || C')$

Note that $\mathcal{A}$ is a valid INT-CTXT adversary since it asks for the verification of a ciphertext it did not previously obtain from an encrypt query.
But it is not a valid INT-PTXT adversary since both $0 || C'$ and $1 || C'$ decrypt to the same plaintext $M$ (and $\mathcal{A}$ previously asked for the encryption of $M$).


Is it necessary to have a certificate when we use TLS When we say a communication is secured by the latest version of TLS, can we say that Man-in-the-Middle attack is not possible? Do not consider the situations that we can down grade the communication protocol. With TLS, is it necessary the have certificate for the server?

If the TLS communication is properly secured then a middle attack is not practically possible. Properly secured includes authentication of the server in order to make sure that one is talking  to (and exchanging the keys with) the expected server and not to some man in the middle attacker. There are various ways to authenticate the server, like certificates or pre-shared keys (PSK). Certificates within a public key infrastructure are the most used method though since they scale best with large setups (like the internet).


Recasting randomly generated numbers to other widths Suppose I have a list of randomly generated uint_8's, uniform over the whole range of uint_8. I write them into a file as raw bytes, no encoding.

Then I reopen the file and interpret the file as packed uint_16's (by pairing up adjacent bytes).

Is my reinterpreted stream of uint_16's a uniformly random distribution in the whole range of uint_16?
Now I reinterpret the bytes as packed int_32's. Is my reinterpreted stream a uniformly random distribution of int_32's, in the whole range of int_32?

Note: uintN_t is the type of N-bit unsigned integers, i.e. integers in the range $[0,2^N-1]$. intN_t is the corresponding signed type, i.e. integers in the range $[-2^{N-1},2^{N-1}-1]$.

Well, it rather depends on what you mean by "uniformly distributed".  If you mean that, over all possible lists, each byte position was from a uniform distribution, that doesn't actually tell you that.

Here's the problem: all "uniformly distributed" in this case means is that, in a sufficiently large sample, each value occurs approximately equally often (in the uint_8 case, about 1/256 of the time).

However, it says nothing about correlations, that is, which values tend to immediately follow other values.  It is easy to design a 'random string' that is perfectly uniform, however the adjacent bytes are strongly biased; this means that, when you combine adjacent bytes, each uint_16 will not be equally represented.  For example, consider a string where, after a byte value $X$, the next position is also the value $X$ with probability 1/2+1/512, and a value $Y \neq X$ with probability 1/512.  This sequence is equidistributed; however if you combine uint_8 values, the resulting sequence is strongly biased.

However, if by "uniformly distributed", you mean that the $N$-byte sequence as a whole was selected uniformly from all possible $256^N$ possible sequences, then yes, uniformness is preserved by combining adjacent elements.

Now, getting down to practice: if the list was generated by a cryptographically secure random number generator (CSRNG), then we can assume that combining adjacent elements is harmless.  That's because we assume that the output of a CSRNG cannot be efficiently distinguished from random by any method; if the attacker could distinguish it by combining adjacent bytes, that would mean that we really didn't have a CSRNG in the first place.

On the other hand, if the list was generated by a statistical random number generator (that is, a generator that was designed to generate output that "looks" random, that is, passes some standard statistical tests), then it's a tad trickier.  Real life generators can have problems when you combine outputs at the "wrong" size; however it is unlikely that one used in practice would have a problem with combining only 2 or 4 elements.  So, in this case, you're probably safe (although you might want to check with the generator to be sure)


How can a fully encrypted homomorphic program resist copying? Let's say that we have an original homomorphically encrypted program with any possible code inside. What methods can it use to ensure that it is impossible to create an exact copy of it? Are there such ways?

I understand that a person without a key will not see the internal content of a homomorphically encrypted program, I'm interested in whether it is possible to limit the exact copying of this program entirely

That sounds impossible: your homomorphically encrypted program is just a program itself, and the fact that it runs some FHE does not matter with respect to the question of whether it can be copied.

A user with direct access to the program can always copy it, whatever you do (e.g. he could always take photos of the source code with his smartphone if he wanted).

If you want to make it truly impossible to copy, you need to run it in a secure environment (and as such a program will be likely very lengthy, that would most likely correspond to running it on a trusted machine to which the user is only given some input-output access).


Is it possible to derive the midstate of a sha256 hash? Let's say I have an unknown string with the known sha256-hash of it. I was wondering if it was possible to now calculate the sha256 of the concatenation of the unknown string and "abc".

(In PHP: hash('sha256', $unknownString .'abc');)

I thought in order to do so "all I need" is to go from the hash that I know back to the midstate of the sha256 algorithm (in most implementations called finalize) and append the data that I want (via, in most implementations called, update) and then call finalize again. Block lengths shouldn't be a problem because the unknown string has a length of 256 bit and my own string has this as well.

Is this possible or by the way sha256 is designed impossible to achieve?

PS: I have no intention in getting the unknown string. I absolutely do not care about the plaintext contents of this.

SHA-256 is computed by first padding a message $m$ and then breaking $\operatorname{pad}(m)$ into $\ell$ blocks $m_1, m_2, \dots, m_\ell$ of 512 bits each.  The padding appends some bits to the message so that it is an integral multiple of 512 bits long.  Then the SHA-256 hash of $m$ is $$f(\cdots f(f(\mathit{iv}, m_1), m_2) \cdots, m_\ell)$$ where $f$ is the SHA-256 compression function and $\mathit{iv}$ is the standard initialization vector.  This means that given $\operatorname{SHA256}(m)$ you can compute $\operatorname{SHA256}(\operatorname{pad}(m) \mathbin\| m')$ for any suffix $m'$.  But you can't necessarily compute $\operatorname{SHA256}(m \mathbin\| m'')$ unless $m''$ coincides with the padding on $m$.


How does knowing the factorization of N help to obtain the secret? Assuming $x=a^2 \pmod n$ and knowing $x$, $p$, $q$ how is it possible to obtain $a$?

Your question is related to the well known RABIN Cryptosystem which is similar to RSA, except the public exponent is 2.

As fgrieu mentioned, decipherment can be easily processed by the CRT algorithm, but some precautions must beforehand be observed during the key generation. In fact the solution of the equation gives 4 roots, which means that the solution of the initial problem when they exist (... $x \in QR(p\cdot q)$) is not unique. And asking which of one of four solution to return is a security problem, and without knowing these constraints, the probability of divulging the factorization of modulus is $0.5$. The determination of the right and secure solution must be carefully studied regarding the form of the factor p & q, and the properties of special integer called "Blum integers".

When restricting to correct message space, there is a unified inversion formula which runs on $\mathbb{Z}/n \mathbb{Z}$. I know it because it was specified in an early draft of SC27-ISO9796 at the end of the $80^{th}$. Unfortunately I don't remember it. Probably Fgrieu can confirm and search for it.


How bad it is using the same IV twice with AES/GCM? I understand that initialization vectors (IV) should not be used twice when using AES/GCM. I am using a counter as an initialization vector. Every time I send out a new packet (I am developing an UDP based protocol that needs packet encryption) I increment the counter and use it as IV.

However, since I will generally need that protocol to transfer files and to send keepalives for very very extended periods of time, in principle for very large files it is conceivable to send more than $2^{32}$ packets, or over the years it is conceivable to send out $2^{32}$ keepalives. To keep the IVs always unique, I would probably need to use a 64 bits integer, but that is 4 bytes more of overhead per packet, that can sum up to quite large quantities which I would like to avoid if not strictly necessary.

So I wonder: how bad it is to reuse the IVs with AES/GCM? Can I have an idea of how dangerous that can be? I mean: if as soon as I repeat an IV once I get immediately so easily exposed to an attack that I could just give out my key publicly, then I have to take countermeasures. However, if that becomes dangerous only when I use the same IV a lot of times, that is completely another thing.

Even a single AES-GCM nonce reuse can be catastrophic.

A single nonce reuse leaks the xor of plaintexts, so if one plaintext is known the adversary can completely decrypt the other.  This is the same as for a two-time pad.
In messages up to $\ell$ blocks long, after a single nonce reuse the adversary can narrow the authentication key down to $\ell$ possibilities with polynomial root-finding and thereby forge messages with high success probability $1/\ell$.

How?  An $\ell$-block message is a polynomial of degree $\ell$ with zero constant term; the authenticator under secret key $r, s$ is $m \mapsto m(r) + s$, where $r$ is reused between messages and $s$ is derived as a secret function of the nonce.  Find authenticators $a = m(r) + s$ and $a' = m'(r) + s$ for distinct messages under the same nonce, and only the ${\leq}\ell$ possible roots of the degree-$\ell$ polynomial $m(r) - m'(r) + a' - a$ in $r$ are possible values of the authentication key.

Use 96-bit nonces; if you don't—if, instead, you use smaller or larger nonces—it will be as if you chose nonces randomly, and the number of messages you can safely handle drops dramatically.  But you can, of course, pad, say, a 64-bit nonce into 96 bits: what matters is only that the nonces be unique.

If the cost of a >32-bit nonce is prohibitive, you could periodically rekey.  For example, if you first establish a long-term key $k$, you can use $\operatorname{HMAC-SHA256}_k(i)$ as the key during the $i^{\mathit{th}}$ epoch, where each epoch covers four billion messages, and $i$ is encoded into a bit string in some canonical way.


Unbalanced Feistel network only generates complete permutations with square lengths I'm generating permutations with a generalized Feistel network which will output integer values $r_j$ in a specified range $[0,period]$ pseudo-randomly, according to the counter input, which will then cycle after having reached each of them all exactly once.

Rather than splitting the counter into two equally sized bitvectors $L$ and $R$, I'm operating on a quotient and remainder, with the ambition of generating permutations of arbitrary length, unlike the $2^n$ that a balanced network or maximal LSFR might generate.

uint16_t feistel(uint16_t counter, unsigned period)
{
    uint16_t d = sqrt(period);
    uint16_t s = period - d*d;
    uint16_t q = counter / d;
    uint16_t r = counter % s;

    for (int i = 0; i < 3; i++)
    {
        uint16_t nr = r;
        uint16_t F = (i * r + q);
        r =  F % d;
        q = nr;
    }

    return q*d + r;
}

This code can correctly generate some maximal permutations. However, it only does so for periods that are square numbers (where s = 0).

Can this be changed so that any choice of period generates a complete permutation? Also, are there any broader numerical issues surrounding the choice of how a number is split and manipulated in an unbalanced Feistal network (divisor * quotient + remainder, sum of two primes, left and right bitvectors, etc)?

I think that this method of yours will not work out. The reason is the way you compute $r = counter$ mod $s$.
Take a simple example of $(counter_1, period) = (3, 11)$ and $(counter_2, period) = (5, 11)$. Here $d=3$ and $s=5$.
You get initial $(q_1, r_1) = (1,3)$ and $(q_2, r_2) = (1,0)$.
After first iteration of the loop, you have $(q_1, r_1) = (3,1)$ and $(q_2, r_2) = (0,1)$.
After the second interation of the loop, you will get $(q_1, r_1) = (1,1)$ and $(q_2, r_2) = (1,1)$.
Now, for the remaining iterations, both $(q_1,r_1)$ and $(q_2,r_2)$ will always go along being equal and will finally result in equal values being returned by the function for 2 different counter values with the same period sabotaging the maximal permutation.
You should get rid of the above mentioned issue by computing initial $r$ as $r = counter$ mod $d$.


Blinding to mask private key operations Blinding is often used to mask private key operations when the underlying problem is integer factorization. For example, it's used in both RSA and Rabin-Williams signature schemes. This presumes integer operations are not constant time.

I have two questions:

Is blinding used in schemes other than integer factorization?
Are there other options to guard the private key against timing attacks available to software implementations on commodity hardware?

The reason I ask is Evgeny Sidorov's Breaking the Rabin-Williams digital signature system implementation in the Crypto++ library (a.k.a. CVE-2015-2141). There was a bad interaction with the blinding value and Jacobi requirements on p, q, which resulted in a private key recovery.

One of the suggested remediations was to disable blinding. I'm trying to gauge the impact of doing it in libraries like OpenSSL and Crypto++, and how much needs to change if blinding is optional. (It is already optional in OpenSSL, but not Crypto++).

1) Blinding has been used, for example, to design a version of El Gamal encryption that is resilient to certain side-channel attacks --- see [PK] and the references therein.

2) The goal of the field of leakage-resilient cryptography is to model and study (from a theoretical perspective) what security can be guaranteed against side-channel attacks (including e.g., timing attacks). See this recent survey or this excellent blog post for more details on the type of models that are being considered.

[PK]: Pietrzak and Kiltz. Leakage Resilient ElGamal Encryption


shared symmetric key Suppose $R$ is a random challenge sent in the clear from Alice to Bob and $K$ is a symmetric key known only to Alice and Bob. Which of the following are secure session keys and which are not? Justify your answers.
  (i)  $R\oplus K$
  (ii) $E(R,K)$

I believe that $R\oplus K$ is secure because it has one of the requirements of the perfect secrecy which is the key space has to have the same size as message space. As a result, $R\oplus K$ is provably secure.

On the other hand, $E(R,K)$ is a secure method to authenticate on side (sender) but it does not authenticate the other side (receiver). There is a problem which is no mutual authentication. Therefore, this is not secure.

However, I have been told that this answer is not correct. What am I missing?

The first method fails completely if one of the session keys gets to be known by an adversary. The idea of session keys is that a key can become known without affecting the security of other sessions. If $K_s = K \oplus R$ is known then the master key becomes known; $K = K_s \oplus R$ after all. So all sessions are now broken.

In the second method I presume that $K_s = \text{E}_K(R)$. In other words, $K$ acts as the key and $R$ as the message to be encrypted (usually we write this as $E(K, R)$ not $E(R, K)$ ...). In that case the session keys are secure, although an authentication step is indeed missing. I'm however assuming that verification of the session keys falls outside the question domain.

If $R$ is used as a key in the second method then the same issue as for scheme 1 arises: $K = D_R(K_s)$ and the master key is known.


Is the scheme $(r, Mac_k(r) \oplus m)$ CPA-secure? I honestly admit this question is taken from a h.w assignment:

  Prove or refute: the following encryption scheme is CPA-secure: Let $(\text{Gen},  \text{Mac}, \text{Vrfy})$ be a secure MAC with tags of length $n$. Encrypt a message $m \in (0,1)^n$ by choosing a random $r \in (0, 1)^n$ and outputting $(r, \text{Mac}_k(r) \oplus m)$.

As I just have started with this course, please point out if my approach or my usage of technical terms are incorrect or imprecise. I am following the book named "Introduction to modern crypthography."

My first approach was to refute the claim. I thought about giving an example for a MAC that is secure but yields a non-secure scheme. For instance, consider the MAC which appends a zero at the end. As far as I can tell,  a PRF $f$ can be used as a MAC, so I could define something like $\text{Mac}(x) = f(x) ||0$ or, even, use some other MAC instead of $f$. It's easy to see that the scheme will not be CPA-secure as an adversary's decision can base solely on the last bit of the message.
In contrast to my first approach, I would actually like to prove it. My intuition tells me, given a random $r$, $\text{Mac}_k(r)$ should be also random. Thus, I get a random string XOR'ed with $m$ (which actually seems like an OTP), which should be secure.
The problem is that I don't know how to complete my proof by reduction. If I build an attacker $A'$ how it should interact with the other attacker $A$? I would start by assuming the scheme is NOT CPA-secure and would come to a contradiction by giving a MAC which yields a scheme which is not CPA secure---but I am very confused on how to do it.

It would be really nice if I could get some clues or related examples on how to formalize my line of thinking.

Your first approach was almost correct. Your question says nothing about the shape of the secure MAC except the length. The secure MAC only says that you cannot forge a new tag from the previous ones.

Let $MAC_1$ be a secure map with output length $n-1$ than

$$MAC_2(m) = MAC_1(m)\|0$$
will be a secure MAC with output length $n$.

Now, put $MAC_2$ into your scheme and use 0 to distinguish the messages. The adversary sends two messages $m_1$ and $m_2$ such that $\operatorname{lsb}(m_1) \neq \operatorname{lsb}(m_2)$. When the messages returned he can distinguish just by observing the lsb's of $MAC(r_i)\oplus m_i$


Can you use memory errors as a source of randomness for cryptography? Obviously, if you need a random number for cryptography, your code should use an api that gets it from hardware. However, not all hardware has a SRNG available. If you are working on a security critical application, and hardware RNG is not available then the appropriate course of action is to abort execution.

BUT, not every application would be deemed security critical. That is to say, while you want security, you are not worried about overly complex attacks because, 1. your application is not worth the effort of being cracked by sophisticated hackers 2. none of your data is considered strictly confidential (you don't want it breached, but it would not be the end of the world).

Assuming a none security critical application, running on a machine without hardware RNG or ECC Memory, would it be viable to allocate a very large amount of memory (perhaps in a long loop) and use the errors that eventually occur as a source of randomness? Would this be more secure than PRNG?

(..) would it be viable to allocate a very large amount of memory (perhaps in a long loop) and use the errors that eventually occur as a source of randomness?

No. Practical use of memory errors as a source of randomness would require manipulation of DRAM timing parameters, as envisioned in this answer and it's reference.
The rate of memory error in a correctly working computer at ground level is very low; anything larger than one error detected per week (as reported by machine with ECC logging) is reason for maintenance [#]. Hence the proposed method requires a terminally impractical delay to get any entropy, or an unreliable computer; and for one well built, that mostly happens at altitude (especially in the South Atlantic Anomaly). Plus, if the machine has ECC, errors are hard to detect portably (reporting of ECC errors tends to be a proprietary mess); and if it is not, and there are sizably many errors, it is to fear one will eventually prevent the program from running as intended.
More practical sources of entropy include

Audio or video input; more generally output of an ADC.
Time of events measured to high accuracy relative to CPU clock (e.g. by way of a performance counter as obtained by RDTSC instruction or API to that). Sources include:

key presses (value gives extra entropy)
mouse/pointing device movement (position gives extra entropy)
arrival of network packets
availability of data from a spinning hard disk
change of second in a real-time clock IC with independent crystal (low entropy rate, but quite reliably entropic)

Extracting the entropy is relatively easy: essentially, hash anything entropic you can get. The one extremely difficult thing is asserting a reliable lower bound of how much entropy was really gathered. Be extremely conservative, and don't assume that something that holds, will. Things change unexpectedly, especially when there's an active adversary, as we assume in crypto.

[#] Reliability studies on DRAM give widely varying estimates. However we are talking like 100 FIT par DRAM IC within a factor of 100, where Failure In Time is the expected number of failures per 109 device⋅hour. Taking the upper extreme 104 FIT, a computer with 4 DIMMs each with 18 DRAM ICs (enough for 32 GiB with ECC using DDR4 mainstream by late 2017), we get 1.2 expected failures per week.
My limited field experience with servers is that when there are ECC alarms more often than once per week, there's a cause, most often a mismatch in memory specs or settings (for new machines only) or a particular bit in one particular IC of a particular DIMM that's marginal (or worn out, for machines that have been humming quietly for some time). The error log's main virtue is to help identifying such condition, and what DIMM to replace rather than scrapping the whole lot.
There are techniques to purposely increase the rate of occurrence of DRAM errors; including lowering the refresh rate much below manufacturer specs, and/or using a RowHammer read/write pattern. However that's extremely dependent on DRAM model. Doing this reliably, portably and within an OS is very difficult; there's a reason MemTest wants to own as much of the machine as feasible.


montgomery reduction multiplicative identity How do you figure out the multiplicative and additive identity with respects to R?

I pick some R such that gcd(R, N) = 1 where N is the size of the group.

Given some field element x in the group, I do x' = xR mod N

How would I figure out the multiplicative identity m such that x' * m = x'

and the additive identity a such that x' + a = x'` ?

The additive identity is $0$, as usual.

The multiplicative identity is the Montgomery representative for $1$, namely $1\cdot R \bmod N = R \bmod N$, just like the Montgomery representative for any other element $x$ is $x\cdot R \bmod N$.


The title of the protocol and explanation of the steps required The secure third party R generates key $k_1$ to communicate with A and $k_2$ to communicate with B.

A requests a key with which to communicate with B.

R generates k un and encrypts:
$E_{k_1}(k) = s1;\ \  E_{k_2}(k) = s_2; \ \ E_{k_2}(p_A) = s_A$
R sends to A $\ s_1$ and $[s_2, s_A]$.

A deciphers his key:
$E^{−1}_{k_1}(s_1) = k$

and sends to B $[s_2,s_A]$

B deciphers:
$E^{−1}_{k_2}(s_2) \ \ $(the key is received);
$E^{−1}_{k_2}(s_A) = p_A$. (B knows that he is communicating with A).

First, I would like to know the title of the protocol. Secondly, why the third party cannot send the block $[s_2, s_A]$ to B right away, why A is the one that sends it?

This protocol is known as Kerberos, at least, as originally implemented (I believe the protocol has been extended significantly since).
Within Kerberos, the tuple $[s_2, s_A]$ is protected by $k_2$ (which both R and B know); hence no one else can modify it.
This tuple essentially tells B "A wants to talk to you, and use key $k$ to do so".  A third party could forward this tuple directly to B, but it doesn't give him an advantage; after all, A really does want to talk to B.  This third party could prevent A from receiving his message from R (and so A doesn't learn $k$), however the third party doesn't learn $k$ either, so B gets a key that will never be used.
It may be that, in the original protocol, the tuple R sends to A was encrypted by $k_1$; this would obviously prevent this attack - it's been a while, and so I forget the details.  Even if it doesn't, this attack doesn't doesn't achieve anything, other than preventing A from talking to B, and an adversary that can arbitrarily modify or delete messages can trivially do that.


Choosing a suitable prime for accumulators I am trying to work out accumulators and generate $S = \{ e_1,e_2 \ldots, e_n \} $ from this (Section 3.4 - Choosing a Suitable Prime).
For each element of $e_i$ compute its representation $x_i$.(This I want to calculate).
To compute representation($x_i$) use following
( According to the paper $x_i$ should be calculated like this and this part I need help with. Please help me understand this)
We are interested in obtaining a prime solution of the linear system, that represents a Universal-2 hash function.
Lemma:
Let H be a universal-2 family from $\{0,1\}^{3k}$ to $\{0,1\}^k$. Then, for all but a $2^{-k}$ fraction of the functions $h \in H$. For every $e \in \{0,1\}^k$ a fraction of at least $1/ck$ of the elements in $f^{-1}(e)$ are primes, for some small constant c.
We accept a prime inverse only if it is greater than $\sqrt{2^{3k}}$. Since domain of H is $\{0,1\}^{3k}$. So, by the results of prime number theory, the density of big prime numbers that are less than $2^k$ is about $1/2k$ for all but a $2^{\Omega(k)}$ fraction of functions in family H.*
Please help me, how can I calculate $x_i$ as a representation of $e_i$?

I'll use as reference Michael T. Goodrich, Roberto Tamassia, Jasminka Hasic's An Efficient Dynamic and Distributed RSA Accumulator from arXiv (2009), not the version originally in proceedings of ISC 2002 or linked in the question.
Disclaimer: I discover this paper while writing this answer, thus the following is highly tentative. Further, there are important things that I fail to make sense of, which means my understanding or the paper is wrong. Therefore, do not use the following for anything more serious than an exploration.

Preliminary: choice of RSA modulus $N=P\,Q$, and base $a$.
When it is wished to store $e_i$ of up to $k$ bits, the scheme as described starts by generating “strong primes¹” $P$ and $Q$ of at least $3k/2$ bits each. I believe they additionally need to be at least as large as required for security of RSA (that's not stated). The article's Experimental Results states "the parameter $N$ of the RSA accumulator is a 200-bit integer", but if I understand the rest suggests $k=165$, which would make $N$ 495-bit. Even this would have been too low when the article came out, see this. Such disregard for a safe choice of $N$ in both the theoretical and practical parts of the article is crying to be fixed. I'll have a try at that.
The article's reference for “strong primes¹” is the Handbook of Applied Cryptography definition 4.52:

A prime number $p$ is said to be a strong prime if integers $r$, $s$, and $t$ exist such that the following three conditions are satisfied:
 (i)    $p−1$ has a large² prime factor, denoted $r$;
 (ii)   $p+1$ has a large² prime factor, denoted $s$; and
 (iii)  $r−1$ has a large² prime factor, denoted $t$.

In the context of RSA accumulators and problems that rely on the Strong RSA assumption (including the question's scheme), I would require at least (i) to hold for $P$ and $Q$; and for good measure I'd use safe primes of the same bit size, as required in the article's reference [6], Josh Benaloh and Michael de Mare's One-way accumulators: A decentralized alternative to digital signatures, in proceedings of Eurocrypt 1993 (with extended abstract).
For a modern implementation I would consider $k=680$, and $P$ and $Q$ random 1024-bit safe primes in the interval $[2^{1023.5},2^{1024})\,$, which are easy to generate.
Also, it's required “a suitably-large base $a$ that is relatively prime to $N=P \,Q$”. For lack of other guidance, I'd consider $a=\lfloor\pi\,2^{2045}\rfloor$.

Primes representative of the $e_i$ to be accumulated.
The paper defines a function
$$\begin{align}h:\{0,1\}^{3k}&\mapsto\{0,1\}^k\\
x\quad&\to h(x)\underset{\text{def}}=U\times x\end{align}$$
where $U$ is a binary matrix of $k$ lines and $3\,k$ columns. And it defines the prime representative of $e_i$ to be accumulated as a prime $p_i$ in $[2^{3k/2},2^{3k})$ such that $h(p_i)=e_i$ (assimilating integers to bitstrings per e.g. big-endian convention).
In order to find $p_i$ from $e_i$, we can simplify the system of $k$ binary equations with $3k$ binary unknowns $U\times x=e_i$, enumerate solutions at least $2^{3k/2}$, and stop at the first prime $x$ found. I located no requirement on the enumeration order, but I guess that it must be deterministic, and pseudo-random would not harm.
The rest seems standard use of an RSA accumulator.

¹ Note: In normal RSA, it's dubious that strong primes are really needed nowadays. Condition (i) [resp. (ii)] aims at blocking Pollard's $p-1$ [resp. William's $p+1$] factoring, but that becomes hopeless as $p$ increases (as needed to resist GNFS), and could only really help in multi-target attacks at low parametrization. Condition (iii) aims at blocking a cycling attack but seems pointless, see Ronald L. Rivest and Robert D. Silverman's Are ‘Strong’ Primes Needed for RSA?. None of these conditions are required by the conservative FIPS 186-4 appendix B3 for primes 1024-bit or larger intended for RSA moduli used in signature.
² Nothing in either the paper or the HAC hints at how large in the context of RSA accumulators. The guidance in FIPS 186-4 is not intended for this context; using it for (i) would be adventurous.


Capacity bits in SHA-3 I am trying to understand the sponge construction, and in the official web site I found this sentence:

The last c bits of the state are never directly affected by the input blocks and are never output during the squeezing phase.

Now I understood that the capacity is used to hide the internal state to an attacker. But I can not understand two aspects:

How is the capacity filled?
If it is part of the internal state, how can be possible that is not affected by the input blocks?

The capacity $c$, together with the rate $r$, is the state of the algorithm between the applications of the sponge.

It is of course affected by the message (there is no other input after all) but not directly: the input first has to go through the sponge function, $f$, after it is XOR'red with the rate, $r$. Similarly, only the rate $r$ is output during the squeezing. So the previous capacity $c$ is similarly protected by a sponge. Note that there is always an $f$ between the input and output (of course).

The capacity and the rate are first initialized to zero.


Constant number of rounds in Yao's Protocol for semi honest adversaries According to me, every OT takes a constant number of rounds and since we have to do an OT for every input of one party, we'll have to do O(n) OTs which would correspond to O(n) rounds. But I have read at various places that the number of rounds in Yao's Protocol is constant. Am I missing something?

The OT inputs/outputs don't depend on each other, so they can all be done in parallel.


Understanding forking lemma and oracle replay attack Many signature schemes use forking lemma to prove security, like scheme in here.In short, that goes through a reduction technique which called oracle-replay attack to solve the difficult algorithmic problem, requiring two rounds of simulation for $\mathcal{F}$ to obtain two valid signature pairs $(m,r,e,s)$ and $(m,r,e',s')$,where $r$ is a "commitment", $e = H(m||r)$,$s$ and $s'$ is related to $m$, $r$ and $e$. But how to ensure the forger $\mathcal{F}$ will output the same message $m$ and $r$ ,since they may select randomly in each simulation?

see also
[PS00] David Pointcheval and Jacques Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 2000.

We use the fact that forger $\mathcal{F}$ is nothing else but a Turing machine with some random tape. And since $\mathcal{F}$ is in our possession, we can choose the tape.
Therefore, we can rerun $\mathcal{F}$ with the same tape, and behavior of $\mathcal{F}$ will be just the same (until the point where the oracle will return different value and desired "forking" occurs).


How could you disclose what you like and have someone respond with what you want without revealing who you are? Bob likes Apples and Oranges (virtual, not physical). Alice and Eve are fruit sellers (again, virtual, not physical). Bob wants to indicate his appetite to buy one Apple and one Orange without revealing who he is. Alice and Eve want to sell to Bob but they can't know Bob's identity. How does Bob communicate his preference to buy, and then take receipt, without Alice and Eve ever knowing who he is and without using a central authority?

All Bob needs is to generate an Ephemeral key: just make (say) an RSA key, use it to initiate and proceed with communications with Alice, then delete it when he's done, taking care never to use it to process any personally-identifying information.
In fact, this is what web browsers do every time you connect to a website: by default, only the server has a certificate anchoring its identity; clients are anonymous until or unless they supply authentication. Your queries to, say, Searx are confidential, known only by the host and the anonymous client which started that TLS session.
(The bit about "no central authority certifying Alice" is a massive, separate question -- it is the puzzle which X.509, DANE, and an entire host of decentralized proto-solutions are still struggling to solve to this day; but I'll include a proto-solution to it as well.)
With any public-key cryptosystem, it's trivial to implement an ephemeral or "anonymous" key, by simply not attaching identity attestations to a freshly-generated public key and then throwing it away afterwards; if you're only concerned with the authenticity of one party (Alice is a recognized fruit seller or someone whom Bob otherwise knows the public key of; Bob is an anonymous client with no identity persisting beyond the scope of a single discussion session), it's quite easy -- For example (all messages listed are both signed by the sending key and encrypted by the receiving key):
Bob: (Acquires Alice's putative pk_A)
Bob: (Generates a keypair sk_B, pk_B)
Bob -> Alice (sk_B -> pk_A): "Buying oranges for 3 bitcoin, reply-to [pk_B]"
Alice -> Bob (sk_A -> pk_B): [initiate zero-knowledge proof of orange possession]
Bob -> Alice (sk_B -> pk_A): [challenge proof]
Alice -> Bob (sk_A -> pk_B): [complete proof]
Alice -> Bob (sk_A -> pk_B): "send 3 bitcoins to [btc_A] if you want them"
Bob -> Alice (sk_B -> pk_A): [transaction]
Alice -> Bob (sk_A -> pk_B): [oranges]
Bob: (deletes sk_B and all trace of pk_B off his computer)

In the real-world, something like this happens if you buy something from an online merchant using a burner e-mail (or no e-mail) and either General Delivery or inherently digital data served over the same TLS connection, though without a "proof" of the online merchant's legitimacy (which, again, is a whole separate scope from merely allowing bidirectional secure communications with an anonymous participant).

[Note that Bob and Alice are switched from their canonical roles in your question; I have written my answer to reflect that, but, in the future, you should use "Alice" to represent the initiator/sender of communications and Bob as the recipient or secondary participant. Additionally, "Eve" is used to denote the malicious party -- the hacker or "Eavesdropper" -- who may be just eavesdropping, or may be launching interactive or invasive MitM attacks; her abilities are generally assumed to comprise control of the network.]


How are trapdoor functions developed/found and where can I find existing ones? Trapdoor functions are a fundamental part of public key cryptography. An example of the most common trapdoor is

Prime Factorization, used in cryptosystems such as RSA

How are these trapdoor functions found?

There are some theoretical constructions of TDP and you can find two examples in the technical report by Oded Goldreich. It is concerned with enhancements of trapdoor permutations, why they are required and two constructions of the enhanced TDP (in appendix) based on RSA and Rabin's collection.


Use additional keys to thwart key compromise? Is it good or bad practice to design crypto protocols for key compromise by using additional keys? Argument for bad practice would be: When you have a key you should trust it and not throw more keys at the protocol "just in case". Is there any research/substance to that argument? Eventually, does it all boil down to a risk analysis (cost of compromise vs cost of additional keys)?

A small example to illustrate my question:

Assume Alice and Bob regularly communicate with each other using encrypted (using symmetric $K_{enc}$) and authenticated (using symmetric $K_{auth}$) messages:

$Cryptotext = Enc(K_{enc}, msg)$
$Alice \rightarrow Bob: Cryptotext, Hmac(K_{auth}, Cryptotext))$

Very rarely they want to communicate messages $M$ whose integrity is extremely important.

Under which circumstances (if any) would it make sense to use a second $K_{auth-important}$ to protect these extremely important messages?

$Cryptotext_M = Enc(K_{enc}, M, Hmac(K_{auth-important}, M))$
$Alice \rightarrow Bob: Cryptotext_M, Hmac(K_{auth}, Cryptotext_M)$

A motivation might be that since $K_{auth}$ is used in all communication it is more exposed and at least theoretically more likely to become compromised by recording and analyzing traffic. However, the protocol becomes more complex and if burglar Bert breaks into Alice's or Bob's safe, he will still find $K_{enc}$, $K_{auth}$ and $K_{auth-important}$.

There is no one answer.  It depends why you think that keys might be compromised.  That has to depend upon a threat analysis, based upon how the protocol will be deployed  and what the most likely failure modes and forms of compromise might be.

For instance, it is pretty clear that a key that is stored in software on an Internet-connected computer is (all else being equal) probably at higher risk of compromise than a key that is stored on a computer that is never connected to any network.  This then leads to protocols where a long-term signing key is stored in a hardware security module (HSM) that's airgapped and never connected to any computer, and is used to sign certificates for emphemeral public/private keypairs, where the private key is stored on an Internet-connected computer.  Such a use of additional keys might have security benefits.

However, just adding extra keys "just in case" often doesn't make any sense, if it's not done to defeat a specific threat.  For instance, suppose we take a protocol that uses some key $k_1$ to encrypt data, and we now introduce a new key $k_2$ that is used to encrypt $k_1$.  If the key-encrypting key $k_2$ and the data-encrypting key $k_1$ are stored on the same computers, and if the underlying encryption algorithms are secure, it is not clear what failure modes would cause compromise of one of those keys without the other being compromised at the same time too -- so in such a case, adding an additional key might not add any significant security benefit.


ChaCha cipher + Poly1305 The Poly1305-AES paper summarizes the MAC as

$$ \mathrm{Poly1305}(m, \mathrm{AES}_k(n)) = {H_r(m) + \mathrm{AES}_k(n)} \mod 2^{128} $$

Can I presume that $+$ here is just meant as a form of 16-byte mixing $H_r(m)$ and $\mathrm{AES}_k(n)$, and that XOR would be equally effective (since both already are 16 bytes)?

Now following from that, if I were to use Poly1305-ChaCha, could I simply append $H_r(m)$ to the plaintext and XOR it with the cipherstream just like regular plaintext? Because the cipherstream is already a function of the key and the nonce this seems safe.

To answer your original question: no, you can't presume that you can replace the addition mod $2^{128}$ within $Poly1305$ with XOR, and not change the security properties (at least, not without some serious analysis).

The security of the MAC depends on the fact that, given any two distinct messages $M_1$ and $M_2$, and any integer $\Delta$, then the following is true only for a limited number of values of $r$:

$H_r(M_1) - H_r(M_2) \equiv \Delta\bmod 2^{128} $

In other words, if you treat this as an equation in one unknown $r$, then there is only a small set of solutions, no matter that $M_1$, $M_2$ and $\Delta$ are (assuming $M_1 \neq M_2$)

If you replace the addition in $Poly1305$ with exclusive or, then the corresponding relationship would be:

$H_r(M_1) \oplus H_r(M_2) = \Delta $

It may be the case that one might be able to find clever values of $M_1$, $M_2$ and $\Delta$ where this holds for a number of values of $r$; if this is possible, then this would cut severely into the security properties.

Now, it is possible that this altered equation also has a bounded number of solutions in $r$; unless someone does some analysis and shows that, it seems unwise to trust it.


Examples of applications that use the Schnorr digital signature? I have made a study on digital signatures, especially on the Schnorr digital signature, and I was just wondering if there is some way I can find names of actual (known) applications that have applied and used this kind of digital signature.

I haven't been able to find anything by myself, so any help is appreciated.

Despite their theoretical security advantages, Schnorr signatures aren't very popular. Probably because they were patented. Since the patents expired in 2008 they might rise a bit in popularity. But probably only in the elliptic curve form, and not in finite fields.
I don't know of any application actually using Schnorr signatures, but I know several that plan to or at least considered it. Either in the form of EC-Schnorr or Ed25519.
Both of these are essentially Schnorr signatures, but on elliptic curves. Ed25519 adds a few modifications, such as making signing deterministic and a message hash that hashes R before the message, but it's still very similar to Schnorr.

Tahoe-LAFS plans to use Ed25519
Ticket #217 - Ed25519-based mutable files -- fast file creation, possibly smaller URLs
https://tahoe-lafs.org/pipermail/tahoe-dev/2012-March/007109.html
It looks like they'll include in some places in their next big release (1.10)

Cryptosphere plans to use Ed25519
https://github.com/tarcieri/cryptosphere#readme

Bitcoin developers considered using Ed25519:
Theoretical max speeds for ECDSA verification
But it seems like they won't actually use it

EMVCo considers using EC-Schnorr in their EMV standard

EMV is a global standard for credit and debit payment cards based on chip card technology. As of end-
2010, there were more than 1.24 billion EMV compliant chip-based payment cards in use worldwide.

From the EMVCo homepage

What is the EMVCo position on elliptic curves or other alternative cryptography?
EMVCo constantly reviews alternative types of cryptography. For further information regarding elliptic curve cryptography with EMV see the ECC draft of Book 2 (June 2007) located on the EMV website under Specifications > Additional Files > New Cryptography Drafts. The EMVCo Security Working Group is considering the use of ECDSA (or Schnorr ECDSA) for offline card authentication and the use of ECIES for offline PIN encipherment.

From EMVCo Security FAQ


Onion address encoding Could you please explain what the pipe (|) in tor specification means -- is it a bitwise or or a concatenation of the values?

  Encoding onion addresses [ONIONADDRESS]

  The onion address of a hidden service includes its identity public
  key, a    version field and a basic checksum. All this information is
  then base32    encoded as shown below:

  onion_address = base32(PUBKEY | CHECKSUM | VERSION) + ".onion"

  CHECKSUM = H(".onion checksum" | PUBKEY | VERSION)[:2]

  where:

  PUBKEY is the 32 bytes ed25519 master pubkey of the hidden service.
  VERSION is an one byte version field (default value '\x03')
  ".onion checksum" is a constant string
  CHECKSUM is truncated to two bytes before inserting it in onion_address

From the context, I understand it is a concatenation-- is that so?

If one has a working short Python\Node\Ruby snippet for that, it would be lovely.  :)

As you suspect, it's a concatenation symbol. Some times it's $|$ and others $||$.  Or $+$. Python and PL/SQL examples to confirm. Or a cryptographic example: bottom of page 5 of FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and
Extendable-Output Functions.

If it were bitwise OR, you'd make a real mess of the public key's use with PUBKEY | CHECKSUM | VERSION.

It can get weird though if you dig deeper as: Is there a common symbol for concatenating two (finite) sequences?


How many different keys can be derived with HKDF before two outputs are identical? How many different keys can be derived with HKDF before two outputs are identical?
This question is about collision resistance, not about generating different keys with different parameters (eg. different salts/info parameters).
For HKDF with SHA-256 would it be $2^{128}$ since the collision resistance of HMAC-SHA-256 is 128 bit?

I've seen this a few times, so I want to point out something that is a general misconception. People often think that for key derivation, it's really important that I don't get repetition, since that is a break. However, this is actually very not true, and the opposite is true. I will explain.
The "ideal situation" is to just choose keys, truly at random. In this case, if I am working with 128-bit keys, the birthday paradox still holds. As such, after generating $2^{64}$ truly random keys, they will repeat. This is not a problem at all. On the contrary, it guarantees that even if you saw all of the previously generated keys, you have no information on the next one. Furthermore, all (symmetric) encryption uses an IV, so you'd need the random IV and the key to collide in order to be able to detect that two different people/cases are using the same key.
One would think that it would be better to choose keys purposefully so that they don't repeat. But this would mean that keys get less and less random, and have lower entropy as time goes on. In particular, given past keys, the new key is known to not equal any of those. So, we actually do not want to do that.
Just to stress this, using AES for key derivation directly (e.g., in CTR mode), the quality of the key derivation goes down when you get close to the birthday bound because the keys can't repeat. Thus, since the keys can't repeat, that means that the key does not look like a random one. I know that this is the opposite of most people's intuition, which is why I felt it important to point out.


Is collision resistant hash enough for one-block counter mode? Let $H:\{0,1\}^*\rightarrow \{0,1\}^\ell$ be a collision resistant hash function (CRH), and let $\Pi = (\mathsf{enc,dec})$ be an encryption scheme with the following properties:

$\Pi.\mathsf{enc}: \mathcal{K} \times \{0,1\}^\lambda \rightarrow \{0,1\}^\ell, \lambda\leq \ell,$ define as follows: $\Pi.\mathsf{enc}(k,m) = m \oplus H(k)$
$\Pi.\mathsf{dec}: \mathcal{K} \times \{0,1\}^\ell \rightarrow \{0,1\}^\lambda$ define as follows: $\Pi.\mathsf{dec}(k,c) = c \oplus H(k)$

is $\Pi$ chosen plain-text secure (CPA)? To the best of my knowledge, if $H$ is modeled as a pseudorandom generator (PRG) or a pseudorandom function (PRF), then $\Pi$ is CPA if a distinguisher cannot distinguish the output of the PRG/PRP from an output produced by a truly random function. However, I am not able to find such a reduction for a CRH.
Let's say Alice uses $\Pi$ to share a message $m$ over pair-wise channels with Bob and Charles (Alice-Bob, Alice-Charles share a symmetric key produced by a Diffie-Hellman exchange).

Alice sends $c_b = m\oplus H(k_{AB})$ to Bob and $c_c = m\oplus H(k_{AC})$ to Charles

Let's assume Decisional Diffie-Hellman. if an adversary is able to break the CRH, can it extracts $m$ from $\{c_b, c_c\}$? (we can assume that besides Bob and Charles, Alice sends the same message to other people).
Edit: I think the answers to this question help explain why CRH is not enough to provide CPA security. However, in my opinion, it does not fully answer this question because, as mentioned in the answers below, simply providing a uniformly distributed output does not imply CPA. Non-determinism is needed.

It depends what you mean by collision resistance.
If by collision resistance you mean that the output of $H(.)$ cannot be distinguished from a stream with full collision entropy (i.e. a $H_2=\ell$) then by Jensen's inequality we cannot distinguish from a stream with Shannon entropy at least this large and so the conditions for a one-time pad are met.
If by collision resistance you mean that hash function collision cannot be found without less work than $n$ hash function evaluations, then no. Let $n=2^{256}$, let $\ell=1024$ and define $H(x)$ to be SHA3(x)||SHA3(x). Collisions in $H(x)$ are in one-to-one correspondence with SHA3 collisions and so cannot be found with fewer that $2^{256}$ hash evaluations (with the proviso that SHA3 remains strong). Thus there is a 256-bits of collision resistance, but the encryption function is now horribly weak as the every other 512-bit block of key stream is a repeat of the previous.


Operation which needs much computing power to be created, but just a little to be solved? Does somebody know a cryptographic/mathematic operation, that needs much computing power to be "encrypted"/"created" but doesn't need much power to be "decrypted"/"solved"?

Lots of problems are hard to solve but easy to check. For example:

finding hash pre-images of particular values such as 0
calculating discrete logs of small numbers modulo a prime
finding the factors of a large composite of a special form like $2^p-1$

I don't think there's an essential difference between solving and checking they're just arbitrary descriptions of the operations.

I imagine an unstated requirement of your question is that it should not be possible to pretend to have solved hard problems by generating random solutions and then saying that you arrived at the solution by solving the hard reverse problem.
This is a bit like shooting arrows randomly into a wood and then painting targets round the arrows wherever they have stuck in the trees.


Can a nonce be used to steganographically hide a message? If a standard encryption scheme involves a nonce, as most do, can the nonce be used to hide another small message?
That is, the nonce (rather than being randomly generated) is a hidden message XORed with another secret key.  As long as this other secret key is hashed/random and unique for each message, this is equivalent to random, right?
In an extended nonce setup (such as Xsalsa) 192 bits could be sent as a hidden/deniable message.  I realise this is still tiny, but it seems truly deniable since you are using a standard encryption scheme, therefore overcoming the issue detailed in the answer here.
Aside from the obvious problem/hassle of exchanging a 2nd secret key and sending small messages as a series of larger ones, is this a viable idea?

You can do this, although the implications are limited.

If you have a secret key, an algorithm, and a communication channel that can send bytes, you can send an encrypted message.
It doesn't matter what secondary uses (i.e. nonce) that data may have.  What matters is that they transmit the message.
Algorithms typically provide security proofs based on properties of the nonce.  If the nonce is indistinguishable from a random number, it can be used as if it were a random number.  If a nonce is not the product of two prime numbers, then it can be used as if it were not the product of two prime numbers.  As long as your "nonce" obeys these properties, whatever they are, it will be secure.

In general, this idea is as viable as any stenographic system which hides the content in a protocol.  Its validity depends greatly on a threat model.  Your adversary clearly has the ability to observe your encrypted traffic (or there would be no need for stenography like this).  Can they also require you to use specific algorithms?  If your approach was popular, you might run into issues where the adversary mandates an algorithm for nonce.  This algorithm may satisfy the proofs needed to ensure the underlying communications are secure, but be insufficient for use in your stenographic approach.  (for example, they might require you construct nonce from a merkle tree, and provide them the frontier of the tree at any time to prove you are using their algorthm.  This could decrease the bandwidth of your stenographic channel to any arbitrarially small amount)
The most likely issue would be an algorithmic proof of the underlying communication algorithm which depended on a property you no longer had.  For example, there are communication schemes which depend on the unpredictability of an initialization value to prevent replay attacks.  If your stenographic communications get cracked enough to start predicting the nonce on your future messages, you may become susceptible to replay attacks that you would otherwise be immune to.  This is a case-by-case thing, so you'd have to go into the specifics of your underlying message stream to see whether such an exploit might accidentally arise.


should one worry about timing attacks with signature verification? To compare two varablies in such a way that timing attacks don't exist it's generally recommended you pad the strings to the same length and then look at each byte, even if an earlier byte was different.

In ECDSA and DSA you compare $r$ to some value to see if the signature is valid. But I'm thinking that there's no need to do a timing insensitive equality test because, with signature verification, you're using all publicly available information anyway?

Correct.  In fact, often—and pretty much always for their modern cousin EdDSA—the verification procedure is implemented with variable-time operations, because there are no secrets involved.

However, you may wish to take care in case you rely on key privacy anywhere in your protocol.  The paper is presented in the public-key encryption setting (distinguishing ciphertexts under one unknown key from ciphertexts under a distinct but also unknown key), which is straightforward to transfer to the public-key signature setting (distinguishing signatures under one unknown key from those under another)—but maybe the adversary in your case wants to learn which public key you're verifying signatures of, and does so by probing how long it takes to compute a rejection with various different signatures.  It's a stretch—and maybe it's actually moot for some reason that I haven't thought of—but I'm not aware of any research on that specific question.


Problem with this authentication protocol Consider such authentication protocol:

Alice and Bob share a key.

Bob sends alice a nonce.
Alice encrypts it with shared key and sends to bob.

Now assume Alice was successfully authenticated.

But there is such attack mentioned

  Trudy can hijack connection after authentication, if she can send
  packets with Alice’s source address

This seems to be a general problem with authentication protocols. Even if steps 1 and 2 are secure and authentication protocol is secure, trudy can always mount above mentioned attack after the authentication protocol is finished, isn't it?
How are such problems dealt with?

This is usually solved by creating a session key as part of the authentication process, then using authenticated encryption for the whole session. This is how e.g. TLS does it. Even if an attacker could hijack the connection, they do not have the session key so they cannot produce valid data.

The session key can be constructed in various ways. For example, a very simple, purely symmetric key protocol could have Alice generate a random key, encrypt the nonce using that key and the session key using the longer term key. The rest of the session would be encrypted and authenticated using the session key.

In practice it is a good idea to use something like Diffie-Hellman key exchange, since it gets you forward secrecy, among other things.


Is succinct verification of an arbitrary data transformation theoretically possible? Is it feasible? How? Given input string S, and transformation (i.e. computer program) T, is it possible to provide a succinct proof that another binary string S' is identical to the output T(S)?

By "succinct", I basically mean significantly less computationally intensive than repeating the original transformation. Also, I am ok with limiting the operations that can be performed by T to a specific set, but ideally this set should be Turing-complete.

I am encouraged by what I have read about zk-SNARKs that this type of thing is at least within the realm of the conceivable, but much of the underlying cryptography is currently unfamiliar territory to me, and it is not clear whether this type of proof is something I can use in my code, how much effort this would take, and how much compute power would be necessary for sizable input data sets.

Ideally, I'd like to leverage a reasonably friendly API to a well-written cryptographic library, but I am also willing to do a fair amount of the grunt work and open-source what I come up with.

Direct answers, as well as any helpful resources, will be much appreciated.

Terminology: "public-coin" means the verifier does not need to keep any of its

randomness secret, and "private-coin" means "not necessarily public coin".

By IP = PSPACE, the correctness of operations can be interactively verified by a public-coin verifier whose runtime scales with the amount of space used for the transformation.

Such protocols can be modified so that additionally the verifier only needs an amount

of space that is logarithmic in the amount of space used for the transformation,

at the cost of becoming private-coin and the resulting protocol's number

being something like the square of the original protocol's number of rounds.

This paragraph is about protocols which emphasize the verifier using very little space.

Theorem 1 of Interactive Proofs for Muggles gives such a protocol in which the

verifier is public-coin.  These two papers apparently give up [public-coin]ness (at least

my search didn't find any reference to the property) in return for more efficiency gains.

I do not know of any way to combine the IP=PSPACE results with

the low-space results or even achieve any tradeoff between them.

  Although you only asked about proofs, you mentioned SNARKs,

  so the rest of this answer is about arguments rather than proofs.

By this paper, collision-resistant hash families are enough for all T with a public-coin

verifier and a constant number of rounds.  By this paper, fully-homomorphic encryption

is enough for all T with a private-coin verifier and 4 messages (2 in each direction).

Theorem 2 of Interactive Proofs for Muggles claims that a PIR scheme with bounded communication is enough for uniform low-depth T with a private-count verifier and

2 messages (1 in each direction).  However, as far as I can see, they also need

the PIR scheme to be 2-message (which all current candidates I'm aware of are).

This paper's results are similar to the previous paragraph.  Based on the title,

I imagine that SNARKs for C is the most practical candidate SNARK scheme.


How to measure brute force speed of a computer for a give cipher with given number of keys for second for a given key space As I understood brute force attack is measured in number of keys which in turns give time required based on speed of computer

It is quite interesting find out how effective an arbitrary computer is and estimate to total time required to try all number of keys in a given key space.

Are there any tools available to practically estimate the effectiveness of a computer to try all number of key in a key space to brute force attack block cipher.

For example

key length: 32
key space:  2 ** 32
Time:
   10 ^ 9 keys/sec = 4 sec
   10 ^ 12 keys/sec = 4 ms

Theoretically we can calculate with all these assumption. But, is there any way/tool/application to measure speed of a computer and how many keys it can try per second without trying all number of keys in key space.

Your question is too broad. What algorithm you mean? Brute-forcing DES is different from brute-forcing AES-256 GCM.

Also if you have some scheme where password is derived using Argon2, then password derivation itself can be essentially slower than the actual encryption.

It depends also on implementation of brute-forcing. Less skilled attacker can try every possible key and will perform the whole sequence of the algorithm that is being brute-forced. Where as skilled attacker will be aware about known attacks on particular algorithm and will implement brute-forcing more efficiently; depending on algorithm this can be a few bits, can be also much more.

Try to formulate your question more precisely. Then you will get more precise answers.


Is there parameter recommendation of DSA or RSA? I know there are recommendations of elliptic curve parameters (such as NIST P-xxx).

Are there recommendations of DSA (or DLP such as Schnorr signature) or RSA parameters?

If not, why?

Are there recommendations of DSA[...]?

Yes, but you really want to verify these parameters yourself. DSA uses - as parameters - $(p,q,g)$ such that $q\mid p-1$ and $\operatorname{ord}(g)=q$. Among other things you want to verify that $q$ is prime, that $p$ is prime, that $q\mid p-1$ indeed holds, that $g^q\bmod p=1$ (ie that $g$ has the alleged order), that $p>2^{2047}$ and that $q>2^{255}$.

  Are there recommendations of [...] RSA [..]?

No, but you can re-use the public RSA exponent safely. To understand what can  be shared and what not, we first need to understand the relevant RSA parameters which are $(N,e,d)$ such that $ed\equiv 1\pmod{\lambda(N)}$ where $\lambda(\cdot)$ is the carmichael function. Now note that $(N,e)$ forms the public key and given just $N$ recovering $e$ or $d$ from each other is equally hard (ie as hard as brute-forcing the value). Note however that given a valid $(N,e,d)$ one can recover the factorization of $N$ (by applying the classical part of Shor's algorithm) using which one can break all other key-pairs $(N,e')$ (by the same way you'd normally find $d$ when generating the key), so sharing $N$ is out, but sharing $e$ is fine and commonly done with the value $e=65537=2^{16}+1=F_4$, where $F_4$ is the fourth fermat number.