Random decomposition of symmetric key Considering a symmetric cipher (i.e : AES in counter mode), is it possible for any given key to be randomly decomposed into other keys without knowing the message or the ciphertext, such as :

100 = 45+55 (or) 30+70 (or) 25*4 (or)...

Key1 = Key2|Key3 (or) Key4|Key5 (or)...

For any message, applying Key1 or Key2|Key3 would have the same encryption/decryption result.

One-time pad would be an option but it is not very practical because it would take the same length as the message. I am open to all suggestion. Thanks !

It might help if you explain what problem you're trying to solve.

For example, what exactly do you mean "Key1 = Key2|Key3"?  If you mean (say) taking a 256 bit AES key, and splitting it up into two halves (where you need to present both halves to encrypt/decrypt), well, that's easy; however, I doubt that's what you're asking.

Alternatively, when you say "Key2|Key3", you might be asking to split the key into two halves; where Bob has one half (and performs the operation on it), and Carol has the other hand (and she takes Bob's result and her own key, performs the operation on it, and her result is exactly what Alice got with the original key.  If so,  we can consider (for example) 2AES; that is, you encrypt the message with AES key 1, and then with AES key 2.  So, the full key can be considered AES key 1 concatenated with AES key 2; obviously, we can split it into two halves.  However, I suspect that this won't address your problem (whatever it is) either.

Assuming that the second guess was on the right track, and you insist that the operation on key 1 are exactly the same as the operations on key 2 and key 3, well, we run into a problem.  Generally speaking, symmetric ciphers aren't closed operations; there usually aren't any key 2's and key 3's which are jointly perform the same operation as key 1.  However, one example does come to mind: Pohlig-Hellman; with that, given a key, you really can split it randomly into two keys.  However, I again can't be quite certain if that's what you're looking for either.


Multi-Linear Secret Sharing vs. Shamir Secret Sharing I hope someone can help me. I read several papers including the original paper, "Multi-linear Secret-sharing Schemes," by  Beimel et al., and watched the following video https://www.youtube.com/watch?v=3GFdp7V_yog but still struggling with the concept of multi-linear secret sharing scheme. I know that in LSSS, the secret is an element of a field, and a dealer distributes shares to parties. Consequently, the parties can independently use linear mapping to recover the secret. I will use the same example in the video; a secret is shared in field, F_2, and the matrix is as follows:

My questions are:

The first and the second rows of the matrix are labeled to the same party, ie P_2, but how can you give different shares to the same party?
Only P_2 and P_4 can recover the secret because when they combine their shares, the r_2, r_3, and r_4 gets canceled, But P_2 already has r_2 in two different rows. What is the difference between row 1 and row 2?
what is the difference between Shamir's secret sharing and multi-linear secret sharing.

Thank you

I'm not an expert but I will try to answer from my understanding.

LSS allows you to divide the secret to many shares and it does not limit you to give only one share to a person. In the example you have given, the secret is divided into 5 shares and gave to 4 people. In this case, P_2 receives 2 shares.

Having r_2 in two different rows doesn't help much in this case because there are other terms to help hiding the secret. You can treat both row as a different share of secret. In this case, it is hold by the same person P_2.

The above example is Linear Secret Sharing, where the reconstruction of the secret come from the linear algebra operation from the matrix used. Multi-Linear Secret Sharing is like an extension to LSS by hiding more than one secret at the same time and use the similar algorithm to reconstruct the secret.

Shamir Secret Sharing, on the other hand, rely on polynomial interpolation to reconstruct the hidden secret. Using the fact that d+1 points can interpolate degree d polynomial with Lagrange's Coefficient, we can assure that for d+1 shares can reconstruct the hidden secret. This is a good explanation video on SSS.


Estimating difficulty of "Memory-Hard Proof-of-Work" based on "size of memory"? In Bitcoin proof-of-work, the difficulty of Proof-of-Work is estimated and calculated based on total hashing power of the participants. If total hashing power of the participants is higher, then PoW is more difficult.

If we use a Memory-Hard-Proof-of-Work scheme, the difficulty of Proof-of-Work is still estimated based on the hashing power ? OR based on the size of memory ?
In other word, is it feasible to design a Memory-Hard-Proof-of-Work scheme in which we could estimate the Pow difficulty based on the size of memory, instead of hashing power of participants ?
Has such a Memory-Hard-Proof-of-Work scheme designed yet by which we could estimate the difficulty based on memory size?

Just as an example: a Memory-Hardened Proof-of-Work Scheme: https://eprint.iacr.org/2017/1168.pdf

P.S. 1: Related question: Memory-hard proof-of-work: are they ASIC-resistant?

P.S. 2: If you need any further complementary explanation about the question, please let me know.

The measure of resource typically used to evaluate memory-hard functions is not the amount of work (i.e., $T$-complexity) but rather the space-time complexity (i.e., $ST$-complexity) of the computation. As the name suggests, it is the product of the maximum amount of space used and the time taken for the computation. (Strictly speaking, we have to also take in account amortization of the cost and the exact measure used is the cumulative space-time complexity, but the notion of space-time complexity still conveys the basic ideas: see [AS] for more details.) Good memory hard functions require $ST=\Theta(n^2)$.

The motivation behind this switch is to discourage the use of ASICs in computing proofs of work. The rationale of using ASICs in computing proofs of work is that they are much faster than CPUs. The speed-up is primarily due to its application-specificity, and the availability of large-scale parallelism. However, there is an asymmetry in the cost of memory (space, i.e.) as it is much costlier in ASICs compared to CPUs. Therefore, if one can construct a function that can be computed “fast” using “sufficient” space (even) on a sequential machine, but takes “more” time if the amount of space used is “lesser” (even with parallelism), then ASICs are not practical anymore as the increased cost of memory counteracts the increased computation power, but computing the function is cheap on a GPU.

Now, to your questions.

  If we use a Memory-Hard-Proof-of-Work scheme, the difficulty of Proof-of-Work is still estimated based on the hashing power? OR based on the size of memory?

The amount of work considered is still in terms of the amount of hashing power, the role of the memory as explained above is just to discourage the use of ASICs.

  In other word, is it feasible to design a Memory-Hard-Proof-of-Work scheme in which we could estimate the Pow difficulty based on the size of memory, instead of hashing power of participants?

There has been a lot of work in the recent years addressing this exact question --- the main motivation being that if space is used instead of work/time as a resource then there would be less energy wasted. The object is called a proof-of-space [D+,A+,F] and the prover/miner is rewarded for dedicating some disk space instead of doing work. (There is also a cryptocurrency, called Chia, that is being deployed based on proofs of space.)

[AS]: Alwen and Serbinenko. High Parallel Complexity Graphs and Memory-Hard Functions.

[A+] Abusalah et al. Beyond Hellman's Time-Memory Trade-Offs with Applications to Proofs of Space

[D+]:  Dziembowski et al. Proofs of Space

[F]: Fisch. Tight Proofs of Space and Replication


What differentiates a password hash from a cryptographic hash besides speed? I understand that password hashes like bcrypt have the principal property of taking a long time to run, but I'm wondering what if anything about password hashes make them superior to merely running a fast cryptographic has a bunch of times.

In particular, why does bcrypt exist when I can just run SHA-256 100000 times? Furthermore, it seems relatively extensible to adapt to increases in computing power. When computers get 100000 times as fast as they are today, I can just reapply the hash to my password hashes 100000 times and at verification time run SHA-256 100000*100000 times to validate a password attempt. Are there flaws in this naive approach. Are there other properties of password hashes that make them particularly suited to hashing passwords? Lack of parallelizability, space complexity, something else?

My question comes about when analyzing a prominent response to the June 2012 incident in which 6 million password hashes were stolen from LinkedIn. In the article, the author emphasizes the value of using a password hash instead of a fast cryptographic hash in validating user passwords. I understood the basic argument for having a hash that's slow but failed to glean from it particular advantages of "password" hashes that made them distinct.

To the best of my knowledge there is no formal distinction, since "password hashes" aren't formally defined.

That said, if you look at this presentation from the author of scrypt you'll see that he wanted:

Password hashing to be CPU hard (i.e. to require significant amounts of CPU processing, in a manner that cannot be optimized away).
Password hashing to be memory hard, i.e. to require large amounts of RAM capacity and RAM I/O bandwidth.

Being CPU hard helps delay offline brute force password breaking, as you note. Being memory hard helps guard against getting dramatic speedups from using a different type of hardware.

Simple SHA hashes require minimal internal state, and can as such be massively accelerated by running hashing in parallel on the 256+ cores of a modern graphics card. An even larger speedup could be had by creating a bunch of FPGA / ASIC chips dedicated to running SHA operations in parallel.

Being memory-hard gives a measure of protection against this, because currently there is no cheap technology to scale memory-I/O. FPGA's are comparatively 'cheap' to make; but large amounts of low-latency memory isn't.

To your questions:

  I can just run SHA-256 100000 times?

If you loop through the same hash function many times, then there might be a small loss of entropy each time, if the hash function isn't ideal. See "Why does PBKDF2 xor the iterations ..". If you improve your own suggestion, for example by mixing in the salt at each iteration, then you get close to the design of PBKDF2. In that case you should use PBKDF2 instead, because PBKDF2 is a mature and peer reviewed design.

  Furthermore, it seems relatively extensible to adapt to increases in computing power. [...] I can just reapply the hash to my password hashes 100000 times and at verification time run SHA-256 100000*100000

That works. At verification time the end user gives you his password in plain text. So you could also verify the password against the old hash using the old hashing function, and create a new hash from the plaintext, using the new hashing function.

For more, see the scrypt presentation as well as the hash + password tag on Crypto, as well as the past discussions here.

Please note: It's great that you learn about this for your own interest and understanding. When it comes to building production software, you should not create your own password hashing implementation -- you should use an appropriate higher-level library, one that has seen extensive security scrutiny.


Creating a k bit random string My goal is to create a random $k$ bit string. My question can be divided in two parts.

If a $n$ bit string $s$ is computationally indistinguishable from a random $n$ bit string, can we say that the string $s$ has $n$ bit min entropy?
But for some reason I can't use the string $s$ directly, I need to convert it to another $n$ bit string $s'$. During conversion something bad happens. The probability of each bit being $0$ or $1$ is not $1/2$ anymore. It is $1/2+e$. Hence the min entropy of the bit string $n$ changes. Let the min-entropy of $s'$ be $l>k$. As hash functions are good randomness extractor, if I apply a hash function $H$ on the string $s'$ that produces $k$ bits, can I say the output of the hash function is a $k$ bit random string?

Thank you for your help.

Addressing the first point, then no.  Min entropy is the smallest estimate of all ways of measuring entropy.  If you consider a string for cryptographic purposes, it's traditional to take the most conservative approach of entropy estimation.  That's the safest way if you wear a tin foil hat.

Min entropy is:-

If s (or X) is random, the individual byte probabilities will be uniformly distributed.  Some Pr(x) will be higher than others.  This range may actually be quite large because randomness can be quite pesky.  Since min entropy takes the max Pr(x) of the range, min entropy will always be lower.  In practice, it may only be 1 - 2% lower for random data.  It will be much lower though for non random data like language.

As a picture, this is a histogram of 1MB of really random data:-

We can assume that this is unbiased. Yet there is significant variation in the individual byte probabilities (the random thing). Ergo there must be a max probability.  This leads to a min entropy value of 7.93 bits /byte. So for an output of 1MB, you can only count on 992000 bytes of entropy for cryptographic purposes.  That's 0.9% less than you might naively expect.  Incidentally the chi for this gives p = 0.15.

As to your second point, I don't think that there is any consensus on this site.  Some say that a hash entropy extractor can only extract half of the original entropy.  Most of this work is highly theoretical though and I am  unconvinced of it's applicability to reality.  On the other hand there are commercial devices that can extract more than half.  I personally believe now that an extractor can extract all source entropy.


Is this a structural weakness of Feistel networks? I'm doing a lot of reading about Feistel networks. Something occurred to me a bit ago that I hadn't realized previously, namely that in any Feistel construction there are bits of the plaintext that are never given as input to the round function without having been mixed with the previous round function's output.

For example, in the first round of a balanced Feistel network $L_0$ is XORed with $F_k(R_0)$ to get $R_1$. Thus, $L_0$ is never used by itself as input to $F_k$, which could violate the diffusion property of the cipher.

Is it even possible to get around this limitation, perhaps with a modified first round?

I don't think this is a real vulnerability in e.g. DES or Blowfish, for the record. Rather, I'm wondering whether this could be used to craft a successful attacker in a game against a reduced-round variant of these kinds of ciphers.

If such a network had only a single round, then you might have a valid concern. This is why there needs to be least three rounds, so that every bit from L can potentially affect every other bit from L (via R from the second round).

It isn't a structural flaw, because multiple rounds are assumed. Changing this round structure would mean that it was no longer a Feistel network, and you would lose the reversibility of each round (when the key is known).


Cryptography Engineering - Design Principles and Practical Applications - Chapter 9 Generating Randomness - Section 9.4 The Generator I'm currently reading "Cryptography Engineering - Design Principles and Practical Applications" written by "Niels Ferguson, Bruce Schneier, Tadayoshi Kohno" published by Wiley in 2010.
In "Chapter 9 Generating Randomness", "Section 9.4 The Generator", there are two paragraphs (see screenshot below) which I do not quite understand.

In particular, how does the author comes with the probability of $2^{-97}$, the number of requests as $2^{97}$, and the total workload for the attacker as $2^{113}$ steps?

This continues from the above question. How does the author mean there are $2^{113}$ steps on both the attacker's machine and the machine that is being attacked?
Any kind folks who can help to explain this clearly greatly appreciated!
Thanks in advance!

This section talks about Fortuna, where it uses a block cipher with a 128-bit block and a 256-bit key size. The cipher is used in CTR mode. In the CTR mode, if an attacker can access the internal state than then the security is lost ( the key and current counter value), therefore after a request, 2 new blocks are generated and used as a new key, and the old key is forgotten to eliminate exposure of the old requests.
All talk is about distinguishing the PRP from PRF in the CTR mode. In the CTR mode with a PRP, if you encrypt with one key then $2^{128}$ blocks are distinct since it is a permutation, but we don't expect this from a PRF. So the PRP-PRF switching lemma applies to distinguish the statistical deviation. After $q$ messages the security lost is proportional to $q^2\!/2^{128}$.
In the classical birthday attack, when the outputs are random we expect collisions, remember the CTR mode doesn't generate one with PRP. For a PRF with 128-bit output, approximately

Once we generate $2^{64}$ outputs there will be  $$\approx (2^{64})^2/2^{128}/2 = 2^{128 - 129} = 1/2$$ change collision. But we will not see one in the Fortuna, it uses PRP in CTR mode! Therefore this is a distinguisher.

if you only generate $2^{16}$ blocks for a single key then the probbaility is $$\approx (2^{16})^2/2^{128}/2 = 2^{32 - 129} = \dfrac{1}{2^{97}}$$ this means this distinguish probability is negligible.

Requesting $2^{97}$ blocks is the reverse of the birthday attack. Since one has $\dfrac{1}{2^{97}}$ change of seeing a collision for $2^{16}$ blocks then you need to request $2^{97}$ blocks to see a collision within a $2^{16}$-block. Therefore the cost is $2^{97}\cdot 2^{16} = 2^{113}$.
For 256-bit block sizes, the collision is no more a threat since you need to $2^{128}$ blocks to see one with 1/2 probability.
$$\approx (2^{128})^2/2^{256}/2 = 2^{256 - 257} = 1/2$$
The $2^{113}$ is continuation from the 128-bit attack cost, since $$(2^{113})^2/2^{256}/2 = \dfrac{1}{2^{32}}$$


How many times can a key be used for HMAC-SHA256 before it needs to be rotated? If I wanted to use hmac for proving that a value hadn't been tampered with, how many times can I use a key before it needs to be rotated?

There is no known inherent weakness in HMAC-SHA256 that requires key rotation for a suitably secret key.

However, other aspects of the system in which you are using HMAC-SHA256 may make key rotation necessary. For instance if you don't want the same message to have the same hmac over time for some reason a key rotation would achieve that (but so would a salt). Or if you know your key comes from an unusually low entropy pool making it easier to brute force than one would expect.


Is there any area where AES-CBC cannot be used ? If so, why? I would like to know the domains or specific applications where using AES-CBC is not advised due to any drawbacks like sequential encryption of AES-CBC ?

CBC does not perform authentication

This property makes it less suitable for places where authentication is required, basically any transport protocol. TLS uses CBC, but by default performs authentication over the plain text instead of the ciphertext, which opened up a host of attacks. CBC can be used here, but it is error prone and may require an additional key for calculating a (H)MAC.

CBC is more error prone than other modes of encryption to error oracles, even if padding oracles (see below) are not feasible. See the paper "Error Oracle Attacks on CBC Mode" by Chris J. Mitchell for more information.

CBC doesn't let you pre-calculate a key stream

Pre-calculated key streams let you XOR plaintext with the pre-calculated stream to provide encryption. For instance AES-CTR makes it possible to let you use very low latency encryption for protocols.

CBC doesn't allow you to perform parallel encryption

As each block is depending on the previous block, all the way up to the last block, it is impossible to perform AES using multiple threads at the same time. This is a performance bottleneck which may invalidate AES-CBC on many systems where performance is required (and that do not have implicit parallelism).

CBC doesn't allow you to skip bytes

As each block is depending on the previous block, it is not possible to start encryption in the middle of a stream (decryption is possible though). This means that CBC is less suitable for re-encrypting parts of a file. Nor does this allow you to easily skip frames in e.g. video or audio play back.

CBC requires padding or ciphertext stealing (CTS)

Padding has many issues: it requires additional block encrypts and will require additional space. If CTS is available (it isn't usually) it requires at least one block, although the IV may be used as well if that is send to the other side. Regardless, CBC may have issues where a minimum number of bytes need to be send, or when a minimum number of block encrypts is required.

Besides that, CBC with padding applied may be vulnerable to padding oracle attacks. These may even be present on applications that are protected with a MAC if decryption is performed before authentication is established. This includes all transport protocols.

CBC requires an IV that is unpredictable to an attacker

This may be an issue where no fast random number generator is available and/or where additional block encrypt (to create an encrypted IV) is not feasible or wanted. This may be an issue on embedded platforms. As it is not directly possible to use a counter, CBC cannot be directly used on places where the IV can be derived from some identifier present in the protocol. It is also tricky to use an IV that is smaller than the block size.

CBC ciphertext errors do not propagate much forward nor do they travel backwards

This is not a feature that is requested a lot, but where it is, CBC does not provide it. Instead a mode such as bi-IGE (bi-directional Infinite Garble Extension) must be used.

Single bit errors in the ciphertext may affect up to 129 bits of plaintext

On the other hand, a single bit error in the ciphertext will garble the a complete block + a bit in the next block. This means that CBC is less suitable in places where error correction is calculated over the plaintext. CTR would be more suitable in such situations.

CBC may fail harder if you use a key too long

If you use a key for close to $2^{n/2}$ blocks, you expect a collision which leaks a block's worth of data. In contrast, CTR-based modes fail more gracefully: as long as you don't reuse a counter value, they only lose indistinguishability at that point.


Does there exist an agreeable algorithm to substitute XOR function in Shamir's no Key Protocol? I think Shamir's no key protocol (also known as three-pass protocol) is a secure cryptography scheme but the designer only proposed the XOR function to encrypt the message which could be easily broken when the eavesdropper has all the encrypted messages: all the eavesdropper has to do is to XOR them and there he has the plain text

I don't remember reading Shamir's original proposal, but I would strongly suspect that he never endorsed the use of XOR in the protocol; if he mentioned it at all, it was as an illustration.

Instead, here is what is commonly referred to as Shamir's three pass protocol:

Alice and Bob agree on a large prime $p$ (larger than any message Alice wants to send)
Alice wants to send Bob the message $M$
Alice selects a random $a$ (relatively prime to $p-1$)
She computes $M^a \bmod p$ and sends it to Bob
Bob selects a random $b$ (relatively prime to $p-1$)
Bob computes $(M^a \bmod p)^b \bmod p = M^{ab} \bmod p$ and sends it to Alice
Alice computes $(M^{ab} \bmod p)^{a^{-1} \bmod p-1} \bmod p = M^b \bmod p$ and sends it to Bob
Bob computes $(M^b \bmod p)^{b^{-1} \bmod p-1} \bmod p = M$

That is, instead of using XOR, they perform modular exponentiation modulo a prime; with this, recovering $M$ from $M^a, M^b, M^{ab}$ is essentially the computational Diffie-Hellman problem, that is, believed hard given appropriate parameters.


Decrypting Multi-Prime RSA with e, N, and factors of N given I was wondering if there was any way to compute the private key $d$ when knowing only $e$ and $N$, and being able to factor $N$ as 4 prime numbers $p, q, r$ and $s$. I've been searching for days and I can't find any way.

In multi-prime RSA, the definition of a valid private exponent $d$ is the same as in regular RSA: any $d$ such that $e\,d\equiv1\pmod{\lambda(N)}$, where $\lambda$ is Carmichael's function. That includes any $d$ such that $e\,d\equiv1\pmod{\varphi(N)}$, where $\varphi$ is Euler's totient.

With the factorization of $N$ into primes $p$, $q$, $r$, $s$ known and under the assumption that these 4 primes are distinct, computing a valid $d$ can be done as
$$d\gets e^{-1}\bmod\operatorname{lcm}(p-1,q-1,r-1,s-1)$$
or
$$d\gets e^{-1}\bmod\bigl((p-1)\,(q-1)\,(r-1)\,(s-1)\bigr)$$

If some of the primes are equal, we need to use more general expressions of $\lambda(N)$ or $\varphi(N)$. The simplest might be that $\varphi(N)$ is the product of factors of $N$ with the first occurrence of a unique prime replaced by one less than this prime. For example, if $p=q$ and $r=s$ and $p\ne r$, we can use
$$d\gets e^{-1}\bmod\bigl((p-1)\,q\,(r-1)\,s\bigr)$$

Also, be aware that the function $x\mapsto x^e\bmod N$ no longer is a bijection over $\Bbb Z_n$; in other words, some rare ciphertexts can correspond to multiple plaintexts. That affects plaintexts that are non-zero multiples of a prime present two times in the factorization.

For example, with

$N=67\times71^2\times73=24655531$,
$\varphi(N)=66\times70\times71\times72=23617440$,
$e=13$,
$d=10900357$, but we have the problem that
$71^e\bmod N$ and $3125420^e\bmod N$ both are $6603710$.

Note: the rationale of using multi-prime RSA is to obtain speedups that require not using $d$; but using $d$ will work anyway, only slower.


Indistinguishability versus semantic security? I found some foundations of crypto course notes that mention that these two are equivalent statements of their own degrees of security and was given the following definitions:

I was always under the impression that the second definition (the one on the bottom) was the prescribed one for Semantic Security, and that computational indistinguishability was a completely separate thing? I do not understand the necessity or intuition behind the need for a "simulator" as it is called. Can someone shed some light?

The definition of semantic security has its origins in the definition of perfect security, where the adversary's information about the message is the same after seeing the ciphertext. Semantic security is exactly the same thing in a computational setting: the adversary's "practically available" information about the message is the same after seeing the ciphertext.

This is formalised by simplifying the problem: the adversary chooses an "interesting" predicate $f$ on the message space and a way to choose messages such that the predicate holds with probability $1/2$. Then we must prove that the adversary cannot determine the value of the predicate with probability significantly different from $1/2$. (You can define a variant of perfect security in exactly the same way.)

Then it turns out that there is a simpler notion - indistinguishability - that is equivalent to semantic security. This notion is easier to work with, so everyone uses that one, to the extent that semantic security is often identified with indistinguishability.


Hill cipher concepts I have some questions about the Hill cipher.

There is a rule for key K:
Determinant of matrix and number of characters of the alphabet must be coprime. What does this rule say? Why it must be like this? So If I had determinant 5 and characters 30, it would not work?

Let's assume I have key K which should be 3x3. I would get the key: ENCRYPT. I would create trigrams like ENC RYP T?? - now the last trigraph is missing two characters. Should this input key be REFUSED by application for example or should I fill it with some values like #?(# alphabet must contain this char). Or how should the application behave when this happens?

Let's assume I have plain text T which is: textabcd - again the same question (as 2.). I have TEX TAB CD? - (should I again insert something in that empty space (?) (for instance #) ?

Should HILL cipher accept MATRICES (input as matrices) or as alphabet key like ABCD?

The Hill Cipher as one of the classical cipher is invented by Lester S. Hill in 1929. It is the first polygraphic cipher that can operate more than one letter at a time.

There is a rule for key K:  Determinant of matrix and number of characters of the alphabet must be coprime. What does this rule say? Why
it must be like this? So If I had determinant 5 and characters 30, it
would not work?

In the Hill cipher, there is an invertible matrix for the key $K$ of size $n\times n$, and the plaintexts $m_i$'s are row vectors of size $n$.
The encryption of a block $m$ is performed by $c = m K$ and the encryption of the message can be considered mathematically take $c = m K$. For decryption, multiply both sides with $K^{-1}$ and get $cK^{-1} = m K K^{-1}$ and $cK^{-1} = m I$. That is the inverse of a matrix and it is a well-known property that to be invertible a matrix must have of square size and have a non-zero determinant.
If the determinant has common factors with the alphabet size then it will not have inverse since invertible matrixes must have invertible determinants. This is due to fact that we are in the composite modulus. In this case, choose a new uniform random key or choose a prime alphabet.

Let's assume I have key K which should be 3x3. I would get the key: ENCRYPT. I would create trigrams like ENC RYP T?? - now the last
trigraph is missing two characters. Should this input key be REFUSED
by application for example or should I fill it with some values like
#?(# alphabet must contain this char). Or how should the application behave when this happens?
Let's assume I have plain text T which is: textabcd - again the same question (as 2.). I have TEX TAB CD? - (should I again insert
something in that empty space (?) (for instance #) ?

In modern Cryptography, we call it padding and the classical era has padding also. I'm not aware that Hill proposed any padding.
Fixed padding can cause serious problems with the Hill cipher since it hasn't got known-plaintext attack security. Putting X or any fixed character can cause information leak about the key.
Wikipedia states it very well. The messages are starting end ending with predictable ways, like my dear ambassador, Weather report, Sincerely your From .. To in the military, etc. Context can change according to the target. Therefore we need randomized padding in the beginning and at the end. This can cause confusion, too. The better one may use nonsense letters for this aim.

Should HILL cipher accept MATRICES (input as matrices) or as alphabet key like ABCD?

If I've understood this part correctly; first, the messages are encoded into row vectors of numbers by using the alphabet then multiplied with the key matrix $K$. The key matrix is also a number matrix, not a character. We operate on the numbers then decode the information back to character.

Little proof of the claim that the determinant must have relatively prime to $n$. When $n$ is a prime it is clear that we are in a field and the determinant must be non-zero by the Invertible Matrix Theorem
The theorem also gives the general case for this as;

In general, a square matrix over a commutative ring is invertible if and only if its determinant is a unit in that ring.

The units are invertible elements. For a given $u$, if $\gcd(u,n)=1$ then it has an inverse, therefore it is a unit. The converse is also true that for a given unit the $\gcd(u,n)=1$ must hold. We can see it form that $u x \equiv 1 \pmod n$ then we can form the bezout's identity $ux+bn=1$ then we can conclude that they are relatively prime.
Or directly; if $ax\equiv 1 \pmod n$, then there is a $k$ such that $ax=bk+1$, equivalently $ax−bz=1.$ If $d=\gcd(a,b)$, then $d|a$ and $d|b$, so $d|ax−bz=1$. We can conclude that $d=1$.


Is there a group of prime order which could fit the CT-Computational Diffie-Hellman assumption? I'm trying to choose a group that is hard under the Chosen-Target Computational Diffie-Hellman assumption, according to the definition in this paper, in order to implement the oblivious transfer scheme defined in the top box on page 10(=406).
The (intimidating, to me) CT-CDH assumption is defined as follows (page 7=403):

Let $\mathbb{G}_q$ be a group of prime order $q$, $g$ be a generator of $\mathbb{G}_q$, $x\in \mathbb{Z}^*_q$. Let $H_1 : \{0, 1\}^∗ \rightarrow \mathbb{G}_q$ be a cryptographic hash function. The adversary $A$ is given input $(q, g, g^x, H_1)$ and two oracles: target oracle $TG(\cdot)$ that returns a random element $w_i \in \mathbb{G}_q$ at the $i$-th query and helper oracle $HG(\cdot)$ that returns $(\cdot)^x$. Let $q_T$ and $q_H$ be the number of queries $A$ made to the target oracle and helper oracle respectively.
Assumption: The probability that $A$ outputs $k$ pairs $((v_1, j_1), (v_2, j_2), \dots, (v_k, j_k))$, where $v_i = (w_{j_i})^x$ for $i \in \{1, 2, \dots , k\}$, $q_H \lt k \leq q_T$, is negligible.

It should be noted that this assumption is equivalent to the standard Computational Diffie-Hellman assumption when $q_T=1$, according to this paper.
Can anyone give an example of a group that fits the bill? I tried $\mathbb{Z}^*_q$ for a prime $q$ under multiplication, but that's of order $q-1$, which is clearly not prime. However, the complexity analysis on page 12 of the paper is in terms of modular exponentiations.
Additionally (I can make a new question for this, if scolded), how would one implement the $(D_j)^{a_j^{-1}}$ operation in step 5 of the protocol? I can't figure out if it's equivalent to the discrete log problem.

The usual technique for having a group of prime size $q$ is to work modulo a prime $p$ such that $q$ divides $p-1$. The target group is then the subgroup of $q$-th roots of $1$ in $\mathbb{Z}_p$. To build such a group, first choose $q$, then selects random values $r$ until you find one such that $p = qr+1$ is prime. This is the way it is defined in the DSA standard.

The remaining part is: how to build $H_1$, the hash function which produces elements in the target group ? For that, you first use a hash function which produces values modulo $p$ (e.g. you use a PRNG seeded with the hashed data, and produce bit sequences of the size of $p$ until you find one which is between $0$ and $p-1$); then, you raised that value to the power $(p-1)/q$. The result is necessarily a $q$-th root of 1, and the whole is a "hash function".

As far as I know, such a group would fulfill the CT-CDH assumption -- i.e. there is no known way to break it. CT-CDH is a "weaker" assumption than standard CDH, but there is no proof that it is strictly weaker.

For your additional question: $R$ knows the $a_j$, which are random non-zero integers modulo $q$. $R$ can thus compute each $a_j^{-1}$ modulo $q$ (that's regular modular inversion). In the expression "$(D_j)^{a_j^{-1}}$, $D_j$ is part of a group of size $q$, so any exponent can be taken modulo $q$.


RSA private key integrity check I am working on a device whose OS provides an RSA Private primitive, where the inputs are the message, and the usual components of a private key. Unfortunately it is bugged so that in some cases of supplying garbage for the private key, the device panics instead of returning an error code.

To try and avoid panics I would like to perform some pre-checks on the private key components. However, due to limited device resources, I'd prefer not to install a full Bignum library.

Are there any simple calculations I can do on the key components to check the key is valid?  Time-efficiency is not a problem.

For example I can do peasant multiplication to verify $n = pq$; but what about validating $d_P$, $d_Q$, $q_{\mathrm{inv}}$ and $d$ ?

Mathematical checks of the consistency of an RSA key can include:
$$\begin{align*}
e&\text{ odd}\\
n&\text{ odd, and of prescribed bit size (if any)}\\
p&\text{ odd, and of prescribed bit size (if any)}\\
q&\text{ odd, and of prescribed bit size (if any)}\\
n&=p\cdot q\\
1&=(d_p\cdot e)\bmod(p-1)\\
1&=(d_q\cdot e)\bmod(q-1)\\
1&=(q\cdot q_\text{inv})\bmod p\\
d_p&<p-1\;\text{ [redundant with }d_p=d\bmod(p-1)\text{ ]}\\
d_q&<q-1\;\text{ [redundant with }d_q=d\bmod(q-1)\text{ ]}\\
q_\text{inv}&<p\\
d_p&=d\bmod(p-1)\\
d_q&=d\bmod(q-1)\\
\end{align*}$$
All parameters must be non-negative. In the above, $\bmod$ is akin to the %operator in C or java, extended to large integers. The upper range checks for $d_p$ and $d_q$ (and to some degree $q_\text{inv}$) are not mathematically indispensable, but are very customary and simplify the check of $d$, hence are included.

As pointed out by Maarten Bodewes, a primality check of $p$ and $q$ could also be performed; that will catch most random errors on these parameters. This will involve operations on large numbers though. And, chances that an accidental modification of the private key cause $p$ or $q$ to become composite while passing all the above checks is low.

In addition, some devices have extra requirements or/and perform extra checks that are not mathematically necessary. When not met, this could cause the observed device panic; in that case it would be a good idea to identify these requirements/checks, and externally check that they are met. Here is a list, believed exhaustive for industry-standard devices/libraries that I have happened to meet:

$d<n$, or perhaps the stronger $d<(p-1)(q-1)$, or the even stronger $d<(p-1)(q-1)/\gcd(p-1,q-1)$; that later one might be gaining traction since it is in FIPS 186-4, Appendix B.3.1 additional requirement 3(a) (at least for key generation).
$2^{2k-1}<n<2^{2k}$ for some specified values of $k$ (like $k\ge512$ with $k$ multiple of $2^w$ for some $w\ge7$, as in ANSI X9.31:1998; I have also seen lower minimum $k$, and lower $w$ down to 3); FIPS 186-4 requires $2k\in\{1024,2048,3072\}$ (at least for key generation).
If the above applies, that $2^{k-1}<p<2^k$ or the stronger $2^{k-1/2}<p<2^k$ (same bounds for $q$); FIPS 186-4 specifies the later, stronger bounds (at least for key generation).
That $|p-q|$ is above some threshold; FIPS 186-4 uses $2^{k-100}$. Notice that proper random generation of $p$ and $q$ makes this overwhelmingly probable, so much that this check is often (safely) skipped at key generation.
$e$ less than some threshold, like $2^{32}$ in an old Windows cryptoAPI, or $2^{256}$ in FIPS 186-4, or $n$ (that one is commonly specified), or $2^{2k}$ with $k$ as above.
$e\ge3$ (necessary for security), or $e\ge2^{16}+1$ (helping towards security of some variants of RSA with questionable padding), or $e=2^{16}+1$ (the most common value), or $e=3$ (the value leading to the simplest and fastest implementation of the public-key function, and believed safe for proper RSA padding).
I've seen code that requires some special condition on the high order bits of $n$ or/and $p$ and/or $q$ for reliable estimation of quotient in some modular reduction; or have other odd requirements on the public modulus; if that's not well documented, that's a bug.
I've once seen an implementation with a tendency to fail for large values of $q_\text{inv}$, and wondered if forcing $p<q$, or vice versa, would prevent that failure (note that exchanging $p$ and $q$ changes $q_\text{inv}$, though).

Various conditions beyond being prime are often specified for $p$ (and similarly $q$) at key generation; like, $p-1$ or/and $p+1$ having a large prime factor (a requirement in FIPS 186-4 for 1024-bit $n$); but I have never seen that checked after key generation (and such check would be uneasy). Similarly, I have seen requirements for a minimal value of $d$, but have never seen that enforced after key generation.

Note: it is rarely made actual use of both $d$ and $(p,q,d_p,d_q,q_\text{inv})$ for the same private key; sometime things will work without $d$, or with only $(n,e,d)$; that would simplify external checks.

A check that $n=p\cdot q$ can be conveniently performed modulo one auxiliary modulus $r$ (or a few relatively coprime moduli). We compute $\widehat n=n\bmod r$, $\widehat p=p\bmod r$, $\widehat q=q\bmod r$, and check that $\widehat n=(\widehat p\cdot\widehat q)\bmod r$. Convenient values of $r$ are $2^{32}-1$ (because modular reduction is easy; like casting out nines, only in base $2^{32}$ rather than base 10), and $2^{32}$ (which operates only on the low-order 32 bits of $n$, $p$, $q$; and thus should not be the only $r$ used for a check). As a consequence of the Chinese Remainder Theorem, these heuristic checks modulo $r$ become a proof if enough $r$ are used that the Least Common Multiple of all the $r$ is at least $n$.

An equivalent shortcut for operations involving $\bmod$ with a large right-hand operator is much more complex. It seems to involve computing the quotient. Assuming $e$ is less than 32-bit, to check that $1=(d_p\cdot e)\bmod(p-1)$ we might compute $x=\lfloor(d_p\cdot e)/p-0.05\rfloor$ using 64-bit floating point ($x$ will be less than $e$, thus fit 32 bits, and most often the correct quotient), then check that $x\cdot(p-1)+1=d_p\cdot e$ using reduction modulo a small $r$ (or a few ones), as above; if that check fails, we increase $x$ by one (always finding the right quotient if $d_p$, $e$ and $p$ are consistent), then repeat the check. But when the quotient gets large, basically we need full blown bignum arithmetic.

CAUTION: beware that most of the above checks (except those manipulating only $n$ and/or $e$) manipulate secret material, and thus can be vulnerable to side-channel attacks. These checks must be done in a safe environment (or protected against side channels such as timing or power analysis, which is complex).


What does the probability subscript mean in Shannon's secrecy definition? Shannon's secrecy can be defined as:

$$P_M (M=m) = P_{SK,M}(M=m|E(SK,m)=c)$$

What does $P_M$ means? (same question for $P_{SK,M}$)

I know that is the probability space M, M being the messages; I do not really understand why that has to be specified - or in general I don't understand what this means.

This is standard notation in information theory but it is redundant as given here, usually it is used as below.

For example
$P_M(m)$ would be used instead of $P_M(M=m)$ both of which refer to the random variable $M$ and the probability that it equals $m$.

$P_{M,X}(M=m,X=x)=P_{M,X}(m,x)$ would refer to a joint distribution in the same way.


Achieving non-linearity in a block cipher using only, rotations, shifts, AND, OR, and XOR It is supposedly difficult to introduce enough non-linearity in block ciphers based on modular addition, data-independent bitwise rotations, and XOR to make them secure against certain kinds of cryptanalysis even though addition is used because it introduces non-linearity into the design that XOR does not have. But what if we also use bitwise AND, bitwise OR, and bitwise shifts (a left bitwise shift fills a fixed-length bit string with zeroes on its left-hand side)? And let's toss modular addition into the flames since that actually does not run in constant time on some processors.

I figure that bitwise AND and bitwise OR can be used to introduce more non-linearity than modular addition. Additionally, though I'm not familiar with the details rotational cryptanalysis, I figured that bitwise shifts can help to thwart it since the for some inputs, the outputs of a function using rotations might be made equal with a rotation applied to one of them. Bitwise shifts would not suffer from this problem. As an example, consider that for inputs $x_0 = 0101$ and $x_1 = 1010$ the function $f(x) = (x \ggg 1) \oplus x$ will return $111$ in both instances. But, if $f(x) = (x \gg 1) \oplus x$, then the outputs will be $0111$ and $1111$, respectively.

The brief answer is: Yes, you can!

You may wish to study NORX, an AEAD scheme submitted to the CAESAR competition, whose essential thesis is that you can simultaneously attain high security, high software performance, and high hardware performance by the same design principles as ARX, but replacing $a + b$, which is slow in hardware, by the approximation $a \oplus b \oplus (a \wedge b) \ll 1$.


Pollard's Lambda algorithm ecdlp with Pohlig Hellman I'm trying to solve the ECDLP problem given an elliptic curve defined over a prime field. This prime is large (about 256 bits).

I managed to factor the order of the curve, and most of the prime factors were smooth, but two of the factors weren't, they were about 80 bits each. I'm given two points $P$ and $Q$, and $Q = nP$, so the goal is to find $n$.

So the order has some smooth factors and some not so smooth factors, so I tried to apply pollard rho to the semi-large primes but that's still a $O(\sqrt{2^{80}})$ complexity, which I think will take too long.

I started looking at Pollard's lambda algorithm. I'm not given a bound on $n$, but I was given an upper bound on $n$, so I know that $n < U$, $U$ was about $b$ bits, could I use with pollard's lambda algorithm (or pollard's rho algorithm) so it's more efficient than $O(\sqrt{2^{80}})$

So is it possible pollard's lambda with the pohlig-hellman algorithm, or is the a better attack to use if I know a number $U$ so that $n < U$ and $Q = nP$.

If the question is "can I solve the ECDLP by combining Pohlig-Hellman and Pollard's lambda", then the answer is yes, provided your $p-1$ is smooth enough.

First off, as mentioned in the comments, a search interval of $[0, 2^{40}]$ is quite doable with Pollard's lambda.

Factorize $p-1$ to get all the $B$-smooth prime factors; let's say there are $k$ of them, the ${r_k}$. Then run Pohlig-Hellman on each of them and obtain the secret key mod $r = \prod_i^kr_i$. If the order of your base point on your curve is $Q$, then your search interval looks like $[0, Q/r]$. So $Q/r$ puts the bounds on how long you would expect the lambda algorithm to find a collision.

What's a good $B$ for smoothness? Now this is implementation-dependent, so that depends on what you're working with and how long you have to wait. In practice, I found that if you factorize $p-1$ up to about $2^{20}$, and you have a few primes of that size, and the order of your base point is much smaller than $p-1$, that cuts $Q/r$ down to a reasonable size, but of course your experience may differ.


Could a collection of data be engineered to encrypt predictably using standard encryption algorithms? Thinking about the rather new problem of Cryptolocker and other crypto-randomware, huge amounts of damage are being caused by malicious actors simply using modern encryption algorithms to encrypt a drive. But this presents an interesting question, and the hint of a possible solution:

Could a collection of data be engineered such that when it is encrypted using a given encryption algorithm, say RSA, patterns in the encryption reveal details that could be used to discover the keys, or at least greatly narrow the search space?

What you're describing is a chosen-plaintext attack.  In this scenario the attacker (you, in this case) creates a specific plaintext for the cryptosystem to encrypt, in an attempt to manipulate it in specific way...In your scenario, to get it to give up information about the key.   Chosen plaintext attacks should not be possible in a semantically secure cryptosystem.  If they are possible, the system is broken, and should not be used.

So, to directly answer your question, no, this should not be possible, and certainly is not generically possible.   There may be specific implementations of crypto-ransomware that are flawed in a way that would make this possible, but you would have to specifically target an attack for that specific system, and it would be useless against any other, including another system flawed in even a slightly different way.


DH Key exchange attack: bad choice of g In the group $\mathbb{F}_p^*$, Bob reads Alice's parameters as $p=234917$ and $g=281$ and uses a secret key $b < 400$ such that $h_b = g^b = 92646$.

Note that $p-1 = 2^2\cdot 11\cdot19\cdot281$

$281^{2\cdot11\cdot19\cdot281} \equiv 1 \mod 234917$

and that

$19452^{281} \equiv 1 \mod 234917$

Find $b$.

281 is too large for the Pohlig-Hellman attack by hand (which is how this question is supposed to be solved). I feel like the answer is staring me in the face but I cannot see it. Can anyone give a hint/help me? Basically we have $2\cdot(\text{order of g}) = p-1$...

I have solved the question by carrying out the Pohlig-Hellman attack for the smaller prime factors and finding that $b \equiv 3 \mod 11$ and $b \equiv 6 \mod 19$, then finding all the integers $< 400$ satisfying this and testing them. The answer is $b=234$.

I am still interested in if anyone has a solution which usesthe order of $g$ though.


Break large exponent calculation into smaller calculations? I am implementing SRP on an embedded platform. It has crypto acceleration and I am using its built in modular exponentiation function, however it doesn't seem to be able to handle an exponent over 32 bytes long. I have an exponent i need to use which is 64 bytes long.

Is there a way to break this exponentiation into smaller exponentiations that the modular exponentiation function can handle?

One method uses the factorisation the exponent: If $a=bc$ then $x^a \equiv x^{bc}\equiv (x^b)^c \mod m,$
i.e. first compute $y=x^b\mod  m$ and then $y^c \mod m$.

This method will work,  if the largest factor of the exponent has at most 32 bytes.

Otherwise you can always use the square-and-multiply exponentitation
method (see https://en.wikipedia.org/wiki/Modular_exponentiation or https://en.wikipedia.org/wiki/Modular_exponentiation or  https://en.wikipedia.org/wiki/Exponentiation_by_squaring)
looping over the single bits of the exponent.


How to prove that an integer is hard to factorize when sampled from a known distribution Suppose that an $n$-bit integer $c$ has been randomly drawn from a distribution $\chi$, whose description is known. Is there a general method to check if this particular sampling helps factorize $n$? Are there any results in this direction (i.e. results like "don't choose an RSA modulus whose factors were sampled with this or that distribution")?

On trail to follow, from Handbook of Applied Cryptography fact 3.7:

Let $n$ be chosen uniformly at random form the interval $[1, x]$.

if $1/2 \leq \alpha \leq 1$, then the probability that the largest prime factor of $n$ is $\leq x^{\alpha}$ is approximately $1+ ln(\alpha)$. Thus, for example, the probability than $n$ has a prime factor $> \sqrt(x)$ is $ln(2) \approx 0.69$
The probability that the second-largest prime factor of $n$ is $\leq x^{0.2117}$ is about $1/2$.
The expected total number of prime factors of $n$ is $ln ln x + \mathbb{O}(1)$. (If $n = \prod p_i^{e_i}$, the total number of prime factors of n is $\sum e_i$.)


How to find the time complexity of modular multiplication? There are two number of length m bits. How do I prove that the complexity of modular multiplication of these two numbers is $O(m^2)$.

Hello, welcome to crypto.SE.

This is not cryptography, but I will answer it with a simplified example to give you the intuition. Lets consider $123 \times 456$.

    123
  x 456
  -----
    738
   615
+ 492
-------
  56088

Right ?

How did you get $738$? Obviously you did $6 \times 3 + 6 \times 20 + 6 \times 1$. Therefore you made 3 multiplications.
Should the first number be $m$ long, you would have had $m$ multiplications.
Because the second number is also $m$ long, you would have to do this $m$ times hence the $O(m^2)$.

From the Handbook of APPLIED CRYPTOGRAPHY, page 71

  Let $n$ be q positive integer. As before, the elements of $Z_n$
  will be represented by the integers $\{0,1,2 ..., n-1 \}$.

  Observe that if $a,b \in Z_n$, then
  $$(a+b)\mod n = \begin{cases}a+b, &\text{if}\ a + b < n\\
a+b-n &\text{if}\ a + b \ge n\\ \end{cases}$$

Note that in term of bit complexity we are in $log(n)$

  Hence modular addition (and subtraction) can be performed without the need of a long division. Modular multiplication of $a$ and $b$ may be accomplished by simply multiplying $a$ and $b$ as integers, and then taking the remainder of the result after division by $n$.

Without any optimizations, note that taking the reminder is just applying at most $m$ subtraction of $m$.
Hence a modular multiplication is at most $2 \times m^2$ operations therefore $O(m^2)$ (and bitwise complexity $O(log^2(m))$).


would this be classed as a cipher text attack? Say i'm given a cipher text to decrypt, however i also have access to a server that performed the encryption; where i could enter
any plaintext and observe the result of encryption.
 would it be classed as a known plain text attack or cipher text? I'm abit confused

Neither, as you've described the prerequisites or - in a theoretical model - the setting for an attack to take place, but not the attack itself.

What you seem to have is a ciphertext oracle which can be used within a Chosen Plaintext Attack (CPA). As you can "enter any plaintext" I presume you can investigate the results and the request encryption of another plaintext from the oracle. If you can use this to attack the cipher then it is known as an Adaptive Plaintext Attack.

If the cipher resists such attacks and the ciphertext doesn't give you any information about the key (or any other unkonwn plaintext) then the cipher is IND-CPA2 secure.


Message signature using RSA in my textbook it is stated, that if we have a message, it's signature using RSA and modulo, we can also sign the inverse of the message.

However, it is not explained why can we do so.

Could someone explain to me the reasoning?

Let the modulus is $n$, the message $1< m < n$. In your textbook RSA the signature is $$s = m^{d} \bmod n,$$ where the $d$ is the private key.

Let the target signature be $s' = s^{-1} \bmod n$ and $m' = m^{-1}$

Let expand $s' = s^{-1} =  (m^{d})^{-1} = (m^{-1})^{d}$

Therefore $s'$ is the signature of $m'$.

That is one of the many other reasons that we never use textbook RSA in practice. We should you RSA-PSS or RSA-FDH for signatures.


SSTP MSCHAP-V2 Authentication before SSL or after SSL Session So with the recent news that there's a lovely new tool to crack MSChapV2 packets.

So the question I have is on a SSTP Connection is the MSChapv2 handshake encrypted pre SSL setup or post. Obviously if it was pre then packets could be stolen, if it was post then thats at least an additional layer of security.

I did ponder over whether this should be stack-overflow, server fault or cryptography. I think cryptography is the best place for it...

So the question I have is on a SSTP Connection is the MSChapv2 handshake encrypted pre SSL setup or post.

Post is the answer. Specifically, SSTP is basically SSL, with special body specific to a tunnelling protocol. You can read the full spec here, but it's a little dry. Essentially, your options are these:

Authenticate through SSL/TLS certificates as you would for any SSL-certificate authenticated site, then establish the wrapped tunnel protocol, authenticating as you go.
Go through the standard key negotiation with SSL, then authenticate over your choice of P2P tunnelling protocol, e.g. with MSCHAPv2. Doing this, your tunnel is already encrypted via the HTTPS part.

From the standard:

  Because SSTP runs by means of an HTTPS connection, SSTP relies entirely on HTTPS for the reliable
  delivery of its messages. The SSTP client MUST authenticate the SSTP server by using HTTPS
  authentication. The SSTP server MAY<1> authenticate the SSTP client by using HTTPS client
  authentication. The SSTP server SHOULD authenticate the SSTP client by using PPP authentication.
  Therefore, PPP authentication is required even when the SSTP server authenticates the SSTP client
  by using HTTPS authentication. For more information about PPP authentication, see [RFC1661]

The essential difference between SSTP and PPTP is the requirement to route TCP over TCP, needed to make this an SSL connection. This has a performance impact, since TCP packets are much less efficient to send and receive than UDP packets or GRE datagrams, the latter being how you'd typically set up a PPTP tunnel.


Other than an exponent greater than 1, what are the considerations when creating a random 256-bit private key using Diffie Hellman? Let's assume that I choose the bits for my 256-bit private key exponent by flipping a coin 256 times.

Are there any other issues, besides the randomness of the 256-bit private key to consider? For example, should the most significant bit always start with 1 in order to ensure a private key of a certain minimum size or is the probability of flipping enough leading zeros to make the exponent small enough to be dangerous statistically impossible or do you simply check the size of the exponent and if it doesn't reach a minimum threshold you choose a different random exponent?

Are there any other issues, besides the randomness of the 256-bit private key to consider?

Not really.  The DLog problem really doesn't have any 'weak keys', that is, keys that can be broken with less effort than other keys.

Now, you might say "hey, isn't the key '1' easier to break than others?"  Not really; you might consider '1' easy to break because $g^1$ is easy to recognize - however, for any fixed value $1000000$, the attacker could compute $g^{1000000}$, and check for that exact value - if the attacker sees that value, he knows the private key, and the probability of that happening is exactly the same as him recognizing $g^1$

  For example, should the most significant bit always start with 1 in order to ensure a private key of a certain minimum size

No - if you set the msbit, then the attacker can limit the space he is searching by that bit, and that may reduce his effort by a factor of $\sqrt{2}$

Now, if you look at X25519, they really do set an msbit; however not for cryptographical reasons.  Instead, the X25519 designer was afraid that an overly clever implementer might skip the leading '0's on the exponent, which would introduce a timing variation (and, in any case, the space reduction point I made above doesn't apply to X25519, because the bits that are variable already cover (almost) the entire subgroup, so setting that one bit doesn't really reduce the attacker's search space).

  is the probability of flipping enough leading zeros to make the exponent small enough to be dangerous statistically

The probability that the leading bits are 000...000 is exactly the same as the probability that they are 011...101 (that is, an arbitrary fixed bit pattern).  By selecting the exponents randomly, you maximize the number of private keys that are possible.


Keyed digest function with odds of collision below the birthday bound? I wonder if it is possible to devise a function $F(K,S,R_S)\mapsto D$ where:

$K$ is some key (I have freedom on $K$, it could even be generated by a trusted party);
$S$ is in $\{0,1\}^s$, say $s=32$; $S$ is a serial number;
$R_S$ is a random value associated to $S$, in $\{0,1\}^r$, say $16\le r\le48$; $R_S$ is produced from $S$ once for all by a random-like function unknown to adversaries;
$D$ is a short digest in $\{0,1\}^d$, say $48\le d\le64$.

such that:

$D=F(K,S,R_S)$ can be computed knowing $K$, $S$, $R_S$, say in at most $2^{28}$ instructions of a typical 32-bit CPU;
an adversary not knowing $K$, knowing $S$, $R_S$, $S'\ne S$, $R_{S'}$, has no advantage in trying to tell whether some $D$ is $F(K,S,R_S)$ or $F(K,S',R_{S'})$; Update: or better, an adversary with black box access to $(S,R_S)\mapsto F(K,S,R_S)$ for some fixed unknown $K$ can not distinguish that from a random oracle with the property laid below in (4);
an adversary knowing $K$, and given $D$ known to be $F(K,S,R_S)$ for $S$ chosen at random, with $S$ and the corresponding $R_S$ unknown, has no method much better than brute force to guess $S$ [where brute force enumerates possible ($S$, $R_S$) pairs, computes $F(K,S,R_S)$, and makes a decision based on matches of that with $D$];
odds that there exists distinct $S$, $S'$ with $F(K,S,R_S)=F(K,S',R_{S'})$ should be as low as possible, and much lower than the birthday bound (about $0.39$ when $7\le d=2s$).

The application is transforming the serial number $S$, and some auxiliary data which limited entropy after hashing is modeled by $R_S$, into a digest that is meaningless to a party not knowing $K$ (property 2), does not directly leak the serial number $S$ to a party knowing $K$ (property 3), and can reliably be used to recognize an object for a given $K$ (property 4). The computation of $F$ will be made as slow as bearable, which will correspondingly increase the cost of brute force in (3).

Things I considered but do not fit:

If $F$ is $H(K||S||R_S)$ with $H$ a random function with $d$-bit output, (4) is not met.

If $F$ is $\operatorname{ENC}_K(S||H(K||R_S))$ with $\operatorname{ENC}_K$ a $d$-bit block cipher with key $K$, and $H$ a random function with $d-s$-bit output, (4) is met with zero odds of collision, but (3) is not met, for an adversary can invert the cipher and find $S$.

If $D$ was wide enough (say $d=2048$), then instead of $\operatorname{ENC}_K$ in the above we could use a deterministic RSA encryption with public keys $K$ generated by a trusted party, and meet both (3) and (4); but I'm considering much smaller $d$.

Quite a difficult question. What you seem to need is a one-way permutation $P$. Indeed, suppose you have it of width $d$, then consider the function
$$
F(K,S,R_S) = E_{K_2}(P(E_{K_1}(S,R_S))),
$$
where $E$ is any good 64-bit block cipher (say, Simon) and $K_1,K_2$ are derived from $K$.  This function $F$ should fulfill (2) because of the encryptions of both sides and (4) because it is a permutation. To satisfy (1) and (3) the permutation $P$ must be moderately easy to compute and difficult to invert.

It is quite hard to construct such permutations on so small domains as 48-64 bits. There are so called trapdoor permutations, which are easily invertible given a secret $K'$. However, this secret can probably be found very quickly in this domain, whether we talk about RSA or HFE.

I would consider algebraic constructions. There are some interesting permutations that have a compact description but no trapdoors, hence usually overlooked by cryptographers. For instance, how about
$$
\left(X^{2^k}+X+a\right)^{s}+X
$$
 over  $\mathbb{F}_{2^n}$ from a 2010 paper? Here $a$ is a field element, and $s,k$ are integers; restrictions on them are given in the paper. Even though I am not aware of any inversion algorithm, some generic methods like Groebner basis algorithms may find a preimage faster than $2^n$. In this case, if the permutation is fast enough, you may iterate it several times as long as you still conform to property (1).


Serpent cipher : Osvik S-Boxes confusion and test vectors I'm having hard time with the implementation of the S-Boxes by Osvik found in this paper: Speeding up Serpent. At the end of the paper, all the s-boxes are given and then, I just implement them. Here's my implementation of $S_0$ as an example :

UInt32Vector Serpent::S0(const UInt32Vector &Y)
{
   UInt32Vector X = Y;
   X[3] ^= X[0]; uint32_t X4 = X[1];
   X[1] &= X[3]; X4 ^= X[2];
   X[1] ^= X[0]; X[0] |= X[3];
   X[0] ^= X4;   X4 ^= X[3];
   X[3] ^= X[2]; X[2] |= X[1];
   X[2] ^= X4;   X4 = ~X4;
   X4 |= X[1];   X[1] ^= X[3];
   X[1] ^= X4;   X[3] |= X[0];
   X[1] ^= X[3]; X4 ^= X[3];

   return {X[1], X4, X[2], X[0]};
}

As you can see, this is exactly the $S_0$ from the paper. I have to precise that I checked my s-boxes 3 times to be sure there are the same as the one in the paper. Now, here's how I use $S_i$ for $i=0,\ldots,7$ :

subkeys.push_back(S[k & 7]({W[j], W[j+1], W[j+2], W[j+3]}));

where $k = 3$ and decreasing by 1 as it is mentioned in the algorithm specification.

What's confusing me is the Osvik implementation of his s-boxes compared to the ones described in his paper. This seems to be different. Moreover, in his key schedule, $i = 3$ is increasing instead of decreasing.

Now, here's my questions :

Where can I find test vectors to test my s-boxes ? I found one for the key schedule in Floppy 4 (ecb_iv.txt) from the full submission package, but nothing about the s-boxes.
Why his s-boxes implementation are different than the ones in his paper ?
Are my $S_0$ implementation and usage corrects with what I gave or did I miss something important ?

Thanks a lot for your helps.

To answer your questions in order:

You won't find test vectors for the s-boxes in the submission - the
s-box functions are implementation specific optimisations,
especially the bit-sliced s-box functions like the Osvik and Gladman/Simpson, which actually compute multiple s-box lookups in parallel.
If you need to test your s-box implementations, I would take the s-box functions from the implementation you're trying to replicate and generate test vectors yourself in isolation.
The difference in the s-boxes between the paper and the C source file is explained on the homepage of those two resources: "...Since then I have made further algorithm improvements, and results optimized for 3-way parallel execution are used in my implementation...".
It looks like Osvik did further searching and testing and came up with better (for x86/x64 architecture probably) s-box functions after publishing the initial functions.
I can't see anything obviously wrong with your approach, but I would recommend picking one of the implementations to compare to and generate some test vectors directly from the s-box functions to be certain.
This is the approach I was planning to use to integrate the Osvik s-box functions into a library that currently uses the Gladman/Simpson ones - I'm glad you pointed out the inconsistency in the paper/source.


Why use indexing for searchable encryption? Searchable encryption can be separated into sequential scan and indexing. Besides increasing search speed, why do we use indexing in searchable encryption?

As an end-user, we do not usually make a keyword list of our document. So, if we don't build an index for our document, is there a method to do searchable encryption (which considers the full text)?

It is mainly to make the search operation more efficient. In searchable encryption, mostly invert index is used. It is a data structure that stores mapping from words to documents or set of documents i.e. directs you from word to document, e.g. something like:

word 1: {doc1, doc2, doc3}
word 2: {doc1, doc3}
word 2: {doc1}

The earliest searchable encryption scheme searches data by sequentially scanning through all encrypted documents. This is not scalable. For example, if you have 10 document and each has 10,000 words in it, then you need to scan through 100,000 encrypted words. For each encrypted word, the comparison operation is cryptographic and is slow (compared to that in plaintext). If you have a large amount of data, you probably will get your results hours later after you submitted your query.
However, the number of distinct words in the documents probably is not very big (say 5,000), and does not increase with the amount of your data. Therefore, using indexes is a natural choice because now you only need to search through the index, and perform comparison operation in the number of distinct words (or even less) to find which entry in the index corresponds to your query, and then you can find the list of documents that contain the word you queried by retrieving and decrypting the list (this part requires additional cryptographic operations, with the number linear in the size of the list). But anyway, this is more scalable and allows searchable encryption to handle very large datasets.
Nowadays, mainstream searchable encryption schemes all use some sort of indexes. Of course, the index structure and cryptographic comparison operation vary greatly from scheme to scheme, but the core idea is to make the search time sublinear in the size of encrypted data.


Can you have perfect secrecy with countable message/key spaces by dropping countable additivity? This classic paper by Chor and Kushilevitz shows that if the key space and the message space are both countably infinite, then it is impossible to have a perfectly secure private-key encryption scheme.  Their proof relies on the fact there exists no uniform probability measure on the set of natural numbers, which in turn relies on the fact that probability measures are countably additive.
But there’s a generalized notion of measure that only requires finite additivity and not countable additivity.  In particular this paper talks about how the asymptotic density of a set of natural numbers constitutes a finitely additive probability measure that is “uniform” in the sense of translation invariance.
I’m wondering whether that could be used to recover some notion of perfect security.  So let the message space, key space, and ciphertext space all equal $\mathbb{N}$, let the family of measurable sets be the family $F$ of all subsets of $\mathbb{N}$ which have a well-defined asymptotic density, let the key be chosen using the asymptotic density measure, and let the adversary have some finitely additive probability measure $P$ over the message space.  Then my question is, does there exist an encryption scheme such that for all $X,Y\in F$ for which $P(C\in Y)\neq 0$, we have $P(M\in X | C\in Y) = P(M\in X)$? (Note that I’m using the same letter $P$ for bother he probability measure over the message space and the probability measure of the ciphertext.)
Of course dropping countable additivity may make this all unrealistic, but I’m just asking a theoretical question.

Let the key, message, and ciphertext spaces all be $\mathbb{Z}$, which is in bijection with $\mathbb N$. I'm going to pick a specific bijection by making the non-negative integers map to evens and the negative integers map to odds, and let $\mu$ be the asymptotic density measure applied to $\mathbb{Z}$ using this bijection. We can then construct a one-time pad by setting $c = m + k$. For any (possibly finitely-additive) probability measure $\mu_M$ chosen by the adversary on $m$, and any set $Y \in F$, $(\mu_M \times \mu)(\{(m, k) \in \mathbb Z^2 \mid m + k \in Y\}) = \mu(Y)$. That is, the resulting measure on the ciphertext is uniform, no matter what measure $m$ comes from. I am stating it this way so as to avoid the division inherent in the $P(m \in X | c \in Y)$ expression in your question.
Details: First, we need to show that $\mu$ is translation invariant on $\mathbb Z$. $\mu(A)$ could equivalently be defined as $\lim_{n \to \infty} \frac{A \cap [-n, n]}{2n + 1}$. To see that translation invariance holds, notice that $|[-n, n] \cap A|$ and $|[-n, n] \cap (A - x)|$ only differ by at most $2 x$, since $[-n, n]$ and $[-n + x, n + x]$ overlap everywhere except for $x$ points at either end. This becomes irrelevant in the limit as $n \to \infty$.
Next, we need to evaluate the product measure. Unfortunately product measures do not seem to be very well defined for finitely additive measures. I will pick one product measure, but in general it is not unique.
\begin{align*}
(\mu_M \times \mu)(\{(m, k) \in \mathbb Z^2 \mid m + k \in Y\})
&= \int_{\mathbb Z} \mu(\{k \in \mathbb Z \mid m + k \in Y\}) d\mu_M(m) \\
&= \int_{\mathbb Z} \mu(Y - m) d\mu_M(m) \\
&= \int_{\mathbb Z} \mu(Y) d\mu_M(m) \\
&= \mu(Y) \\
\end{align*}
Here we have used that $\mu$ is translation invariant on $\mathbb Z$ and that $\mu_M$ is a probability measure, so the integral (i.e., expected value) of a constant is that constant.
However, none of this is physically realizable, at least with a digital computer. Any way of generating a random key is going to give a distribution that has countable additivity, since it can always be broken down into discrete choices, with each outcome having paths leading to it with only have a finite number of choices. I don't think it is physically possible in general, but I have less justification for that.


How many bits in the resultant hash will change, if the x bits are changed in its the original input? I came across a question stating:

  We have a message consisting of 10,000 characters. After computing its message digest using SHA-1, we decide to change the last 19 characters in the original message. How many bits in the digest will change if it is recomputed, and why?

Until and unless this is an explicit attack on the hashing scheme, the new hash would be different than the original one (sort of exhibiting an avalanche effect).

But I am unable to understand how does small changes in the input text affect their corresponding hashes. Like does there exist a relationship on how many bits of the hash will be affected, if a certain change is done to the input text?

P.S.: I am not a 100% sure, but I believe I have read it somewhere that a hashing algorithm should change the bits of hash by $X$% if a new character/bit is added/substituted to the previous input text.

For any one of the SHA hashes, the hash should be indistinguishable from pseudo-random. That means each and every bit flips with a chance of 50%. So on average half of the amount of bits gets flipped, as long as the input message doesn't repeat (because that will match 100% with the hash of the identical message, of course). It doesn't matter how many input bits are removed, added or altered, this is always the case as long as the input message isn't identical to the previous one.

Hashes are likely well distributed, so the likely number of bits that get flipped is a bell curve like you would get by throwing dice. Same thing for the number of zero bits - or one bits of course. So you cannot give an absolute number as an answer to this question. The result is not a function on $x$ if $x$ is the number of bits flipped in the input - as long as $x$ is larger than zero.


Conjugate variables in Quantum Key Distribution? According to Heisenberg's Uncertainty Principle, it is impossible to measure the values of conjugate variables simultaneously as measuring one accurately would make the other equally corrupt.

So in QKD, there's a thing that states that Eve can't eavesdrop as the very act would change it's quantum state(Heisenberg's principle). I would like to know the measurement of which conjugate pair is being referred to here. Do answer fast as I'll need to do a seminar on this topic tomorrow :)

In the simple BB84 protocol, Alice prepares a state in either the Hadamard or the Standard basis. In order to measure Eve need to choose a basis to measure in. The problem for Eve is these two are two orthogonal basis or in a sense "Conjugate". This however is not the same as the conjugate variables you mention in your question.

Measuring in the one of the bases, collapses the state onto a vector in that basis. Measuring in an orthogonal basis would result in a truly random collapse onto a vector in this basis. Hence, no new information is gained about the original state. Thus Eve's choice of basis and the basis which Alice used to encode her bit in must match if Eve hopes to reliably learn Alice's bit.


How exactly are PRNG's used to encrypt material, and what makes one any more secure than the other? I hope my question isn't as lazy as the title indicates. What I want to ask is how people literally integrate a PRNG with encrypting material.

I wrote a silly little script in Python a while back that took a 9 digit seed, then produced a list of 'random' numbers using a linear congruential generator. That was cool and all, but when I tried to use that with my silly internet chat program (Also in python) I failed to see what use it had. Hey, I could match letters, symbols, and numbers to the various digits as a sort of substitution cipher, but that didn't seem really secure at all. If substitution was used every-time, then no generator would be better than the other

I googled for a bit about my question, but all the results didn't seem to go into any specifics about how one would use these randomly generated numbers to encrypt anything. Anyhow, I chose to give it a shot on Cypto, and am hoping someone can either point me to an answer so this can be closed, or equally, provide an explanation.

Well, first of, a linear congruential generator is not a secure pseudo random number generator at all, but if it's just about the basic understanding, we can ignore how you get that stream of random numbers for now.

So, but can you actually use this? The easiest approach is using the stream of random numbers in a stream cipher and just XOR each bit of the message with the according bit in the stream. For the actual implementation your RNG will provide a fixed number of bits and you need to keep track of how many bits you actually used. And then you transmit the result instead of the message itself.

On the other side you do the same.

An alternative would be to work on 8-bit symbols, and you just add the values together (modulo 256). Pseudo code:

Input: message as char array m[]
rng(): call to the RNG, returns an 8-bit integer array of length r.

j = 0
temp = rng()

for i from 0 to m.length:
  m[i] = (int(m[]) + temp[j]) % 256
  i++
  j++
  if (j > 255)
    j=0
    temp = rng()

Maybe this can be made more compact, but it should work for a toy project.


2 party AND computation under passive perfect security In the book written by Ivan Damagard titled "Secure Multiparty Computation and Secret Sharing", at the end of the third chapter he provides a proof for why it is impossible to securely compute 2 party AND function under perfect and passive security with one corrupt party.

Can someone help me provide an intuitive explanation for why the above is true. I was unable to grasp the solution provided by Damagard. I could not find any other resource regarding the same either.

The intuition behind the proof is as follows. Since the output of AND equals 0 when party P2 has input 0, then the transcript is distributed identically when P1 has input 0 and when P2 has input 1. Likewise, in the opposite direction. Thus, the set of possible transcripts when P1 has 1 and P2 has 0 equals the set of possible transcripts when both have 0, and the set of possible transcripts when P1 has 0 and P2 has 1 equals the set of possible transcripts when both have 0.

In the proof, they further show that the intersection of the set of transcripts as above is a subset of the set of transcripts when both parties have 1 (just by the definition of how the transcripts are defined).

As a result, the set of transcripts when both parties have 0 is a subset of the set of transcripts when both parties have 1.

The proof proceeds by arguing that the intersection between these sets of transcript actually has to be empty (since you can't output both 0 and 1). However, I actually think that the proof is already complete when they show that $T(1,0) \cap T(0,1) \subset T(1,1)$. In order to see this, let $t\in T(1,0)$; by what we have stated now it also follows that $t\in T(1,1)$. Since P1's output is determined by its input and transcript, it follows that it outputs the same bit in both cases. This contradicts correctness.

(I emailed with both Ivan Damgård and Jesper Nielsen on this; so thanks to them for them help.)


Trying to understand the struct HkdfLabel from tls1.3 RFC8446 I'm looking at RFC 8446 section 7.1 and trying to understand the following:
HKDF-Expand-Label(Secret, Label, Context, Length) =
            HKDF-Expand(Secret, HkdfLabel, Length)

       Where HkdfLabel is specified as:

       struct {
           uint16 length = Length;
           opaque label<7..255> = "tls13 " + Label;
           opaque context<0..255> = Context;
       } HkdfLabel;

       Derive-Secret(Secret, Label, Messages) =
            HKDF-Expand-Label(Secret, Label,
                              Transcript-Hash(Messages), Hash.length)

HkdfLabel appears to be a concatenation of a few fields, to make it "fit" into the signature of Hkdf.Expand(...).  A few things I'm unclear on:

Are the pieces that make up the struct of HkdfLabel expected to be concatenated in the order they're defined? e.g. length||label||context
length = the hash length in bytes?
the first 0..6 bits of label are not specified, assuming 0?
"tls13 " + Label may be more or less bits than 7..255 allows for the assignment to label.  Is the expectation that it's zeroes if not long enough, or truncated to 256 bits if too long?
same basic uncertainty around context, is the idea that context will always be exactly 256 bits?
Assuming the above is correct, does that mean HkdfLabel will always be exactly 528 bits?

HkdfLabel = hashLength<0..15>||label<0..255>||context<0..255>

Section 3 explains the data structures and their representation as octet strings (or byte strings: this RFC uses “octet” and “byte” interchangeably). See in particular §3.1:

Multiple-byte data items are concatenations of bytes, from left to right, from top to bottom.

An HkdfLabel is the concatenation of 2 bytes for length (big-endian, see §3.3), 7 to 255 bytes for label, and 0 to 255 bytes for context. §3.4 explains the notation <7..255> it means between 7 and 255 bytes inclusive. The length of the HkdfLabel can therefore be anywhere from 9 to 514 bytes.
The length field in the HkdfLabel returned by HKDF-Expand-Label is the value that was passed as the Length argument. When it's called from Derived-Secret, this is the length of the hash in bytes (not bits) (§7.1: “Hash.length is its output length in bytes”).
The first 6 bytes of label are 74 6c 73 31 33 20, the ASCII encoding of "tls 13" (§7.1: “The labels specified in this document are all ASCII strings”).
"tls13 " + Label is the concatenation of a 6-byte string with Label. Since the result must be at least 7 bytes long, this effectively forbids empty labels, which I can't find stated explicitly anywhere. There is no padding or truncation. Note that once again, these are lengths in bytes (octets), not bits. The label must also be at most 249 bytes long to fit.
Context can be anywhere from 0 to 255 bytes


Creating multiple independent keys for cascading - recommended approach? I would like to use cascading encryption with 3 algorithms in a similar fashion to Truecrypt, so for example:

Encrypted = AES( Twofish( Serpent(Secret, key1), key2), key3)

The aim of this is of course simple: if 1 algorithm is broken, the other(s) still provide security.

But what is the best approach to derive each key independent from each other, from the one passphrase? It was not obvious to me from TrueCrypt source how they did it, my websearches have failed, and understandably from that result it seems there are very few discussions so far on crypto stackexchange in regards to generating multiple independent keys.

I'm asking for suggestions, not making any recommendations, but in Applied Cryptography Bruce Schneier mentions how to derive an independent key that can be used to check if a key is valid, which if I'm understanding correctly is approximated as this:

KeyVerify  = Hash(password . salt)               // stored only for verifying but not used
RealKey    = Hash(KeyVerify . password . salt)   // actually used

Note: KeyVerify is independent from RealKey, but not vice versa

So I'm wondering if that approach might be of use, but I'm not confident how to extend it ... for example, something like this maybe?

RealKey2    = Hash(RealKey1 . password . salt) // for 2nd cipher
RealKey3    = Hash(RealKey2 . password . salt) // for 3rd cipher

Seeing as the KeyVerify/RealKey example shows a one-way line of independence, I'm guessing that the order the keys are used in is also a fundamental part of the solution.

$\newcommand{\concat}{\mathbin\Vert}$Use a key derivation function, such as HKDF, to expand a master password-derived key into subkeys for each cipher.

Compute $k = \operatorname{scrypt}(\mathit{password}, \dots)$.
Compute $k_\mathrm{AES} = \operatorname{HKDF}_k(\text{‘AES’})$.
Compute $k_\mathrm{Serpent} = \operatorname{HKDF}_k(\text{‘Serpent’})$.
Compute $k_\mathrm{Twofish} = \operatorname{HKDF}_k(\text{‘Twofish’})$.
Throw out Applied Cryptography and get Cryptography Engineering to replace it, but make sure to print out the unauthorized errata and glue them into your copy of it.
Step back and write down a clear security model for your application, because higher-level logic in your application will be attacked long before the crypto.


Password in first line of file for AES-256 encryption I'm using openssl with aes-256-cbc encryption to encrypt a file. The password is on the first line of the file and the encryption script automatically reads the first line of the file for encryption. Is this procedure secure? OpenSSL stores the salt at the first 8 bytes of the file.

The file looks like this:
1: randomly_generated_password
2: data
3: data
...

And the command to encrypt the file is as follows:

openssl aes-256-cbc -a -salt -in data.txt -out data.txt.enc -k 'head -n 1 data.txt'

Yes it's secure if:

the password contains (i.e. is chosen using) sufficient entropy to resist attack. In practice this means it must be generated by a physical process (like rolling fair dice or flipping fair coins) or a good computer program (usually not the C library rand() function for example) not chosen by a human. Humans are very bad at choosing "randomly" and even when we think something "looks really random" it isn't; see also https://security.stackexchange.com/questions/79275/are-humans-a-strong-or-weak-rng . Note that PBKDFs are usually designed to be artificially
costly and thereby 'stretch' a human-chosen password, but openssl enc uses only ONE iteration of MD5 and adds no strength; even in the 1990s this was not good practice.
the pw file, and all stored and/or (edit) transmitted copies of it, are never available to an attacker but conversely the password data in the file is never lost (unless all the data encrypted using it is also discarded or lost so it is no longer needed)


Difference between Pedersen commitment and commitment based on ElGamal Does any of you know what is the difference between the Pedersen commitment and the commitment that uses the ElGamal encryption scheme?

For the sake of completeness, I recall what both of them look like.

Given two public and large primes $p$ and $q$ such that $q∣(p−1)$, and a (also public) generator $g$ of the order-$q$ subgroup $G \subset \mathbb{Z}^{⋆}_p$, and given two random (secret) values $a,r \in \mathbb Z_q$, we have that in order to commit to a message $m \in \mathbb{Z}_q$, we just have to compute the commitment $c=g^m h^r \pmod{p}$, where $h=g^a \pmod{p}$. Then, to open the commitment, we need the values $m$ and $r$ to be revealed, so that the commitment receiver can verify the commitment.

In the ElGamal encryption (for example, in the exponential version, which looks more like the Pedersen commitment) we also have a generator $g$ of a multiplicative group $G$ of order $q$, a private $x \in \mathbb{Z}_q$, and a public $h=g^x$. In order to encrypt a message $m$, we take a random $r \in \mathbb{Z}_q$ and compute $(g^r, g^m h^r)$. To me, the second part of the tuple looks very much like the Pedersen commitment.

The fact that any encryption scheme can be used as a commitment scheme is well-known. However, I often see the Pedersen commitment mentioned as something completely different to the commitment that uses an ElGamal encryption, and I was wondering whether here is any difference between the two, or they are actually the same.

The main difference is that Pedersen commitments are unconditionally hiding, as given $g^mh^r$ represents an information theoretic hiding commitment, i.e., even an unbounded adversary will not be able to figure out $m$.

In exponential ElGamal encryption, since you publish $(g^r,g^mh^r)$, this so obtained commitment is no longer unconditionally hiding, but only computational hiding. Note that an unbounded adversary can simply try all possible $r\in Z_q$ till it matches $g^r$ and then with this knowledge try all possible $m\in Z_q$ till it matches $g^mh^r$.

Now, if you would only publish the second component in ElGamal, i.e., $g^mh^r$, as commitment and discard the first, this actually is a Pedersen commitment (as the setting you use is identical - i.e., working in a prime order $q$ subgroup of $Z_p^*$). The problem is, that when using this modified type of ElGamal encryption and the person computing the commitment knows the secret key $x$ with $h=g^x$, the ciphertext component $g^mh^r$ is no longer a binding commitment. Observe that you then can choose an arbitrary $m'\in Z_q$ and solve the equation

$m+xr\equiv m'+xr' \pmod q$

for the only unknown $r'\in Z_q$, which implies that

$g^mh^r = g^{m'}h^{r'} \mod p$

holds and thus, the commitment to $(m,r)$ can be opened to other arbitrary values $(m',r')$ (thus not binding at all).

Note that in fact it is essential for Pedersen commitment that the parameters $g$ and $h$ need to be computed by a trusted third party such that the discrete log $a$ between $g$ and $h$ is unknown. Otherwise you would have the same problem as with this "take the second ciphertext component of ElGamal encryption" as commitment. If you want to have such a property you obtain a trapdoor commitment with trapdoor $a$ (which allows you to arbitrarily open the commitment if you know the trapdoor $a$ as discussed above).

Edit:

As Ricky Demer mentioned in his comments I assumed that the commitment is non-interactive. If the receiver chooses the parameters for the commitment scheme and sends them to the sender, then unconditional hiding is given (it must only be ensured that the sender does not know the dlog between $g$ and $h$).

As tylo mentioned in the comments it is also interesting to look at the binding properties of both approaches.

Pedersen commitments are computational binding under the dlog assumptions as seen above.

The exponential ElGamal version - publishing $(g^r,g^mh^r)$ - is, however, unconditionally binding as the first component $g^r$ uniquely determines $r$. Thus, this means that also $m$ in $g^mh^r$ is uniquely determined.


How (in)secure is a signature based on DSA with DSS1 (SHA1) in reality? As I found out the OpenSSL implementation provided by PHP (openssl_sign) only allows DSS1 as the hashing algorithm for DSA signatures (see also my related question).

I’d prefer DSA over RSA in my use case because of the significantly shorter signatures. However, I have doubts regarding DSS1 which is basically SHA1 and therefore considered vulnerable.

The question is: Does this vulnerability also apply when used with DSA? After all the security of a signature is not (only) about finding a hash collision or fast brute-force hash calculations...

How secure or insecure would you say is using DSA with DSS1 when signing a license file for a software? Is it possible that someone can calculate the private key within a reasonable amount of time (having the public key, a message and its signature) or what’s a realistic risk?
I’m aware of the fact that calculations are getting faster and faster (GPUs, cloud based services, etc.) so please include your estimation for the next couple of years.

While no SHA1 collisions have been found, there are some attacks:

~$2^{60}$ collision attack. Estimated to cost around \$1-2 million currently in the cloud. Possibly economical soon, especially with specialized hardware.
Intractable preimage attacks like $2^{151}$ against reduced round variant, $2^{159}$ against full hash. (Cf. $2^{160}$ brute force on any 160-bit hash.)

  How secure or insecure would you say is using DSA with DSS1 when signing a license file for a software?

Like poncho wrote in a comment, using a collision attack against a signature requires the attacker having control over what is hashed. If you only sign messages you've created yourself, e.g. random data, there is no way to mount a collision attack.

  Is it possible that someone can calculate the private key within a reasonable amount of time (having the public key, a message and its signature) or what’s a realistic risk?

Even if a collision would be found, that would not compromise your key. A single collision would typically create a single valid-looking license file.

(A collision against a key signature, like against CAs, is a different matter because that allows one to create an arbitrary, valid, authorized key they can use to make their own signatures. That's why Microsoft is deprecating SHA-1 certificates.)

  I’m aware of the fact that calculations are getting faster and faster (GPUs, cloud based services, etc.) so please include your estimation for the next couple of years.

Current attacks could allow collision attacks in the next few years if you sign user controlled data.

Preimage attacks would require a breakthrough to become viable. Always a possibility, but there is still enough security margin that I wouldn't worry about it.

A note on preimage vs. second preimage:

Whether a preimage or a second preimage attack would be needed depends on your setup. If the scenario is that the attacker wants to create another signed license file knowing one, he would need a second preimage, which is possibly harder. If the scenario is that the attacker knows a signature and needs to create a license file to match it, any preimage will do.


Do I need to use a MAC with asymmetric encryption? The internet has drilled into me that when I delivery any symmetrically encrypted data, I should also deliver a MAC to authenticate it before any decryption occurs. Do I also need to do this if I use asymmetric encryption? If so, what is the proper mechnaism?

The normal pattern that I have used so far is to use the same symmetric key as used for the encryption also for the MAC. Something like this:

// Alice
ciphertext = aes_encrypt(plaintext, aes_key, iv)
mac = hmac_sha(ciphertext + iv, aes_key)

// Bob
verify_hmac_sha(ciphertext + iv, aes_key, alice_mac)
plaintext = aes_decrypt(ciphertext, aes_key, iv)

Now, if I replace the encryption with an asymmetric algorithm, I immediately run into the trouble that there is no symmetric key pre-shared between the two parties. Using the asymmetric key pair's public key for the HMAC key seems nonsensical, as it is obviously public and anyone could fake the MAC.

However, assuming that Bob also knows the public key of Alice, Alice could simply sign the data being sent using an appropriate asymmetric signature algorithm. To me, this seems equivalent to using a MAC.

Is my understanding correct? Furthermore, do the vulnerabilities that require MACs with symmetric cryptography even affect asymmetric cryptography?

Yes, (asymmetric) encrypt-then-sign would provide the same properties as (symmetric) encrypt-then-mac. It would provide integrity and authenticity of the ciphertext.

It is however possible for another person to re-sign the encrypted message if encrypt-then-sign is used. This is a problem when other parties are trusted within the same network. Note as well that it won't necessarily provide integrity and authenticity of the plaintext if another party creates the ciphertext. For this reason sign-then-encrypt is often used instead of encrypt-then-sign.

As the use cases for symmetric and asymmetric encryption would be different there are differences on how to implement encrypt-then-sign. The most important difference is of course that although the session keys are kept by both parties in the case of symmetric encryption. With asymmetric encryption the private key for signing is normally different than the one used for decryption (if more than one party is involved). The private key(s) of a party would be used for signature generation and decryption and the public keys would be used for signature verification and decryption. So you'd have a pretty different key management scheme.

Attacks on symmetric block modes of operations such as padding oracle attacks don't translate directly to attacks on asymmetric primitives. But often the same kind of issues can be found. There is, for instance, a padding oracle attack on PKCS#1 v1.5 encoding for encryption (Bleichenbacher attack). So although not identical, the same kind of issues can creep up.

With asymmetric encryption a hybrid cryptosystem is normally defined. You could use e.g. RSA OAEP and an authenticated symmetric cipher together to maintain confidentiality and integrity. In that case a signature may not be required to maintain integrity and confidentiality. You'd still need a signature of course for authenticity. This construction could be used for sign-then-encrypt (as noted in the second section of this answer).

Beware that using PKCS#1 v1.5 padding and / or CBC mode of operation can be vulnerable to plaintext & padding oracle attacks, so you don't want to use those algorithms for sign-then-encrypt unless you're certain that those kind of attacks are infeasible (which they generally are when using in place encryption / decryption such as file encryption).

  However, assuming that Bob also knows the public key of Alice, Alice could simply sign the data being sent using an appropriate asymmetric signature algorithm. To me, this seems equivalent to using a MAC. Is my understanding correct?

It is. Bob doesn't just need to know the public key though, he needs to trust the public key. But this assumes that you only accept signatures generated by one private key.

  Furthermore, do the vulnerabilities that require MACs with symmetric cryptography even affect asymmetric cryptography?

Yes, they may. But this statement is too broad to be answered with a yes or no. There are certainly different attacks possible on symmetric and asymmetric primitives (that don't easily translate from one system to the other).


Affine encryption function Let $f(x) = ax + b$ be an affine encryption function. $a$ and the cardinal of the field of our keys $K$ (in English, 26) must be coprime so that the encryption function is bijective and the decryption function defined and bijective as well.

Could you please clarify how (in terms of congruences) the two having a $pgcd>1$ make the encryption function not bijective?

Let $n$ be the modulus and $d = \gcd(a,n)$. Then, $ax \mod n$ will be a multiple of $d$. If $d > 1$, this implies that there is no $x$ such that $ax \equiv 1 \pmod n$, and so there is no $x$ such that $f(x) = ax+b \equiv b+1 \pmod n$. So $f$ is not a bijection since it is not surjective.

P.S.: I am not certain how you got the idea of using the word "field" instead of "set", but you should refrain from using it until you have learned what a field is.