What are the leading FHE schemes? I'm trying to understand the current context for fully homomorphic encryption. What are the most influential papers that are the basis for the most close-to-practical techniques today?

Of course Gentry's original paper is the most influential, but it is far from practical. A 2011 paper I see that appears to achieve much better performance (also by Gentry) is https://eprint.iacr.org/2011/277.pdf. What other papers published in the last 7 years are worth reading? (I would prefer papers with a post-quantum context in mind).

In short

BGV (the one you linked), FV and GSW.

More details

The scheme you have linked is known as BGV and I would say that it is the most important. There is a public implementation on Github.
If the application can run in parallel, then BGV is probably the best current choice, because its plaintext space can be view as a product of rings, which gives the user the ability to encrypt several values in a single ciphertext. Then, a single homomorphic operation is actually equivalent to several plaintext operation in parallel.

The FV is another scheme with that feature and is the one that SEAL implements now.

If the application can't take advantage of the parallelism, then, I think the best choice nowadays is the so called FHE over the Torus, or TFHE.

Since you asked for influential papers, it is worth noting that TFHE is based on FHEW, by Miccianco, which is based on a paper by Sheriff Peikert, which is based on (this highly influential paper) GSW, again by Gentry.

Also, YASHE had an efficient version that was implemented by SEAL before, but it turned out to be insecure.


How secure is this logarithmic encryption algorithm? How secure would the following logarithmic encryption algorithm be when tested under the same conditions as high end encryption algorithms (AES, RSA etc...).

Note: For smaller text the text will be padded to form a minimum length of 1024 bits.

For encryption:
1.  Generate random numbers as same length as the message.  R = [5, 13]
2.  Turn message characters into ordinal numbers.  M = [97, 98]
3.  Encryption algorithm is as follows: M^x = R; to solve this: x = log(R)/log(M)

For decryption:
1.  To find the original ordinal number again: M = x_sqrt(R, x); x_sqrt is to find the nth_root of a number, where R is the the radicand and x is index.

Example:
R = [13]
M = [98]

Encryption:
M^x = R
: 98^x = 13
: x = log(13) / log(98)
: x = 0.559425856

Decryption:
M = x_sqrt(R, x)
: M = x_sqrt(13, 0.559425856)
: M = 98

I'll assume R is secret, and is the key; and the ciphertext is given as a list of values x in decimal, as in the example given x = 0.559425856.

This is totally insecure: even without knowledge of R, it is trivial to reduce candidate plaintext letters to almost nothing, just by knowing the corresponding x. e.g. if we assume R is an integer in range [2..127], and x = 0.559425856, the only pair (R,M) possible is (13,98). That can be seen by tabulating x by increasing values as follows

 x               R        M
0.557913767     10       62
0.558189871     13       99
0.558248536     14      113
0.558830625      9       51
0.558890092     11       73
0.559030886     15      127
0.559300193     14      112
0.559329667     12       85
0.559425856     13       98
0.559944654     15      126
0.559957234      8       41
0.560120590     10       61
0.560365305     14      111
0.560680089     13       97
0.560692653     11       72
0.560823605     12       84
0.560868731     15      125
0.561444177     14      110

The problem can NOT be fully fixed by giving just enough decimals of x to allows decryption (here, x = 0.559 would do if we round to the nearest), for that still allows to reduce the possibilities in the plaintext a lot.

A lesser problem is that if the plaintext gets known, it is trivial to find R. Hence R can not be reused for different plaintexts. Hence this is not a cipher by the modern definition of that, which requires that there's a key reusable for several messages. That also makes use of the system impractical, as the OTP is; but at least that one is secure.

Also, the ciphertext is larger than the plaintext; another problem that the OTP does not have.


Can the ECDSA still work without present of hashing function? According to walkthrough steps for ECDSA topic from wikipedia as shown below, What if the impact if we don't apply the hashing function (highlighted in blue in the image) to the raw messages?
Although this sounds a bit silly, but let's say we have both with or without SHA256 engine test cases like below.
Hex Message (256 bits):
"0123456789012345678901234567890123456789012345678901234567890123"
Hex Message after SHA256 (256 bits):
"9674d9e078535b7cec43284387a6ee39956188e735a85452b0050b55341cda56"
Can anyone explain what is the problems with the first Hex Message if I proceed with this to the subsequent ECDSA signing flow?
Just assume Alice signed the raw message in this case?

The truthful answer here is that I don't know. I am pretty sure actually that the better answer is that this is unknown.  The assumption that the hash is only required for collision resistance is blatantly false, since typically one needs a random oracle for such schemes. In ECDSA specifically, we don't have actually have proof of security even with a random oracle, so it's even worse. However, given that it's been around for so many years, its security is essentially a well accepted assumption. However, as soon as you change something, and not hashing the message is certainly changing something, then it falls apart.


Combating traffic analysis over request-response protocols Suppose I am to design a request-response protocol (similar HTTP). For the sake of simplicity let us assume that this is a "chat" protocol where the client can only perform two actions:

Contribute a message to the chat, where the server responds verifying that the message was sent.
Request the chat contents, where the server responds with the chat contents.

All requests and responses have confidentiality, authenticity and integrity assurances. Requests and responses are of variable size.

In this protocol, a passive attacker can apply traffic analysis to estimate the size of a message sent, estimate the size of the conversation contents and distinguish between the two types of requests and responses.

The most obvious way to combat this type of traffic-analysis is to send and receive messages of fixed length at fixed intervals, however, due to the nature of the protocol, this is not possible.

How does one combat traffic analysis in such protocols without changing the nature of the protocol or wasting (a lot) bandwidth?

Update: Some of the information derived from traffic analysis of the protocol is of negligible importance for civilian purposes. I am mainly attempting to reduce the amount of information gained from the length of a request or response.

Suppose that the server supports multiple "chatrooms".

Here are two examples of how an attacker could utilize the length of server responses:

Given that different "chatrooms" do not have contents of equal size, the length of a server response to a "chat contents" request will differ for every "chatroom". This allows a passive attacker to distinguish between "chatrooms" that the user might be accessing.
In the same way as above, a passive attacker that can monitor the traffic of two users can detect if they participate in the same "chatroom".

I would try to exploit the fact that client and server use a unique session, that communications are strictly serialized, and that messages are neither lost nor duplicated (if any such assumption does not hold, I guess it is simple to add a protocol for that). I would also consider the "chat contents" sent back by the server as one the messages (just very big).

To say, let's assume that - as first operation during the handshake- the client and the server agree on a certain randomized dictionary, where each message symbol (letter, group of letters, words, etc) is represented via a communication symbol.

Messages are then communicated only via the new encoding. Moreover, each symbol being produced and received influences the dictionary shared by each end. As result the dictionaries will change constantly, but will remain in sync. Think of an unoptimized adaptive Huffman encoding (if it were really optimized you would give away symbol frequency).

If sessions are long lived, building of the initial dictionary would take negligible bandwidth. I cannot really say what the real bandwidth overhead will be, but if the update mechanism for the dictionary is reasonable, it may be quite low.


Secure Multiparty Computation with Secret Output Is there any MPC scheme that allows a function with several secret inputs to be computed, while the output can only become known to one specific party?
If not, is this even possible?

Yes, all of them support this.

Garbled Circuits
I'll focus on the 2-party case when it comes to garbled circuit based schemes. In these schemes, you typically have one party that garbles the circuit and their own inputs. The second party executes the garbled circuit. To input their values into the computation, an oblivious transfer protocol is often used.

So, say the party that should receive the output is the one executing the circuit. If the party who constructed the circuit, constructs it so that the output "wires" are plaintext, then the executing party gets the answer. Now they simply just don't send the output to the first party and the output remains private to them.

On the other hand, if the party that should receive the output is the one who garbles the circuit, they can simply mask the output wires with a random value. Then the party doing the circuit execution cannot know the outputs. That party sends the output values to the first party, who can unmask them.

Secret Sharing
The other type of MPC we typically see is secret sharing based. In this variant, each party secret shares their inputs with the other parties in the computation. They then compute on the secret shares. At the end, they have shares of the output values. If everyone is suppose to know the output, the parties simply broadcast their shares of the output to all other parties. If only some parties are suppose to know the output, each party can instead send their shares of the output to those authorized to know the output. As long as the thresholds of non-corrupt parties are met, a corrupt party who is not suppose to learn the output cannot.


How does bitmessage encryption work? I have been reading around protocol specification and there is either too much technical detail or too bad articles on various sites.

I need you to explain in simple words how encryption in bitmessage works and what are main security flaws of bitmessage and why?

To be more detailed with with my question I want to understand how asymetric encryption works in bitmessage and why there are collisions with addresses? how is private key stored(or not).

an example of ie. Bob and Alice exchanging a message over bitmessage (with encryption details) would be great!

BTW. Can somebody please create "bitmessage" tag...

I'll answer your "detailed questions", I'm sure the "main security issues" will become obvious afterwards.

How does asymmetric encryption work in bitmessage?
The bitmessage wiki explains how the encryption takes place. I'll quickly explain the basics.
For each message, generate a secure 128-bit IV. Generate a new message key by generating a new ECDH key pair and "agree" on a shared key with the recipient's (=Bob) public key. Hash the shared secret (using SHA-512) and use the first 256-bit as key for HMAC-SHA-256 and the second 256-bit as the key for AES-CBC with PKCS#7 padding. Encrypt the message using this symmetric encryption scheme and form the HMAC on the ciphertext. The message will be composed of the IV, the public ECDH value, the ciphertext and the MAC.
Decryption is pretty straightforward. Derive the shared key using the provided public ECDH value and your private key, derive the authentication key, check the MAC is correct and decipher the message. If the MAC's invalid discard the message as "not for you".

Why there are collisions with addresses?
The way the public addresses are generated is quite complicated and is documented here. I'm not aware of any collisions, however the collision resistance isn't also at 80 bits. Basically you'll obtain a collision if the RIPEMD160 of the SHA-512 of the two public keys (encrypting, verifying) yields a collision. Now the odds of finding a collision are even a bit lower than the birthday bound of RIPEMD160 (80 bits) as the hash has to start with a zero (or more zeroes). Furthermore the addresses have to live in the same stream (at the moment there's only one) and they have to share the address version.

How is the private key stored (or not)?
The protocol doesn't describe how the private key is to be stored. However the reference implementation does the following:
The private key is stored keys.dat, without encryption, easily accessible by anyone having access to this file. In case of deterministic addresses it can be reproduced with a passphrase, in case of random addresses it can't be.

As you see, the main security issues with the points you mentioned are, that the keys are stored unprotected and that the uniqueness of addresses relies on the collision resistance of RIPEMD160.


How does ECDSA signature verify work in EOS and ETH/BTC, compare to standard (on text book I mean) I have been studing ECDSA signature/verify for a while. By my understanding: the standard ECDSA signature/verify process (which we find on text book) are like below:

- A sender combines message and its ECC public key (pk), do hash, then using ECC sk (private key) to generate signature; it then append the signature with the message (ECC pk include), send all these to receiver;

The receiver do ECDSA verify by using the ECC pk, the message and the signature output true or false;

Question1: for EOS signature verify process looks not likely align to a standard ECDSA signature verify above:

A EOS node may need do two kinds of ECDSA signature verify:

1). Check each Tx signature--from code it use a routine naming as get_signature_keys, indicate it recovers the pk? Then follow up by a routine naming as check_authorization (this does not like a real signature verification, I couldn't understand what a "check authorization" means--by all mean it does not like a signature verify);

2). Check a Block's signature, this routine (name as "verify_signee") however, looks likely a real ECDSA signature verify.

Question2: I know BTC/ETH may adopt quite different method as they are PoW so each miner must do signature verification for each Tx inside a block, but as they have much more time (several minutes) than in EOS, they would be using the standard ECDSA verification?

The two questions are somehow related. The answer to your question (2) is no. In BTC/ETH, signature verification is like the first method you mentioned: the verifier extracts the public key from the signature, hash it, and compare the results to the address where the coin comes. If so, the signature is valid.

The main reason why this is used instead of the normal ECDSA verification is that when you verify a signature, you don't have the public key, but only an address that is the hash of the public key. Therefore you cannot verify using the normal procedure. The key recovery procedure is another way to verify signatures without much security loss.

Edit to add: The signature is generated using the normal ECDSA signature algorithm. Recovering the public key from a signature is a well-known trick. For example, it is documented in Section 4.1.6 of SEC 1. See also one of the answers for this question for a better explanation. Note it is possible to recover two candidate public keys from a signature, but as I said, this is not going to result in much security loss. See the discussion here.

Now for the "check authorization" part, a transaction in EOS may require authorization from one or more accounts. So the system verifies that the transaction has been signed by all of the necessary signatures to grant the specified authorization.

Then for the block signature verification, in EOS, there are only 21 producers that can generate blocks. Each producer has a producer key. This is the key for signing blocks and identifying themselves. This key cannot sign transactions on EOS, it can only sign blocks. Therefore it cannot transfer or claim EOS. The producer public key is known by parties who verify blocks, thus the normal ECDSA verification is used.


How secure is SHA1? What are the chances of a real exploit? I read that, in February 2017, a SHA1 collision was calculated for the first time. This, and earlier theoretical proof, means that SHA1 is officially cryptographicaly insecure. But, when using SHA1 in a protocol (SAML assertions in my case), both the protocol dictates a certain message format and the information in the message has to be meaningful to create a real collision exploit. Under these circumstances, how feasible is a real exploit?

Not being hindered by any real knowledge in the field I suspect this will 'never' happen. Or am I missing something?

Actually SHA-1 has been "officially insecure" for a longer time, since an attack method was published in 2011. The 2017 collisions was just the first known case of actually running the attack. But everybody was already quite convinced that the attack worked, and, indeed, the 2017 collision was produced with the expected computational cost.

The important point is that we are talking here about collisions. A collision is when you find two distinct messages that are hashed to the same value.

In many protocols, collisions don't matter; what is important is the resistance to second preimages. A second preimage is like a collision, except that the attacker does not get to choose one of the messages; the attacker is challenged to find a colliding pair of messages, the first one being fixed. Finding second preimages is a lot harder than finding collisions. For a "perfect" hash function with a 160-bit output (like SHA-1), a collision can be found with effort 280, while finding a second preimage requires effort 2160 (i.e. a million billion billion times more). Moreover, while a structural weakness is known in SHA-1, that allows lowering the cost of the collision attack from 280 to 263, making it merely "very expensive", no such weakness is known that would help for second preimages.

So right now, SHA-1 seems still very very robust for second preimages, and any protocol that uses SHA-1 and relies on second preimage resistance can keep on doing so safely for the time being.

The tricky issue is to determine if a given protocol relies on second preimages, or if collisions can impact it. SAML is a complicated beast. It seems that it uses SHA-1 in conjunction with digital signatures, and this relies on second preimages, except in situations where attackers can get to choose part of the data that is being signed, in which case they might want to exercise a collision between "innocent-looking data" and malicious data. In the case of the published SHA-1 collision, this is done with PDF files because the PDF format is flexible enough to turn an difference in only a few bits into an arbitrary visual effect.

The cautious course of action would be to migrate to SHA-256. There is no absolute urgency to do so; but if ten years from now you still use SHA-1, then this means that your software management is terrible (and this is much more likely to be an issue than SHA-1 weaknesses).


Reverse cascaded AES encryption I was wondering if it is possible to decrypt a cipher-text using a single key which was encrypted twice.

For example: Let's assume that we encrypt a plaintext using AES-CTR and encrypt the output again with AES-CTR using a different key. It's clear that there exists a keystream that can be used to decrypt the message in one step. However, I do not know if this keystream can be generated by the AES algorithm and if we can calculate the respective key efficiently.

Dos anyone know if this is possible or has a keyword, article, blog post I could look for?

PS: I know that this will NOT increase the security.

No, the set of AES-CTR keystreams is not closed under XOR.  That is to say, in general, for any two AES keys $K_A$ and $K_B$ there will not exist a third key $K_C$ such that $$\textsf{AES}_{K_A}(x) \oplus \textsf{AES}_{K_B}(x) = \textsf{AES}_{K_C}(x)$$ for all $x$.

At least, there is no reason to expect that such a key $K_C$ could be found.  Offhand, I can't think of an obvious way to prove that one could not just somehow magically exist, but that would seem to require either a truly astronomical coincidence or a deep and fundamental weakness in AES.

In fact, there's a simple counting argument suggesting that this should never happen, simply because the set of possible CTR mode keystreams is immensely larger than the (already very large) set of AES keys.
Specifically, AES keys are 128, 192 or 256 bits long, depending on the AES variant used, but an AES-CTR keystream repeats with a period of $128 \cdot 2^{128}$ bits.  Thus, out of the $2^{128\cdot2^{128}}$ theoretically possible keystreams with that period, only $2^{256}$ can actually be generated by AES-256-CTR (and even fewer for the other AES variants).

Since the mapping from AES keys to the corresponding keystreams is supposed to be effectively indistinguishable from random, that also means that the probability of the XOR of any two AES-CTR keystreams just happening to itself be an AES-CTR keystream is at most one in $2^{128 \cdot 2^{128} - 256}$, i.e. effectively zero for all practical purposes.*

Of course, we do know that the mapping from AES keys to keystreams is not actually random, and there are even some known related-key attacks on AES that demonstrate this.  But as far as I know, nobody's ever found anything to suggest that the XOR of two AES-CTR keystreams would be any more likely to match another AES-CTR keystream than the infinitesimally small probability of that happening by chance.

*) Literally.  That's a probability of about $1/10^{10^{40}}$, i.e. about 0.00000...0001, where the ... stands for about 10 000 000 000 000 000 000 000 000 000 000 000 000 000 more zeros, give or take a few (or a few decillion).


Can elliptic curve cryptography encrypt with public key and decrypt with private key like RSA? I know that RSA can be used for both, encryption and signature.
What about EC? I know about ECDSA/EdDSA, but to my knowledge it can only be used to sign.
I also know about ECDH, but it is a key agreement protocol.
Is there some elliptic curve based public key encryption algorithm?

Yes, there is a elliptic curve based public key encryption
Let $a$ be Alice's private key and $a=aG$ be her public key. Bob, who wants to send an encrypted message to Alice, does the following :

Bob chooses a random number $r$, $1\leq r\leq n-1$ and computes $rG$
Bob then computes $M+r\alpha$. Here the message $M$ (a binary string) has been represented as a point in $\langle G\rangle$
Bob sends the encrypted text pair $\langle rG,M+r\alpha\rangle$ to Alice

On receiving this encrypted text Alice decrypts in the following manner

Alice extracts $rG$ and computes $a\cdot(rG)=r\cdot(aG)=r\alpha$
Alice extracts the second part of the pair $M+r\alpha$ and subtracts out $r\alpha$ to obtain $M+r\alpha-r\alpha=M$

There is a drawback in this as block of plaintext has to be converted to a point before being encrypted, denoted by $M$ above. After the decryption it has to be re-converted to plain text.


Are encryption algorithms with fixed-point free permutations inherently flawed? Flaw in Enigma
One of the Enigma machine's flaw was the derangement (fixed-point free permutation) of the produced ciphertext, or simply put: No plaintext-letter can be enciphered to itself. See this example from Wikipedia of how this text (in German) "Keine besonderen Ereignisse" can or can't be encrypted:

More modern encryption algorithms used during WW2, such as the Enigma-alike Typex machine used by the British, eliminated this flaw, meaning that a plaintext-letter sometimes could indeed be encrypted to itself.
And as far as I know most modern encryption algorithms (i.e. AES) also allow for the possibility of plaintext-letters being encrypted to themselves.
Questions
My questions are:

Are all encryption algorithms with fixed-point free permutations inherently flawed?
Can it be mathematically proven that all fixed-point free permutation algorithms can be broken with a "faster-than-brute-force" attack?

Are all encryption algorithms with fixed-point free permutations inherently flawed?

Yes - when fixed points, or the lack of them, is knowable and detectable.

This is a violation of multiple modern semantic security definitions. For example, this means that plaintexts with repeating symbols are distinguishable with high probability from plaintexts that has none. It means you with a high probability can determine what a plaintext does not include, especially if you can observe multiple communications.

This violates security notions like chosen plaintext attacks, indistinguishability from random, and more.

  Can it be mathematically proven that all fixed-point free permutation algorithms can be broken with a "faster-than-brute-force" attack?

It always makes it easier to guess the plaintext (as according to the answer of question 1), but it does not necessarily make it easier to derive the original key (what bruteforce normally refers to). You can often not say with certainty what the original plaintext is without the key, but often you can settle for an educated guess.


what are the benefits/limits of constructing AEAD using Duplex mode with ARX primitive (chacha20 for example)? I understand that WAGE cipher uses duplex/sponge mode with stream based cipher for  Authenticated encryption with associated data (AEAD)  and NORX uses duplex/sponge mode with LRX structure , so , Is it possible to design AEAD cipher using duplex/sponge mode with ARX structure (Chacha20)? what are the advantages/disadvantages?

I could not find an example in NIST Lightweight candidates

It is possible!

The SPARKLE suite is a round 2 family of NIST candidates that uses ARX-based permutations to build sponge-based hash functions (called ESCH) and duplex-based AEAD (called Schwaemm): see their website and the NIST list of candidates.

Some advantages of ARX would be the smaller code size and the speed it allows. A disadvantages would be a harder masking (an implementation technique preventing side-channel attacks).


Diffie-Hellman key exchange, then so what? I know how the Diffie-Hellman Key Exchange (DHKE) works. But where is it used? And ok, now both have the same key. But how are those keys used anyway?
I've heard that HTTPS is using the DHKE. Ok, but what are they doing with the key? Are they just multiplying the message with the key? And dividing by the key on the other hand?

The multiplicative DHKE and its Elliptic curve version ECDH can be used to establish a common secret between the parties. Once the key established, this key can be used to derive symmetric keys for AES-GCM, AES-CCM, and ChaCha20 which are the cipher suites in TLS 1.3. These ciphers are Authenticated Encryption with Associated Data (AEAD) and provides Confidentiality, Integrity and Authentication. In other terms, they provide the standard of IND-CCA2/NM-CCA2- ciphertext indistinguishability and non-malleability under adaptive chosen-ciphertext attack. Combining asymmetric with Symmetric encryption is called the hybrid cryptosystem and this is common practice. We prefer it since public-key cryptosystems are very slow compared to public-key encryption systems.
DHKE can be used static-static, static-ephemeral, and ephemeral-ephemeral. As of TLS 1.3, Static RSA and Diffie-Hellman cipher suites have been removed so that forward secrecy is now obligatory.
To derive a symmetric key a Key derivation Function can be used, it can be used even to derive multiple keys and IV/nonce. Once a key is derivation method is agreed on both sides, the sender can encrypt the message by one of the cipher suites of the TLS with the derived key and the other side can use the same key derivation to derive the key to decrypt.
Another example is the Integrated Encryption Scheme.


Use of Lamport's Signature as a primitive Is Lamport's One Time Signature used as a primitive to construct any other cryptographic protocols?

I don't know of a use of Lamport's scheme precisely as Lamport originally published it; however if we include generalizations of the idea (such as Winternitz signatures), then it has been used as the basis of Hash Based Signatures, such as this proposal


Implementing AES encryption for firmware distribution system I need to implement an AES encryption for firmware distribution system.
I have a bootloader that can decrypt various AES variants (ECB,CBC,CTR).

When I approached this I found few issues that aren't clear to me.

First, there's the IV vector, which is strange to me.
This vector has to be known to the encryptor and also the decryptor, does it makes sense?
On the decryptor side (source code) I need to input the IV vector, however, on the encryptor side (software encryptor) I can't choose IV vector. (NCrypt, AES Crypter lite, Kryptel). I know that ECB doesn't need one, but how can the software encryptor do CBC or CTR without it, is it randomly generated?  If so, how the decryptor will know it?
Another question is regarding the actual size of the encrypted file. It must be divisible by the block size, right?  So if my block size is 128, why the output of AES Crypter lite for instance produces a file size which is not divisible by 128?

Yes, the IV (not "IV vector" because IV = "initialization vector" :p) is public and is only used to introduce randomness in the encryption process to prevent it being fully deterministic, while still preserving entropy in the key material.
You normally send the IV along with the ciphertext (yes, it is safe if you do it right), and how it is generated depends on the mode of operation (some, such as CBC, require unpredictable IV's, while others like CTR require only uniqueness). If you have no entropy source on the encryption machine, you can keep a permanent 64-bit counter and use that with CTR, but this has a lot of gotchas and is prone to error in general, randomness is usually the safest thing to do.
No, only pure block modes such as ECB or CBC "require" the plaintext to be a multiple of 128 bits long, but this can be fixed through padding (adding some extra bytes to complete the final block, adding enough information in it so that the decrypting machine can remove the extra padding without confusion) - note this isn't completely safe either and can lead to ingenious attacks.

Other modes of operation don't actually work on the plaintext directly, but generate a bitstream of any length from the key (there is a limit but with modern ciphers it is essentially infinite) and exclusive-or it with the plaintext - this way the plaintext can be any length you want. E.g. if you wanted to encrypt a 300-bit message in AES128 with CTR mode, this is how it would go:

choose your 128-bit IV
encrypt the IV with AES128 with the key
XOR this 128-bit block with the first 128 bits of plaintext
increase the IV (before you encrypted it) by one and encrypt it again
XOR this 128-bit block with the next 128 bits of plaintext
increase the IV by one and encrypt again
you only have 44 bits of plaintext left, so XOR the first 44 bits of the 128-bit block with the remaining plaintext bits and throw away the rest

Does it make sense?


What are the contents of a certificate and how can I view it? I understand on a conceptual level that a certificate is nothing more than just a verified public key. The next question I have, is how exactly do I see the contents of a certificate? Apart from the public key it verifies are there other information that the certificate contains? Does the certificate also contains the signature of the public key etc. etc.
Pointers on how to further explore certificates would be appreciated!
Edit
I am mostly thinking about the ones used with HTTPS/TLS

HTTPS/TLS uses X.509 certificates generally. There is more detail here in the latest TLS specification.
You can view HTTPS certificates in a browser.
As per Wikipedia:
The structure of an X.509 v3 digital certificate is as follows:
Certificate

Version Number
Serial Number
Signature Algorithm ID
Issuer Name
Validity period

Not Before
Not After

Subject name
Subject Public Key Info

Public Key Algorithm
Subject Public Key

Issuer Unique Identifier (optional)
Subject Unique Identifier (optional)
Extensions (optional)

Certificate Signature Algorithm
Certificate Signature


Is battery usage an important parameter for mobile based key exchange protocol? I am studying a key exchange protocol based on public key cryptography technique specifically designed for mobile devices.

I noticed there is no importance given to battery usage by these protocols. I want to ask how important is this criteria? And if it is important, why is it ignored by certain researchers?

Here are some examples where it is ignored:
https://www.researchgate.net/profile/Srinivasan_Bala/publication/266161322_A_PRACTICAL_FRAMEWORK_FOR_MOBILE_SET_PAYMENT/links/54b649650cf26833efd36dc2.pdf

http://ieeexplore.ieee.org/document/6158876/?arnumber=6158876&tag=1 (Symmetric key technique)

The Kungpisdan Et al. paper you cite does make mention of battery powered devices with "low-computational capabilities" in section 2.2 "Mobile Payment – Problems and Limitations" although they do not describe exactly why they feel this is a limitation leaving the reader to infer the obvious 'the battery might go flat and make the user unhappy' or 'it's too slow'

But it seems they think it's very important as it is the whole motivation for the protocol they describe.

Modern 'smart phones' perform many many key exchanges, encryption, decryption, signing and so on all day every day. I'm not sure I see the problem.

You SHOULD NOT degrade the security of a system to save a few micro-amps of power.

Even embedded systems that are required to run for many years off a single battery sill use the best possible security. For example LoRaWAN uses authenticated AES with 128 bits keys.

Just to clarify my statement that battery conservation is "the whole motivation" for the protocol that was my opinion. They do also mention data costs and "wireless networks also have limitations on low bandwidth and poor reliability". Firstly protocols, be they security related or not, should be designed to be reliable on the principle that all networks are inherently unreliable be they on your phone or PC. So far as the cost is concerned the customer has already committed to downloading 100's of KB for the privilege of purchasing something via their smart phone so can probably sink the costs of using the existing secure payment service. The consumer is never going to know if they are using SET or SET/A+ or care.

The origional SET/A protocol was published in 1998 and at that time all of the above concerns were valid. Not so in 2015 when SET/A+ was proposed.


How do I figure out the number of unique combinations I am developing an algorithm that uses a lookup table to process the data, I want to know how many unique tables can be created. If I have a table of 256 values I know that 256! would tell me how many tables are possible, but the math of the algorithm moves forward or backward along this table based on the calculation so the tables are essentially circular with the first and last value sitting next to each other.  Because of this every table with the values in an order that would match exactly to another table except a different start/end would not be unique and not counted.

Without generating every possible table and testing it against others how do I figure out many tables are possible?

The number of possible unique tables for your application is $255!$.  The key term you will want to look up is circular permutation.

The number of tables you can have without wrapping around is a permutation of the elements (also called a 'linear permutation').  The number of possible tables of a permutation of the elements is $n!$, which is why you (correctly) calculated the number of possible permutations of the table as $256!$.

Because your use is circular, you would need to calculate the number of unique circular permutations, which is equal to $(n-1)!$.  So for the usage in your application where you have 256 elements, the number of possible tables is $(256-1)! = 255!$.


Input limitations on the RC6 cipher RSA has limitation in input size for encryption and decryption.

Can RC6 be used for encryption and decryption of files larger than 5 MB?
Is there any limitation for input size?
Is RC6 safe for using encryption or has it faced any attacks?

RC6 is secure, and has no effective limit on input size.

RSA is an asymmetric cipher. It is not designed for general purpose encryption, and so has a very tight limit on the amount of data that can be encrypted. In fact, unlike symmetric ciphers, textbook RSA is based on a mathematical problem, so the ciphertext is the plaintext raised to an public exponent, modulo a large public integer. This modular operation puts a hard limit on the length of the plaintext to be encrypted. Note that RSA is not used to encrypt anything directly. It is used to encrypt a smaller symmetric key which is then used to protect the confidentiality of further communications.

RC6 is a symmetric block cipher. The amount of data that can be encrypted with a single key depends on the mode of operation in use, as well as the block size of the cipher. For a cipher with 128-bit blocks, like RC6, the amount of data it can securely encrypt is vast. To put it into hard numbers, in order to have an already astronomically small 2-32 chance of leaking a little bit of information from one 128-bit block in CBC mode, you need to encrypt more than four petabytes of data with one key. A mere five megabytes is nothing.

There are no known attacks which weaken RC6 to the point that breaking it is practical. As it did not win the AES competition however, it has received comparatively less analysis. A large amount of information on its security can be found by searching "rc6 cryptanalysis pdf".

Obligatory disclaimer: Choosing the cipher is the easiest part of implementing a secure cryptosystem. If you are designing your own cryptosystem, don't. Simply using RC6 is not enough to provide security. You need to choose the proper mode of operation, use authentication, use a secure KDF if the key is to be derived from a password, mitigate a variety of attacks if used on the network (reflection, replay, man-in-the-middle, etc). Don't think that, just because you are using a secure cipher, that the data you encrypt is secure.


Is there any way to check hash of homomorphic encrypted data? I need some algorithm that satisfies:

H - hash function
Enc - encryption function (using public key)
M - secret data
$Enc(H(M)) = H(Enc(M))$

Let this system exist: the First person has a secret data $M$, he publishes hash H(M) so everyone knows it. He encrypts data with public key of the second person and publishes it, so second can get and decrypt it. But the third person needs to check if the published hash is a hash of data that was encrypted and sent without knowing the data.

Note: I'm not a cryptographer, please take what I write below with a grain of salt. Most probably this protocol, without further fixes (or even fundamentally), is flawed.

I'm reformulating your question as follows, dropping the hash requirement, and replacing it with an interactive proof.

Alice has a message $m$ and wants send this message $m$ to Bob.
Charlie is monitoring the public communication between Alice and Bob; and wants Alice to publicly release a blinded version of $m$; so that he can verify Alice indeed is sending the encrypted version of $m$ to Bob.

The protocol has 2 parts in it; but first let's define the parameters.

$m$ is the message from Alice to Bob
$(e,N)$ is Bob's RSA public key, $(d,N)$ is Bob's private key.

Encryption and Blinding

Charlie creates a random number $1 < r < N$ and announces it publicly.
Alice computes the following values:

$x = m^e \bmod N$ (RSA encrytion)
$x_{blinded} = (m * r)^{e} \bmod N$ (Note that $(m * r)^{e} = m^e * r^e$)

Charlie then, verifies $x_{blinded} = x * r^e$ (this way Charlie ensures that, $x$ indeed contains the encrypted message)

Decryption

Bob decrypts $x$, calculating $m = x^d \bmod N$ (RSA decryption)


Comparison of values in Paillier homomorphic encryption For a project, I am using homomorphic encryption with the Paillier cryptosystem, and I have to compare two values...

Can this be done using homomorphic encryption?
And I know subtraction can be done using homomorphic encryption, but can anyone simplify the steps?

Any advice will be helpful.

Can [comparison] be done using homomorphic encryption?

Not without interaction with the person with the private key.

Suppose there was a possible way; given $E_k(a)$ and $E_k(b)$, one could determine whether $a < b$.  If so, then one could use that to decrypt - given $E_k(a)$, one can encrypt various values of $b$ and then check whether $a < b$ or not - when we find a value $b$ such that $a < b$ and $a \not\lt b-1$, then we know the value of $a$.

Now, another possible meaning of comparison is, given $E_k(a), E_k(b)$ create $E_k(0)$ if $a < b$ and $E_k(1)$ if $a \ge b$.  In that case, Pallier along with that comparison operation becomes fully homomorphic; for example, to compute the NAND of $E_k(a)$ and $E_k(b)$, one just compares $E_k(1-a)$ (easily computed with Pallier) to $E_k(b)$ - once we have a homomorphic NAND function, we can construct any circuit.

  And I know subtraction can be done using homomorphic encryption, but can anyone simplify the steps?

Given $E_k(b)$, we can compute $E_k(-b)$ simply by computing the modular inverse of $E_k(b)$ - that's because $E_k(b) = g^b r^n$ and so $(E_k(b))^{-1} = g^{-b}(r^{-1})^n$, which is a valid encryption of $-b$.

Then, we can do the normal homomorphic addition to compute $E_k(a - b)$


Allowing third party to verify and/or replay a draw I’m not an expert in crypto, and I would like to design draw system (like a lottery, but choosing one of the participants), the most open possible, allowing a third party to verify the data/draws, and even replaying it with the data, giving the exact same results.

Would it be helpful to verify the draw, if I publish the seed of my RNG, and would it be OK (as in “not compromising any security”) to do so?

Ultimately, my goal is to eliminate any chance of influencing the draws.

Here is a paper that examines one possible approach to do this.  In essense, it this allows anyone who cares to through in some randomness; when the deadline occurs, then all the inputs are published (so everyone can verify that their input was included), and then all the inputs are hashed together (using a transform that is slow to compute, but can be verified quickly).  The output of this transform can then be used directly to generate the selections for your lottery.

Because the eventual output is a complex (and hard to predict) verifiable function of everyone's input, then anyone who contributes an input knows that lottery was selected honestly.  And, because the transform is deliberately hard to compute, they know that no one could do some precomputations a few seconds ahead of the deadline, and generate an input at the last second to skew it.

The paper uses this to select a random elliptic curve; it could just as easily be a lottery...


Packet loss, AES and IV's I'm extending a VoIP application that uses UDP to transport data.
The idea is to use AES to encrypt each audio packet. For each call, a key will be randomly generated.

The scenario inclues:

Packet loss, no retransmission;
Each packet will have noice in it (so it's very unlikely to send two identical packets);
Each datagram will carry one audio packet;
Encryption key won't be stored anywhere and will be discarded after the call.
Encryption will be done using openSSL EVP, following this example.

Questions:

Which cipher mode should I use, taking into account packet loss? I was thinking about CTR since it does not depend of previous/next packet to encrypt/decrypt each packet.
Is it safe to NOT use an IV in this case (always use zero or NULL)?
As far as I got my code done, I had to initialize a new EVP context for each audio packet, so that there wouldn't be any bytes left to be written to the encrypted datagram. If I don't do this, my audio packets may be currupted. Is this the right way to overcome this issue?

Which cipher mode should I use, taking into account packet loss? I was thinking about CTR since it does not depend of previous/next packet to encrypt/decrypt each packet.

That doesn't matter too much. However, if you go for CTR mode you must make sure to never repeat the IV. Using a counter as nonce/IV is not such a good idea if there is package loss. You should probably have some way of ordering packets anyway, so you could put a sequence number in each generated packet and use that.

Note that you should not use the same key for two way communication. Also note that CTR mode doesn't protect against alteration of the data (so an attacker could at the very least insert noise). Timing and data rate may also tell an attacker a lot. With audio / voice there are a lot of ways to leak data through side channel attacks.

  Is it safe to NOT use an IV in this case (always use zero or NULL)?

Not with CTR mode if you value the confidentiality of your plaintext. When reusing a key you should generally always use different IV's. For CBC mode they should even not be predictable by an attacker.

As the data contains audio (which isn't that structured) you could possibly take some leeway with some of the constraints, but history tells us that this is very dangerous indeed. Besides that, it's often the case that packets also contain important meta-data, if just to control the network connection / stream.

  As far as I got my code done, I had to initialize a new EVP context for each audio packet, so that there wouldn't be any bytes left to be written to the encrypted datagram. If I don't do this, my audio packets may be currupted. Is this the right way to overcome this issue?

Already answered here.


Is it possible for an element to be swapped with itself in RC4? Given the design of RC4, is it possible or impossible for the values $i$ and $j$ to be equal to each other when $S[i]$ and $S[j]$ are swapped?


How to find a small generator with small inverse? Does it have negative impact to security? (for Schnorr subgroup of $\mathbb{Z}/P\mathbb{Z}$) Given a prime $P$ with
$$P= r \cdot q+1$$
with $q$ prime as well.
I'm looking for a generator $g$ of the Schnorr subgroup with order $q$ which is small by value and has a inverse (to $\bmod P$) which is small as well:
$$|\{g^i, \forall i \in [0,P-1]\}| = q$$
$$g^q = 1 \bmod P$$
$$g < m \text{ } \land \text{ } g^{-1}<m$$

To find a Schnorr group generator $g$ in general we can pick a random value $h$ until
$$ h^r \not= 1 \bmod P$$
$$\rightarrow \text{ } g = h^r \bmod P$$
To find $g^{-1}$ we can use the Extended Euclidean algorithm or just compute:
$$ g^{-1} = g^{q-1} \bmod P$$

Questions:

Q1.) What is the best way to find $g,g^{-1}$ which are each less than value $m$?  (edit: found some with step-by-step computation. Main interest now is Q3 (edit-end))
Q2.) How small can $m$ be?
Q3.) Would a small $g,g^{-1}$ have any impact to security?

Trial for Q1: Ways to find small $g, g^{-1}$
a.) pick random $v$ number and project to Schnorr group $v_s = v^r \bmod P$
(all values but $1$ of a Schnorr group are generators)
b.) compute inverse with EEA or with $v_s^{q-1} \bmod P$ (any way faster?)
c.) check if  $g, g^{-1} < m$ . If not repeat a.)b.)c.)

Another way than random picks all the time would be an initial random pick for $g$, and a 2nd random value $w$ in this group to start from. Compute the inverse of both as well and traverse through the group with new generator $g^*_j$:
$$g_j^* = w \cdot (g)^j \bmod P$$
$${g_j^*}^{-1} = w^{-1} \cdot (g^{-1})^j \bmod P$$
$$w \cdot (g)^j \cdot w^{-1} \cdot (g^{-1})^j = 1 \bmod P$$
and test if $g^*_j$ and its inverse are smaller than $m$.
This computes the values faster but will it be faster in finding suitable generator? Can it be for certain values the results lay in a valley of bad values?

Trial for Q2: How small can $m$ be?
The product of $g, g^{-1}$ need to be at least $p+1$
That means $m \ge \sqrt{p-1}$
Is there another higher border for smallest $m$?

In general the equation need to hold:
$$g \cdot g^{-1} = a\cdot P +1 \equiv 1 \bmod P $$
$$a \in [1,P-2]$$

Can the factorization of $(aP+1)$ be used to solve Q1 ($g,g^{-1}$ products of factor(combinations))?
Any way to guarantee its inside the Schnorr group?
Or just check again with $g^q = 1 \bmod P$?

Q3.) Would a small $g, g^{-1}$ have any impact to security?

It would not appear so.  It is easy to show that, if we had a generator $g$ that makes the Discrete Log (or the Computational Diffie-Hellman) problem easy, then the Discrete Log/CDH problem is easy with respect to any base $h$ that's within the same subgroup.

Suppose we had a way that, given $g, g^x$, gave us the value $x$.  Then, what we could do, given $h, h^y$ is first find the value $z$ such that $g^z = h$ (by solving the discrete log to the base $g$), and then the value $w$ such that $g^w = h^y$ (again, solving another discrete log to the base $g$); then, we have $h^{wz^{-1}} = h^y$; since we know $w$ and $z$, that tells us the discrete log.  Similar (but more complicated) logic allows us to solve the Computational Diffie-Hellman problem, given a CDH oracle with respect to base $g$.

However, this is not a complete answer to the question; it might be that the existence of a small $g, g^{-1}$ makes all discrete log/CDH problems easy.

I don't know of a way this can be disproven.  However:

None of the known discrete log methods have significant speed-ups when given a small $g, g^{-1}$ (by significant, I mean more than speeding the operation of multiplying by $g$)
For just about any prime, there will be tiny $g$ values that generate groups that contain the Schnorr group as a subgroup.  If there were a fast way to complete discrete logs with a tiny $g$ in this group, then you could use that to compute discrete logs in the Schnorr group (and although this argument doesn't take into account the tiny $g^{-1}$, there's no obvious way to use that).


Impossible hill cipher question I've been trying to solve this question from Forouzan's book ("Cryptography And Network Security") and haven't been able to wrap my head around how to solve it.

The plaintext “letusmeetnow” and the corresponding ciphertext
“HBCDFNOPIKLB” are given. You know that the algorithm is a Hill
cipher, but you don’t know the size of the key.
Find the key matrix.

I inverse the 2x2 plaintext matrix and multiple with a 2x2 ciphertext matrix and take a mod 26. However, the key matrix is always in fractions, never an integer.
It would be great if someone could point me in the right direction / tell me what I'm doing wrong.
Thanks in advance!

Two independent ideas:

In the Hill cipher, elements of matrices are in the ring of integers modulo the number of characters in the alphabet used, usually $n=26$. Therefore, as long as the denominator of a fraction is coprime with $n$ (that is, for $n=26$, if the denominator is divisible neither by $2$ not by $13$), that fraction reduces to an integer modulo $n$.E.g. $\displaystyle\frac23\equiv18\pmod{26}$ since $2\equiv3\cdot18\pmod{26}$.
The Hill cipher is sometime instantiated with a $3\times3$ or larger matrix.


Security of RSA for padding $\texttt{0x00|message|random_bytes}$ I've read this and this but I'm not understanding why padding a message with a simple random is not secure.

For example, consider a 256 bytes modulus. We can agree that the first byte from the message is 0x00, the next $n$ bytes are the message itself and the next $m$ bytes are random bytes. We have that $1+n+m=256$. The message is then encrypted with RSA. When decrypted, one can remove the first byte and the last $m$ bytes.

The first bytes 0x00 ensures that the message is less than the modulus and the last $m$ bytes will guarantee a probabilistic encryption.

Why isn't this secure?

Your message format is;

$$\texttt{padded_message} =\texttt{|0x00|message|random_bytes|}$$

You did not specify what will happen if the message is short. If we assume that it is filled with zero then a short message is;

$$\texttt{|0x00|0x00...0x00|short message|random_bytes|}$$

Now there is an active attack. Since the attacker knows the public key $(n,e)$ then the attacker can modify your ciphertext $$c = E_{k_{pub}}(\texttt{padded_message})$$ by multiplying with the encryption of $2$ $$c_2 =  E_{k_{pub}}(2)$$ and the result is;

$$D_{k_{prv}}(c \cdot c_2) = \texttt{|0x00|0x00...0x00|short message|r|random_bytes|0} $$

where your plaintext (short message) is shifted by one and a random bit value is assigned from MSB of the $\texttt{random_bytes}$.

The BT in The PKCS#1 v1.5 padding can prevent this attack. For a general answer, please see;

How does PKCS 1.5 solve the insecureness of Textbook RSA?


What are the current known weaknesses/attacks on quantum key distribution? I am writing a paper on the implementation of QKD in the future. I want to know if there are any viable attacks on the BB84 protocol or QKD in general? I know of the Photon Number Splitting attack or spectroscopy in the case of diode manufacturing but I have heard that there are already solutions for those. Are there any other attacks that I have missed out?

The Attack you mentioned (PNS) is a "hardware attack" it depends on how you physically distribute the qubits.

The only "protocol attack" (known for the BB84) is the "intercept & resend" that can be applied on every hardware you use and can be performed very easily(but Eve is easy to detect if the key is, at least, 72 bit long).

Another attack that can be performed is the man-in-the-middle, but this is not related to the protocol but to the total absence of authentication in the BB84.

This answer is focused on the BB84 protocol because of every protocol have different points of strength and weakness so "QKD in general" is a bit vague... i hope this can help you.


Secret key formed by the combination of several keys I think there exists an algorithm to create a key from the combination of a group of keys in such a way that if I encrypt a message using the key formed from the combination, I should be able to decrypt it using any one of the keys from the group. Any idea?

A trivial solution would be to encrypt the message under all the different keys and concatenate the ciphertexts. However, this obviously has a large blow-up in terms of ciphertext length.

An idea to decrease the blowup would be to encrypt the message under a new short key $k'$ to get a ciphertext $c$, then encrypt $k'$ under all the IDs $k_1,...,k_n$ individually and concatenate the results to $c$ and broadcast the concatenation.

This may not be great in practice but it has an asymptotic rate of $1$, which is better than the trivial solution's rate of $1/n$.

One caveat for both the above solutions is that there would have to be some ordering on the stations, and the stations would have to know their place in the ordering.


Block chain and storage issues On reading about block chain technology, it was observed that it leverages the distributed ledger technology through P2P, here integrity is ensured through hash computed by miners, and then is validated by all peers in the network and then added to the block chain permanently if validation passes.

Questions:

If the block chain is ever growing chain, doesn't it run out of storage? Can't this chain be removed permanently?

Does the validation require all peers to agree that the chain is valid or only the majority?

What if a malicious peer joins the group and gives false validation that a valid block is invalid? Does this break the entire chain?

If the block chain is ever growing chain, doesn't it run out of
  storage? Can't this chain be removed permanently?

No, the whole point of a blockchain is that everybody has to store a copy of the blockchain. That's what makes it decentralized, so there's no authority that stores the blockchain and "watches" over it.

The current bitcoin blockchain (as of 9th April 2019) is $\approx 211$ GBs large.

  Does the validation require all peers to agree that the chain is valid
  or only the majority? What if a malicious peer joins the group and
  gives false validation that a valid block is invalid? Does this break
  the entire chain?

Individuals always agree on the longest blockchain, since that is the one with the most work behind it. If a malicious person wants to create a longer and different blockchain he would have to outcompute everybody else who is working together honestly and that is not very feasible. The malicious person needs to have more than $50\%$ of the total computing power to fool everybody.

It could actually be possible, that a fork happens if two miners create a new block. If that happens then you just wait to see which one of the forks gets more blocks attached to it. This would then be the longest block and you then agree on this fork. The other fork can be discarded.

If you still have some questions, then I would recommend to watch this video from the YouTube channel 3Blue1Brown, it explains it quite well.


Are two outputs of a PRF computationally indistinguishable when using two different keys? Assume we have a pseudorandom function $f(\cdot)$ that maps an input to $\mathbb{F}_p$ where $p$ is a large prime number.

Assume $r_1$ and $r_2$ output of the pseudorandom function using two different keys.

Question: Are $r_1$ and $r_2$ computationally indistinguishable?

Computational indistinguishability is transitive, the proof can be found in these lecture notes. Informally speaking:

We have an advantage $\epsilon_1$ to distinguish distributions $X$ and $Y$, and we have an advantage $\epsilon_2$ to distinguish distibutions $Y$ and $Z$, and the triangle inequality gives us an advantage $\leq \epsilon_1 + \epsilon_2$ to distinguish $X$ and $Z$. Since both $\epsilon_1, \epsilon_2$ are negligible (to be more precise, negligible functions in some security parameter), their sum $\epsilon_1 + \epsilon_2$is also negligible.

For a pseudorandom function we know that it's indistinguishable from a random function, which is just a uniform distribution for every possible input. So both functions are indistinguishable from the same distribution, and by transitivity we get that they $f_{k_1}(.)$ and $f_{k_2}(.)$ are also indistinguishable.

Edit: This is only true for independent keys, thanks to Yehuda Lindell for pointing this out. The question states "different keys", which might not fulfill this requirement.

If you have dependent keys, then indistinguishability does not necessarily hold. Specifically, let $F$ be a pseudorandom function. Define $F'$ as follows: if the key $k$ is even then define $F'_k(x)=F_k(x)$; else, if $k$ is odd, then define $F'_k(x)=F_{k+1}(x)$. It is possible to prove formally (by reduction) that if $F$ is a pseudorandom function then so is $F'$. Now, consider the case that you are given $k_1,k_2$ with $k_2= k_1 + 1$. Then, with probability $1/2$ it holds that $k_1$ is even. In this case, it follows that $F'_{k_1}(x)=F'_{k_2}(x)$. Thus, $F'_{k_1}(x)\|F'_{k_2}(x)$ is not a pseudorandom string.

Under some related-key assumptions you could prove something, but this isn't standard. It's also probably beyond the scope of this question anyway.


How does the Signature Scheme in Picnic Works I am trying to understand how  signature scheme proposed to NIST, Picnic, works.

The propossal uses ZKboo and ZKboo++ as their basis. I can see how the ZKPoK works, where the witness x is some key for any block-cipher. A prover and a verifier can run a game based on MPC in the head such that they can re-encrypt some pre-define bitstring using x.

However, this is not quite intuitable translatable to Digital Signatures. For instance, the propossal suggests that I should use H(r||m) as the protocols challenge. It is not clear however, what the response (z) actually is?

In the presentations they cite easy examples such as the Fiat-Shamir transform to signal that a Signature Scheme can be easily (and naively) obtained. They even use the same terminology as when the transform is applied to the Schnorr protocol, signaling that it is enough to use the message as the challenge (e). However it is not clear to me how this can be, because I do not how to plug the challenge in. I think I am struggling to see the role of the challenge as a hash of the message during both Signing (Prove) and Verification (Verify).

How is this challenge being incorporated into z (say, as an encryption using thewitness as key?) What is actually z? And what is the equation being verified to check the validity of the signature?

Finally Kudos to the designers, I love the basic idea, I hope I manage to understand it better with your help!

There are a few steps involved in the design:
1. design a sigma protocol with special soundness.
2. transform the above sigma protocol to a nizkpok.
3. use the above nizkpok to prove the possession of x, such that F(0) = y, where y is the public key, x is the private key, F is an OWF.

The encryption is a PRF used to sample an OWF.

When talking about H(r,m), H is a (quantum) random oracle used in step 2 to obtain a nizkpok based on FS-transformation (Uhruh transformation).

The feature of Picnic is the use of MPC-in-the-head to obtain a sigma protocol with special soundness. This is done in few steps:
1. prover emulate a number of semi-honest execution of MPC where each party has input as a secret share of the witness.
2. prover commits to all views and states of all parties in all executions.
3. verifier open a selected subset of parties from each execution and check that the parties are behaving honestly.

Intuitively, is the prover misbehave for some parties, it will be caught with some probability; on the other hand, the semi-honest security of the MPC protocol ensures that even if some parties are opened, no information on other parties inputs (and thus the witness) is revealed.

Given the above, one can see that the challenge is the set of parties to open, and the response are the decommitments to open the views of these parties.


5bit ASCII armor with FEC? For transmitting a ciphertext (or any other binary data) over means which only support 5bit ASCII/Baudot characters (for example morse code or RTTY) I am looking for a way to armor my data and have it output in capital letters  and numbers only, making sure that a certain amount of characters can be sent or received wrong.
The codegroup utility does one part (ASCII armor to only capital letters) but lacks the FEC, whilst par2 FECs my data but outputs binary.
Does such a combined mechanism exist, posdibly even including the encryption part?
I am not specifically looking for programs, any description of how such a thing works would be greatly appreciated and my assumption is that the crypto community would know best.

Quick and dirty solution: split the ciphertext to be transmitted into blocks with par2 and encode each block using codegroup.  Join the blocks together with some unambiguous and easily identifiable separator.
For this specific combination you could use e.g. ----- as the separator when encoding (and maybe accept any sequence of dashes as the separator when decoding).
When decoding, split the message into blocks, decode each block into bytes using codegroup (discarding any blocks that fail to decode) and them combine them using par2 to (hopefully) recover the original ciphertext.

The reason for this particular combination is the way that par2 and codegroup work:

Par2 apparently implements an erasure code that splits the input data into a sequence of blocks (of some arbitrary number of bytes, which I believe is configurable but typically on the order of kilobytes) and adds a number of redundant extra blocks that allow the original data to be recovered even if some blocks are lost.  Being an erasure code, it doesn't even attempt to correct errors within blocks — rather, it assumes that all blocks are received either correctly or not at all.

Codegroup apparently adds its own CRC checksum to the encoded message to detect errors, and refuses to decode it if the checksum does not match.  Thus, even partial message corruption will generally result in full decoding failure.

Thus, there's no point in trying to do error correction within a single codegroup-encoded message — the CRC ensures that, with very high probability, a message either decodes correctly or not at all.  (A CRC is not a cryptographic checksum, and it's possible and even quite easy for a deliberate attacker to modify a message in a way that it won't detect.  But against random message corruption it's quite effective.)
However, codegroup and par2 actually pair up pretty well, as long as you encode each par2 block separately.  Par2 wants corrupted blocks to be discarded, and that's exactly what codegroup does.  You just need to make sure that the encoded blocks are combined in a way that lets any intact blocks be reliably separated from each other and from corrupted ones.
The resulting combined scheme may not be optimal in terms of error resistance vs. length expansion, but it should work fairly well at least against rare and/or bursty errors (which, if the message isn't entirely garbled, are likely to leave enough whole blocks intact to allow decoding).  If you expect having to deal with a high rate of non-bursty errors (e.g. single bit flips), you may need to tweak the scheme (e.g. by modifying codegroup to apply a convolutional error-correcting code instead of just a CRC to the data).

Anyway, your question doesn't really deal with encryption, so its topicality here seems marginal at best.  If you do want to also encrypt your data (which you briefly allude to in your question), the general consensus seems to be that you should do encryption and error correction in separate layers: first encrypt, then apply error correction to the ciphertext.
While error-correcting codes do share some underlying mathematical similarities with some encryption schemes, in practice their goals are different enough that trying to make a single scheme do both at once seems futile.  Separating the encryption and the error correction into independent layers simplifies the design and analysis of both components and allows you to use well tested and optimized standard designs for each purpose.
(FWIW, I tried to find a good existing canonical question on that, but the closest I got was Encryption-then-encode or encode-then-encryption?, which isn't really as definitive in its conclusions as I perceive the overall consensus to be.  But it'll do for now.)


Is encryption possible without secure random numbers? All cryptographic algorithms I know of that satisfy Kerckhoffs's principle rely upon secure random number generation. Assuming the existence of a 'numerical oracle' capable of perfectly predicting the outcome of any random number generator, is a Kerckhoff-compliant algorithm possible?

All secure cryptography requires a secrete key, it can be a symmetric shared secret or an asymmetric key pair with secret private key.
The question is how do you get a secret if there are no secure random number sources.
Note there are natural sources of random numbers which don't rely on cryptography for their security, but the question said the oracle can predict any RNG including predicting radioactive decay and cosmic rays, and the number I'm thinking of. That is an impressive oracle you have there.
If there is no initial secret, and anything we do to try to create an initial secret is detectable by the oracle then anything the legitimate user can do so can the attacker.
A secret is how we differentiate between legitimate users and attacker, the attacker is assumed to not know the secret.
With all secrets given up by the Oracle there is no difference between legitimate and attacker and no secure cryptography.


Negotiate a secure connection without certificates? I would like to have a simple  experience for a user for setting up a secure connection between two computers against a MITM attack. Something like the following:

  A number (possibly base64) appears on both screens, the user verifies
  that the number is identical and clicks OK.

Is there a standard algorithm for this?

If not - would the following be secure?

Each computer sends the other its public signing key. And then on each computer:
The keys are concatenated.
Then hashed with PBKDF2 (or the like).
The user is then shown that hash on both computers, and clicks OK on
both if they match.

Since an attacker can create signing keys quickly (since the attacker doesn't care that they be prime-based) trying for keys that will create the same hash as the one shown, the hash shown to the user would need to be relatively long (~100 bits?).

If you have a side channel where you can verify a string is identical you can simply do a Diffi Hellman key exchange and then verify both sides have the same resulting key.
If the side channnel is secure from evesdroppers you can directly compare the key. But you would probably prefer to compare a hash of the key. This also allows comparing something much shorter then the actual key.
For example I have seen systems for voice communication which after setting up the key the parties are expected to read out a verification number, but this simply assumes the mitm can not take the place of both parties and read out a different number to each. With nothing pre shared preventing man in the middle is tricky.
If you have a mitm resistant side channel which is public and very low bandwidth the above solution works. If it is high ebough bandwidth simply do DH key exchange over it.

Edit: to ensure the user can compare a short hash we should add a large random nounce before hashing the key. So a mitm won't be able to make keys which will collide with a truncated hash.


Are there any classical proven secure cryptographic algorithms other than OTP? Boiled down to the core as I understand it:

  A cryptographic algorithm has provable security if it's unbreakable, even if an adversary has unlimited computational power / time.

If my understanding is correct then cryptographic algorithms like RSA / Diffie-Hellman are not considered to be provable secure since they would be broken to an adversary with unlimited computational power / time.

The only classical algorithm I know of that behaves in this manner is the OTP. I'm specifically asking about classical algorithms because I know that there exist quantum cryptographic algorithms that are provable secure, i.e. QKD.

My questions are:

Is my understanding of provable security correct?
And if so, are there any other classical algorithms that are provable secure?

A cryptographic algorithm has provable security if it's unbreakable, even if an adversary has unlimited computational power / time.
Is my understanding of provable security correct?

It doesn't appear to be accurate. It appears to be mixing up "provably secure" and "information-theoretically secure".
You can have a system that is provably secure as some problem X, and it could easily be the case that X is easily solved. "Provably secure as X" does not mean "it's unbreakable". It's a relation, not an absolute statement.

And if so, are there any other classical algorithms that are provable secure?

So this question should probably read:

are there any other classical algorithms that are information-theoretically secure?

The standard goals of information security are confidentiality, integrity, and availability.
One Time Pads are for the goal of confidentiality.
One Time Macs are the analogous algorithm that provide information-theoretically secure integrity.
I don't believe there is any such algorithm for availability. It's not clear what information-theoretically secure would even mean in such a context.
For the One Time Pad, I think there is a proof that any encryption algorithm that is information-theoretically secure is equivalent to a One Time Pad, but I can't think of a paper/answer to point to off hand. I think the proof I am thinking of is that any information-theoretically secure encryption algorithm requires a key that is at least as large as the plaintext.


Quantum key distribution and the one-time pad Why is QKD usually associated with OTP ?

QKD is about key distribution, where as OTP is about using key as long as message to get perfect secrecy, can any one explain how they are related ?

Well, to understand why QKD is often associated with OTP, we need to review what Quantum crypto is, and why it claims to be secure.

Overall, we know of three implementable paradigms for cryptographical security:

Informational: the attacker does not have enough information to determine the plaintext from the ciphertext
Computational complexity: the process of deriving the plaintext from the ciphertext involves solving a mathematical problem that is just too difficult for the attacker.
Quantuum: the laws of physics forbids the attacker from learning the data needed to rederive the plaintext without disturbing the system detectably.

For example, OTP uses the "Informational" paradigm, while AES uses the "Computational complexity" paradigm.

Most of the cryptographical systems in use today rely on the "Computational complexity" paradigm.  It appears to work well in practice; however, there is one troubling detail; there's an assumption that the underlying problem is too difficult for any attacker, and the only evidence we have of that is "lots of fairly bright people tried to solve the problem, and were unable to".  Quantuum crypto attempts to get around this assumption by instead relying on the laws of physics; those laws have been fairly heavily tested, and it would appear to be a solider foundation than the assumption that a specific mathematical problem is difficult.

However, if you pair QKD with a symmetric cipher, well, you're no longer relying on something that is stronger than a computational complexity assumption; if the attacker can solve the mathematical problem associated with the symmetric cipher, he has broken the security.  Indeed, in some sense, pairing QKD with a symmetric cipher gives a solution that is the worst of both worlds; you get the implementation difficulties (not to mention the potential side channel attacks) that we see with Quantuum Crypto, while giving a system that's guaranteed to be no stronger than conventional crypto.

In contrast, if you don't use a symmetric cipher at all, and instead you exclusive-or the distributed bits with the plaintext bits (analogous to what an OTP does), you do get a system that is potentially stronger than conventional crypto.  Now, whether it is stronger in practice (because of the side channel attacks that have been found on QC implementations), and whether that increased strength is actually worth the considerably larger implementation cost, well, that's a different question.


Problem with a reduction using Hybrid Argument I have an issue with this proof.
We define two games:

$$H'(\lambda):$$
1) Pick $R \in \mathcal{R}(n,l)$ (the space of truly random functions from $\{0,1\}^n$ to $\{0,1\}^l$

2) we define $\mathit{Enc}'_k(m)=(r,R(r) \oplus m)$, where $r$ is random from $\{0,1\}^n$.

3)$\mathcal{A}$ is an adversary who chooses two messages from $\{0,1\}^l$

4) A single bit is choosen randomly by a challenger $\mathcal{C}$, and the message $m_b$ is encrypted

5)Receiving the message $m_b$ adversary must guess what message was encrypted.
 It is the CPA-game and so we assume that $\mathcal{A}$ have access to the encryption oracle.

The other game is $H''(\lambda)$ defined as before but

$\mathit{Enc}_k''(m)=(r_1,r_2)$ where $r_1,r_2$ taken randomly from $\{0,1\}^{n}$ and $\{0,1\}^l$

I know that the difference between them is the second part of the Encryption algorithm, but I don't understand why in $H'$ game there are collision problem.
The proof tells that calling $E(\mathit{bad})$ the problem of collisions in encryption queries, it sufficies to prove that $E[\mathrm{BAD}]$ have negligable probability and so

$$\Pr[E(\mathrm{BAD})]= \sum_{i,j} \Pr[r_i=r_j] \leq (q^2) 2^{-n}$$

Why in the first scheme there are collision problems and why if there are collision problems the two schemes can be distinguishable?

If there is a collision in the $r$ in the first game, then the attacker can learn the XOR of two plaintext messages by XORing the second elements. In the second game, the XOR of the two second elements if there is a collision will just be random. Thus, the attacker can distinguish these two games if there is a collision.


Is there a form of AES encryption where the cipher text matches the length of the clear text and does not show patterns? I have clear text, usually less than 10 bytes, which contains a few infrequently changing bytes.

Reading: http://lollyrock.com/articles/nodejs-encryption/ I tried aes-256-ctr:

The cipher text is as short as the clear text, which is good.
The cipher text contains patterns, at the positions of the infrequently changing bytes, which is bad.

I tried aes-256-cbc:

The cipher text length is rounded up to the nearest 16 bytes, which is bad.
The cipher text appears random, which is good.

Is there a form of AES encryption where the cipher text matches the length of the clear text and does not show patterns?

What you want is length-preserving encryption, which is a special case of Format-preserving encryption.

A standard mode for achieving this FFX mode, which uses a blockcipher, like AES, in a Feistel network. This mode is relatively complex and slow.

But I strongly recommend using normal authenticated encryption over format preserving encryption whenever possible. Format-preserving encryption always leaks if two plaintexts are identical, whereas semantically secure encryption avoids this leak. It also lacks integrity protection, unlike authenticated encryption.


Segmenting encryption to get the same results with the same key The given examples below are dummy and in English. They are mainly for place holding as this is a concept question rather specific example based

Given AES has a block size of 128 bit (16 letters of English) and assume I am using the 128 bit key version without an IV.

Assume I have the plaintext hellohowareyoutodayihopeyouareok and the key 1234567890123456

If i take the first section of the plaintext hellohowareyouto and run the encryption on it with the above key and get the ciphertext 111erqsdgdisa222 and later we run the plaintext dayihopeyouareok with the same key we get the ciphertext 333isdisiodfi444.

My question is, given the cipher works on blocks of size 128 bit, if we take the entire plaintext hellohowareyoutodayihopeyouareok and encrypt it with the same key, would we get 111erqsdgdisa222333isdisiodfi444 ?

If no, why not? (Given the IV is constant, or no IV exists, given not all encryption algorithms require and IV. The story of having a fixed IV for all encryption being a bad idea is a different topic and not the aim of this question)

Yes this would work as stated by you.

Explanation:

If you're using a library supporting ECB (which you are actually using in this example) you can input the whole 32 bytes of plaintext and will receive the corresponding 32 bytes of ciphertext. Splitting the operation into two calls doesn't make any difference for libraries as internally they do nothing else than simply calling the encryption function for each block and concatenating the ciphertext to get the output.

Standard note:

Do not use the encryption mode proposed by you (ECB) in the "real world".  Rather use GCM or an other authenticated encryption mode as you also have to check if your data was altered and came from the correct source.


Amateur question: two-way RSA? Is this a sensible scheme for 2-way client/server communication? A client connects to a server. The server and client both generate RSA keys, and send over the public ones to each other. If the client wants to send a message, they encrypt it with the server's public key, send it over, and the server decrypts it. Vice versa with server -> client.

Does this make sense? Presumably breaking this is equivalent to breaking RSA, right? Is something like this ever used in practice? If not, what do alternatives do better?

The scheme you described is not a sensible scheme for 2-way client/server communication.

The new RSA public keys are not authenticated, thus you are not safe against active attackers, who could intercept the connection (or replace one of the partners). Those could read all the content, and/or replace it with their own.
If you would be using authenticated public keys (e.g. by certificates), the privacy would be given (i.e. an attacker couldn't read messages). But your messages have no authentication, and an active attacker could replace messages with their own ones, insert his ones, or drop messages.
You are using "ephemeral RSA key pairs" for each connection – this incurs a slight performance overhead, as generating new RSA key pairs is slightly expensive.
Using RSA for bulk encryption (and even more decryption) is really expensive, compared to a same-security block or stream cipher. Don't do this.

This is not essentially the same as what TLS is doing with RSA (assuming RSA key exchange):

In TLS the server's public key is accompanied by certificates, which allows the client to verify that it is really speaking to the right server. (The client is normally not authenticated.)
In TLS the client generates some random data and sends it by RSA to the server, to this some more random data from both client and server is mixed and used to produce symmetric keys for encryption and authentication using a symmetric cipher and a (symmetric) MAC algorithm. These are used for the actual communication (after some check to verify that both have the same keys).


Do 2DES and 3DES2 have the same effective key length? I am following the notes "Introduction to Modern Cryptography" by Bellare and Rogaway, and on the chapter about blockciphers there is the following claim (page 11 of https://cseweb.ucsd.edu/~mihir/cse207/w-bc.pdf):

  2DES, although having the same effective key length as 3DES2 and offering what appears to be the same or at least adequate security, is not popular in practice.

However, from what I understood, the effective length of 2DES is 57 bits, since it can be attacked by the meet-in-the-middle attack (this is stated on the end of page 10). On the other hand, the text says that 3DES2 does not appear to be target of meet-in-the-middle attacks, so its (effective) key length is 112 bits.

So I was wondering if I am missing something about these statements or if there might have been a mistake in the text (I did not find any errata).

Definitely a mistake. The text clearly contradicts itself.

  ... 2DES has an effective key length of 57.

And later...

  There does not
  appear to be a meet-in-the-middle attack on 3DES2 however, so that its key length of 112 is also
  its effective key length.

which clearly contradicts

  2DES, although having the same effective key length as 3DES2 and offering what appears
  to be the same or at least adequate security, is not popular in practice.

As a bit of an aside, 3DES2 is considered by NIST to have an effective key length of at least 80 bits, but definitely not the full 112 bits, due to its vulnerability to known-plaintext attacks with $2^{40}$ blocks.


Comparison Vigènere vs. Monoalphabetic cipher I have a question for a class of secure communication, but I have no idea about how to proceed in order to answer it. I'll be very grateful to whom replies to me.

Assuming that brute force attack with 80bit keys is infeasible, let's compare the security of the Vigenere cipher with the security of the monoalphabetic cipher in the ciphertext-only attack model considering the encryption of 10 character messages with randomly chosen secret keys for each encryption.

Which cipher among Vigenere and monoalphabetic provides better security when the security criterion is only based on the size of the key space ( brute force attack )?
Is there any other consideration for which the answer would be different than in a)?
Can any of these ciphers provide absolute security? if so give a precise definition of the configuration that would allow for it.

Hint: $2^{80}=1.2 \cdot 10^{24}$ ; $26^{10}=1.4 \cdot 10^{14}$ ; $26! = 4 \cdot 10^{26}$

a) The question seems to be about a comparison of the size of the key spaces. The hint already shows the key spaces for Vigenère with a 10-letter key ($26^{10}$) and for simple substitution ($26!$). Simple substitution has the much bigger key space.

b) Using frequency analysis simple substitution is much easier to solve. Basic frequency analysis does not help for Vigenère (at least not without additional methods). With that in mind Vigenère could be considered more secure than simple substitution. In fact: both are not really secure, don't rely on them.

c) Vigenère with a key that is exactly as long as the plain text could be considered absolutely secure. But then again, it would be highly unpractical. :-)


How can bit slicing be constant time, when Mix Columns is in the cipher I'm reading about bit-slicing techniques, and one thing about it caught my mind.

The strength with bit sliced implementations are (apart from that they are fast) that they are running in constant time. This outrules side-channel attacks based on timings.

Now, my question is:
How can ciphers such as AES run in constant time, when bitsliced? The MixColumns operations works in $GF(2^8)$, so whenever an eight bit from the matrix multiplication is $1$ before the multiplication, the result has to be reduced modulo the polynomial of the Galois Field to not overflow. To me that seems like, the running time of the cipher depends on the input then? (I can understand why SubBytes, ShiftRows and constant additions are constant time).

Is the solution for bit slicing to reduce (XOR) with the polynomial after every operation, or is there a smarter trick? It seems like a slowdown, since bit slicing is often done for speed.
(I'm not an expert on Galois Fields either, so I'm not sure if it's okay to XOR with the polynomial after each operation, as that would be like adding a value to the result everytime)

Thanks for enlightening in advance! There is not THAT much documentation on bit slicing. It seems like everyone knows that its fast and knows it exists, but very few implementations has actually tried using it.

EDIT: It does not seem like, it would be okay to reduce with the irreducable polynomial after every multiplication. If I XOR the polynomial to a result, which 9th bit is $0$ (i.e. result does not overflow), then it will overflow since the irreducable polynomial in AES is $100011011$ (in bitform).

You can (and should) do the reduction in constant time using masking.  That is, instead of using the following (non-bitsliced) pseudo-C code to do the reduction:

if ((result >> 8) & 1) {
    /* bit 8 is set: clear it and flip bits 0, 1, 3 and 4 */
    result ^= 0x11b;
}

you can simply do:

result ^= 0x11b * ((result >> 8) & 1);

(where your compiler may optimize the multiplication by a constant into a series of bit operations, if it's more efficient on your CPU architecture).

This can then be trivially bitsliced, e.g. like this:

/* bit0 .. bit7 store the 8 bits of the result(s), bit8 is the overflow bit */
bit0 ^= bit8;
bit1 ^= bit8;
bit3 ^= bit8;
bit4 ^= bit8;


What are possible caveats when generating a group for use as parameters for Diffie-Hellman key exchange? As reusing a widely used group for Diffie-Hellman key exchanges might lead to far easier third-party key discovery through precomputation for that specific group, I would like to know what can possibly go wrong when generating custom groups for use as Diffie-Hellman parameters.

Here is what I currently believe to be true about the requirements. Please correct me or explain further if this is wrong or not detailed enough:

A field is needed for the Diffie-Hellman key exchange to work.
Rings without zero divisors are also integral domains. Integral domains that are finite are also fields. For some reason, a group with a prime modulus is also a finite ring without zero divisors and therefore a finite integral domain and therefore also a field.
To be hard to attack, the modulus needs to be large enough and one needs to be sure that the modulus is actually prime and not just pseudo prime.

One requirement that you don't have listed is that the generator $g$ needs to generate a subgroup that's of a large prime order; here's what can go wrong if that is not true:

If the order of $g$ (which we call $q$) has a factor $r$, then the attacker can, hearing $g^x$, determine $x \bmod r$ in $O(\sqrt{r})$ time.  If $r$ isn't large, this immediately implies that you're leaking data
Worse yet, if the order $r$ is smooth (has no large factors), that makes the DLOG problem easy.

One strategy is, as mandragoe suggests, is look for a prime $p$ with $(p-1)/2$ prime as well.  There is certainly a lot to like about this strategy; you can use (say) $g=2$, which can make the computation easier (and if the order of $g$ happens to be $2q$, all that means is that the attacker can learn the lsbit of your DH private values, which really doesn't tell him much, and you can avoid even that by making sure that $p \equiv 7 \pmod{8}$.

On the other hand, it is also a comparatively costly option, as looking for a value $p$ that meets both conditions means going through a lot of candidates.  Now, if you're doing this computation only rarely (say, once a day), that's really not that big of a deal; however if you're coining a fresh group for every exchange, it is certainly more expensive that you need.

An alternative approach is:

Search for a 256 bit prime $q$
Once you have that, scan through 2048 bit values $kq+1$ for a prime; when you find it, call it $p$
For $g$, select an arbitrary value $x$ (2 works), and compute $x^k \bmod p$; if that value is not 1, use it for $g$.

The order of the generator $g$ will be $q$, which is a sufficiently large prime that we don't need to worry about attacks that take $O(\sqrt{q})$ time.

The expensive operation is the search for $p$, which is no more expensive than any other prime search for that size.


Do all stream ciphers (and AES-128-CTR in particular) produce equal output size as the input size? I'm particulary interested on knowing if the output of the AES-128-CTR ciphertext is always going to have the same size as the input plaintext, or it could be padded somehow. It seems so from my tests using openssl.

My input (plaintext) is a bytestream (not a bitstream). Is there any difference bytestream / bitstream regarding output ciphertext size?

Does this output size == input size applies to all stream ciphers?

First I will start with AES-CTR. This is a mode which turns a block cipher into a stream cipher. Since AES has a 128-bit block size, the output of the primitive is in blocks of 16 bytes. If you have a 3 byte message, 3 bytes is kept from that block to encrypt the plaintext via XOR. A broken implementation may not truncate. CTR requires a Nonce, which is generally included with the ciphertext and is usually 96-bits (12 bytes) in length, making that final message length 15 bytes. Salsa and ChaCha also require a Nonce.

Other variants of CTR mode include the authenticated GCM, which would then add an authentication tag to the ciphertext, at an implementation defined length.

Nonces and authentication tags are generally a multiple of 8 bits, so if you are encrypting a byte string, you should end up with one. Other data required to decrypt the message may be concatenated to the ciphertext, such as KDF iteration counts and salts, cipher or KDF identifiers, and message sequence identifiers. If an authenticated mode is used, and these are processed as additionally authenticated data, they are required to decrypt as per specification, even though without them you may still be able to recover the plaintext. Additionally authenticated data may included something that is not part of the ciphertext, such as the email or IP address of the sender.

Some stream ciphers do not explicitly require a Nonce, but they may be processed as part of the key, and still need to be included with the ciphertext.

Various implementations may obfuscate or operate on the plaintext prior to encryption. Plaintext compression can substantially change the ciphertext size, or may have no effect at all, depending on the content. Obfuscation may pad the entire message to 140 bytes, so it can then be plaintext encoded to fill an entire SMS message, hiding the true message size.


Privacy and warrants to obtain information How could a site issue a `warrant'*, a document which:
1) Others can verify was issued from that site
2) Contains a date stamp, a named site and instructions which can be presented to a third site by the named site as authority to carry out an action.

Of course, the problem is to make this secure, and I was hoping that someone could tell me where to look to find out how to do this. I suspect that this is very well known, so just a reference would do.

To explain more, I need to say why the name `warrant' was used. The idea is that a court can issue a warrant, and that a police officer can then take the warrant and police ID to a third party to obtain whatever (information..). The motivation is to increase privacy by requiring explicit and traceable authorisation for information collection, so the need for secure communication and identification is paramount. E.g., consider a monitoring system attached to a camera. The camera could be programmed to require authorisation from a higher entity in order to release data to the monitoring system, so the system has to give the camera a warrant. The procedure should be resistant to someone hacking into the monitoring system without the required authorisation...

Thanks and apologies for the low standards from a beginner here!

Your warrant just needs a simple digital signature, which provides the properties of authenticity and non-repudiation. That is very basic. Of course you need a proper public key infrastructure (PKI) along that, to ensure that everyone actually knows which verification keys are real, etc.

Regarding your different authorization levels, you might want to look into Mandatory Access Control, which then needs to be fulfilled by the PKI. But instead of granting access, you use it to decide which certificates are signed within the hierarchy. I guess you are looking for a compliance solution here, not a fancy technical solution, which might not have a mature implementation.

In general, this question is actually not about cryptography (at most about the application of cryptographic standards) and might be better suited for security-SE.


What is the collision resistance of a 2048-bit hash based on SHA-3? Let $M$ denote the message. Let $B_i$ denote eight different bitstrings (chosen arbitrarily or randomly) such that $$0 \le \text{length}(B_i) \le 12345678.$$ Consider the following function (it outputs a 2048-bit hash of the input): $$H(M) = {H_1} \mathbin\Vert {H_2} \mathbin\Vert {H_3} \mathbin\Vert {H_4},$$ where $\mathbin\Vert$ denotes concatenation and $$\begin{array}{l}
{h_1} &= \text{SHA-3-512}({B_1} \mathbin\Vert M),\\
{h_2} &= \text{SHA-3-512}({B_2} \mathbin\Vert M),\\
{H_1} &= \text{SHA-3-512}({h_1} \mathbin\Vert {h_2}),\\
{h_3} &= \text{SHA-3-512}({B_3} \mathbin\Vert M),\\
{h_4} &= \text{SHA-3-512}({B_4} \mathbin\Vert M),\\
{H_2} &= \text{SHA-3-512}({h_3} \mathbin\Vert {h_4}),\\
{h_5} &= \text{SHA-3-512}({B_5} \mathbin\Vert M),\\
{h_6} &= \text{SHA-3-512}({B_6} \mathbin\Vert M),\\
{H_3} &= \text{SHA-3-512}({h_5} \mathbin\Vert {h_6}),\\
{h_7} &= \text{SHA-3-512}({B_7} \mathbin\Vert M),\\
{h_8} &= \text{SHA-3-512}({B_8} \mathbin\Vert M),\\
{H_4} &= \text{SHA-3-512}({h_7} \mathbin\Vert {h_8}).
\end{array}$$

Since all values of $h_i$ are the outputs of a simple MAC (which is known to be secure enough for SHA-3) and all values of $H_i$ are taken by extracting one cryptographically secure 512-bit hash of two independent 512-bit bitstrings, I would expect that the collision resistance of $H(M)$ is close to 1024 bits of security. Is this assumption correct?

No.

It turns out that for a tree composition and concatenation of $n$-bit hash functions, collisions can be found at $O(2^{n/2}\operatorname{poly}(n))$ cost.  So it still has pretty much 256-bit collision resistance.  The additional complexity buys you essentially nothing.

Note that 256-bit collision resistance is already obscenely high, against all plausible attackers (and there's no advantage even if you have a quantum computer); anything beyond it is completely meaningless.

Side note: If the adversary knows the $B_i$, the antiforgery property of a MAC, derived from the prefix-PRF $m \mapsto \operatorname{SHA3-512}(k \mathbin\Vert m)$, is not relevant.  If the adversary doesn't know the $B_i$, then this is not the scenario of collision resistance—but you're not going to get better than ‘512-bit security’ anyway, which is already (completely meaningless)^2.

Rather than worry about how to obtain (completely meaningless)^4 security levels from the cryptography, you should focus on writing a clear statement of your application's security model, making sure it's easy to audit and understand in the context of what you're trying to achieve, and making sure you've covered all possibly relevant threat models.


What happens if CBC-mode uses the same IV for all processes? In CBC mode (Cipher Block-chaining mode), each block of plaintext is XOR with the previous ciphertext block before being encrypted. What happens if I use the same IV instead of the previous ciphertext block? Is it vulnerable to Chosen plaintext attack?

If the modification is done, the encryption looks like this:

$$C_i=E_K(\text{IV}\oplus P_i)$$

and assuming the "IV" is public, this is essentially ECB mode with a security-irrelevant pre-processing by XOR'ing a constant into the message.

Assuming the "IV" is non-public, this is essentially an XOR cipher encrypted with ECB mode and in particular this is still vulnerable to the standard ECB attack that you can detect repeated blocks, which means that the mode / construction can be broken under a standard (formal) ciphertext-only attack where the attacker-chosen messages are 2 blocks.