Is it ok to transmit an IV as a custom HTTP header? Considering an AES OFB encryption algorithm, suppose that I'm sending a message over HTTP (not HTTPS) and my message body contains the cyphertext. I'd like to know if transmitting a random initialization vector as a custom HTTP header is considered a bad practice, having into account that it's conventionally appended to the beginning of the cyphertext.

From a cryptographic standpoint, it doesn't matter how you transmit the IV. You can send it as a header, in the message body, as the path in the request method, or even the URG pointers in a few TCP packets. From the perspective of the encryption process itself, it doesn't care how it got the IV, no matter how silly the transmission method used, as long as it got it in the end.

From a web development standpoint, it's bad practice to include data that is applicable to the payload in the headers. Sending an IV in a custom HTTP header slightly increases overhead when compared to simply prepending it to the ciphertext and sending it all. You don't even need an elaborate serialization format. Just prepend the fixed-size IV and call it a day. This has the additional benefit of not breaking the HEAD method, which requests the HTTP headers but not body. I can't think of any reason why you could possibly want the IV sans ciphertext.


Is there a way to create an encrypted email with no third party application I would like to send and receive emails between group of people. Is there a way to create it with no need to use some other 3rd party application. Is there a way just to transfer files between 2 people so there won't be any way to decrypt it by any other technology?

It depends on what email host you use. Hosts like Gmail have built in SSL encryption. There are other standards like the S/MIME encryption feature built into Microsoft Outlook. Check out this post https://superuser.com/questions/25658/gmail-and-ssl-encryption-how-much-is-encrypted


AES GCM vs other encryption modes in embedded environment for network traffic I'm doing a lot of research since I'm doing an internship for a company where I need to upgrade their security level. Their own protocol needs a cryptographic upgrade and I'm leaning towards AES since it is well known (also good from a sales standpoint).

Now the idea is there are different modules which can talk to one an other with a specific self-design protocol. This entire protocol gets encrypted (It works on top of TCP).

Currently there is no good authentication, every modules has a secret key (the same, though one of the future wishes is to use a key diversification method) and the current way of authentication (knowing it comes from one of our modules) is because if it can encrypt/decrypt it has the key so it is one of our modules. which is cute but nowadays this could be done better.

So now for what I've figured out so far:
- GCM provides authentication (the company said their way of authenticating is good enough, i disagree).
- AES is fast and can be implemented in very little code. (I don't know about GCM but CBC works like a charm)
- With GCM making sure you have a secure IV is of the utmost importance. (It has scared me a bit when i read how much can go wrong with GCM)

My questions:
IS AES really the best way to encrypt a lot of network traffic or would a stream cipher like salsa20 (or any other stream cipher, i only know a bit about salsa) be better?

How can one make sure if you use GCM (or CBC) the IV stays secure, would simply generating a random number and then adding 1 to it be secure enough? I have the feeling it won't be, haha.

Like i said every module has a secret key (the same secret key), should this secret key be used every time as the AES key or should every x messages a new key be derived from this secret key?

Just to clarify, Things like full TLS would be to big to run on the hardware it would take up to much space and processor power but it is a light weight version of TLS we are working towards since the modules must eventually negotiate a crypto standard to use. <-- making your own encryption? not really though making our own combination might be as bad? I don't know.

As you can tell I'm quite new to all of this, i know the math behind AES and RSA but implementing it PROPERLY isn't remotely the same so I'm really careful with the things I do which is why i ask these elaborate questions.

EDIT: Should i have placed this on security.stackexchange?

EDIT2: the embeded specifications for our test device (other production devices will most probably have a better chip)
it's a 32-bit CPU with 100Mhz, 2MB Flash ROM (program storage), 32KB Flash ROM (for data storage) and 256KB RAM
see: Development board or RX63N group specifications

If you are constrained by the embedded environment, you should consider CCM instead of GCM as AES mode.

One of the major constrain when implementing GCM is that the authentication part (the GHASH) is totally unrelated to AES and should be implemented in its own way.
And, to make it reasonably fast, you have to use  key-depended look up tables which will consume RAM.

CCM on the other side uses a variant of AES-CBC-MAC as authentication function and AES-CTR as encryption function, so there is a lot of code reuse and runs at half the speed of a normal AES-CTR (since it needs to process the same block with encryption AND authentication).

That is to say that you could end up in overall better performance (considering both code, ram and speed) with AES-CCM than with AES-GCM, although the latest could be faster if you make use of table in RAM (which is not a problem for PCs implementations but could be a problem in embedded environment).

Some details on the embedded environment could have helped in understading better the trade-offs.


Implementations of GCM with 64-bit cipher The paper The Galois/Counter Mode of Operation (GCM) describes mainly the 128-bit case, for use with 128-bit block ciphers such as AES. AES-GCM test vectors are available from NIST.

The paper also describes GCM for 64-bit block ciphers. My question is, has anyone actually implemented GCM for a 64-bit block cipher, and/or published test vectors?

This would not be recommended in most cases. Note that AES-GCM fails terribly if an IV repeats. In a 64-bit block cipher, if you want the probability of such a failure to be below $2^{-32}$, then you would be very limited in the number of messages you can encrypt. If you can guarantee a unique IV each time, and are not using a random IV in order to get uniqueness, then maybe it can be OK.


How to compute a smooth-degree isogeny given a generator point of its kernel? I need to compute an isogeny from $E: y^2 = x^3 + ax + b$, given a generator point for its kernel subgroup, using Python.
The point has smooth order.

I need both the parameters for the curve and polynomials for point mappings.

I have already read about Vélu's formulas, but it seems it will take a lot of time to compute each point in the subgroup, and more time to evaluate the curve parameters.

I know PARI and MAGMA provide an algorithm for that, but I need to understand the algorithm to write it on my own.

I am trying to use this for computing SIDH.

The complexity of Vélu's formulas scales linearly with the size of the kernel subgroup, so directly applying them to a point of huge order is not feasible for isogenies of "cryptographic" degree.

Instead, SIDH implementations decompose an isogeny of degree $\ell^n$ into $n$ isogenies of degree $\ell$. An easy way to do this is the following:
Suppose given a point $P\in E$ of order $\ell^n$, where $\ell$ is "small"; we wish to compute $E/\langle P\rangle$.
We decompose the isogeny $\varphi\colon E\to E/\langle P\rangle$ as:
$$
    E = E_0
    \xrightarrow{\psi_1} E_1
    \xrightarrow{\psi_2} E_2
    \xrightarrow{\psi_3} \dots
    \xrightarrow{\psi_{n-1}} E_{n-1}
    \xrightarrow{\psi_n} E_n = E/\langle P\rangle
    \text,
$$
where each $\psi_i$ has degree $\ell$.
A straightforward calculation shows that the kernels of the isogenies $\psi_i$ can be obtained by pushing $P$ through the previous isogenies $\psi_1\dots\psi_{i-1}$ and multiplying by an appropriate cofactor:
$$
    \operatorname{ker}\psi_i = \langle[\ell^{n-i}](\psi_{i-1}\circ\dots\circ\psi_1)(P)\rangle
    \text.
$$
Since $\lvert\operatorname{ker}\psi_i\rvert=\ell$ is small, computing each $\psi_i$ is efficient.
(Of course, this representation can also be used to efficiently evaluate $\varphi$ at a given point by simply passing the point through the chain of $\psi_i$s.)

Notice that it is this decomposition that gives the legitimate users of the system an advantage over attackers: It allows Alice and Bob to compute an isogeny in time logarithmic of the computational effort that an attacker needs to perform. In that sense, it is serves the same purpose as square-and-multiply (and its variants) for group-based Diffie-Hellman instantiations.

Finally, note that this straightforward strategy for computing $E/\langle P\rangle$ is not necessarily the most efficient possible: Depending on the relative costs of isogeny computations and point multiplications, there may be better strategies; see the original SIDH paper (Section 4.2.2) for details.


What is the maximum key size for a 128 bit AES? What is the maximum key size for AES 128,
Will using a key greater than maximum gives extra security or error? Is there a minimum key size?

Suppose a key is 128 bit, does it means The key is of length 16characters

Suggest me a good password to key function.

Despite similarities, it is really important to understand that passwords and cryptographic keys should not be carelessly conflated.  Some important contrasts:

Passwords are normally selected by human beings according to their whims.  Cryptographic keys are meant to be randomly generated by an algorithm.
Passwords are usually intended to be memorized by human beings.  A strong cryptographic key cannot generally be memorized—they're too random and complex—and thus generally stored in a secure device.  In the parlance of multi-factor authentication, passwords are "something you know" while cryptographic keys are "something you have."
Passwords have to be text that human beings can manually input into their devices.  Cryptographic keys are fundamentally binary data (despite being sometimes serialized and deserialized as text) and are generally not meant to input manually.

I say all this because your question really comes down to a lack of understanding of these differences.  AES doesn't use passwords, it uses keys.  AES-128 keys are fixed-length binary data; they don't really have "characters" because they're not text.  As others have said, the maximum key size for AES-128 is the same as the minimum and only key size: 128 bits.

Many programs that use AES-128, however, do present a password-based user interface, and maybe you've encountered one of these.  But what these programs are doing, behind the scenes, is internally transforming the user's password into a proper cryptographic key.  In those programs your password can generally be any sensible length you like, but generally then the password is the weakest link—an attacker who can guess your password doesn't need to crack the AES encryption.  So to achieve the full security strength of AES-128 in such a program you would need to choose an extremely strong password—something most users won't know how to do.  In this case I recommend looking into Diceware and their FAQ, which has some useful advice on how complex of a password to choose.


How does randomized hashing defeat collision attack? SEC#1 recommends randomized hashing when using SHA-1 with ECDSA; SPHINCS+ uses randomized hashing in WOTS+ to defeat collision attack so as to reduce signature size.
How does a randomized hashing defeat collision attack? What are the limitations?

In randomized hashing for Merkle-Damgard based hash function (like MD5, SHA1, SHA2) the input preprocessed with a salt before hashing applied. This process doesn't modify the underlying hash function uses it as a black box, It is proposed by Shai Halevi and Hugo Krawczyk in 2007;

Strengthening Digital Signatures via Randomized Hashing

For MD based hash functions. They defined the Target Collision Resistant (TCR) as;

a family of hash functions $\{H_r\}_r\in R$ (for some set $R$) is target collision-resistant if no efficient attacker $A$ can win the following game, except with insignificant probability:

A chooses a first message $M$, then receives a random value $r \in_R R$, and it needs to find a second message $M' \neq M$ such that $H_r(M_0) = H_r(M)$. The value $r$ is called a hashing key, or a salt.

and they also defined the Enhanced Target Collision Resistant (eTCR) since signature schemes like DSA don't support to sign the salt $r$. To support this they use relaxing the conditions to strengthen the mode of operation. This scheme is

sufficiently strong to ensure the security of the resultant signatures even if we only apply the underlying signature to $H_r(M )$ and do not sign the salt $r$.

The game is played as;

A chooses a first message $M$, then receives a random value $r \in_R R$, the salt r, the attacker can supply a second message $M'$ and a second salt $r'$, and it is considered successful if $(r, M ) \neq (r', M' )$ but $H_r (M ) = H_{r'} (M')$.

and it needs to find a second message $M' \neq M$ such that $H_r(M_0) = H_r(M)$. The value $r$ is called a hashing key, or a salt.
They define two methods as;

$$H_r^c(m_1, \ldots , m_L) \overset{def}{=} H^c(m_1 \oplus r,\ldots, m_L\oplus r).$$ This scheme is TCR under second-preimage resisantce (SPR)
*. This suit RSA signature since we can extend the modulus so that the $r$ can be signed, too.

And the below scheme is eCTR under SPR, too *, This is useful for DSA like algorithms in which signing additional data, $r$, is not easy.
$$\tilde{H_r^c}(M)\overset{def}{=} H_r^c(0|M)  = H^c(r, m_1 \oplus r,\ldots, m_L\oplus r).$$

They designed their scheme so that the security of the resultant signature scheme does not depend on the resistance of the hash function to off-line collision attacks. In short, they related the security of their scheme to the second-preimage resistance of the compression functions.

* Actually, the proofs rely on two properties that related to SPR. e-SPR is the real hardness of collision resistance of $H_r$ and $\tilde{H_r}$. And, c-SPR, which is related to the hierarchy of collision resistance.
Note 1: There is a web page that shows how this and similar method can be easily applied to NSS Library and Firefox.
Note 2: The extended version of the paper is here ( and it is not https!)


How can a non-crypto-expert implement crypto libraries in a programming language? I'm a regular developer and thus not a crypto expert. I'd like to use ECDSA as a library in a programming language, Idris, which still doesn't have one. I could, obviously, try and port a particular implementation of my choice, run some tests, and call it a day. But that sounds unprincipled for something that needs strong security.

Is there any standard procedure or best practices to guide a normal developer to implement such a thing properly, without falling on the "don't roll your own crypto" trap?

The best option is to avoid doing so as much as possible. Ideally, your language of choice will offer a wrapper around a battle tested library such as libsodium (or maybe bearssl one day).

Additionally, in a perfect world, the interface that the library/wrapper provides should be designed to make it difficult if not impossible for you as the developer to shoot yourself in the foot. For example, if generation of the nonce for some kind of CTR-like mode is left up to you and not handled by the libraries you're using, you probably want to use a different library.


What is the difference between any secret sharing scheme and arithmetic secret sharing scheme It looks like that only difference between two of them the variables. But it does not make sense for me and I could not find exact definition of arithmetic secret sharing scheme. I mean what exactly this is? (Most of you understand that I am really new in these stuff.) Thank you.

As far as I can tell, it seems that the term "arithmetic secret sharing" was coined by Cascudo, Cramer and Xing in their 2011 paper "The Torsion-Limit for Algebraic Function Fields and Its Application to Arithmetic Secret Sharing".  Certainly, all the mentions of the term in the crypto literature that I could find with a few minutes of searching seem to cite this paper, and the term does not seem to appear in the literature (or, really, anywhere on the web) before 2011.  So if you want an exact and authoritative definition of what it means, that paper seems like the obvious place to look.

Indeed, the introduction to the paper by Cascudo et al. cited above provides the following, unfortunately rather technical, definition:

  An $(n, t, d, n - t)$-arithmetic secret sharing scheme (with uniformity) for $\mathbb F_q^k$ over $\mathbb F_q$ is an $\mathbb F_q$-linear secret sharing scheme where $k, n, t ≥ 1$, $d ≥ 2$, the secret is
  selected from $\mathbb F_q^k$ and each of the $n$ shares is an element of $\mathbb F_q$. Moreover, there is $t$-privacy (in addition, any $t$ shares are uniformly random in $\mathbb F_q^t$) and, if one considers the $d$-fold “component-wise” product of any $d$ sharings, then the $d$-fold
  component-wise product of the $d$ respective secrets is $(n - t)$-wise uniquely determined by it.

Almost the exact same definition, with the omission of only some conditions on the parameters $k$, $n$, $t$ and $d$, is also given directly in the abstract.  In section 5 of the paper, the authors also give the following alternative (and unfortunately even more technical) definition:

  DEFINITION 10 (ARITHMETIC SECRET SHARING SCHEME).
  An $(n, t, d, r)$-arithmetic secret sharing scheme for $\mathbb F_q^k$ (over $\mathbb F_q$) is an $n$-code $C$
  for $\mathbb F_q^k$ such that $t ≥ 1$, $d ≥ 2$, $C$ is $t$-disconnected, $C^{∗d}$ is in fact an $n$-code for $\mathbb F_q^k$, and $C^{∗d}$ is $r$-reconstructing. $C$ has uniformity if, in addition, it is $t$-uniform.

So, what exactly is an arithmetic secret sharing scheme, and what are they good for?

After quickly skimming the paper, I'm not yet 100% sure myself.  Certainly, they seem to be information-theoretically secure threshold secret sharing schemes constructed using finite field arithmetic, much like Shamir's secret sharing scheme.  Based on just my cursory reading of the paper, I'm not 100% sure whether Shamir's scheme itself falls within the scope of "arithmetic secret sharing", or whether it's merely possible to somehow construct arithmetic secret sharing schemes based on Shamir's scheme.  In any case, "arithmetic secret sharing", in the general sense, seems to be a fairly broad umbrella term that encompasses a number of schemes independently introduced in earlier papers by other authors, as cited by Cascudo et al.

As for what they're good for, apparently, one major application is secure multi-party computation, and specifically secure multiplication.  According to the paper's introduction, they can also be used for constructing error-tolerant secret sharing schemes, as well as for verifiable secret sharing.


Why is the Fiat-Shamir heuristic deemed secure in the ROM? In their paper On the (In)security of the Fiat-Shamir Paradigm, Goldwasser and Tauman show that the Fiat-Shamir heuristic does not work with any hash function. From the paper:

  The most important question however remained open: are the digital signatures produced by the Fiat-Shamir methodology secure? In this paper, we answer this question negatively.

However, they do state that it is secure in the random oracle model:

  [Pointcheval and Stern] proved that for every 3-round public-coin identification protocol, which is zero-knowledge with respect to an honest verifier, the signature scheme, obtained by applying the Fiat-Shamir transformation, is secure in the Random Oracle Model.

I'm confused because it seems to me that they then (in my opinion) go on to show that the Fiat-Shamir heuristic is never secure, not even in the random oracle model.

From the paper:

  Intuitively, the idea is to take any secure 3-
  round public-coin identification scheme (which is not necessarily zero-knowledge) and extend
  its verdict function so that the verifier also accepts views which convince him that the prover
  knows the verifier’s next message. Since the verifier chooses the next message at random,
  there is no way that the prover can guess the verifier’s next message during a real interaction,
  except with negligible probability, and therefore the scheme remains secure. However, when
  the identification scheme is converted into a signature scheme, by applying the Fiat-Shamir paradigm, the “verifier’s next message” is computed by a public function which is chosen at
  random from some function ensemble and is known in advance to everyone. A forger, who
  will now know in advance the “verifier’s next message” on any input, will be able to generate
  an accepting view for the verifier. This makes the signature scheme insecure regardless of
  which function ensemble is used to compute the “verifier’s next message” in the identification
  scheme.

Doesn't this also work in the random oracle model? It seems to me that this is attacking the very concept of replacing new randomness by anything (except pseudorandomness), be it hash obtained by evaluating a hash function, or actual randomness chosen by the random oracle (but available in advance, so not new randomness).

Instead of evaluating the hash function on the arguments relevant for the randomness substitute, the prover can ask the random oracle for the hash. Sure, this will be true randomness, but the verifier will get the same randomness from the random oracle in the next step, so the prover still knows in advance what "random" value the verifier will choose.

The paper by Goldwasser and Tauman is another paper in the series of the failure of the random oracle model; its novelty is applying this principle to the Fiat-Shamir paradigm and interactive protocols. However, an easier place to start is the seminal paper of Canetti, Goldreich and Halevi, called The Random Oracle Methodology, Revisited. This paper shows that there exist signature and encryption schemes that are secure in the random oracle model, but fail for every concrete instantiation, for any hash function. They prove this by carefully constructing a scheme that will fail for any hash function instantiation. Their proof does not work in the random-oracle model (as with Goldwasser and Tauman) since the description of the hash function does not exist when it's a random oracle (it's certainly not polynomial size).

It's important to understand what this actually proves. The theorem proven shows that it is impossible to generically replace the random oracle with a hash function. That is, there does not exist any hash function that can be used to replace the random oracle in every construction, in order to get a proof in the standard model. Furthermore, there exist constructions that cannot be proven secure in the standard model at all, for any hash function. Thus, the random oracle model is not "sound" in the sense that it cannot always be a stepping stone to a standard-model proof.

What this does not say is that there are no random-oracle constructions that can be proven secure in the standard model. Since my previous double-negative sentence will surely be confusing, I'll explain. There may exist schemes that are proven secure in the random oracle and can be instantiated with a concrete hash function. These proofs do not state that this is impossible. Thus, it is theoretically possible that a hash function can be found to instantiate RSA-OAEP to be secure in the standard model, and it is theoretically possible that a hash function can be found to instantiate Fiat-Shamir on Schnorr's protocol specifically so that the result is a secure signature scheme in the standard model (I may be wrong, but I don't think that this has been proven to be impossible). To be honest, it is very unlikely that this is the case (at least in my opinion), but this hasn't been ruled out.


Using a Hash as a secure PRNG I was just looking at some NIST PRNG recommendations, specifically at Hash_DRBG. I read briefly through the algorithm, and even though it is not overly complex, it still seems unnecessary to me. I asked myself how I would implement a (cryptographically secure) PRNG on top of a Hash algorithm (SHA256 or SHA512), what came up is:

Idea one:

Obviously this can only provide half the "strength" of the hash

Initialization: state = hash(seed);
Iteration: output = first_half_of(state); state = hash(state);
Reseeding: state = hash(state || new_seed)

Idea Two:

Maybe with a separate counter

Initialization: state = hash(seed);
Iteration: output = hash(state); ++state;
Reseeding: state = hash(state || new_seed)

Now, these two "schemes" seem safe to me, I'm a complete crypto noob though. The point is that I don't think that I'm the first one to think of these very basic PRNGs, and I'd like to understand the reason for NIST not to choose something similar in their recommendations. Do these PRNGs have some (obvious?) weaknesses? (If not, is there something known about after how many iterations they should be reseeded?)

Both ideas are safe if the hash function behaves like a random oracle and has a large enough output (in particular for "idea 1": with a function which outputs n bits at a time, it is expected that the state will enter a cycle of length about 2n/2, after about 2n/2 steps, so if you want "128-bit security", you will need n = 256 or more).

However, we do not have random oracles, but concrete hash functions, which are not as good and have subtle "flaws" which can compromise simple PRNG designs without contradicting the core security properties of the hash function. See this answer for some details. Proposals like yours are not necessarily weak when used with existing hash functions like SHA-256, but it is hard to make sure of it.

The NIST constructions are a bit more complex because they try to be more robust, or at least more convincingly robust. For these reasons, HMAC_DRBG is preferred.

If you want a lot of pseudorandomness with a very high bandwidth, you should look at specialized stream ciphers like these ones (a stream cipher can be turned into a PRNG by making it encrypt a long sequence of zeros). Alternatively, use AES in CTR mode, which will be devilishly fast on recent x86 processors (the ones which have an hardware AES implementation).


Big-O Notation: Encryption Algorithms I am currently completing a dissertation concerning the encryption of data through a variety of cryptographic algorithms.

I have spent much time reading journals and papers but as yet have been unable to find any record of their performance complexity.

Would anyone have an idea of the Big-O complexity of the following algorithms?

RSA
DES
Triple DES (Which I would expect to be of the same order as DES)
AES
Blowfish

Thank you in advance; if you could provide a link to a reputable and citable source if would be very much appreciated.

Most of these algorithms (i.e. the block ciphers DES, Triple DES, AES, Blowfish) are normally only working on a fixed block size, and take approximately the same time independently of input, thus they are $O(1)$.

If you put them into a mode of operation to encrypt longer messages, you usually get an $O(m)$ complexity, where $m$ is the message size, as you have $O(m)$ blocks of data to encrypt.

(One could design modes of operations with different complexity, but they have to touch at least each input bit once to be reversible, thus $O(m)$ is a minimum. Also, with $O(m)$ block cipher calls you can do enough to make it secure, so there is no point of making it slower.)

Two more notes to specific ciphers:

Yes, Triple-DES usually needs thrice the computing power as DES, but this then becomes $O(1)$ or $O(m)$, too.
Blowfish is known for its quite slow key schedule (which takes as long as encrypting about 4 KB of data), but this is still $O(1)$.

Thus, $O$-notation is not really an interesting thing to look at in block ciphers.

It gets a bit more interesting when we look at algorithms with a varying input size. For the asymmetric algorithm RSA, we have the public (and private) key modulus $n$, and its size $k = [\log_2 n]$ in bits can be considered a security parameter. (The private exponent $d$ is of similar size, while the public exponent $e$ is usually some small number like $3$ or $65537 = 2^{16}+1$.) The message size is then limited by $O(k)$, too.

Encryption and decryption are both modular exponentiations of plaintext or ciphertext modulo $n$, with the respective exponents. With the square-and-multiply algorithm, encryption needs $O(1)$, decryption $O(k)$ multiplications and a similar number of modular reductions, each of $k$-bit or $2k$-bit numbers ... which means about $O(k^2)$ or $O(k^3)$ elementary operations (with a quite small factor, as you use the word size build into your processor).

Decryption can be sped up by storing the factors of $n$, but this still gives only a constant factor, I think (i.e. it reduces the $k$ in the formulas).

RSA also uses one of various padding schemes, but this should be in O(k) and thus not contribute to the complexity.


ChaCha20-Poly1305: Can my salt/pass for a KDF also be the nonce? I have a PSK. I don't want to use it directly. I want to pass a "salt"/password into a KDF and get a new key for authenticated encryption with ChaCha20-Poly1305 .

I need to give the other side the nonce used.

I don't have enough space to fit all of this in a packet.

My plan was to generate a random nonce. But then thought...

Is it bad to use my pass/salt (16 bytes) as the nonce (12 bytes) as well? I could save the space of sending the nonce by just lopping 4 bytes off the salt.

I know all about the dangers of reusing a nonce. But I'm not sure it applies here because my "old PSK" is thrown into the KDF with the salt/pass so does it matter if that also makes up the nonce?

If you have a PSK then you don't need a password. You can just derive new session keys from the PSK, e.g. using a salt within HKDF. It is also possible to derive a key and IV if you're already using a salt. You could also use a counter starting at zero as nonce / IV instead because the resulting key is considered "fresh".

Generally, you simply need a unique key nonce combination for any encryption operation for stream ciphers. If you always apply a random salt to derive both than that requirement is fulfilled, because the key is always fresh. Reusing the salt is however immediately fatal to the security, so the salt should consist of say, 12 bytes / 96 bits or more generated by a secure random number generator.

Using a random salt together with a PBKDF is also possible, but as indicated, I'm not sure if you need a password and therefore a password stretching function such as a password hash / PBKDF.


Decrypt 3DES with a key and a nonce? I have been tasked with moving an authentication service from our provider to somewhere else. The code base for the current service is not available to me, but I know these things:

I have a 65 character plaintext key
Something labeled a "nonce" with 3 characters and in plain text
An encrypted string which (possibly coincidentally) begins with the nonce and is 35 characters long.

I have tried many of the googled suggestions without luck. Mostly nobody even mentions using a nonce.

Can anyone give me some idea of what I might want to do to decrypt the string? Nodejs or python would be my tools of choice?

Challenge-based symmetric-key authentication works a bit like this:

Server picks a randomly chosen challenge and sends it to the client.
Client "transforms" the challange with his key and send the result back to the server.
Server does the same transformation with the same key, and verify if the two matches.

The transformation can be an encryption algorithm, but usually well-designed system would use a MAC (message authentication code) such as HMAC.

In your case, the nonce is most likely a challenge, although 3 character only provides 24-bit (<21 bits if ASCII-only) insecurity.


AES/ECB vs AES/CBC for <16 bytes AES/ECB is commonly considered "weak" to the point that some static analysis software identifies it as not secure and suggests using AES/CBC instead.
The question is: what if size of encrypted input is always less or equal 16 bytes?
I suspect AES/ECB will be as good as AES/CBC in this case...
The other question is: will AES/GCM be any better (secure) for <16 bytes input compared to AES/ECB &| AES/CBC?
Thank You

I could've sworn this was a duplicate question, but I can't find a good match for it here right now, so let me answer it instead.

What if size of encrypted input is always less or equal 16 bytes?
I suspect AES/ECB will be as good as AES/CBC in this case...

For plaintexts shorter than the cipher block size (i.e. 16 bytes for AES), CBC mode encryption is equivalent to:

padding the plaintext up to 16 bytes,
XORing the padded plaintext with a random 16-byte IV,
encrypting the resulting 16-byte block with raw AES (i.e. in "ECB mode"), and
concatenating the random IV and the AES output to form the encrypted message.

XORing the plaintext with a random IV does, in fact, provide a concrete security benefit: it ensures that even two identical plaintexts will (with overwhelming probability) encrypt to different ciphertexts, preventing an attacker from learning whether two encrypted messages conceal the same plaintext or not.  With ECB mode, which is purely deterministic, an attacker could simply compare the two ciphertexts to find out if the plaintexts are equal or not.
However, in this particular short-plaintext scenario, that's the only benefit of the IV.  In particular, it's of no help against any attacks that would involve breaking AES (or compromising the encryption key), since if an attacker can invert the AES encryption (step 3), they can then trivially undo the IV XOR (step 2).
On the other hand, the use of a random IV actually makes CBC mode vulnerable to some tampering attacks that EBC mode happens to be invulnerable to.  In particular, for short messages like in this scenario, an attacker capable of intercepting and tampering with the encrypted message can flip any bit(s) in the plaintext just by flipping the corresponding bit(s) in the IV!
Now, technically this does not compromise the claimed security of CBC mode, since CBC mode doesn't claim to protect message integrity against tampering attacks in the first place.  But a lot of people aren't aware of that, and in any case message integrity protection is still important and should be ensured somehow, either by using an encryption mode that provides it directly (such as GCM) or by using a message authentication code on top of the encryption layer.

The other question is: will AES/GCM be any better (secure) for <16 bytes input compared to AES/ECB &| AES/CBC?

Yes, GCM is better than either ECB or CBC for messages of any length, since it provides both message authentication (tampering resistance) and full semantic security (leaks no information about the plaintext other than its length).
(In some cases, specifically for messages sufficiently shorter than one cipher block, using ECB mode and verifying the padding after decryption can actually provide a form of message authentication.  But this doesn't work for longer messages.  CBC mode doesn't provide any authentication for messages of any length.)
The same holds for any other secure authenticated encryption mode as well, not just GCM.  There's not that much difference between them (in terms of security; speed, code complexity and library support can of course vary), and they're all secure against nearly all passive and active attacks if used correctly.  In practice, the main ways in which the security of such an encryption mode can be compromised are:

key compromise (obviously, no encryption scheme is secure if the key is leaked),
user / implementation error (bugs in the code, not using the mode according to its specifications),
information leakage via message length (e.g. if the plaintext is compressed before encryption; see e.g. the CRIME and BREACH attacks on SSL), and
bad IV generation (the security of many encryption modes, including GCM, can fail catastrophically if the same IV is used for two different messages).

Thus, whenever possible, my recommendation would be to use an authenticated encryption mode that provides IV misuse resistance (such as AES-SIV or AES-GCM-SIV) and a reputable open-source implementation of it, such as Miscreant, that provides a simple "black box" API with the least possible room for user mistakes.  And if you're encrypting variable-length data, be very careful about possible leaks via its length, since no general-purpose encryption scheme can fully conceal that (and most don't even try).


Does adding OWF of the private key to encryption scheme hurts security? Suppose I have a symmetric semantic-secure encryption system $\Pi = (Enc, Dec)$ and an OWF $f$.

Now, define the following encryption scheme $\Pi^{'} = (Enc^{'}, Dec^{'})$ where , $Dec^{'} = Dec$ and $Enc^{'}(k, m) = Enc(k,m)\mathbin\|f(k)$

Is that encryption still secure? I already tried to formally prove this claim with a hybrid argument, i.e. claim that

$Enc(k, m0)\mathbin\| f(k) \approx Enc(k, m0)\mathbin\| f(r) \approx
Enc(k, m1)\mathbin\| f(r)  \approx Enc(k, m1)\mathbin\| f(k) $

However, this proof turned out to be wrong (for example, maybe $Enc$ and $f$ both reveal the first bit of $k$ in the clear).

It's possible to have a secure encryption scheme that ignores the first half of its key, and a secure OWF that leaks the entire second half of its input. Composing them as in your question results in something profoundly insecure.


Why does AES ciphertext entropy always close to 8? I have three binary files: 31744 byte length (1), 5712980 byte length (2) and 10806008 byte length (3).

The alphabet is all 256 symbols from 00 to ff. I compute the shannon entropy, replacing probability with frequency.

(1) H = 4.291334237835409

(2) H = 7.999155088532762

(3) H = 7.993862849926811

Then I encrypted all three files with AES. Alphabet is still the same. I computed the shannon entropy.

(1)' H = 7.255697988479884

(2)' H = 7.999970021706294

(3)' H = 7.999829860973214

Ok, I see the difference and the entropy of encrypted data is higher, it is expected.

But why entropy of encrypted data close to 8 and doesn't grow up? Entropy of plaintext bytecode is growing up with the size of data, but entropy of encrypted bytecode doesn't grow up with the size of data. Please, give me answer and some links if they exsist.

What you did in your entropy estimation is effectively modeled the process of selecting a random byte from the file, and computed the entropy that would be in that byte? You can do that (and, since you have the exact probability distribution, you could compute the Shannon entropy). However that would also answer your question - such a process would give you an 8 bit value; of course the entropy in that byte can't go beyond 8.

(The comment converted into an answer because, well, it appears to be the answer)


Classification of BFV and CKKS scheme? I would just like to ask what is the classification of both BFV and CKKS scheme are they Somewhat Homomorphic or Fully Homomorphic?

Brakerski/Fan-Vercauteren (BFV) [Brakerski12, FV12, BEHZ16, HPS18]
https://eprint.iacr.org/2012/144.pdf

Cheon-Kim-Kim-Song (CKKS) [CKKS17]
https://eprint.iacr.org/2016/421.pdf

Both schemes are presented as Leveled Homomorphic Encryption schemes, which means that for each $L$, there is at least a set of parameters ($\lambda$, $q$, etc) that allows us to homomorphically evaluate circuits of multiplicative depth up to $L$ (and the reciprocal also holds, i.e. for each set of parameters, there is a limit $L$ on the multiplicative depth of the circuits that can be evaluated).

In those basic forms, they are not really fully homomorphic, because once you set the parameters, you can't evaluate any circuit.

However, there are bootstrapping methods for both schemes, and once you implement the bootstrapping to refresh the ciphertexts after each operation, they become fully homomorphic.

For the FV scheme, the bootstrapping is presented in the own paper, in section 5.

For the HEANN scheme (which you called CKKS in your question), the bootstrapping method only appeared in that subsequent paper and it was improved in this paper that was published this year in Eurocrypt.


Which ECB ciphertext stealing scheme is this? I am stuck with identifying ciphertext stealing method with the following properties:

mode of operation is ECB;
recommended padding scheme for this application is PKCS#7, but apparently it is not used;
all blocks except the last one are encrypted / decrypted as usual;
the last block is not padded, but still encrypted / decrypted somehow.

For example, with Blowfish cipher and key 72E9DD9D29:

encrypted: A4 3F 83 8D CE D2 54 2E | 4F
decrypted: 82 DD 00 00 00 01 03 FF | 1E

I cannot figure out how that last (incomplete) block is encrypted / decrypted, so that if it is ignored and not processed, the penultimate block would be the same, — that does not look similar to ECB ciphertext stealing method described in Wikipedia, as block contents is not exchanged. This may seem obvious to an expert, but I already ran out of ideas.

This may sound crazy and absurd, but it seems that this scheme is simply broken:

on encryption, the last block is somehow padded (the exact method is not really relevant, but perhaps the trailing bytes of penultimate plaintext block are copied) and encrypted, then finally ciphertext is trimmed to match plaintext size;
on decryption, the same buffer is reused for each block, so the last ciphertext block is naturally padded with the trailing bytes of penultimate ciphertext block, then decrypted, and finally plaintext is trimmed to match ciphertext size.

Obviously, such an “encryption” irreversibly corrupts the last block, resulting in garbage being output on decryption. However, application software appears to ignore bad data silently, discarding the last record, absence of which is not evident to user, unless he specifically looks for it.

Well, I am not totally sure about this, as I only analyzed (OllyDbg to the rescue!) the decryption stage and header parsing, while object records are parsed on later stages of a quite-high-level processing, but it looks improbable to me that those high-level routines could perform a custom non-trivial restoration of the last block, — the more so that the last record appears to be missing, unless plaintext is guessed by hand (guessing is possible due to the highly predictable nature of plaintext, especially in the last block). However, if I am terribly mistaken, and such a scheme with properties specified in question is theoretically feasible, it would be interesting to know about it.


Picking a cipher suite for embedded system emails I have an embedded system product that emails out event notifications periodically.  I have implemented a non secured email version, but want to use SSL/TLS, if possible.  Can I only use 1 cipher suite for space considerations?  Or, do I have to support many types?  I'm trying to keep it simple, but not sure if there will be issues with just one or a couple.  Any input on how others would handle a simple one-way email feature using SSL/TLS?

You can support as many or as few as you like - take a look at RC 5247 for TLS 1.2.  If you are on an embedded system w/o any hardware crypto, you may want to skip the RSA algs that take a long time in favor of the ECDH.  In any case, look for an embedded crypto library that available for your toolchain and cpu vs writing it yourself.  It'll save time as well implementation flaws.

You might try initiating a TLS session with one of these email hosts and see what comes back for the algorithms they support - I suspect it's pretty extensive.  Then you could be sure that the ones you pick will work.

Wireshark is your friend for this.


RSA: Private key calculated from public key? The wiki article on RSA (https://en.wikipedia.org/wiki/RSA_(cryptosystem)) says that d is "the modular multiplicative inverse of e (mod φ(n))" , where d is the private key and e and n make up the public key. How come an interceptor cannot calculate the d in the exact same manor as the encrypter does, if the interceptor has knowledge of e and n?

When p and q are primes and  n = p$\cdot$q ,  one will have

{p,q}    =    $\bigg\{\hspace{-0.06 in}n\hspace{-0.04 in}+\hspace{-0.05 in}1\hspace{-0.05 in}-\hspace{-0.03 in}\phi(n)\pm \sqrt{\left(n\hspace{-0.04 in}+\hspace{-0.05 in}1\hspace{-0.05 in}-\hspace{-0.03 in}\phi(n)\right)^{\hspace{.04 in}2}-(4\hspace{-0.04 in}\cdot \hspace{-0.04 in}n)}\hspace{-0.05 in}\bigg\}$   ,

so for semiprimes, computing $\phi$ is equivalent to factoring.

The above reasoning doesn't work for multi-prime RSA, but even there, there's no obvious way for the adversary to compute $\phi$ of the modulus more easily than just factoring the modulus.


Why should a distribution being pseudorandom strictly be a sequence of distributions being pseudorandom According to Katz Lindell book,

Let Dist be a distribution on l-bit strings. Informally, Dist is pseudorandom if the experiment in which a string is sampled from Dist is indistinguishable from the experiment in which a uniform string of length l is sampled. (Strictly speaking, since we are in an asymptotic setting we need to speak of the pseudorandomness of a sequence of distributions Dist = {$Dist_{n}$}, where distribution $Dist_{n}$ is used for security parameter n. We ignore this point in our current discussion.) More precisely, it should be infeasible for any polynomial-time algorithm to determine (better than guessing) whether it is given a string sampled according to Dist, or whether it is given a uniform l-bit string.

What do they mean here by sequence of distributions?

A sequence of distributions is a definition of a distribution for each $n$. For example, consider the distribution $Dist_n$ to be a string of length $l(n)$ generated using some pseudorandom generator with a seed of length $n$. Then, for each $n$, the distribution is actually different. The reason why technically you need this is because the notion of negligible is asymptotic - it needs to be a function so that for every polynomial, the function is smaller than it for some large enough $n$.


How is HMAC hashed message decrypted on the receiver side We know that MAC algorithm and key are used in both sender and receiver side to get the matching MAC tages to prove that the data is authentic.

Now in HMAC we know that, it makes use of crytographic hash function which is irreversible, so when we use HMAC from the sender side to encypt a message using the HMAC formula, then at the sender side how will the receiver decrypt the message (hash function is irreversible), so how is the message at the receiver end, integrity is preserved and validated? Please explain.

Actually the HMAC value is not decrypted at all. The recipient takes all the needed input and she computes the HMAC on her own side and check if the result she got it is equal to the value on the message she got.

You can roughly see the HMAC algorithm as an symmetric key signature. You cannot decrypt an HMAC, you only check that the value is correct.


Does GCM need to incorporate the length of the associate data and the length of the ciphertext to be secure? What is the reason for incorporating the lengths of the associated data and ciphertext into the calculation of the authentication tag in GCM? Is it for security?

Well, if the lengths were not included, then an attacker could modify the ciphertexts (or the AAD), and still have something that would be accepted by the receiver.

Here are some of the obvious ways an attacker could do this:

He could add (or remove) trailing 0 bits (or bytes); as long as the number blocks remains constant, this would not change the tag.  Of course, this is because GCM uses an all-0 padding at the AAD and ciphertext; as designed, that's safe (because of the length block)
He could prepend a block of all 0's to the AAD (and if there is no AAD, he could do that to the ciphertext); because the polynomial that GHASH computes start with the 0 value, an initial 0 value would still result in a 0 (and thus not change the tag)
He could migrate part of the AAD to the ciphertext (or versa-visa); for example, if the AAD consists of blocks $AAD_1, AAD_2$, he could make the AAD the single block $AAD_1$, and prepend the block $AAD_2$ to the ciphertext.  Again, without the length block, this would be undetected.

Of course, it would be fairly easy to tweak how GCM worked internally so that the first two methods wouldn't work (use a padding method other than all-0's, start the polynomial with the value $H$ rather than 0); however the third attack would be harder to mitigate.


Given one message encrypted repeatedly with the same 'n' but different 'e's, is it possible to decrypt the ciphertext without simply bruteforcing n? I'm trying to solve a problem where I've been provided with a few public keys and the ciphertext, and I've been told that the plaintext was encrypted repeatedly using all of these keys. However, all of the keys have the same $n$ and a multitude of $e$s, varying from 2 to 126 digits. All of the other attacks involving matching $n$s only seem to work for multiple plaintexts encrypted with multiple keys, where in this case it's one plaintext encrypted with multiple keys. Is there any attack other than brute factoring that could allow me to find the plaintext?

As a better example:
Bob is concerned about his security, so he asks Alice to produce 3 keypairs, $(n, e_1), (n,e_2), (n,e_3)$ and then encrypts his plaintext, $M$, with each of the 3 keys, feeding the ciphertext $C$ from each into the next, so that by the time he's done, $M$ has been encrypted with all three keys in series to produce one final $C$ which is sent to Alice.

Ok, here's a hint:

Suppose you know the values of $P^{e_1} \bmod N$ and $P^{e_2} \bmod N$.  How could you use those two values to compute $P^{e_1 - e_2} \bmod N$?  How could you then use this repeatedly to compute $P^{\gcd(e_1, e_2)} \bmod N$?


Integer encryption preserving equality I have read too many different options for encryption that I now feel quite lost. I need a simple, secure (don't we all) scheme for encrypting integers (32-bit) with the following requirements:

Ciphertext is also an integer (32-bit) or a long (64-bit)
For integers x1=x2 then ciphertexts E(x1)=E(x2)
For integers x1<>x2 then ciphertexts E(x1)<>E(x2)
If I know E(x1) it will be very hard to decrypt x1 without the (private) key

Is there such a simple scheme?

Some of your conditions are already met by the definition of an encryption scheme:

Encryption has to be reversible, so that a ciphertext can be the encryption of (at most) one plaintext.
Your last point is basically just a ciphertext only attack. That is usually the weakest considered attack, and for todays security definitions not enough. So any scheme which is considered secure, it also includes this.

The only non-trivial part is your first point, because it is not that easy to find an encryption scheme, which has ciphertexts of 32 or 64 bit length. Of course you could use 3DES (64 bit), but that should not be recommended any more today. But there are other options:

Stream ciphers don't expand the ciphertext. When choosing a stream cipher, use a current one, and consider to use keystream btis beginning after some threshold. RC4 is popular but has quite a few security problems.
Using a block cipher in OFB, CTR (or KFB) mode of operation functions very similar to stream ciphers, and you can just drop the bits you don't need.
Format preserving encryption is a method which enables you to have that 32 bit to 32 bit relationship. But there are a lot of constructions, and quite a few build upon the other mentioned methods.


Polynomial sum of negligible functions need not be negligible Let $\{\epsilon_i\}_{n \in \mathbb{N}}$ be a sequence of negligible
   functions and $q(n)$ be a polynomial in $n$. Then $f(n) = \sum_{i = 1}^{q(n)} \epsilon_i(n)$ need not be a negligible function.

Ideas

A typical negligible function is $2^{-n}$. Maybe we can expand it to the family $2^{-(n+i)}$ and set $q(n)$ to something that will give a sufficient large sum [didn't work]

Consider the negligible functions
$$\epsilon_i(n) = \begin{cases} 1 & \text{if } n \le i \\ 0 & \text{if } n > i \\ \end{cases}$$

and $q(n) = n$

It should be easy to show that each $\epsilon_i$ function is, in fact, negligible, but the sum $f(n)$ is not...


IV Re-use and Chosen Plaintext against 56bit Blowfish (CBC) I am looking at a very old protocol which uses Blowfish to encrypt packets with a constant 8-byte IV in CBC mode.

Assuming I have:

The ability to arbitrary encrypt known plaintexts
The IV

I know that this lets me identify which plaintexts begin with an identical block and lets me identify also which plaintexts are exactly identical (since the cipher texts will remain identical until the first divergent block).

Is there any information which IV-reuse might leak that could be used to reduce the brute-force space for a dictionary attack or otherwise learn additional information about the plaintext?

I know that there are several theoretical weaknesses in Blowfish (such as this reflection attack against weak keys) but I am not sure if IV-reuse makes it possible to identify weak keys with less data than the hundreds of gigabytes proposed in those attacks.

No.

You're already assuming that chosen plaintext attacks should be considered. A known IV together with your ability to arbitrary encrypt known plaintexts is enabling exactly that attack vector to the block cipher. These attacks are all attacks on the block cipher, and Blowfish is considered rather secure, if deprecated because - among others - the block size. A mode of operation cannot influence the security of the block cipher itself, and CBC is still considered a secure mode of operation when it comes to storing data confidentially.

What you can do is attack the cipher or protocol in different ways. You say that Blowfish is used to encrypt packets, so it could be that CBC/PKCS#7 based padding oracle attacks apply. If no message authentication has been performed a lot of other plaintext oracle attacks could also become available. If the authentication is optional you can always try padding oracle attacks while leaving the authentication out (this seemingly idiotic strategy used to work against Web-security frameworks). There are quite a surprising number of attacks to transport security, so if they still use Blowfish you can almost be sure that it is not completely secure.


Time-locked Puzzles & Dead Man's Switch Intervention I have been researching time-based puzzles. Specifically, computationally expensive algorithms for the purpose of a time-lock. This has lead me to sequential squaring, firstly, as well as some memory-hard approaches and of course trusted third parties. Creating a scheme that cannot be deciphered in N time, though not entirely trivial, is at least in theory doable. My question though is as this might relate to a dead man's switch.

Suppose we have Alice who wants to encrypt her message so that should N time pass without her intervention, Bob can decrypt it. What model of system could she come up with so that if she intervenes, perhaps complexity (Or something else that prevents decryption for more N) is added to the problem?

None of the approaches I've been reading about consider this possible scenario. In addition to accounting for time, how can we also account for periodic intervention, adding to N and/or difficulty?

Creating a function that can’t be solved in N time
Some assumptions need to be addressed to adequately answer this question; the first is to establish that there are different protocols provided a scenario with an honest/dishonest Bob. In a scenario where Bob only acts honestly the solution, to creating a function that can’t be solved in N time, is less of a cryptographic discussion and more of a software portability issue. In addition it will be assumed that all encryption and decryption methods are public information.
The definition of a dead man’s switch
Now I’ll assume that when you refer to a dead man’s switch you’re referring to a system that executes some task when there is the absence of user interaction, and that this particular system is implemented in software. Most non-mechanical dead man’s switches are limited by the reliability of the power source and energy storage, and thus become uninteresting.
Assuming a dishonest Bob
Now in this scenario we will assume that Bob will try to cheat and find a method to decipher the message in time less than N. Being able to decipher the message in time greater than N is of no particular interest or even an issue.  So then the burden falls to Alice to prove that her particular decryption method is the fastest that exists, and to ensure that in the event that a faster method is discovered, that she is able to identify the cheating party. Furthermore Alice must ensure that her decryption system is sequential in so far as it can’t easily be run in parallel on a distributed computer network.
Discovering a cheating party is matter of recording the time stamp immediately after generating the message with expected decryption time of N, and by then calculating the time differential after the receipt of the decrypted message. Now assuming Alice has discovered a cheating party she must infer the capabilities of the attacker.

Did Bob discover a faster decryption method?
Possible

Does Bob have more computational resources?
Possible

Did Bob execute a pre-computation attack?
Not Possible :)

In addition Alice must assume at all times there is the possibility of silent failure: Where Bob could have completed two of the previously mentioned attacks, decrypted the original message before there was any system intervention, and is sitting on the cryptographic equivalent of a dirty-bomb.
Alice’s system intervention
As I understand your question you’re interested in a system where Alice could actively manipulate the expected decryption time N. In which case Bob would need to be interacting with a system where Alice has read/write access. Bob would also need a method to know when decryption was successfully completed without knowing the required decryption time N, or the original message that was encrypted. Alice also would need a method for periodic intervention WITHOUT changing the original encrypted master secret.
This is based on the assumption that the dead man switch would be used to distribute a static master secret (MS). Alice encrypts a message (M) with expected decryption time X, and issues cipher (C) to Bob. At some point before the expected decryption time X Alice needs to change the decryption time X by Y. Now this is just a bad idea because it will be more complicated to predict the computational capabilities of Bob, which is pretty much the only point of this exercise….but I digress. Then Alice computes the new cipher (C’), and issues the new value to Bob. But as Daniel pointed out Bob could just as easily continue to decrypt the original cipher (C) to recover the original message (M) independently of the new cipher (C’). So it’s likely that the secret key would be some variable time value (T’) to recover a non-secret and non-random message (M’).
This would be the indicator message to relay to Bob that decryption was completed. Bob would then use the variable time value (T’) and attempt to decrypt some master secret (MS). If decryption was unsuccessful Bob would continue to decrypt the most recently distributed cipher (C’). The issue is that Alice could just as easily distribute the master secret (MS) without having to distribute all the false variable time (T’) secrets for decrypting the master secret (MS). The triggering system would remain unchanged, and thus there would be no reason for variable time (T’) values. As such all continued interaction between Alice and the dead man switch would serve only to distribute the master secret (MS).
Third Party
A system where the master secret (MS) is delivered to a trusted third party would be possible only when implemented in a completely mechanical system. Given the fallibility of humans and the inherent possibility of system compromise. The United States Postal Service would be the best delivery method.
tl;dr
This system will provide no fail-safe for Alice. If this is wrong please edit.


Why is SRAM PUF considered weak PUF? I have read in many places that SRAM PUF is considered a weak PUF, since it generates a single response (based on the value of all RAM cells upon power-up).

Why can't I use just a limited number of bytes from the RAM space in order to create a CRP?
For example  if I have a 64kB RAM, I can divide it into 256 sections, each section 256B long, obtaining 256 CRP's? (Assuming that all the RAM cells are stable and can be used for PUF...)

In the article, "weak PUFs" are for key storage, and "strong PUFs" are for authentication, but both are PUFs.  It's just a function of how you use them.  A 32-bit PUF is just a random 32-bit number.  What makes a weak PUF strong is pairing it with an HMAC circuit, or something for a challenge response.
A few notes on the article:  the assumption that EEPROMs are expensive in both power and area is not really true.  It's difficult to find any IC without some sort method to hold the serial number, and if it is not EEPROMs, it's e-fuses (eFUSE, antifuse).  Everything in IoT has some sort of method to program memory.   To that end, if I have EEPROM infrastructure already, PUFs cost more regarding area, and both circuits have the same issues when I de-cap something and put my probes on it.  The circuit discussion was rather weak and some of the implementation examples in the overview won't work on aggressive nodes.


Is webkey a reasonably secure authentication system? I just created Webkey in the last couple days. This should allow any website to do single-password auth with a much higher level of auth security and convenience for users (single password with potentially hours or days expiry, text-entry-less single-click authentication if the password hasn't expired yet).

It uses RSA keys generated in-browser, stored in encrypted form using aes. The user's password is never sent over the internet (even in encrypted form). This utility can be hosted entirely statically (and is currently being hosted at http://webkey-auth.github.io/guest.html ).

Is what I'm doing here theoretically secure? I think this could be a huge improvement over auth based on sending usernames and password - which is kind of the weakest link in internet security at the moment. What are potential problems with how this works?

First of all, you should make a more formal definition of the protocol. Security cannot be assessed without a proper definition.

Second you don't specify an key sizes. RSA-512 is such a low key size that it may be considered broken. On the other hand, you may run into performance issues if you choose a higher key size (Elliptic Curve crypto would make more sense). This is not theoretical security, I know, but it kind-of makes sure that this will never run for any practical key sizes.

The same for the challenge. 3 characters is way to low and almost begs for replay attacks if the same challenge is ever send. A 16 byte challenge should be the minimum.

You seem to be using a Node.js include for your RSA key pair code. That's strange if the key generation is offered within the browser as you suggest.

The biggest usability issue is the fact that you may loose your private key if the browser storage is destroyed. The RSA key seems to be local to the browser, so sharing different devices isn't specified.

It doesn't seem to be specified what happens if you loose your key.

I haven't seen any requirements for TLS (with server authentication). You'd need that otherwise an attacker may steal your key by simply injecting Java Script code.

All in all, there's too much missing from the description of your protocol to make a full security review. But it seems there is a lot that may need improvement before it can be used for any serious purposes.


Does authenticated encryption add any protection to a signed digital envelope? The general scenario of hybrid encryption is to use public key cryptography for the exchange of a one time session key that can be used for the encryption of the plaintext with a symmetric encryption algorithm. A digital signature attached to that structure is what I know as a digital envelope. Furthermore, some resources agree that sign-encrypt-sign can help to prevent certain unlikely but possible attacks.

On the other hand, for strictly symmetric scenarios, the use of authenticated encryption is usually recommended as a default good practice.

Does it make sense to bring these two approaches together? Especially, would authenticated encryption (as opposed to semantically secure but unauthenticated encryption) provide any protection against any scenario not covered already by the digital signature?

I suggest that you look at Signcryption; a short survey appears here, and efficient schemes appear here. Just signing then encrypting or vice versa in a naive way is not secure (especially in the multi-user setting). So you have to do this right. Once you have a concrete scheme, you then have to see what level of security the encryption scheme needs to be. Typically it does need to be CCA secure, and the way to build CCA-secure symmetric encryption is the same as authenticated encryption. (Note that doing hybrid encryption or KEM/DEM, you need both the asymmetric and symmetric parts to be CCA secure.)  However, it really depends on exactly what you are doing. Look at the cited references as a starting point.


Is one-time-pad still secure if the number of 1's in the key is revealed to the attacker? For example, if $m = 10011$, $k = 11001$, $n=3$ (which is the number of 1's in k), $c = m \oplus k = 01010$. If $c$ and $n$ are revealed to the attacker, is this scheme still secure?

The security notion one usually considers for OTP is perfect secrecy, which informally means that the ciphertext does not reveal any information about the original message, regardless of the computational power of the adversary. It is already known that this requires that the key size must be equal to the plaintext size and that all keys are equiprobable. That way, for each ciphertext you could find a key that decrypts the ciphertext to any possible message.

However, your proposal violates these principles. Assuming the key size (and plaintext size) is $S$, then the number of possible keys is not $2^S$ (i.e., all the possible keys of length $S$, as in the regular OTP), but $\binom{S}{n}$, which is much less than $2^S$. This has the consequence that for a given message $m$, not all possible ciphertexts are equiprobable, or conversely, for a given ciphertext not all possible messages are equiprobable (in fact, some of them have no probability).

Let's see it with your example. With regular OTP, for a length of 5 bits there are $2^5 = 32$ possible keys (as well as messages and ciphertexts). If an adversary gets $c$, there are 32 possible messages that correspond to that ciphertext. That is, the ciphertext is completely useless to the adversary. Now, in your proposal, for $n = 3$ there are $\binom{5}{3} = 10$ possible messages for a given ciphertext, since there are only 10 possible keys. The ciphertext $c$ and knowledge of $n$ makes possible to the adversary to deduce which 10 messages (out of the 32 possible) are related to the ciphertext. Therefore, he is gaining some knowledge about the original message.


Is Hybrid Encryption CCA secure? If Enc is a PKE(Public Key Encryption) with key generation algorithm KG and message space $M = \{0, 1\}^n$, and SE is a Symmetric Key Encryption(SKE) with key space $\{0, 1\}^n$ and message space $M' = \{0, 1\}^*$ then the hybrid encryption
uses the same key generation KG, but its message space is $M' = \{0, 1\}^*$ and its encryption procedure $Enc'(p_k, m)$ picks a random symmetric key $k \gets \{0, 1\}^n$ and outputs ciphertext $(c, c')$ where $c = Enc(p_k, k)$ and $c' = SE(k, m)$. The decryption given $(c, c')$ decrypts $k$ from $c$ using the private key corresponding to pk and then decrypts $m$ from $c'$ using $k$.

If Enc is a CPA secure PKE on $M = \{0, 1\}^n$ and SE is IND secure SKE on$ M' = \{0, 1\}^*$,  is Enc' CPA secure PKE on $M'$?

If Enc is CPA secure PKE and SE is CCA secure SKE, is Enc'
 CCA secure?

If the KEM is only CPA-secure, then the resulting scheme might not be CCA-secure. For example, consider a CPA-secure KEM that ignores the last bit of its ciphertext. Then it is possible to modify a KEM ciphertext in a way that doesn't affect its payload, which is enough to break CCA security of the hybrid scheme.

If the KEM and DEM are both CCA-secure, then the overall hybrid scheme is also CCA-secure. This is proved formally in Section 7 of:

  Cramer, Shoup: Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack

However, it is possible to have a CCA-secure hybrid encryption scheme where the KEM is (slightly) weaker than CCA secure. This was first demonstrated in:

  Kurosawa, Desmedt: A New Paradigm of Hybrid Encryption Scheme

The weakened KEM security definition and composition theorem for hybrid encryption were formalized/generalized in:

  Hofheinz, Kiltz: Secure Hybrid Encryption from Weakened Key Encapsulation


Partition attack on the possible values of RSA modulus This is a question that arises from an exercise you can see here on breaking a bad EKE construction with RSA. However, my question does not tackle that construction.

The problem is that we work with an RSA modulus $N$ and with $e=3$ for encryption. As usual, $gcd(3,\phi(N)) = 1$. Also $N$ is a 1024 bits number. I need to reduce the possible $N$ in order to do an exhaustive search attack. It is claimed that:

  1.As $N$ is odd and between $2^{1023},2^{1024}$ then the first and last digits are ones.

  2.$N \, mod \,3 = 1$

  3.The set of valid $N$ is at least $\frac{1}{8}$ of the full space (I understand the 1024 bits)

The first is clear to me. But I don't see a good reason for the second. Even if I admit the second point then I would have removed about $\frac{2}{3}$ of the possibilities (something more because of the first point). Why is it claimed that $\frac{7}{8}$ of the possibilities are removed?

But I don't see a good reason for the second.

One requirement for RSA is that, if $p, q$ are the prime factors of $N$, then $p-1, q-1$ must be relatively prime to $e$ (if this is not true, then it becomes impossible to uniquely decrypt, as $gcd(e,\phi(N)) \ne 1$).  Now, if $e=3$, that means that $p \not\equiv 1 \bmod 3$ (and $q \not\equiv 1 \bmod 3$).  And, since $p, q$ are prime (and presumably greater than 3), we have $p \not\equiv 0 \bmod e$, $q \not\equiv 0 \bmod 3$.  That leaves, as the only alternative, $p \equiv q \equiv 2 \bmod 3$.

And, multiplying two values which are both 2 (modulo 3) together gives a value which is 1 (modulo 3).  That is, if $N \not\equiv 1 \bmod 3$, then $N$ cannot be a two factor modulus that works with $e=3$

  Why is it claimed that $\frac{7}{8}$ of the possibilities are removed?

My guess would be that Serge miscalculated here (however, his main point holds).  The first criteria (top and bottom bit must both be 1) eliminates $\frac{3}{4}$ of the possibilities.  As for the second point (which is independent), I suspect that they assumed that eliminating the $N=2 \bmod 3$ possibilities removed another half (and they they forgot about the $N=0 \bmod 3$ possibility); that miscomputation would have them eliminating $1 - (1 - \frac{3}{4})(1 - \frac{1}{2}) = \frac{7}{8}$.  However, if we recognize that $N=0 \bmod 3$ would be possible on an incorrect guess (and can also be eliminated), that means that step 2 eliminates $\frac{2}{3}$ of the possibilities (as you noted); that gives us an aggregate of $1 - (1 - \frac{3}{4})(1 - \frac{2}{3}) = \frac{11}{12}$ of the incorrect possibilities (and so the result is actually stronger than originally claimed).


When all shares of a secret are given to adversary as a permuted matrix Suppose we have a secret $\sigma$.

The secret comes from a universe in which the elements are not necessarily distributed uniformly.

We split $\sigma$ into $n$ shares $[\sigma_1,...,\sigma_n]$ (using Shamir secret sharing). So the order of shares matters.

We know given all the shares in the right order one can recover the secret.

We permute all the shares in a matrix (see below). We fill the empty indices with some dummy (or random) values $d_{i,j}$
\begin{matrix}
    d_{11}       & \sigma_{n} & \sigma_{2} & \dots & d_{1,m} \\
    d_{21}       & d_{22} & \sigma_{i} & \dots & d_{2,m} \\
    \dots                                   \\
    d_{k,1}       & d_{k,2} & \sigma_{3} & \dots & \sigma_{1}
\end{matrix}

Question: Given the matrix, can the adversary recover the secret with a high (or non-negligible) probability?

I emphasis that $\sigma$ may have very greater distribution probability than the other elements of the universe and the adversary knows that probability.

Please note that the values $k$ (number of rows) and $m$ (number of columns) are independent of the number of shares $n$ and we can increase them if it's needed.

====================================

Edit:
Newly added:

Suppose we have two permuted matrices one contains shares of secret value $\sigma$ and dummy values; and the other matrix contains shares of $\gamma$ and random values. We give away the two permuted matrices and one-to-one mapping of the elements to the adversary. The mapping tells the adversary that value in $i,j$ position in one matrix corresponds to value $k,l$ position in the other matrix.

Question: Would the adversary learn the secret values $\sigma$ and $\gamma$ with a non-negligible probability.

Let us first consider the problem without involving Shamir secret-sharing
at all.  Suppose that $n = 140$ and that the secret $\sigma$ is a 140-byte Twitter message. The space is thus restricted considerably, from all possible $256$ byte values to the printable
characters permitted to be used in Twitter messages, and the distribution in this restricted space might also be nonuniform because of etaion shrdlu. The secret sharing
is trivial: each of the $140$ shareholders gets one byte, and the secret
is recovered only when all $140$ shares are assembled in the correct
order.

An adversary is given a large number composite number $N$ of bytes
(arranged into a matrix if the OP so desires, though I am not sure why
this imposes some structure on the data) including
the $140$ shares and the other $N-140$
entries filled in "at random". Can the
adversary recover the secret with large enough probability to be
a significant concern?  Well, the answer might depend on the
assumptions. If the $N-140$ "other" bytes are "filled in at random"
from the space of all $256$ bytes, then the adversary can simply
discard all bytes that are not part of the Twitter character set.
This reduces the workspace from $N$ bytes to
approximately $p(N-n) + n$ bytes where $p$ is the ratio of the size
of the Twitter character set
(80? 96?) to $256$. It might also be possible to make some educated
guesses and apply the known distribution of the message set to discount excessive numbers of letters x or q or z etc or punctuation marks, etc.  So, with no secret sharing, the extraneous bytes that
the adversary is handed should be chosen not at at random, but
roughly with the probabilities with which they occur in Twitter
messages.

Many of these concerns go away when Shamir secret sharing is used.
Now, the shares are of the same length as the secret, but
share $\sigma_i$ is the value of the polynomial
$$S(x) = \sigma + a_1 x + a_2x^2 + \cdots + a_{n-1}x^{n-1}$$
(where the $a_i$ are randomly chosen nonzero entries) at some
nonzero element $\alpha_i$ in the field.  Even if $\sigma$ is restricted,
these random polynomial coefficients ensure that the shares
$$S(\alpha_1), ~S(\alpha_2),~ S(\alpha_3),~ \ldots,~ S(\alpha_n)$$
essentially look like random choices. In fact, some of them might
even equal $0$.  Thus, if we fill the $N-n$ other entries with other
random choices (allowing $0$ as a choice too), the $N$ possible
shares handed to the adversary will conceal the true shares very well.
I don't have a formal proof for this, but I doubt that any statistical
test can distinguish the actual shares from the fakes with even a
minuscule chance of success.  Of course, one must ensure that $N$
is much larger than $n$ so that there are enough . I venture to suggest that $N = O(n^2)$ will be found to be more than adequate, and
perhaps even something like
$10n$ might work well enough.


How is the EAX-mode used in EAP-PSK (RFC 4764)? According to the specification of RFC 4764, contents in EAP's third message and fourth message are required to be encrypted by AES-128 in EAX mode (also called protected channel).

In RFC 4764, the length of ciphertext is as the same as the length of plaintext. However, the test vectors in The EAX Mode of Operation show that the ciphertext must be longer than the plaintext.

Therefore, what happens in RFC 4764?

In RFC 4764, the ciphertext does not include the authentication tag created by EAX (which is treated separately); you can see this in figure 1, where they show the ciphertext (of length L) and the tag separately.

In contrast, the test vectors do include the authentication tag, and that additional length make the ciphertexts look longer.


Prove preimage resistance property Let $ f : \{0,1\}^* \rightarrow \{0,1\}^n$ and $ g : \{0,1\}^* \rightarrow \{0,1\}^m$. $h$ is created by concatenate f and g: $ h : \{0,1\}^* \to \{0,1\}^{n+m}$ with $h(x) = f(x) || g(x)$. How do I prove that both $f$ and $g$ must be preimage resistant if $h$ is to be preimage resistant? Is the same true for 2nd-preimage resistance?

Firstly a hash function $H : \{0,1\}^* \to \{0,1\}^{k}$ is preimage resistant if

Given any hash $y$ it is infeasible to find any message $x$ such that $H(x)=y$ .

Now for your case lets assume that one of the functions, say $g$, is not preimage resistance.
Now suppose we have a $h-$hash of unknown message $x$, we know, from the construction of $h$ , that the last m bits of our hash are equal to $g(x)$.

Since $g$ is not preimage resistant we somehow are able to find the value of $x$, which obviously means that we have found the message $x$ that results in a certain $h$-hash


Is there a public key encryption scheme with optimal key size? Symmetric encryption schemes such as AES have known security levels equal to their key sizes (i.e. breaking an encryption with an $n$ bit key needs about $2^n$ work steps).  Elliptic curve encryption gets halfway towards optimal: its security is half the size of the public key.

Are there any public key encryption schemes known which have security level equal to size of public key?  If not, do any do better than ECC?

I am skeptical that there will ever be a public key system that has the property you are seeking. Of course it would be possible to wrap a public key system up inside a symmetrical system to get that effect. For example, I could use 4096 bit RSA key which I protect with a 56 bit DES key, thus giving the system the strength of that, weaker, 56 bit symmetrical key. But leaving such things aside, I think that public keys will always be "special" in that their size in bits is not a direct representation of their strength in bits.

Short statement of why I'm skeptical

Not just any number can be a secret key. So even if the worst case for the attacker who has to just randomly guess at candidate secret keys, they can rule out a large number of things before they have to start guessing.

Symmetrical strength.

To understand why I'm skeptical, it is important to understand why strength == keysize works for symmetrical systems. Only then can we look at what is different about public key systems.

Alice picks, completely at random, a 128-bit key, k for AES. If AES isn't broken, Oscar's best hope is to simply guess k. (Actually, Oscar's best hope is to not attack Alice's key at all and instead try to get the message before it's encrypted or after it is decrypted or something else altogether.) If Alice used a cryptographically appropriate random number generator to pick k then k will be any one of 2^128 numbers, each with equal probability.

Brute forcing symmetric keys

We are assuming through all of this (and this is a very fair assumption) that Oscar has a way of testing a key that will tell him whether or not he has the right one. In order to be sure of finding Alice's key, k, Oscar would need to make at most 2^128 guesses. On average, he only needs to check about half of those, so it is 2^127 guesses.

This works out that way because any candidate guess is as like (well, actually unlikely) to be the right one as any other. There is nothing to prefer certain guesses to others.

There is also no way (if everything else is designed properly) to get any information about k from looking at the encrypted traffic. There also should be no way to get any information about the key even if you know what some encrypted messages decrypt to. And finally (and this has been a really hot topic in practical cryptographic implementations), there should be no way to get any information about the key even if Oscar can get Alice to decrypt messages that he creates.  In sort, a properly designed symmetrical system reveals absolutely no information about the key other than the fact that it is, say a 128 bits long.

So that has all been a long winded way of driving home the point that Oscar's best attack is to just guess at keys and any 128-bit number is as likely as another other.

Public keys

Public keys are nothing like symmetrical keys. We've got the public key, p and the secret key, s.  Alice picks a secret key, s, and calculates p based on s. She then publishes p.  It is crucial that p is calculated from s. For these systems to work, there has to be a special mathematical relationship between p and s.  For RSA s can be a pair of really big prime numbers and p can be something like the product of those two primes. (For the rest of this discussion I'm going to pretend that p is the product of the two primes, that this isn't quite how RSA really works.)

As you probably know, Alice can solve problems using s that cannot be done with knowledge of p alone, but p can be used to create such problems and p can be used to verify that the problems have been successfully solved.

The strength of the system depends on (among other things) that it be hard to compute s from p.

Brute forcing private key

The analogy, I suppose, of a brute force attack on an RSA public modulus (to discover the primes) would be to take primes at random that are about the appropriate size (so half as many bits as p) and see if they divide p evenly.  So here you see that a brute force attack involves far far fewer guesses than the size of p.  If p is 2048 bit number, then the factors of p will each be around 1024 bit numbers.

Furthermore, not every 1024 bit number is prime; only about 1 in 300 of them are prime. (I'll say 1 out of every 256 so make rounding easier in my next step.) So for a brute force attack on a 2048 bit public key, Oscar "only" has to make 2^1016 guesses.

Now that is an awful lot of guesses, and would be more than sufficient. If this were the best way to discover s, then you would only need RSA keys about about 280 bits to get 128 bit security. But of course, this is an incredibly stupid way of attacking RSA.

However, there are two points from that simple example.

The secret key is (often) much smaller than the public key.
Not any number can be the secret key.

Either one of these mean that in terms of just blind guessing (brute force) the number of guesses necessary will be substantially shorter than the actual size of the public key.

Don't brute force

There are ways to try to go from p to s that are better than just doing that kind of random guessing. In the case of RSA, there are much better ways. In terms of the discrete logarithm problem in integer fields (for Diffie-Hellmen public key stuff), there are much better ways than brute force guessing to discover the private keys as well. Indeed, if the private key isn't chosen with considerable care there are enormous shortcuts that Oscar can take.

The best we can hope for

The best we can hope for is where guessing is the best strategy, but it will still be guessing in a limited domain. It won't be every possible number the size of the public key.  Even though ECC and DH are based on the discrete logarithm problem (DLP), they are the DLP in different fields, and ECC is holding up remarkably well.

I don't know if we have theorems that prove that ECC will continue to hold up. It isn't perfectly at this "best case", but so far it seems to be close to that.

Resources

I really recommend the book Understanding Cryptography by Christof Paar and Jan Pelzl. Chapters 8 and 9 do an outstanding job of explaining ECC and the kinds of attacks that might exist against it. The book is written well enough that it can genuinely be used for self study.


How does the UE communicate its ephemeral public key to the HN in 5G networks? I have been taking a look at ETSI TS 133 501 V16.3.0 to see how exactly does a User Equipment actually authenticates itself to the Home Network.
This is supposed to be done during the AKA procedure, but when I look at it, the HN is able to retrieve the SUPI from the SUCI without the UE having sent its ephemeral public key (section 6.1.2). Has the UE already sent its ephemeral public key before AKA takes place?
Also what seems odd to me is that in section 6.12.5, which talks about how to obtain the SUPI from the SUCI, nothing is said about the UE's ephemeral public key. However in annexe C, all protocols (except for the null one) are ECIES based and therefore HN needs to know UE's ephemeral public key.

Ok, so after a lot of reading I realised that the UE's public key is actually concatenated to the ciphertext to create the SUCI. So it's by sending the SUCI that the UE actually sends it's Ephemeral public key


One-way function definition I cannot understand why a one-way function $f$ is defined in this way

$\text{Pr}(f(A(f(x))) = f(x)) < \frac{1}{p(n)}$

and not

$\text{Pr}(A(f(x)) = x) < \frac{1}{p(n)}$

where $A$ is a randomized algorithm.

Where is the difference? Is the second one weaker?

The two conditions indeed represent different things. Consider the function that, given an $n$-bit input, returns $n$ zeroes. This clearly meets the second definition (if you have $n$ zeroes, a randomized algorithm has just a $1/2^n$ chance of guessing the input, because any $n$-bit input returns that output), but it also clearly fails the first ($A$ is just "return $0^n$"). So the first condition is not weaker than the second; in fact, anything failing the second clearly fails the first (you just use the same algorithm $A$, and use $A(f(x))=x$ and so $f(A(f(x)))=f(x)$). So the first is in fact stronger than the second.

The key difference between the two is that the second is just about finding the exact input we fed into the function. If a function meets this condition, then it means an attacker who knows the output isn't going to figure out our actual input. But that's often not what we're concerned about. In many schemes, it's a problem if the attacker can find any input to get a given output, whether or not it's the actual input we used. Condition 2 asks for the inverse; condition 1 just ask for an inverse, and if the function isn't one-to-one there's a difference between the two. In crypto, one-way functions tend to be used where finding an inverse is a problem.

To use a password hash as an example, suppose my password is swordfish, which hashes to ABCDE1234, and the hash function meets condition 2 but not condition 1. Because of (2) you can't efficiently figure out that my password is swordfish, but because it fails (1) you can find something that hashes to ABCDE1234 (say, letmein12). Sure, you didn't get my password, but you found some inverse of ABCDE1234, and it doesn't help me that you didn't get my password - letmein12 works just as well for your purposes.


Are TLS connections in china mostly encrypted with AES or with SM4? What is the dominant symmetric cipher used for TLS connections in China? Is it AES, as it is in the US, or is it SM4?

I think as of June 2020, it's still AES, as SM4 isn't registered in IANA formally backed by an RFC yet, and most browsers used by netizens in China are based on Chromium (some users use FireFox, and some government websites still requires IE!).


Is 1D Perlin noise cryptographically secure As the title, if I have:

A stream of 1D noise

And I know:

The noise is generated using the Perlin method with a known number of octaves > 1. (as implemented here)
The random numbers used in each call to the Perlin noise method are generated using the Mersenne twister.
The Mersenne twister is initialised with the same seed in every call.

Is it possible to attack the state of the random number generator and therefore predict future noise?

I know that some steps in this process are vulnerable. But when combined, can this still be attacked?

First of all, the Perlin method requires a random number generator as input. It seems deterministic in nature by itself. So if the random number repeats with a given seed, then I suppose it should always generate the same stream. In that case it is insecure as it is predictable even without any particular attack. Besides that, if the seed is a predetermined value then it could be considered a constant in the derived MT algorithm, and it would therefore go against the Kerckhoff principle.

As the Perlin method is not strictly made to be irreversible, I don't see how it would protect an insecure PRNG. For instance, I would expect that it generates certain maximum and minimum values for which the output of the random number generator can be established. If that happens for enough bits, then in the end enough state of the Mersenne Twister may be known to retrieve the seed, breaking any security present in the combination of the two algorithms.

Let's assume that the Perlin method at least leaks some information about the stream. In that case the question becomes: can you break the Mersenne Twister given enough output, even if that output is further apart? And that question I don't know the answer to; I would however not assume that it is impossible.

However, things will get worse: if the Mersenne Twister only uses a 32 bit seed and the Perlin method is indeed deterministic, then it is completely feasible to try all possible seed values and simply run the algorithms on them, comparing the output against known values. And as the 32 bit strength of the seed is nowhere near enough security, the algorithm would not just be theoretically but also practically broken as it would be easy to brute force the seed.

Practically this would require you to know the parameters of the specific Perlin noise generator as well, of course. Again, considering those secret would go against Kerckhoff's principle, so theoretically it would still not be secure even if those have enough strength to secure the implementation.


ElGamal malleability for a given function f(m) Given the function $f(m)=m^3$, where $m$ is a plaintext message, what is a function for which ElGamal would be malleable to produce $f(m)$. I know for $t * c_2$ that this would yield $t * m $ but I haven't been able to figure out how it works with powers of $m$.

To understand how this works, let's first recap how ElGamal works:

All parties agree on system parameters $(\mathbb G_q,q,g)$ first such that  and the order of $g$ in $\mathbb G_q$ is $q$. All the formulaes to follow need to be read as being done in $\mathbb G_q$ written multiplicatively, except if specified otherwise.

Next the recipient picks a random $x\in\mathbb Z_q$ and publishes $\beta=g^x$ as his public key and keeps $x$ as his private key.

Now finally the sender picks a random $y\in\mathbb Z_q$ himself and computes $c_1=g^y$ and $\beta^y=g^{xy}$. He uses this "shared secret" to multiplicatively blind the message $m\in\mathbb G_q$ as $c_2=m\cdot \beta^y$. The cipher text is now $(c_1,c_2)$.

Now you want to modify $(c_1,c_2)$ to $(c_1',c_2')$ such that $m'=m^k$ for arbitrary choices of $k$.

This is indeed trivial. First observe what happens if you calculate $(c_1',c_2')=(c_1^k,c_2^k)$. As you may already see, this means you actually calculate $(g^{yk},(g^{xy}\cdot m)^k)$ and this is exactly $(g^{yk},g^{xyk}\cdot m^k)$ which in turn decrypts to $m^k\bmod p$ as the recipient will just compute $c_1^x\equiv g^{xyk}$ to unblind the message $m'$.

In the above explanations, plug $\mathbb F_p$ (with $\mathbb P\ni q=(p-1)/2\wedge p\in\mathbb P$) in as your group $\mathbb G_q$ and $k=3$ to get the answer to exactly your question. Alternatively you may plug the group of the points on your favorite elliptic curve in as your $\mathbb G_q$ and pick $k=42$.


Who provides prime numbers for cryptographic protocols? I am currently writing a thesis about different cryptographic protocols like DH-Key exchange, TLS or IKE.
Most of them rely on a prime number earlier or later, so for security reasons I wondered if this prime number is supplied by the user and if yes that leads to the question if I can manually provide it (for example to use a pseudoprime to break the underlying primitive more easily).
I really tried to search online, but there are very little information about this part of protocols. I hope you can help me with that.
Thank you for your time and answers :)

Let's have a look at how these are implemented:
RSA
RSA is probably the example, showing how prime numbers are used in cryptography. In order to calculate a private key, two prime numbers, $p$ and $q$ are "chosen". What that means in practice is that your computer will generate a random number (and set a few bits) and then check whether or not the generated random number is a prime.
Well...not exactly. Actually, the generated number is a "pseudo prime number", which is a number that is probably a prime number, but we can't know for sure. In order to be certain, we would have to divide the number by every prime number up to the square root of the prime candidate.
Why isn't this check done? As you can imagine, checking whether or not 13377216267221394781281321803240685565647633863945354245591337480581850892718220086347852930388186839929611014777408043323753186115505611255512212061593047 is a prime factor of  168581487233807662095985877892466382655984504887588184273878566402288131033127314863556248166230176818735604347430473403376658381900826700241919315590165489510028586594896744589808921429729412701596114362546978418049726172509111051384159129475101054095614648000575426731420406552789078218487162756487172295557 is a computationally expensive task. Especially if our current tests run magnitudes faster and can give us a $4^{-k}$ chance of a non-prime passing the test, with $k$ being the number of runs of the Miller-Rabin test.
You can even try this yourself by running openssl genrsa. You will see output like this:
Generating RSA private key, 2048 bit long modulus (2 primes)
................+++++
...............+++++
e is 65537 (0x010001)

Each . means a potential prime candidate was generated, and each + means a round of Miller-Rabin was passed. According to this answer, even three rounds of Miller-Rabin will be enough to make it very unlikely that a randomly generated non-prime passes the Miller-Rabin test. So as you can see, OpenSSL stops after five passed rounds and moves on to generating a new number.
Diffie-Hellman Key Exchange
In order for DH to work, there needs to be a public prime $p$, which can be a known default value. These can be generated on-the-spot by either the client or the server, but publicly known default values can be used. Since these are just transmitted over plain text, an attacker can intercept them.
It should be noted that you want to pick a $p$ for which $p-1$ has a large prime factor $q$.
The secret keys $a$ and $b$ generated in DH don't need to be primes, so any random number will suffice.
Are they supplied by the user?
Yes and no. Many protocols require a user's private key, which they supply in form of a key file. Nothing stops a user from generating their own key file with any prime number of their choosing.
However, most users won't do that, as there is really no benefit to that. Even an attacker has no benefit of supplying something like a semi-prime (a number that is the result of two prime numbers, e.g. 15), since that would not give them any advantage.
Definitely, no serious program will ever ask the user to enter a prime number, which is then used for cryptographic purposes, aside from demonstration tools.