How to encrypt dates using format preserving encryption and avoid collisions I'm encrypting with an FPE algorithm in C#.  What I did is convert the date I want to encrypt to the day of year value and a year value like so.

string input = "1901-01-01";
DateTimeOffset parsedDateOffset = new DateTimeOffset();
bool parsed = false;
parsed = DateTimeOffset.TryParseExact(input, "yyyy-MM-dd", CultureInfo.InvariantCulture, DateTimeStyles.AllowWhiteSpaces, out parsedDateOffset);

if(parsed){

    DateTime dtNew = new DateTime(parsedDateOffset.Year, parsedDateOffset.Month, parsedDateOffset.Day);
    int dayOfYear = dtNew.DayOfYear;
    int yyyy = parsedDateOffset.Year;

// Then I encrypt the day of year separate from the year

    int encodedDay = FE11.Encrypt(365, dayOfYear, Encoding.UTF8.GetBytes(input.ToString()), Encoding.UTF8.GetBytes("0"));
    int encodedYear= FE11.Encrypt(2015 - 1901, yyyy, Encoding.UTF8.GetBytes(input.ToString()), Encoding.UTF8.GetBytes("0"));

// Then combine them together again taking into account leap year

     DateTime encodedDate = new DateTime((int)encodedYear, 1, 1).AddDays((int)encodedDay - 1);;
     if (DateTime.IsLeapYear((int)encodedYear))
     {
         encodedDate.AddDays(1);
     }
}

However I'm encountering duplicate dates (i.e. for two plaintext dates result in the same encrypted date)  But with format preserving encryption this should not be the case, and I know it is because of the way I am emcrypting the year separate from the day of year.

Does anyone have any suggestion to overcome this?  I have tried introducing a tweak but the problem persists.

Ideally I would like to encrypt only one value.  But encrypting the day of year alone still requires me to place it in the context of a year when presenting the final encrypted result.

Are there other date representation besides day of year that might be useful?

EDIT:  The FPE library I am using at this time is called DotFPE located here https://dotfpe.codeplex.com/ (which is supposedly a port of the Format Preserving module of Botan Crypto)

So, in the comments, you state that

  I'm using the original date as the key

This is the reason for the duplicate dates. The encryption is entirely deterministic for a fixed key. When you change the key, however, it is not. So it is entirely plausible that encrypting the number 215 with the key 215 could result in the same ciphertext as encrypting the number 10 with the key 10. But, encrypting the numbers 215 and 10 each with the same key, say 111, should be guaranteed to result in different ciphertexts (assuming you are not using the tweak, or using a fixed tweak).

If you had a fixed, random key, then you should get different ciphertexts. Adding in a random, per-message "tweak" can also cause this behavior.

So you can fix this "problem" by just using the same key everywhere and no tweak. This does, however, scare me. You are using deterministic encryption in an application that has a fairly small domain. Could make you vulnerable to frequency attacks, or other attacks, depending on the exact application.


Comparing two definitions of one-way function I'm reading Rafael Pass's lecture notes on one-way function and came across two definitions.

The first one is: A function $f$ is one-way if $f$ can be computed in P.P.T. and there exists no non-uniform P.P.T. $A$ such that

$\forall x \in \{0,1\}^*, Pr[A(f(x)) \in f^{-1}(f(x))]=1$

However this definition is considered imperfect because (for example) under this definition $f(x)=|x|$ would be hard, because "it will take $2^c$ time to write a valid inverse to something such that $f(x) = c$. " (quoted from the note).

Then it gives the second definition, $\forall$ nuPPT $A$, $\exists \epsilon$ such that $\forall n \in N$

$Pr[x \leftarrow \{0,1\}^n; y \leftarrow f(x): f(A(1^n, y)) =y] \le \epsilon(n)$

It seems like I can't appreciate the subtlety here and I have two questions:

Why does $f(x)=|x|$ take $2^c$ time to write down an inverse.
Why $1^n$ is necessary in definition 2.

Can someone shed some light?

I assume that $|x|$ in the exercise denotes the length of the bitstring $x$.

If so, the answer is simple: a polynomial time algorithm needs to complete in a number of steps bounded by a polynomial function of the length of its input.

How long is $|x|$, represented as a bitstring?  Well, it takes $k$ bits to represent a number between $2^{k-1}$ and $2^k-1$, so the length of the input $n = |x|$ is about $\log_2 n$ bits.

Thus, in order for $A$ to be a polynomial-time algorithm, $A(|x|)$ must complete in at most $p(\log_2 |x|)$ steps, where $p$ is some polynomial function.  But writing out a string containing $|x|$ bits obviously takes at least $|x| = 2^{\log_2 |x|}$ steps, which is not bounded above by any polynomial function of $\log_2 |x|$.

Essentially, the problem is that the input $|x|$ given to $A$ is "too short" compared to the expected output $x$.  The way we "fix" this issue is simply by giving $A$ an extra input $1^n$ whose length matches the length of the expected output.  That way, by "padding" the input of $A$ to be at least as long as what its output should be, we effectively allow the running time of $A$ to be a polynomial function of the length of both its input and its (expected) output, while still adhering to the standard definition of a polynomial-time algorithm.

In programming, we'd call this a hack, or perhaps a kluge.  But it's a convenient kluge, as it saves us from having to redefine "polynomial time" in crypto differently from the way it's usually defined in complexity theory, and so avoids facilitates communication between these two related fields.

Alas, the cost of this notational uniformity is that the extra $1^n$ argument sometimes appears confusing to new students in crypto — especially as some authors, perhaps out of some misplaced sense of professional embarrassment, seem rather reluctant to explain that it is, indeed, essentially just a notational hack to make the standard definition of "polynomial time" fit what we need in crypto.


Few questions about CBC MAC I want to use CBC MAC. First I hope to find some implementation of block cipher which I will use in CBC mode, which I understand is CBC MAC. But I have two questions:

1) If the length of the message to be authenticated is not multiple of block cipher block length, what shall I do?

2) Do I need to use session keys with CBC MAC? e.e. use different key for each message. Or I can use one key for long time period?

2) To strengthen CBC MAC one recommended way as mentioned on Wiki is to put the length of the message in the first block. But how should I encode the length, as string? Or in binary? If block length of cipher is say 64 bits, do I encode the number as 64 bit number? e.g. if message length is 230, I should use following value as first block:

00000000 00000000 00000000 00000000 00000000 00000000 00000000 11100110

?

1) Fill remaining of last block with nulls.

2) No, you can use same key for more messages, but not the same as encryption key.

3) Usually this is done binary, like you did. If you are going to use CBC MAC with variable length messages, you must do this.

I recommend you to use XCBC or CMAC instead (CBC MAC variants for variable length messages).


What is the role of steganography in network security? Quick definition:

  Hiding secret messages inside what seem to be harmless messages is nothing new. The word steganography itself originated in Greece and means “covered writing”. During important historic events of our past, steganography was often used to trade personal secrets, plan covert operations and send political espionage information.

source: steganography

What is role of steganography in network security?

I’m not aware of any uses of steganography in network applications, and considering almost all of the networking protocols are open protocols, there’s little room for the application of it. If you need security, you use various forms of encryption.

That being said, the only example I can think of of steganography in modern days is, some printers also printing out some form of a serial code and timestamp in a (almost) hidden part of the printed out material.


Attack for RSA 1024 bit with Low Public Exponent I am facing a challenge at university.
Our teacher give us the challenge to try to break an RSA 1024 bit.

We have public modulus N and public exponent e (0x03), we don't know the padding.

We have a signed message with RSA key (128 bytes) and we know that the unsigned message is an MD5 hash, we have also the MD5 hash (jus to verify).

The first goal is to find if possible the private exponent d.
The second goal is to forge a new signed message (hash) valid.

Can someone point me out which type of attack i can use and what programming language give more performance to do that?

Thanks a lot, any information will be helpful.

The original poster clarified that:

the application of RSA is signature (not encryption as originally stated);
at least one signature $s$, the value of $N$, and $e=3$ are given;
the signature is by signing an MD5 hash of a message, and a hash of the message matching the signature $s$ is also a given.

The first, low-effort thing to do with the givens is computing $r=s^e\bmod N$, which in most RSA signature schemes is the so-called message representative (single practical exception: in some schemes including some in ISO/IEC 9796:1991, ISO/IEC 9796-2, ISO/IEC 14888-2, the message representative could also be $N-r$).

The message representative $r$ that we now have was determined by the signer from the MD5 hash (that we know) of some message, using some in principle public process that we are not given. That process usually involves padding on the left or/and right with repetitive constant bytes, or randomness; perhaps hashing; and in modern schemes XORing some portions with the result of some public mask generating function of some other section of the message representative. Many paddings found in practice are easily recognizable by some prescribed constant byte at some prescribed location; all are bound to be unambiguously detectable if one has the specification and parameters necessary to check a signature.

Doing the above, the original poster reported that $r$ is exactly the hash (the tool computing $r=s^e\bmod N$ has output the 16-byte hash with a 00 on the left, perhaps because the hash starts with the byte B5 and that's in the range 80..FF of negative byte values for two's complement).

So we conclusively know that there is no padding; in other words, it is used textbook RSA signature, or equivalently the padding type 00 of section 8.1 of PKCS#1 Version 1.5 of 1993, also RFC2313 of 1998 (I find it unjustifiable that this non-padding is in these documents with so little warning).

We know the padding, and it is so lacking that we know the signature matching many hash values: for example the all-zero bitstring of 1024-bit ($s=0$) is the signature of the hash consisting of the all-zero 128-bit bitstring ($r=0=s^e$); the bitstring with only the $k^{th}$ bit set ($s=2^k$) and $k\le42=\lfloor{128\over e}\rfloor$ is the signature of the hash with only the $3k^{th}$ bit set ($r=2^{3k}=s^e$); more generally we know the signature for any hash which value is a cube in $\mathbb N$. However that is not solving the concrete problem of forging a message passing a signature check of its MD5 hash, thus does not answer the question. We have several options to proceed towards that goal:

Trying to find $d$ (or more precisely, one of several working private exponents $d$), which would trivially allow to sign any message. In RSA, example cryptograms (if valid) are of no help towards that (we do not know how to prove it, but if such a mean was found after 38 years of public research, it would make the headlines). The only practical way we could find such $d$ is by factoring $N$. Factoring a properly generated 1024-bit RSA modulus is currently well beyond the possibility of anything but deep-pocketed organizations like the NSA, which would not claim that capability if they had it (a plausible but unproven conjecture). Thus if we try factoring $N$, it will only succeed if $N$ was poorly chosen. If the teacher mentioned some factoring method (like Fermat's, or Pollard's $p-1$), it might be worth trying that.
Trying to find a message that matches the existing signature. That's a preimage attack on MD5 (first preimage since we do not have a message), and although the collision-resistance of MD5 is now broken, its preimage resistance stands valiantly; so that won't work. We are not in a position to obtain the signature of a chosen message, thus we can't make use of MD5 collisions.
Trying to find a message and a new matching signature going with that. If we had many signatures, that would be feasible by a transposition to signature of the attack on textbook RSA encryption of Y. Desmedt and  A. M. Odlyzko: A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes (in proceedings of Crypto 1985). It is re-explained in the context of signature by Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann in section 3 of Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures (extended abstract in proceedings of Crypto 2009). But unless we have many valid signatures, that can't work.
[Late addition, independently found by Poncho] Another method to try to find a message and a new matching signature going with that, but without requiring extra valid signature, would be hashing messages with a random ending until their hash happens to be a cube (it is then trivial to find their signature). This is expected to require about $2^{{e-1\over e}128}=2^{85.3\dots}$ hashes, which would require the resources devoted to bitcoin mining in like a year (and can't be done with exactly that hardware: it seems to consist of ASICs hard-wired for SHA-256 rather than MD5, and no way to stop hashing on cubeness, or likelihood of that).
[Credit goes to Poncho in this comment] Trying to find a message and some value that the verifier will accept as a valid signature, even though it is not the normal signature. That might be possible in particular if the verifier checks a signature $s$ by computing $s^e\bmod N$ and checking that the rightmost 16 bytes match the MD5 hash of the alleged message $M$, but fails to fully check the rest of the padding (something similar was a formerly common goof).
Assuming checks are made on at most the $w\le\lfloor{\log_2(N)\over e}\rfloor$ rightmost bits of $s^e\bmod N$ (here $w$ can be up to $341$, much more than the hash width), we can pick messages $M$ (e.g. at random within messages that it is useful to get signed) until $r=\operatorname{MD5}(M)$ is odd (or more generally $r=u\cdot2^{e\cdot v}$ with odd $u$, which gives a little extra freedom in the choice of $M$); and then find a $w$-bit number $s$ with $s^e\equiv r\pmod{2^w}$, which will exist. $s$ can be found in $w$ steps each finding an additional bit for $s$ starting from the right, with $s^e\equiv r\pmod{2^k}$ for $k$ increasing from $0$.
Then $s$ (zero-padded on the left to the width of a signature) will be accepted as a signature for message $M$ !! Notice that $s^e<N$, thus $(s^e\bmod N)=s^e$, and we know that the rightmost $w$ bits of $s^e$ (which we assumed are the only ones checked) match the true message representative $r$ for our message $M$. We don't need any signature to carry that attack, which fits the problem statement; but since we do not have the code of the verifier, we will only know if it works by trying.

If Poncho and I missed any other avenue for attack that might fit the question, I want to know!

Attack 5 assumes an hypothetical verifier goof. Attacks 3, 4 and 5 depend entirely on the disastrous/absent padding. Attacks 4, 5, and to a lesser degree 3, also depends on $e$ being very small, with the common $e=65537$ enough to block 4 and 5, and appreciably slow 3. The lesson about RSA signature should be to

Ensure that verifier code is correct in how it checks padding, which is done with best confidence by a combination of scrutinizing the source code and testing; the most critical being that what's been reviewed is what's actually used (including but not limited to that the compiler did not goof, and that an adversary can't zap some of the checks by altering what's run, which could be at any point from the developer's penetrated development machine, to the internals of the target CPU in a fault attack).
Use a proper padding for RSA signature, with the bare minimum PKCS#1 V1.5 type 01 (now officially named EMSA-PKCS1-V1_5), and EMSA-PSS preferable (specially in circumstances where the attacker might obtain the signature of even partially chosen messages).
Use $e=65537$ (or more, but that's technically unjustified) unless it is used a padding with a strong security argument (including EMSA-PSS). There might be additional reasons to stick to $e=65537$, see this.


Standard lightweight one-way hash functions for IoT devices What are the standard lightweight one-way hash functions used in current Internet of Things devices?

I could find some proposal of hash functions in conference papers but I want to know the ones which are being currently used. I found no concrete answer while searching on internet.

Here you have a study about different cryptographic methods in different IoT devices:
Midgar: Study of communications security among Smart Objects using a platform of heterogeneous devices for the Internet of Things
In this study, the authors (Sánchez-Arias, García, and García-Bustelo) explain the time that the different methods need to send messages and a comparison between the methods, about their current state and about the time that they needed.

Abstract
In last years, the Internet of Things has been a revolution in terms of applications and research. Currently, there are a great variety of nodes connected to each other to create different applications in areas, ranging from sport to business, inter alia. These applications compromise our private information about our bank accounts, health, and location. This makes us take safety measures to achieve a secure communication, where the interception of a message by a malicious user cannot compromise our privacy.


Weaknesses in ARX block ciphers What are the weaknesses in a block cipher that uses modular addition, rotations with fixed amounts, and XOR? Can substitution boxes or permutation boxes be replicated with these three operations? Would the weaknesses in an ARX block cipher be present in an ARX stream cipher?

What are the weaknesses in a block cipher that uses modular addition, rotations with fixed amounts, and XOR? Can substitution boxes or permutation boxes be replicated with these three operations?

The obvious question to ask is "what permutations can you form using those three operations"?

The surprising answer is "you can implement any permutation using a sufficiently large pile of those three operations in the proper sequence"; that is, you can find a sequence of operations which swap two specific entries (and leave everything else alone); you can concatenate those together to form any arbitrary permutation.

Hence, there cannot be any generic weakness that would apply to sufficiently long ARX ciphers.  Of course, this doesn't address what "sufficiently long" means; it may be longer than what's in use in practice.

And, yes, there exists an ARX equivalent to any invertible sbox.

Exhaustive search on 3 bit blocks shows that you can reach every permutation with at most 9 operations, which isn't that bad.  However, doing a search on 4 bit blocks would require searching over $16! \approx 2^{44.25}$ distinct states; a bit more than I can handle with my current resources.


Single bit error in CBC Why does a single bit error when using the CBC block cipher mode of operation affect the decryption of a block (Oj) with a probabilty of 50%? And in the following block, why is the one bit error in the exact position as in cipher block? Differently worded: why is the 1 bit error propagation 1:1?

If you have an error in a cipher text block you can generally represent this as:

$$C'=C\oplus\Delta$$

Now if you try to decrypt this block using the previous ciphertext block $IV$ as IV you get $P'=IV\oplus D_K(C\oplus\Delta)$ which is completely unrelated to $P=IV\oplus D_K(C)$ assuming the block cipher acts as a pseudo-random permutation. As the input changed the chance for each plain text bit flipping are 50% (independently), everything else would be considered a weakness of the cipher.

Now for the second part:
Assume you have the errorneous message $C_1'=C_1\oplus\Delta$ and a normal $C_2$. The decryption $P_2'$ is then $P_2'=C_1'\oplus D_K(C_2)=C_1\oplus\Delta\oplus D_K(C_2)$ and as $P_2=C_1\oplus D_K(C_2)$, you see that $P_2'=P_2\oplus\Delta$ meaning the error of the previous block propagated perfectly into the next plain text.


Discrete logarithm with exponentiation oracle Suppose $(n, d)$ is an RSA private keypair. We know the public key only (wlog suppose it's $(n, 2^{16}+1)$ and we are given oracle $E$, decryption oracle for $(n, d)$. Is there any efficient algorithm to recover $d$? This is a bit easier than directly attacking for known pair of plaintext and ciphertext, as for any $m$ we can astablish this relation:

$$
E(m) \equiv m^d \pmod n
$$

No, there is no known way to recover $d$ using an Oracle that, given $m$, returns $m^d \bmod n$; there is also no proof that such a method does not exist.

Such a method would imply that the RSA problem (which is, given $m^e \bmod n$, recover $m$) is equivalent to the factorization problem (which knowledge of $d, e$ would allow you to solve); it is unknown if these two problems are equivalent.


Is the hash function defined in this exercise collision-resistant? I have this problem:

  "Let ${\rm Enc}_k(m)$ a safe block encryption system. We define a hash function $H(m)$ as follows:

  $m$ will be concatenated with $0$ until $|m|$ is a multiple of len(block);
  we break the sequence $m$ into $n$ blocks like $m = m_0 \mathop\| m_1 \mathop\| m_2 \mathop\| \dots \mathop\| m_{n-1}$;
  we apply this algorithm:

c ← Encm0(m0)
for i = 1 to n-1 do
  d ← Encm0(mi)
  c ← c NOR d
end for
H(m) ← c

Where c NOR d denotes the bitwise operation NOT (c OR d), i.e. (for single bits) 1 NOR 0 = NOT (1 OR 0) = NOT 1 = 0.

Is this $H$ resistant to collisions?

The padding scheme isn't collision resistant.

For any message $m$ where $|m| \not\equiv 0 \pmod n$, there will always be a collision between $m$ and $m || 0$.


Block Ciphers - Standardize plain text I need to use AES-128 to encrypt a plain text about 720 bits.

Is it correct to say that – in this case – the plain text will be divided in 5 blocks of 128, the result will be equal 640 bits, and the other 80 bits would be expanded to 128 bits?

The total result would be 6 cryptograms( 5 - 128 bits, 1 - 80 bits expanded to 128 bits) that will be concatenated.

In the end, what I would like to know is: what's the correct procedure to standardize the plain text to be encrypted by algorithm?

You cannot encrypt 720 bits plaintext using just AES-128. AES is a 128 bit block cipher. Such a block cipher has an input of 128 bits of plaintext and an output of 128 bits ciphertext; and that's it. You need some kind of construction to make block ciphers encrypt larger or smaller plaintext.

Such constructions are known as (block cipher) modes of operation. Some of these constructs like ECB (usually insecure) or CBC require padding (what you call "expansion"), most of the others do not. Even ECB and CBC can be used with ciphertext-stealing to avoid padding.

Probably the best way is to chose a mode of operation that doesn't require padding; CTR mode operation is probably the most used mode for new implementations. It is also the most used within authenticated modes of operation such as GCM, which come highly recommended.

If you're stuck with ECB or CBC then choosing PKCS#7 compatible padding is probably the best / most compatible padding out there. Beware of padding oracle attacks though (did I mention authenticated encryption already?).


Primitive polynomials and irreducible polynomials? This question may seem annoying to some scholars as it is a very silly question but as I am new on this topic, it seems quite confusing.

  All minimal polynomials or primitive polynomials are considered as irreducible polynomials but all irreducible polynomials are not considered as minimal/primitive polynomials.

Can anyone please clarify this statement?

The definition of a primitive polynomial $P$ is that it is an irreducible polynomial with an extra condition, which is that $X$ is a generator of the whole group of non-zero polynomials modulo $P$.

To clarify things:

We consider a finite field $K$ (for instance, $K$ may be the integers modulo a given prime $q$). $K[X]$ is the ring of polynomials with coefficients in $K$. Each polynomial has a degree, which is the largest index of non-zero coefficient; for instance, $X^2+1$ has degree $2$. By convention, we will say that the zero polynomial ($P = 0$) has degree $-1$; other constant polynomials ($P = a$ for some constant $a \neq 0$) have degree $0$.

We can define an Euclidean division of polynomials, in which, given two polynomials $A$ and $B$, such that $B$ is not zero, one can find two polynomials $Q$ and $R$ such that $A = BQ + R$, and the degree of $R$ is strictly less than the degree of $B$. Moreover, this decomposition is unique: for given $A$ and $B$, there is a unique pair $(Q,R)$ that works. The remainder $R$ is also known as "$A$ modulo $B$". If $R = 0$, then $A$ is said to be a multiple of $B$.

An irreducible polynomial $P$ is one such that it is the multiple of no other polynomial whose degree is less than the degree of $P$, but more than $0$. For instance, over field $\mathbb{Z}_2$, the polynomial $X^2+X+1$ is irreducible; but $X^2+X$ is not, since it is the product of $X$ with $X+1$. (Note that irreducibility depends on the base field; $X^2+1$ is irreducible in $\mathbb{R}[X]$, not in $\mathbb{C}[X]$.)

Given a polynomial $P$ of degree $n > 0$, we can consider $K[X]/P$, which is the ring of polynomials modulo $P$: after all additions or multiplications, we reduce the result modulo $P$. This defines a ring structure, and contains all polynomials of $K[X]$ whose degree is strictly lower than the degree of $P$ (i.e. polynomials of degree $0$ to $n-1$, inclusive). If $K$ contains $q$ elements, then $K[X]/P$ contains $q^n$ elements.

It so happens that, when $P$ is irreducible, then $K[X]/P$ is itself a field. Non-zero polynomials in $K[X]/P$ are then a multiplicative group, of size $q^n-1$.

Consider, then, the subgroup generated by $X$ (the polynomial of degree $1$ whose coefficient of index $1$ is $1$, and coefficient of index $0$ is $0$). You take $X$, $X^2 \pmod P$, $X^3 \pmod P$, and so on. At one point, you will get back to $1$. The order of $X$ modulo $P$ is the smallest $k > 0$ such that $X^k = 1 \pmod P$. Since all these $X^j$ form a multiplicative group, it follows that $k$ is a divisor of $q^n-1$.

When $k$ is equal to $q^n-1$, then the polynomial $P$ is said to be primitive. This means that by computing the various $X^j$ modulo $P$, you end up covering all non-zero polynomials modulo $P$.

All primitive polynomials are irreducible, because we simply defined them that way: to be primitive, a polynomial must first be irreducible. However, not all irreducible polynomials are primitive. For instance, if we work with $K = \mathbb{Z}_2$ (the field with two elements, $0$ and $1$), then polynomial $P = X^8+X^4+X^3+X+1$ is irreducible, but not primitive (there are $255 = 2^8-1$ elements modulo $P$; but the subgroup generated by $X$ only contains $51$ of them).

Primitive polynomials are mostly relevant for linear feedback shift registers. It can be shown that the contents of a LFSR of size $n$ bits can be interpreted as a polynomial in $\mathbb{Z}_2[X]/P$ for a given polynomial $P$ of degree $n$, that depends on the positions of the feedback bits of the LFSR. Shifting the LFSR by $1$ bit then corresponds to multiplying the contents by $X$. Therefore, the period of the LFSR (number of shifts until reaching back the starting state) is maximal ($2^n-1$) only when $P$ is primitive.

LFSR are "old crypto", back from a time when that notion of period was felt to be really important (when you hear somebody talk of "the cryptoperiod", you know that he is doing cryptography from the 1960s, and he missed out the last 50 years of research in cryptography). Nowadays, LFSR and primitive polynomials are less relevant. Irreducible polynomials, however, are necessary to define field extensions. The degree-8 polynomial shown above, which is irreducible but not primitive, is used in the definition of the AES S-Box.


Clarification of Proof: Proving perfect secrecy for One Time Pads I came across a version of a proof that One Time Pads have perfect secrecy and have a few questions with this version of the proof. The proof is attributed to Dan Boneh (the proof starts on slide 10),

  Definition: A cipher (E,D) over (K,M,C) has perfect secrecy if
  $\forall m_{0}, m_{1} \in$ M,      $(\left\vert{m_{0}}\right\vert)$ =
  $(\left\vert{m_{1}}\right\vert)$ and $\forall$c $\in$ C,  such that:
     Pr[E(k,$m_{0}$)=c] = Pr[E(k,$m_{1}$)=c] where k is a random variable that is uniformly sampled in the keyspace K.

My understanding of the Proof is as below,

  Lemma: OTP has perfect secrecy

Proof:

For every message m and every ciphertext c:

Pr[E(k,m)=c] = ${\dfrac{\text{ #keys k in K s.t. E(k,m)=c}}{\text{Total number of Keys}}}$

Suppose that we have a cipher for all m,c: k in K: E(k,m)=c is equal to some constant.

If that is the case then for all $m_{0}, m_{1}$ the probability of E(k,m)=c is the same and Dan states the the denominator (total number of keys) is the same as the number of keys k in K such that: E(k,m)=c.

If this probability is true then the cipher has perfect secrecy.

Let m in M and c in C, then the number of OTP keys that map m to c is 1.

If E(k,m)=c => k $\oplus$ m = c => k= m $\oplus$ c

What this says is that the number of keys k in K: E(k,m)=c = 1 which completes the proof that OTP has perfect secrecy.

Questions:

Why does Pr[E(k,m)=c] = ${\dfrac{\text{ #keys k in K s.t. E(k,m)=c}}{\text{Total number of Keys}}}$
Why is the #keys k in K s.t. E(k,m)=c equal to the total number of keys? Is it because of the following condition: $\forall m_{0}, m_{1} \in$ M,      $(\left\vert{m_{0}}\right\vert)$ = $(\left\vert{m_{1}}\right\vert)$ -- which means one of the requirements for perfect secrecy is that every message m has to be the same length, hence meaning that every key k also has to be the same length, and for each unique message m there must be a unique key k that encrypt its. So the total number of keys is equal to the total number of messages.

But this line of reasoning still doesn't make sense to me. Say there are 5 messages: $m_{1},m_{2}, m_{3}, m_{4}, m_{5}$ and 5 keys that encrypt those messages: $k_{1},k_{2}, k_{3}, k_{4}, k_{5}$ -- then the total number of keys is 5 and the total number of keys that uniquely map $m_{1},m_{2}, m_{3}, m_{4}, m_{5}$ to $c_{1},c_{2}, c_{3}, c_{4}, c_{5}$ is 1, namely: E($m_{n}, k_{n})=c_{n}$ for each m,k, c, as you have a 1-1 pair for messages to keys, so the ratio is 1/5 and not 1. What is wrong with this? Or is it counting the total number of such keys that make (k,m) to c? If it counts the total number of such keys, then that answer is 5 in this example. I'm confused.

How does showing Pr[E(k,m)=c] = ${\dfrac{\text{ #keys k in K s.t. E(k,m)=c}}{\text{Total number of Keys}}}$ = 1 prove OTP have perfect secrecy. This doesn't make any sense to me given the statement of the theorem.

I need help understanding this proof, breaking down what the proof is saying.

Thanks!

As you have shown, the number of keys such that $E(k,m)=c$ for given $m$ and $c$ is $1$. So the probability

$$Pr[E(k, m) = c] = \frac{1}{number\,of\,keys}$$

with $k$ chosen randomly from $K$ is the same for any plain text and any cipher text, so

$$Pr[E(k, m_0) = c] = Pr[E(k, m_1) = c]$$

for all $c \in C$ and $m_0, m_1 \in M$ with $|m_0| = |m_1|$, and thus by definition the OTP has perfect secrecy.


Is LUKS Anti-Forensic information splitter (AFsplit) indistinguishable from random data? I want to know if AFsplit(random_data_input, stripes, digestmod=sha) output is indistinguishable from random data.

The attacker only has access to AFsplit output data.

EDIT: This question is too vague as the answer depends on the randomness hypothesis taken about random_input_data. Take care of it reading the proposed answers.

The purpose is to use this function in a deniable encryption implementation.

About AFsplit: AFsplit provides a security against forensic attacks on disk bad blocks. AFsplit splits data among several disk blocks so that if a block is put in reserved "bad block" area, it doesn't contain a complete sensitive information (particularly, a revoked key slot). LUKS uses AFsplit to store the key slots.

Note: I'm not speaking of LUKS itself that is, of course, a plain header. I just want to focus on this particular function.

Below is AFsplit Python implementation:

import sha, string, math, struct
from Crypto.Util.randpool import RandomPool
from Crypto.Cipher import XOR
def _xor(a, b):
    """Internal function to performs XOR on two strings a and b"""

    xor = XOR.new(a)
    return xor.encrypt(b)

def _diffuse(block, size, digest):
    """Internal function to diffuse information inside a buffer"""

    # Compute the number of full blocks, and the size of the leftover block
    full_blocks = int(math.floor(float(len(block)) / float(digest.digest_size)))
    padding = len(block) % digest.digest_size

    # hash the full blocks
    ret = ""
    for i in range(0, full_blocks):

        hash = digest.new()
        hash.update(struct.pack(">I", i))
        hash.update(block[i*digest.digest_size:(i+1)*digest.digest_size])
        ret += hash.digest()

    # Hash the remaining data
    if padding > 0:
        hash = digest.new()
        hash.update(struct.pack(">I", full_blocks))
        hash.update(block[full_blocks * digest.digest_size:])
        ret += hash.digest()[:padding]

    return ret

def AFSplit(data, stripes, digestmod=sha):
    """AF-Split data using digestmod.  Returned data size will be len(data) * stripes"""

    blockSize = len(data)

    rand = RandomPool()

    bufblock = "\x00" * blockSize

    ret = ""
    for i in range(0, stripes-1):

        # Get some random data
        rand.randomize()
        rand.stir()
        r = rand.get_bytes(blockSize)
        if rand.entropy < 0:
            print "Warning: RandomPool entropy dropped below 0"

        ret += r
        bufblock = _xor(r, bufblock)
        bufblock = _diffuse(bufblock, blockSize, digestmod)
        rand.add_event(bufblock)

    ret += _xor(bufblock, data)
    return ret

Is LUKS Anti-Forensic information splitter (AFsplit) indistinguishable from random data?

No.

AFSplitting is merely meant to provide diffusion, not cryptographically secure randomness.

When you check the LUKS On-Disk Format Specification (eg PDF of v1.1.1) you'll notice it states

  LUKS uses anti-forensic information splitting as specified in [Fru05b]. The underlaying diffusion function shall be SHA1 for the reference implementation, but can be changed exactly as described in the remarks above.

Even though the (broken due collision attacks) SHA-1 function is used as a diffusion function in the reference implementation, that doesn't mean the AFSplitting function does provide any more than that – diffusion.

While it definitely has a (let's just call it) random character, you should not generally rely on it to provide cryptographically secure randomness indistinguishable from random data. That's not what AFSplitting (by itself) is intended to provide. While diffusion surely adds to randomness, there's a big difference between “diffusion” and “cryptographically secure randomness indistinguishable from random data”. Both are hardly exchangeable terms.

And I'm not yet considdering practical breaks against SHA-1 which also might or might not render the answer into a clear “no”… but that's another question.

EDIT

To clarify this a bit more indeep, trying to clear up some confusion in the comments by the asker.

Let's remember the question asked

  I want to know if AFsplit(random_data_input, stripes, digestmod=sha) output is indistinguishable from random data, not knowing random_data_input.

and

  … I just want to focus on this particular function.

The question didn't ask if PBKDF2 is indistinguishable from random data and the question did not assume input to AFSplit to be indistinguishable from random data either.

Therefore, when merely focussing on the AFSplit functionality (as the question asks), one can and has to cryptanalytically assume distinguishable data inputs too. Otherwise, the input to AFSplit would have needed to be defined as “exclusively data indistinguishable from random data”, but the question doesn't limit the input to such indistinguishable data when asking what AFSplitting outputs.

In LUKS the user password is entered and processed by PBKDF2 (which provides the randomness which should be indistinguishable from random data.  The master key is then splitted by the AFsplitter into a number of stripes… via diffusion (using SHA-1 or an alternative replacement).

So, any data indistinguishable from random data needs to be produced outside the AFSplit function. If you'ld feed AFSplit distinguishable data, AFSplit won't magically turn the data you feed it into data indistinguishable from random data; it merely diffuses what you feed it. That's all you get when keeping the focus on this particular function (and the main reason for no as an answer). How the input to AFSplit should be produced in a LUKS implementation is another story, and goes well beyond the AFSplit function (which is merely a diffusion-providing piece of the LUKS cake) and therefore well beyond what was being asked – which was to focus on this particular function.


What does 0...0 and 1...1 mean I am very new to cryptography but can someone explain what exactly does 0...0 and 1...1 mean in general term. Is it that 1st and last bit can be 0,0 and `1,1 respectively and in-between bits can be anything $(0,1)$?

In case it helps… I stumbled upon this while trying to solve the following multiple choice question:

  Let F be a block cipher with n-bit block length. Consider the message authentication code for 2n-bit messages defined by Mack(m1,m2)=Fk(m1⊕m2). Which of the following gives a valid attack on this scheme?

  Obtain tag t on message m,0…0 (with m≠0…0), and then output the tag t on the message 0…0,0…0.
  Obtain tag t on message m1,m2 (with m1≠m2), and then output the tag t on the message m2,m1.
  Obtain tag t on message m,0…,0, and then output the tag t⊕(1…1) on the message m,1…1.
  Obtain tag t on message m,m, and then output the tag 0…0 on the message 0…0,m.

Please note that I do not want an answer to the multiple choice question. I merely want to know how to interpret the notation 0...0 and 1...1.

What exactly does $0...0$ and $1...1$ mean usually?

This simply means a (more or less) long string of $0$s or $1$s or more clearly $000000...000000$ and $111111...111111$.

Related notiational notes, you may have to use soon:

Sometimes the notation $0^n$ and $1^n$ is also used for these strings with exactly $n$ zeroes and ones.

Even more generally it's usually expected that people see the pattern, namely that nothing changes (or else there would be a note about this), for example $\lambda_0,...,\lambda_n$ is expected to be filled with $\lambda_i$ with $i\in \mathbb N_0, 0\leq i\leq n$ or relatedly $(\alpha,...,\alpha)\in \mathbb R^n, \alpha \in \mathbb R$ would be the same principle, that you'd have to fill the blanks with as many $\alpha$s as needed.

One last note: If you'd want to indicate that you want a leading string $0$ and a trailing string $0$ and stuff you don't care about in the middle you'd usually notate it as $n\in\{0,1\}^*$ and $0||n||0$ which means "place an arbitrary string of arbitrary length between the zeroes".


I believe that you're evaluating the feedback polynomial incorrectly; both in your diagram, and in the chart you have listed, it would appear that you have a feedback polynomial similar to $x^5 + x^4 + x$ (note: there are a couple of different ways to turn a feedback polynomial into an LFSR; I'm not sure which one you're intending to use).

To fix your diagram, one way to fix it is if you place the taps at $b_3$ and $b_1$ (not $b_5$ and $b_2$)


What is meant by a 1.5 pass cipher? In What is the advantage of AEAD ciphers? Maarten Bodewes used the term 1.5 pass cipher in his answer.
What is the difference between a 1.5 pass cipher and a 2 pass cipher?
And why is Poly1305 a 1.5 pass cipher? Isn't the authentication tag in ChaCha20-Poly1305 calculated after the encryption in a separate step?

A 2-pass authenticated cipher is a mode of operation that uses two full (block) cipher operations for each byte in the message. There is also a mode of operation, OCB mode, which uses a single pass to provide both message confidentiality and message integrity / authentication (it has been encumbered by IP-rights issues, so it isn't used that much).

A 1.5 authenticated cipher of course doesn't perform the encryption or authentication operation for every other byte. It simply uses an authentication algorithm that - when implemented right on the right hardware - is considered faster than the block cipher. Hence the 1.5 pass which should be read as one full pass of the block cipher + one pass - counted as 0.5 - for the faster authentication operation.

As an example GCM requires one block cipher operation and one 128-bit multiplication in the Galois field per each block (128 bit) of encrypted and authenticated data. 128-bit multiplication in the Galois field can be considerably faster than an AES block encrypt. Poly1305 has the same function as GMAC which specifies the Galois field multiplication within GCM.

Both GMAC and Poly1305 require post pre- and post processing. So for smaller messages the difference between a 1.5 and a 2 pass authenticated cipher may be less pronounced (depending as well on how much pre- and post processing the 2-pass cipher requires).

Please do not directly view the 0.5 as a performance indication. It depends on the algorithm and implementation what the speed differences are with 1-pass and 2-pass ciphers. it's just an indication that it should not be considered another full pass when it comes to the expected speed.


Can a broken cipher reveal the key? Suppose I cascade cipher A and cipher B to encrypt a message. Both ciphers use the same key. I know that theoretically, the security of the setup when used correctly is at least as secure as the most secure. In other works, if cipher A or cipher B is broken, there is still cipher B or cipher A protecting the data. Is it possible under any case for cipher A or B to "reveal" the key, since it's broken? If this happens, then the attacker would know both keys and be able to decrypt the text.
TL;DR: Can a broken cipher ever reveal the key directly?

I know that theoretically, the security of the setup when used correctly is at least as secure as the most secure.

That's true if they use independent keys.  If they use the same key, the security of the cascaded cipher may be much worse.  Consider the case where cipher B happens to be the exact inverse of cipher A with the same key.
However, that doesn't answer the question you asked (as in the above example, the key is perfectly secure; the plaintext not-so-much):

Can a broken cipher ever reveal the key directly?

Obvious yes.  In the most trivial case, consider the 'cipher' the appends the key to the plaintext, and outputs that.
Even if we disallow such obvious egregious examples, we could have a cipher B that encrypts securely, but appends a 'tag' which is a function of the ciphertext and the key (which is common with combined mode ciphers) - if the computation of the tag was weak enough, you could recover the key just with the ciphertext and the tag, even if the plaintext given to cipher B was perfectly secure.


Is it safe to use MD5 in a proof of work system? Here is the POW system: you are given a string and you need to compute a suffix so that first few bits of the MD5 value are all 0. I know MD5 is collision vulnerable, but is it safe to use MD5 here, or, state it in another way, is there a non-bruteforce way to compute the suffix?

Currently, it is probably safe. There are preimage attacks on MD5 but they are only slightly better than brute force. With a proof of work that only requires the initial bits of the hash to match it would likely be easier to use brute force than try to apply any attacks on it.

However, I cannot see a good reason you would do that instead of using a more secure hash function, like SHA-256 – or SHA-256/128 if the output length must match.


What is post Quantum Cryptography? Post-quantum cryptography is cryptography under the assumption that the attacker has a large quantum computer; post-quantum cryptosystems strive to remain secure even in this scenario.
Post-quantum cryptography like lattice-based cryptography is designed to be secure even if quantum computers are available.
The Question that pops on my head are:

How can we define post-Quantum Cryptography?
What is the specification that makes it somehow impossible to break?
Can post Quantum Cryptography makes it somehow impossible to break for a long time?

How can we define post-Quantum Cryptography?

You pretty much included a relatively accurate informal gist in the sentence before this question:

Post-quantum cryptography is cryptography under the assumption that the attacker has a large quantum computer; post-quantum cryptosystems strive to remain secure even in this scenario.

The more interesting question follows:

What is the specification that makes it somehow impossible to break?

First a minor clarification: few algorithms are impossible to break in a conceptual sense - worst case scenario, guessing the key is always a viable strategy (the exceptions are one-time-pads and the analogous one-time authenticators). So it's a matter of cost rather than possibility, namely how much time it would require to defeat the system (space can also play a role in addition to time).
Post-Quantum cryptography usually refers to asymmetric algorithms (key agreement, public key encryption, and digital signatures) that are not known to be vulnerable to Shor's algorithm.
There are other quantum algorithms, but Shor's algorithm appears to be the main concern for cryptography.
The relevant mathematical problem appears to be "The Hidden Subgroup Problem":

The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. The framework captures problems like factoring, graph isomorphism, and the shortest vector problem. This makes it especially important in the theory of quantum computing because Shor's quantum algorithm for factoring is essentially equivalent to the hidden subgroup problem for finite Abelian groups, while the other problems correspond to finite groups that are not Abelian.
The hidden subgroup problem is especially important in the theory of quantum computing for the following reasons:

Shor's quantum algorithm for factoring and discrete logarithm (as well as several of its extensions) relies on the ability of quantum computers to solve the HSP for finite Abelian groups.
The existence of efficient quantum algorithms for HSPs for certain non-Abelian groups would imply efficient quantum algorithms for two major problems: the graph isomorphism problem and certain shortest vector problems (SVPs) in lattices. More precisely, an efficient quantum algorithm for the HSP for the symmetric group would give a quantum algorithm for the graph isomorphism. An efficient quantum algorithm for the HSP for the dihedral group would give a quantum algorithm for the $\operatorname{poly}(n)$ unique SVP.

So post-quantum algorithms are built from problems that aren't equivalent to the Hidden Subgroup Problem for finite Abelian groups.
Symmetric Algorithms
For symmetric algorithms, the relevant threat is Grover's algorithm, which provides a speed up for the generic brute force search. Defending against this is simpler than defending against Shor's algorithm: Simply double the size of your keys and hashes, and everything should be ok.
This is why AES-256 (and 256-bit keys in general) are recommended for "long-term security" - a 128-bit key could be broken for 64 bits worth of cost once your adversary has a full scale quantum computer capable of running Grover's algorithm.


Security of hash functions over input extended with a random value Hashing a single message say $H(M)$ is vulnerable to a birthday attack.
But what if a combination is hashed, such has $H(M,R)$? Is it still vulnerable to the attack?

I think it is because $M, R$ can be assumed to be as $X$, so in essence $H(X)$ is being hashed and the birthday attack possibility still exists. Is this logic correct?

I think so cause $M, R$ can be assumed to be as $X$, so in essence $H(X)$ is being hashed and the birthday attack possibility still exists.

Yes, that's correct.

Note that there is no such function as $H(M, R)$, you'd need some way of combining the values; lets assume concatenation though (so $H(M | R)$).


How to decode an OTP message? First off, I'm extremely sorry if this comes off as a "homework dump", but to clarify, it isn't. I don't want the answer, I want to know how to get to the answer. My cryptography professor gave us an assignment to do, and without explaining this concept, he believes we all understand how to do it, and I definitely don't.

The problem is in two parts:

The one-time pad encryption of the message attack at dawn is 6c73d5240a948c86981bc294814d (the plaintext letters are encoded as 8-bit ASCII and the given ciphertext is written in hexadecimal) What would be the one time pad encryption of the message attack at dusk under the same OTP key?
The one-time pad encryption of the message attack at dusk is 6c73d5240a948c86981bc294814d (the plaintext letters are encoded as 8-bit ASCII and the given ciphertext is written in hexadecimal) What would be the one time pad encryption of the message attack at noon under the same OTP key?

Thanks for any/all help

If you know the plaintext and the ciphertext, getting the key is trivial.

$$c=m \oplus k$$

Try moving the terms around. Hint: $m$ and $k$ can be functionally swapped (change position with each other), ie. only one term needs to be secret. You already know one term. I've pretty much given you the answer.

About the decoding procedure: The ASCII table linked by Reid is a good resource. Alternatively you can use an online ASCII to Hex encoder to

get the binary representation of the ciphertext
get the binary representation of the known plaintext

and then do the prodecure on paper. Once you understand that you can write a Python script to do the job for you.

only one term needs to be secret: That's what I said above and I'll clarify because that statement is not accurate.

You need to know any 2 terms of the equation $x=a \oplus b$. to solve for any other term. That means $a=x \oplus b$ and of course $x= b \oplus a$. Therefore any stream cipher (or OTP) is secure as long as the adversary only knows one term (namely the ciphertext).


If a hash function $H$ is collision resistant, is it true that $H(x)\neq H(x')$ for all messages $x, x'$ with $x \neq x'$? I am puzzled with a question that seems to be based on theory.

If there is a collision resistant hash function (since it is not possible for a hash function to be collision free, this is a theoretical question),
would it be true to say that there are no two unique hash values for all possible messages $x$ and $x'$ where $x\neq x'$?

I feel like this would be true... Can anyone back me up on this?

As you correctly observed, for any function $H\colon \{0,1\}^\ast\to\{0,1\}^n$ collisions must exist, simply because $\{0,1\}^\ast$ is an infinite set and $\{0,1\}^n$ is finite.
One could define "hash function" to mean something else (e.g., taking only a bounded input length), but this is non-standard.

However, the term "collision resistance" denotes something different from what you seem to think: It just means that collisions are hard to find, in a computational sense.
We expect from a good hash function that nobody is able to find two inputs that lead to the same hash value, but we do not care about their abstract existence, which is a necessary evil.

Thus, no: Collision resistance does not mean that $H(x)\neq H(x')$ for any $x\neq x'$. It rather means that practically, nobody should ever find $x\neq x'$ with $H(x)=H(x')$.


Creating a hash of XOR'd blocks Suppose a message $m$ is divided into blocks of length $160$ bits: $m
> = M_1 || M_2 || ... || M_l$ And define $h(m) = M_1 \oplus M_2 \oplus ... \oplus M_l$

  Which of the three desirable properties of a good cryptographic hash
  function does h satisfy? Show that it does not satisfy the other two.

Three desirable properties of a cryptographic hash function
http://en.wikipedia.org/wiki/Cryptographic_hash_function#Properties

I feel like if there is only one, like the question states, it has to be the first one, preimage resistance.  However, given a hash $h = 000....0$
I can find a bunch of $m$'s that could give that particular hash.  Maybe since there are lots of solutions you can't pin point the specific $m$ that gave that value?

What do you think?

I believe that this is a poorly written question: such an $h$ obviously doesn't have either preimage resistance, second preimage resistance or collision resistance.

The inability to rederive the specific value of $m$ based on its hash is not an interesting property; it's pretty much true of any function which generates an output shorter than its input.

I don't know where you're getting these questions from; based on this question, I'd suggest you look elsewhere.


Benchmark for SHA-3 (Shake128) I am trying to find the average of hash rate (benchmark) for SHA-3(Shake128) for a normal and supercomputer in order to estimate the brute-force attack which I can get if from ( keyspace / hash rate )...then I found this website:

https://bench.cr.yp.to/results-hash.html

I could not understand these tables i.g. (Cycles/byte for 8 bytes) what do they mean by cycles/byte? Is it that hash rate for 8-bytes?

Cycles per byte means the number of CPU cycles that must elapse in order to process a single byte of input for a specific processor. A CPU's clock frequency determines how many cycles per second the processor is running at (for example, 2.6 billion per second for a 2.6 GHz processor). Note that this is a rather crude type of benchmark, because the bottleneck may not be waiting for each instruction to retire. Memory access latency, shared resources, etc. can slow things down.


Factoring $n$ in RSA knowing $e$ and $d$ I know that if $(n,e)$ is the public key in RSA and we also know $d$ the private key, then there is a probabilistic algorithm to factor $n$.
I'm reading the proof from Fact 1 on here.

I understand the proof until it says

"A straightforward argument shows that if $g$ is chosen at random from $\mathbb{Z}^*_N$ then with probability at least $1/2$ (over the choice of g) one of the elements in the sequence $g^{k/2}, g^{k/4}, \cdots ,g^{k/2^t} \mod N$ is a square root of unity that reveals the factorization of N."

Why is that last paragraph true?

Ok, lets see if we can go through one line of reasoning, and see if that makes sense.

If we have the sequence:

$$g^{k/2^t} \bmod N, g^{k/2^{t-1}} \bmod N, …, g^{k/2} \bmod N, g^k \bmod N$$

We know that the last entry evaluates to 1, and we are looking at the probability (for random $g$) that the entry immediately before the first 1 is a nontrivial squareroot of 1.

Now, we can consider the sequences modulo $p$ and $q$, namely

$$g^{k/2^t} \bmod p, g^{k/2^{t-1}} \bmod p, …, g^{k/2} \bmod p, g^k \bmod p$$

$$g^{k/2^t} \bmod q, g^{k/2^{t-1}} \bmod q, …, g^{k/2} \bmod q, g^k \bmod q$$

Now, we might not be able to compute these values before we know the factorization, but that's OK, we're just considering them.

Both sequences end in 1, and consist of a (possibly empty) sequence of non-1 values, followed by all 1 values.  In addition, $g^{k/2^i} \bmod N$ is a nontrivial squareroot of 1 if $g^{k/2^i} \bmod p$ is 1 and g^{k/2^i} \bmod q$ is the last non-1 value (or versa-vica).  In other words, we'll have a nontrivial squareroot if the two sequences turn into a 1 value at different positions in their sequences.

So, the question is: what is the probability bounds on that?

Now, if $g$ is a random (equiprobable) value in $\mathbb{Z}_N^*$, then $g \bmod p$ and $g \bmod q$ are equiprobable and independently distributed values in $\mathbb{Z}_p^*$ and $\mathbb{Z}_q^*$; hence both sequences are selected from random starting values.

And, half of the values of $g$ are quadratic residues modulo $p$ and half are quadratic nonresidues modulo $p$.  For a quadratic nonresidue, the mod-p sequence will become a one at step $t_p$ (where $p-1 = 2^{t_p} z_p$ for odd $z_p$; for a quadratic residue, it will be come one at an earlier step.  Hence, the maximum probability for any particular step will be 0.5.

The same logic holds for $q$.

Now, $g \bmod p$ and $g \bmod q$ are independent variables, and so the maximum coincidental probability will occur if both chains have two stages with probability 0.5 each; in that case, the probability that they are difficult will be $1 - (0.5 \cdot 0.5 + 0.5 \cdot 0.5) = 0.5$

This argument could be tightened up a bit; however it should be enough to give you some insight...


Proving that a function is not invert-able (one way function) I am having problems with proving if the one-way function (https://crypto.stackexchange.com/tags/one-way-function/info) is hard to invert or not.

$2^\sqrt {m} $ one-way function  $ f: \{0, 1\}^{2m} \to \{0,1\}^{2m} $

and $ g(x) = f(0...0^m || x_1, x_2, \ldots, x_m) $  $ g: \{0, 1\}^{m} \to \{0,1\}^{2m} $ (the || means here concatenation). Is function g one-way and what could be told about its security?

I think you can prove $g$ is not guaranteed to be one-way by the following counter example. First let $S$ be the set of all strings in $\{0,1\}^{2m}$ that starts with $m$ zeroes. Take any OWF $f$ of the type you describe. Consider the function $f'$ that is identical to $f$ except on all inputs $x \in S$ it acts as the identity function. I.e. for all $x \in S$ we have $f'(x) = x$. Now if you use $f'$ to construct $g$ then $g$ will clearly not be one-way (because this means $g$ is just the identity function). So all you need to prove is that $f'$ is still a OWF.

Now I sketch an argument that $f'$ is in fact a OWF. Since $f'$ only changes the output of $f$ on a negligible amount of inputs, the distribution of output of $f'$ and $f$ on a uniformly random input should be statistically indistinguishable. However, if there exists an adversary $A$ that demonstrates that $f'$ is not a OWF, then that adversary would work as a distinguisher between the two output distributions. Thus,  $~f'$ must be a OWF.

I am not sure this is 100% watertight, so you may want to work through the proof yourself :).


Weakness in using only one RSA key pair for two-way communication? In Alice/Bob/Cindy terms (EDIT: and with a little more detail):

Alice and Bob have each securely obtained one key of an RSA keypair from a trusted third party. Alice has one key ($e$ and $n$), Bob has the other ($d$ and $n$, where $d\equiv e^{-1} (mod\ \phi(n))$).

The RSA algorithm technically does not care which of the two keys is used to encrypt and which to decrypt; if $c_1 \equiv m^e (mod\ n)$ and $m \equiv c_1^d (mod\ n)$, then $c_2 \equiv m^e (mod\ n)$ and $m \equiv c_2^d (mod\ n)$. ($c_1 \neq c_2$)

Therefore, Alice uses $e$ and $n$ to encrypt a message $m_a$ into ciphertext $c_a$ and sends it to Bob, who decrypts it with $d$ and $n$, then encrypts his response $m_b$ with the same $d$ and $n$, and sends the ciphertext $c_b$ to Alice who can decrypt it with $e$ and $n$. Thus, one pair of asymmetric keys is being used to form a two-way communication channel, instead of the normal one-way usage.

Now, Cindy does not know $e$, $d$, or $n$, or any artifact used to produce them, such as $p$ and $q$. she can only see $c_a$ and $c_b$ as they are passed between Alice and Bob. Given that all other security concerns with RSA are properly handled, such as $\geq$2048-bit keys and OEAP padding scheme, is there an "efficient" way (an attack) by which Cindy can obtain $m_a$ and/or $m_b$?

The question and comments seem to be asking the following:  If an implementation of RSA is used in the following way, is it still secure?  An RSA modulus $N = pq$ and exponent $e$ are generated, and (N,e) is given to Party $A$ and $(p,q,e)$ is given to Party $B$.  Then, the parties encrypt their communication where Party $A$ encrypts using the modulus and exponent, while party $B$ encrypts using the private primes and the exponent.

To really answer the question, we'd have to define what encryption padding method is being used (OAEP, PKCSv1.5, etc) and what notion of "secure" we want.  We'd also have to define what it means to encrypt with the secret key instead of the public key.  But as long as the encryption methods with either key are generating the same ciphertext (more precisely, the same distribution over ciphertexts), then whatever reasonable security notion we want will be achieved in this setting under the same hardness assumptions.  This is because the adversary is seeing ciphertexts that are all indistinguishable for ciphertexts generated in the usual way, so the basic security achieved will transfer over easily in provable way.


Is Wiener's attack on RSA extendable to larger keys with low hamming weight? Using small private exponents with RSA improves performance.

However, it has been shown (Wiener, 1990) that if $\log d \leq \frac14 \log N$, the private exponent $d$ can be reconstructed from the public key $(N,e)$.

Smart, Inc. uses special private keys designed such that they are:

Larger than the minimum bound recommended by Wiener, and
Still very efficient because of their low Hamming weight

Are such keys safe to use?
How could one reconstruct the private keys from the public?

I did some research and think that Wiener's attack might be on the right track.

First, you have a typo in your question. Wiener's attack works if $\log(d) < 0.25 \log(N)$.
This is not the best possible attack. "Boneh and Durfee" improved the result to $\log(d) < 0.292 \log(N)$.

I'm not aware of any better result, but that does not mean such results do not exist.
In particular, it is quite unclear whether it would help an attacker to know that the Hamming weight of the private key is small.

Generally, it is very risky to use these corner cutting techniques. There are countless proposals for speeding up RSA by generating the private key in a particular way that already.

A good overview over the topic is Alexander May's thesis. This thesis is a few years old, but does nicely show what kind of attacks are possible, and more importantly how complex this subject is.

I would recommend not to use any RSA implemenation that tries to optimize performance by fiddling with the secret key.


Do I need to generate unique IV for CBC encryption of a file if I encrypt multiple blocks of data? The situation is that I download a mp3 file (song) and I encrypt blocks of data (4096 bites for example).
The output of every encryption operation I save it in a new file.

When I play the song (encrypted file) I work with buffers. If I seek near the end of the song, for example, I need to somehow extract the IV that I used for encryption.

How can I generate a safe IV for encryption  and be able to decrypt in this situation ?

The question tells CBC is used. I assume that, even though the suggestions to use CTR are good. I consider a block cipher with block size of $b$ octets (e.g. $b=8$ for DES/3DES, $b=16$ for AES), and that the IV used at encryption (possibly random) is stored in the first $b$ octets of the encrypted file, with the ciphertext following.

With CBC, decryption can start at any position in the file. To decipher from octet at offset $n\ge b$ in the enciphered file (offset $n-b$ in the original file), start reading at offset $b(\lfloor n/b\rfloor-1)$, read $b$ octets from there and use that as IV, start deciphering normally but discard the first $n\bmod b$ octets. When $b$ is a power of two (which is most common), in C or similar languages, start reading the IV at offset ((b-1)|n)-(2*b-1) and skip (b-1)&n octets.

In the case of streaming audio or video, this simplifies to: make $n$ a multiple of $b$ (typically, a multiple of 4096 will do), use the first $b$ octets as IV, and play what's deciphered with a player that mutes until it found a sync pattern.


Which is better ECDHE with TLS 1.0 I have a webserver which only supports TLS 1.0 and I am not sure about something: Which is the better cipher in this group when aiming for the best security?

TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA (0xc00a)
TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA (0xc014)
TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA (0xc009)
TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA (0xc013)
TLS_ECDHE_ECDSA_WITH_RC4_128_SHA (0xc007)
TLS_ECDHE_RSA_WITH_RC4_128_SHA (0xc011)
TLS_ECDHE_ECDSA_WITH_3DES_EDE_CBC_SHA (0xc008)
TLS_ECDHE_RSA_WITH_3DES_EDE_CBC_SHA (0xc012)

I chose only ciphers with ECDHE for Perfect Forward Secrecy. Speed is not very important, for me secure is more important.

These ciphers are used in my Java application for retrieving data from a HTTPS website. My doubt was due to the fact that the CBC Ciphers are vulnerable to BEAST Attacks.

The best option you have is TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA. This is likely to provide most security, as the AES keylength is maximal and ECDSA keys tend to provide more security than RSA keys, as a 128-bit security level is quite common with ECDSA (field size: 256 bit) whereas 112-bit is the standard with RSA (keylength: 2048 bit).

However in practice TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA may be easier to deploy as RSA certificates are usually a lot cheaper and easier to get.

To get even further you're also fine with TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA and TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA as a 128-bit key is quite common today and chances are your ECDH group also provides "only" 128-bit security, meaning you can get higher speed without sacrificing security.

As explained in the comments by CodesInChaos you should definitely avoid RC4, which is also officially banned from TLS as per RFC 7465. To repeat what CodesInChaos said:
 The CBC-suites are less an issue than RC4 because ...

modern browsers mitiagate BEAST (CBC-based attack) even on TLS 1.0
BEAST is an active attack, whereas RC4 already falls due to passive attacks
BEAST is hard to exploit in practice and relevant features seem to have been removed.

This removes the TLS_ECDHE_RSA_WITH_RC4_128_SHA and TLS_ECDHE_ECDSA_WITH_RC4_128_SHA ciphersuites from the list. You should also avoid 3DES, as it provides "only" 112-bit security, but is significantly slower than AES making it inferior in every aspect, so you shouldn't choose TLS_ECDHE_RSA_WITH_3DES_EDE_CBC_SHA nor TLS_ECDHE_ECDSA_WITH_3DES_EDE_CBC_SHA.

However, if possible you should migrate to TLS v1.2 (or newer). There you should avoid all cipher suites not finishing with ..._SHA256 or _SHA384 as the other ones use SHA-1 which is deprecated. Furthermore TLS v1.2 (or newer) allows (v1.3 will force) you to use non-CBC mode ciphers, especially AEAD ciphers, which don't suffer from BEAST or similar attacks. This means that as of now the best choice (in terms of security) for the cipher suite is TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384, with TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 not being a lot weaker. If possible you should prefer ECDSA (or EdDSA) over RSA although RSA can be sufficiently secure when using appropriate keylengths.


Is it possible to anonymize web traffic so that the IP Address cannot be determined while still being able to determine distinct IPs? I'd like to find a way to anonymize IP addresses in web logs to ensure user privacy given the following requirements:

If given an IP address, there is no way to look up which requests came from the IP address.
Given the set of requests, it can be determined which requests came from the same IP address.

This way no one (including an attacker) can determine the original IP addresses from the log.  An attacker (anyone with access to the log) would be able to determine which IPs are distinct, though.

I'm envisioning something like the this.  Each request is sent through a function that creates a unique identifier for each IP address (notice that request 1 and 4 are from the same IP address, but result in different hashes).

Request 1 - 192.168.0.1 => EIDKSJD
Request 2 - 192.168.0.2 => GIEKDJS
Request 3 - 192.168.0.3 => CIDJSDJ
Request 4 - 192.168.0.1 => DJCUDJS

But there is another function that takes two outputs and determines if they came from the same IP.

same_parent(EIDKSJD, GIEKDJS) returns false
same_parent(EIDKSJD, DJCUDJS) returns true

This method has it's downsides, specifically that searching for duplicates is not efficient.  If there's a method that is efficient for searching and meets criteria 1 and 2 above, I would up-vote twice if I could :).

In general, against an attacker that has fully compromised your webserver, your full requirements are unsatisfiable.

The reason is that, in order to find out which requests have been made from a given IP address, the attacker can always simply fool your server into thinking it has received a request from that address, and then compare the resulting log entry to the others.  (Of course, there may be more direct ways to achieve the same result, but this is a generic attack that works against any scheme.)

Conversely, against attackers who don't have full access to your webserver, but only to the logs, there's a simple solution: store a secret key on the server (in some way that will keep it out of the attacker's hands) and tag each log entry with HMAC(key, address).  Without the key, an attacker cannot distinguish HMAC from a random function; in particular, they won't be able to tell anything useful about the HMAC tag except that each IP address corresponds to a particular tag.

However, it's generally pretty hard to ensure that attackers can't get the key (and can't otherwise fool the server into logging a fake request) even if they can somehow get access to the database.  Just storing the key in, say, a secure hardware security module isn't enough, since the generic fake request attack still applies, so basically you need to harden your entire webserver.

You'll also want to make sure that your server isn't vulnerable to IP spoofing, e.g. by making sure that your TCP sequence numbers are unpredictable, and that requests are only logged after packets have been exchanged both ways between the client and the server.  Otherwise that would provide yet another way to create fake log entries without having to directly compromise the webserver at all.


What can be learned from the ciphertext of LibSodium's crypto_box_detached()? LibSodium, (https://github.com/jedisct1/libsodium), has a function crypto_box_detached() which does authenticated encryption using the public key of the recipient and the private key of the sender (using Curve25519). I believe this function is compatible with Daniel J. Berinstein's corresponding function in NaCl (http://nacl.cr.yp.to/), although with a different interface.

If Alice creates a message for Bob using this function and a random nonce, is it possible for Eve to distinguish the ciphertext+MAC from random data?
What about if Eve has the public keys of Alice and Bob, does that make it easier to distinguish it from random data?
If Eve has their public keys, can she in any way deduce that the message came from Alice or that it is destined for Bob?

I'll answer the related questions in order:

No, because a ciphertext (generated from a key stream generated by a stream cipher)  should be indistinguishable from random data, and a MAC should be as well.
No, because #1 depends on the secret, and the secret was derived using a Diffie-Hellman key agreement algorithm, using the given curve. To know information about the secret, it is required to obtain one of the private keys.
No, because that follows directly from #1 and #2.

Notes:

traffic analysis is not taken into account for this answer as it is outside the scope of the cryptographic properties;
the size of the ciphertext (equal to the plaintext size) + MAC size may leak some information to an attacker.

It seems that the detached variant was explicitly defined to separate the tag and the ciphertext, so it seems a bit strange to talk about ciphertext + MAC (only the order of ciphertext and MAC seems different from the non-detached variant of the same method).


How can I show that the DDH problem is self-reducible? I have trouble to understand how I can show that the Decisional Diffie-Hellman problem (DDH) is self-reducible.

I found this as a description of a random self-reducible problem.

Given an instance I1, it can be solved as follows:
(a) transform I1 into a uniformly random instance I2
(b) solve I2 and
(c) transform the solution for I2 into a solution for I1

Can someone (try) to explain me how I can show that the Decisional Diffie-Hellman problem (DDH) is random self-reducible based on these 3 steps ?

What we have to show for random self reducibility is that we can reduce an efficient algorithm for solving an arbitrary
(worst-case) instance to an algorithm that solves a random instance efficiently. Consequently, an efficient algorithm for the
average case implies an efficient algorithm for the worst case. You already have outlined how this is technically done in your question and I'll show you a construction for the computational version of this problem.

Example CDHP

Let $G$ be a group (w.l.o.g. of prime order $p$) generated by $g$. The CDH is given two elements $g^a$ and $g^b$ and to
compute $g^{ab}$.

Lets say we have a solver $\cal A$ for CDHP in $G$, then we can construct an algorithm $\cal B$ that uses $\cal A$
as an oracle and $\cal B$ solves any instance of the CDHP in $G$ with the same probability as $\cal A$ and only
requires "a little" more time than $\cal A$ (see below the time required for the sampling of the elements and the
extra arithmetic that has to be done).

It goes like this:

$\cal B$ receives $(u=g^a,v=g^b)$ as input and does the following:

Choose uniformly at random elements $x,y$ from ${\mathbb Z}_q$
Compute $u'=ug^x$, $v'=vg^y$ and run $\cal A$ on $(u',v')$
Take the output $w'$ of $\cal A$ and do the following: compute $w=w'\cdot u^{-y}\cdot v^{-x}\cdot g^{-xy}$
Output $w$ as solution to the CDHP for instance $(u,v)$.

Observe that if $\cal A$ solves the CDHP then also $\cal B$ solves the CDHP, since then

$w'=g^{(a+x)(b+y)=ab+ay+xb+xy}$ and thus

$$w=g^{ab+ay+xb+xy}\cdot u^{-y}\cdot v^{-x}\cdot g^{-xy}=g^{ab+ay+xb+xy-ay-xb-xy}=g^{ab}.$$

Note that due to the "blinding" in step $2$, the instance for $\cal A$ is uniformly distributed and independent from the original instance to the CDHP $(u,v)$, i.e., a "fresh" random instance.

I only have argued informally and let the exercise to write the analysis down formally to you.

DDH

Having this example it should not be too hard to devise such a reduction for the DDH.


Parallel hash construction I'm wondering why hash constructions aren't parallel like CTR mode for encryption?

For example: We have ideal block cipher E, where we encrypt message block with counter and xor output block with message block. Then we xor (sum) all blocks and encrypt it with length of message and xor with sum of all blocks to get hash. If last message block is shorter than block size it is padded with zeroes.

$H_{0} = E_{0}(m_{0}) \oplus m_{0}$

$H_{1} = E_{1}(m_{1}) \oplus m_{1}$

$...$

$H_{n} = E_{n}(m_{n}) \oplus m_{n}$

$H_{sum} = H_{0} \oplus H_{1} \oplus ...\oplus H_{n}$

$H = E_{Length}(H_{sum}) \oplus H_{sum}$

Is such construction known to be insecure? Or is it secure?

Dmitry said that a collision in the xor can be found with a generalized birthday attack.

Actually, it's a lot worse than that; second preimages of sufficiently long messages can be found in polynomial time; hence an enormous block size (which might help against the birthday attack) doesn't help.

Let us call the size of the output of the ideal block cipher $n$.  Then, let us consider a message that consists of (at least) $n$ blocks; and for each block, we consider two distinct alternatives, at position $i$, we would have arbitrary selected blocks $M_i$ and $M'_i$.

We would then compute $H_i = E_i( M_i ) \oplus M_i$ and $H'_i = E_i( M'_i ) \oplus M'_i$.

If we have a target value $Z$ for the exclusive or's (which we would have for a second preimage problem), we would then consider what sum of $H_i$ and $H'_i$ would exclusive-or to the target values; this can be viewed as a linear algebra problem, and can be solved with, say, Gaussian elimination in time $O(n^3)$


How to decrypt using CRT, and then verify by encrypting without CRT? Here is the actual question that I need to answer:

An RSA encryption scheme has the set-up parameters $p = 31$ and $q = 37$. The public exponent is $e = 17$.

Decrypt the ciphertext $y = 2$ using the CRT.
Verify your result by encrypting the plaintext without using the CRT.

I have figured out the answer for the first part: $x = 721 \bmod 1147$, but I am unsure how to encrypt it. I know that using RSA would mean: $y = e_{kpub}(x) \equiv x^e \mod n$, where $x,y \in \mathbb{Z}_n$, so it should be as easy as $721^{17} \bmod 1147$, but this is a huge number that I cannot work with. I am pretty sure that I should use the square and multiply algorithm, but I don't understand how, and my textbook is not clarifying.

I know that $x^{17}$ means #MUL + #SQ= 5, but what do I do with this information? The textbook does not describe this well.

I could really use some help!

The square and multiply algorithm allows you to compute $g^k$ in an arbitrary group using $O(\log k)$ multiplications, instead of the $O(k)$ you would expect.
This is done by letting:
$$k = \sum_{i = 0}^{\lceil \log_2 k\rceil} 2^i k_i,\quad k_i\in\{0,1\}$$
To be the base-2 decomposition of $k$.
Then, we have that:
$$g^k = g^{\sum_{i = 0}^{\lceil\log_2 k\rceil}2^ik_i} = \prod_{\substack{0\leq i \leq \lceil\log_2 k\rceil\\k_i = 1}} g^{2^i} $$
I'll demonstrate the computation for your particular case, where we want to compute $721^{17}\bmod 1147$.
Note that for modular arithmetic, we additionally have Euler's Theorem to work with, which states that:
$$x^{\varphi(N)}\equiv 1\bmod N$$
Where $\varphi(N)$ is Euler's totient function.
Using basic properties of $\varphi$, one can compute that $\varphi(31\times 37) = 30\times 36 = 1080$.
So throughout our computations, we have the identity $x^{1080}\equiv 1\bmod 1147$ (which unfortunately ends up not being useful).

One can compute by hand that $721^2 = 519841$, which we can then reduce mod $1147$ to get $721^2\bmod 1147 = 250$.
We can repeat this to find that $250^2 = 62500$, which we reduce mod $1147$ to get 562.
We square this again to get 315844, which we reduce mod 1147 to get 419.
Finally, we square this again to get 175561, which we reduce mod 1147 to get 70.

Collecting together these computations, we get:
\begin{align}
721^{2^0} &= 721 \mod 1147\\
721^{2^1} &= 250 \mod 1147\\
721^{2^2} &= 562 \mod 1147\\
721^{2^3} &= 419 \mod 1147\\
721^{2^4} &= 70 \mod 1147.
\end{align}
Note that $17$ decomposes base 2 as $1 + 16 = 2^0 + 2^4$.
We can then find the result via:
$$721^{2^0}\times 721^{2^4} = 721\times 70\mod 1147 = 50470 \mod 1147 = 2\mod 1147$$

You may look at this and think it still involved a ton of multiplications of three digit numbers.
This is true --- this is the group operation in $(\mathbb{Z}/1147\mathbb{Z})^*$, so one expects to have to do it a number of times.
You can count to see that we only used 5 multiplications, instead of the 16 one would naively expect. It's still not great to do by hand though, but the only way I know of making the computations better by hand is by using the Chinese remainder theorem, which you specifically don't want to be used.


Is this encryption algorithm built from MD5 secure? I'm being asked to use an encryption algorithm in my code, and besides the fact that I'm sure there will be implementation faults that lead to vulnerabilities, I also have concerns about the algorithm itself. I'd like to know how strongly I need to convince these guys to not use this. If it is an acceptable algorithm and there is a name for it, I'd like to know so I can find an implementation of it somewhere (I've been trained to not implement my own crypto).

I'm not a cryptographer, and this is coming from a large company and from people with much more programming experience than I have, so if I do need to convince people not to use this, it will be difficult.

The algorithm starts with a secret concatenated with a random string the length of an MD5 digest.
It MD5-digests this initial string and XORs the digest with the input data (up to the length of the MD5 digest).
It takes the result of that XOR operation, saves it to the output buffer and digests it concatenated with the original secret to get a new digest.
Then it keeps going until it has covered the whole input.

The goal of this scheme is to allow messages to be read by parties who know a secret and to not allow those messages to be read by parties who don't know the secret.

Now that I understand the notation, I can make this clearer:

$C_1 = M_1 \oplus \operatorname{MD5}( secret || random )$

$C_n = M_n \oplus \operatorname{MD5}( secret || C_{n-1} )$

I also don't understand how this is to be decrypted. It seems like the same random string is needed for that, in which case, we have the problem of how to get the random string to the other parties – is it okay for that part to be sent in plaintext?

The algorithm (now reasonably clear) is reminiscent of a block cipher in CFB mode, with $random$ as the IV (which can be public), $secret$ as the key, and MD5 used as keystream generator instead of the block cipher.

Decryption works as in CFB:
\begin{align*}
M_1 &= C_1 \oplus \operatorname{MD5}( secret\mathbin\|random )\\
M_n &= C_n \oplus \operatorname{MD5}( secret\mathbin\|C_{n-1} )
\end{align*}

If MD5 was secure in the Random Oracle Model, that would be as secure as a 128-bit block cipher in CFB mode. Although MD5 is not secure in the ROM, I do not see an attack compromising the confidentiality of the message in a non-interactive attack, assuming the $secret$ is unguessable and $random$ not reused. In particular, I do not see that the feasibility of MD5 collisions, or MD5's length-extension property, directly enable an attack.

Main issues are:

This is unsafe if $secret$ is short or/and susceptible to enumeration, for there is no key stretching used.
This is unsafe if the attacker can inject something in the message being encrypted, based on earlier ciphertext blocks in the same message.
This is unsafe if the deciphering side reveals deciphered messages that do not make sense, and the attacker can modify the ciphertext.
There is no attempt at protecting the integrity of the message.
No test vectors are given.
This is inefficient compared to a block cipher (but in a context where MD5 is the only efficiently implemented cryptographic primitive, it might still beat a block cipher coded in an interpreted language).
MD5's name is tarnished, it has known weaknesses, and attacks only get better.
The whole thing is not an established algorithm, and nothing in the present answer constitutes any form of endorsement, much to the contrary.


Is it safe to hash a packet with a shared secret to prove authenticity? I am developing an online game, where the server is written in Node.js and the client uses Godot. The issue is that Godot has no cryptographic functionalities (it can only encrypt and decrypt files, not elements in memory).

As implementing cryptographic functionality would be out of my capabilities with Godot, I've been thinking of a way to authenticate UDP packets.

I have the following idea: client logs in via HTTPS and gets a refresh token, and a shared (with the server) secret. The refresh token is used to renew the secret every 10 mins.

To authenticate UDP packets (which are sent unencrypted), the packet contents are hashed with the secret included, the packet is sent with the hash. Then the other side verifies that the hash with the secret is valid.

Is this approach secure enough? Considering that the secrets would be randomly generated long strings, would an attacker be able to calculate the secret by analizing several packets? My options for hashing are MD5 and SHA256 which are the algorithms available in Godot.

Being that UDP is only used for game events which don't need extreme security (so no personal information, payment details etc are ever sent in this channel), would this work?

From what you I described I understand your scheme to be following:
Each message $M$ gets a tag $T$ which is $H(S \mathbin\| M)$ where $H$ can be MD5 or SHA2 and $S$ is a common secret. Both hash functions are vulnerable to a length-extension attack effectively allowing to compute $H(S\mathbin\|M\mathbin\|x)$ from $H(S\mathbin\|M)$ and the length of $M$ so your scheme should not be used for authentication.

A better alternative would be to use a message authentication code (short MAC), which is a group of algorithms specifically crafted for cases similar to yours, including the widespread HMAC which allows to turn even broken hash-algorithms like MD5 into relatively secure MAC's.


How do high hash rates affect hashed password security? Given the increase in hash rate since the rise of numerous block chains, I wonder how this affects the security of many hashed password systems.

Is a standard linux /etc/shadow file still regarded safe or does it somehow need to be updated with another algorithm or bigger salt or in some other way?
Are hashed passwords using hmac with sha256 safe given a 20 character long secret key? Can someone give some rough calculations to give an idea how long it takes to find a password?
Is it advisable to use hmac with a slower algorithm like bcrypt, scrypt or PBKDF2?

By "safe" I mean can modern hardware like ASIC reproduce a given hash in a reasonable amount of time. Some background context to my question. User input will be one way encrypted (hmac sha256) stored in a database. Suppose the database is hacked, how hard is it for an attacker to find original user input. If it turns out this type of encryption is too easy for asic machines, should I switch to some other one way encryption like bcrypt or pbkdf2?

Linux uses "sha512crypt", which isn't memory-hard but is fine given a moderately strong input passphrase.

HMAC-SHA256 isn't a password-hashing algorithm. It's not even a hash function. It requires a uniformly-random secret key which it uses on a message to produce a Message Authentication Code (tag) of that message under that key. The password-based key derivation function PBKDF2 uses HMAC internally to create a KDF, which can also be used as a password-hashing function. The rest of this question is impossible to answer: a 20-character long secret key just doesn't define much. "Character" isn't well-defined. 16 bytes, chosen uniformly at random (ie 128 bits) will be secure as the key for HMAC-SHA256. No password is used in such a system, since HMAC doesn't take a password.

This question is nonsense. It's impossible to use HMAC with PBKDF2, since PBKDF2 uses HMAC. Likewise bcrypt isn't a cryptographic hash function and therefore violates some of the assumptions used in HMAC's security proofs.

Use Argon2id for your password hashing function if possible. If that's impossible, use bcrypt. If that's impossible, use PBKDF2-HMAC-SHA256 (I doubt you've got scrypt in that case).
Use the EFF Long Word List and 5 good-quality dice, and pick a passphrase long enough for your desired security. Each word is just over 13 bits of entropy, so 7 words is 91 bits (safe for the next few decades), 10 words is 130 bits (definitely safe for the next few million years unless the attacker has a really big quantum computer), 20 words is 260 bits (safe even against planet-sized quantum computers for a few million years). If you're using 10 words or more, password-hashing function choice doesn't really matter much.


Quadratic Residues in identification setting Suppose Alice has two primes $p$ and $q$ such that $p\equiv q \equiv 3 \pmod 4$. $n=p\cdot q$ is part of her certificate to identify her. A party say Bob, sends her a random quadratic residue ${}\bmod n$, say $x$. To identify her, Alice computes $y$, a square root of $x$ and send it to Bob. He simply verifies $y^2\equiv x\pmod n$.

This completes the verification but Bob can now impersonate Alice. I am stuck trying to find what information does calculating square root modulo $n$ leak. I am guessing it has something to do with the fact that $p\equiv q \equiv 3\pmod 4$.

My question is after this, how can Bob calculate a square root modulo $n?$ That is if someone, say Eve, sends Bob a quadratic residue ${}\bmod n$, say $z$, how can Bob calculate a square root, say $d$, i.e, $d^2\equiv z\pmod n$, i.e., how can Bob convince Eve that she is communicating with Alice?

The problem with the protocol isn't specifically that it allows Bob to perform square-roots on his own; it's that it allows Bob to deduce the factorization of $n$ with high probability (and with that, he can perform square-roots).

Here's how Bob would do this:

He selects a random value $0 < r < n$, computes $x = r^2 \bmod n$, and sends $x$ to Alice.
Now, $x$ actually has 4 square roots modulo $n$ (unless $x$ happens not to be relatively prime to $n$; that's improbable).  Alice picks one of the four, and returns that value $y$ to Bob.
Bob now has two values $r$ and $y$ with $r^2 \equiv y^2 (\bmod\  n)$, or in other words, $r^2-y^2 = (r-y)(r+y) = kn$ for some integer $k$ (note: this equation is in the ring of integers, not in the ring of integers modulo $n$).
If $r \ne y$ and $r \ne -y$ (probability 0.5, because $r$ was selected randomly, and $y$ has 4 possible values, 2 of which satisfy one of the relations, and 2 of which satisfy neither), then $(r-y)(r+y)$ is a multiple of $n$, but neither $(r-y)$ nor $(r+y)$ is a multiple of $n$.  Hence, one of $r-y$, $r+y$ must be a multiple of p, and the other must be a multiple of q.

That is, a straight-forward computation of $gcd( n, r+y )$ directly yields one of the prime factors of $n$.

This happens with probability 0.5; if Bob knows how Alice selects which of the four possible square roots (e.g. she always selects the one that is itself a quadratic residue), then he can increase this probability by putting conditions on the $r$ he selects.


OpenSSL PBKDF2 documentation I'm using OpenSSL 0.9.8 on OSX Maverick, and I want to use a PBKDF but I can't find any doc/man about it on OpenSSL's website.

I'm working on QCA, an OpenSSL wrapper for Qt, and when I arrived there was PKCS5_PBKDF2_HMAC_SHA1 as PBKDF2, a function I can’t find either on the OpenSSL website. It's marked as DEPRECATED on OSX, so my questions are: Is there one or multiple PBKDF2 on OpenSSL? If there is/are, does anyone know where I can find the documentation please?

In 0.9.8 there is only PKCS5_PBKDF2_HMAC_SHA1.

Sample C code:

#include <openssl/evp.h>
#include <openssl/sha.h>

void PBKDF2_HMAC_SHA_1nat(const char* pass, const unsigned char* salt, int32_t iterations, uint32_t outputBytes, char* hexResult)
{
    unsigned int i;
    unsigned char digest[outputBytes];
    PKCS5_PBKDF2_HMAC_SHA1(pass, strlen(pass), salt, strlen(salt), iterations, outputBytes, digest);
    for (i = 0; i < sizeof(digest); i++)
        sprintf(hexResult + (i * 2), "%02x", 255 & digest[i]);
}

In 1.0.1 there is also PKCS5_PBKDF2_HMAC, which allows passing in different underlying hash functions.

Sample C code for PBKDF2-HMAC-SHA-512:

#include <openssl/evp.h>
#include <openssl/sha.h>

void PBKDF2_HMAC_SHA_1(const char* pass, const unsigned char* salt, int32_t iterations, uint32_t outputBytes, char* hexResult)
{
    unsigned int i;
    unsigned char digest[outputBytes];
    PKCS5_PBKDF2_HMAC(pass, strlen(pass), salt, strlen(salt), iterations, EVP_sha512(), outputBytes, digest);
    for (i = 0; i < sizeof(digest); i++)
        sprintf(hexResult + (i * 2), "%02x", 255 & digest[i]);
}


Can AES-CTR add values without decryption? I recently have studied AES cipher. On CTR mode, is it possible to add, subtract, or XOR plaintext values on encrypted data?

For example: we have an encryption of $4$ and $6$ under the same AES key, respectively denoted by $AES(4)$ and $AES(6)$.

Without decryption, can we achieve the following?

$$AES(4)⊕AES(6)=AES(4+6)$$

Where "$\oplus$" is any operation we can do over AES.

No, with AES in CTR mode, it is not

  possible to add/subtract(or XOR?) plaintext values on encrypted data

nor define operator $\boxplus$ such that $\operatorname{AES-CTR}(4)\boxplus\operatorname{AES-CTR}(6)=\operatorname{AES-CTR}(4+6)$ that works for unknown key and plaintexts. Informally: if that worked, it would be a weakness of the encryption scheme, which would be leaking information about plaintexts from the ciphertexts.

Notice that the above notation is misleading, as the result of AES-CTR depends on 3 parameters: Key, IV and plaintext, with IV normally random (making the argument above non-rigorous). But still, even if we assume fixed IV, what's asked can't be done: it is asking an operator $\boxplus$ such that $\forall s,\forall x,\forall y, (s\oplus x)\boxplus(s\oplus y)=s\oplus(x+y)$ where $\oplus$ is XOR, and $s$ is whatever the IV encrypts to under the key considered; which is impossible.

More generally, no secure mode of operation of any secure block cipher allow homomorphic encryption.


Can the access policies defined using different access structures (Monotone Span Program and Access Trees) be used together in CP-ABE scheme? In order to add authentication features to this CP-ABE scheme, I have tried to combine it with the ABS scheme proposed by Maji et. al.

I want to use the sign() and verify() algorithms of ABS scheme. But the problem is that the two scheme support different access policy structures; CP-ABE uses access trees to define access policy whereas the ABS uses monotone span program (MSP).

What changes are necessary for the two access policy structures to work together? For example, can I translate an MSP access policy to an access tree?

Can the access policies defined using different access structures (Monotone Span Program and Access Trees) be used together in CP-ABE scheme?

Yes. As Attribute-based signcryption with hybrid access policy (Yu and Cao, 2015) shows, it is possible to combine an Attribute-based Encryption scheme with an Attribute-based Signature scheme of different access structures and different flavors. This is commonly referred to as Attribute-based Signcryption.

  What changes are necessary for the two access policy structures to work together?

That would be a longer answer along with the necessary security game.

  For example, can I translate an MSP access policy to an access tree?

Yes, because a monotone access tree has the same expressiveness as a Monotone Span Program. I don't know whether there is an algorithm for this. It is usually done the other way around. For example, access tree to LSSS is described in Efficient Generation of Linear Secret Sharing Scheme Matrices from Threshold Access Trees (Liu, Cao, Wong, 2010).

Note that a Monotone Span Program (MSP) is equivalent to a Linear Secret Sharing Scheme (LSSS). Again, I'm not sure if there is an algorithm of doing the translation out there.