In RSA, how does the CPU deal with this huge modulus (8192 bits)? Whilst I understand how the RSA algorithm works, I don't understand how the CPU operates when it needs to use the mod function with a huge number $n$, for example.

$n = 8192$ bits;
$c = m^e \mod n$;

In essence my question is how does the CPU deal with this huge modulus?

It (or rather, the software running on it) will use arbitrary-precision ("bignum") arithmetic.  The way this works is basically the same way in which you (probably) learned to do arithmetic on paper at school.

The arithmetic taught to us humans at school is base-10 arithmetic — that is, we represent numbers as strings made up of ten different digits, from "0" to "9", where each digit alone represents a different small number below 10, and where placing a digit to the left of another digit multiplies its value by 10.

Assuming you didn't totally sleep through grade school, you probably remember having to memorize the addition and multiplication tables for single-digit numbers: 1 + 1 = 2, 7 + 7 = 14, 6 × 4 = 24, and so on.  Those are the basic "atomic" operations for base-10 arithmetic, and once you know how to do them, you can combine them to calculate things with larger numbers.

(You don't have to have the basic operations all perfectly memorized, of course; if you, say, forget what 7 × 6 is, but still remember that 6 × 6 = 36, you can just count six more numbers up from that to end up at 42.  And even if you were to forget what e.g. 7 + 7 is, you could, say, count on your fingers to arrive at 14.  It just turns out that, for us humans, memorizing those basic single-digit operations — i.e. implementing them with the human equivalent of a look-up table — makes arithmetic a lot faster than working them out from first principles every time.  For computers, the tradeoff may be different.)

For example, depending on how math was taught at your school, you may remember writing down an addition problem on paper something like this:

Exercise: 12345 + 67890 = ______

             <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
             <-- result

and the working it out digit by digit, from right to left.  Here, you'd start with 5 + 0 = 5 (with no carry):

       0     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
        5    <-- result

and then proceed to 4 + 9 = 13 (i.e. write down 3, carry 1):

      10     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
       35    <-- result

and then 1 + 3 + 8 = 4 + 8 = 12 (i.e. write down 2, carry 1), and so on all the way to:

    1110     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
    80235    <-- result

You may have also learned similar pencil-and-paper algorithms for other elementary arithmetic operations, like subtraction, multiplication and even long division (which can also be used for modular reduction).  The important thing to realize is that all these calculation methods are based on rules for manipulating strings of digits, and on simple arithmetic operations on single digits.  As long as you can do the basic single-digit operations, and know the algorithm for combining them together, you can do arithmetic on paper with numbers as large as you want (or need) to!

So how do computers do it, then?  They could of course use exactly the same decimal arithmetic rules as we do, but that would be pretty inefficient.  A typical CPU already has fast circuitry to add or multiply together any two 32 or 64 bit (and possibly even larger) numbers with a single machine code instruction, so it makes a lot more sense to treat 32 or 64 bit arithmetic as the basic building block.

Thus, a typical computer implementation of bignum arithmetic effectively works with "digits" that are 32 or 64 bit integers, and represents larger numbers as strings of those smaller integers.  The algorithms used are very similar to those we'd use for pencil-and-paper calculation, except that instead of base 10, a computer is far more likely to use base 232 or 264.

For example, let's calculate the sum of two random 128-bit numbers (written in hexadecimal for convenience):

Exercise: 3d96d3e9d019665051ecf94e4c0c697b +
          a80314053a779df7464ea2feebf771be = ______

A modern CPU might be able to calculate that directly, but let's assume that we only have a 32-bit CPU available.  Fortunately, we can break up our numbers into 32-bit chunks and use the same addition algorithm we used before:

                                         <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                                         <-- result

So first, we need to calculate 4c0c697b + ebf771be, which our CPU easily tells us is 13803db39 (i.e. 32-bit result 3803db39, plus carry 1):

                             1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                               3803db39  <-- result

Next we ask our CPU to calculate 51ecf94e + 464ea2fe, and to increment the result by one because of the carry, which yields 983b9c4d (and no carry for the next position):

                    0        1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                      983b9c4d 3803db39  <-- result

We can then proceed with the remaining two 32-bit additions in the same way, getting d0196650 + 3a779df7 = 10a910447 (i.e. 0a910447 and carry 1) and 3d96d3e9 + a8031405 + 1 = e599e7ef:

  0        1        0        1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
    e599e7ef 0a910447 983b9c4d 3803db39  <-- result

And there we have our result!

I used addition for this simple example, but similar algorithms can be used for other arithmetic operations, including exponentiation and modular reduction (which one would normally combine into a single modular exponentiation algorithm, since it's much more efficient to do them together rather that to first exponentiate and then reduce).

Also note that the arithmetic algorithms used for cryptography tend to be somewhat specialized, since in crypto it's often important to avoid timing attacks and other types of side-channel attacks by making sure that the algorithm takes the same amount of time to run (and consumes roughly the same amount of power, etc.) regardless of what the numbers being added (or multiplied or raised to a power, etc.) are.


Decisional Diffie-Hellman: compute Legendre symbol of $g^{ab}$ from $g^a$ and $g^b$? From https://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption:

  Importantly, the DDH assumption does not hold in the multiplicative group $\mathbb {Z} _{p}^{*}$, where $p$ is prime. This is because given $g^{a}$ and $g^{b}$, one can efficiently compute the Legendre symbol of $g^{ab}$, giving a successful method to distinguish $g^{ab}$ from a random group element.

The only way I can think of to distinguish $g^c$ from $g^{ab}$ is:

If $\left(\frac{g}{p}\right)=-1$, then $\left(\frac{g^{ab}}{p}\right) = 1$ if and only if $a$ or $b$ is even (which is $3/4$ of the times).
So if $\left(\frac{g^c}{p}\right) =-1$, probably $g^c\neq g^{ab}$. Nothing is certain.

How'd do you compute $\left(\frac{g^{ab}}{p}\right)$ given $g^a$ and $g^b$?

Because (I assume) $g$ is a generator, it is not a square (prove this), so its Legendre symbol is $-1$. And hence, the Legendre symbols of $g^a$ and $g^b$ leak the parities or $a$ and $b$. Hence they leak the parity of $ab$, which leaks the Legendre symbol of $g^{ab}$.


Demonstrating the insecurity of an RSA signature encoding scheme I'm working on problem 12.4 from Katz-Lindell. The problem is as follows:

  Given a public encoding function $\newcommand{\enc}{\operatorname{enc}}\enc$ and
  a textbook RSA signature scheme where signing occurs by finding $\enc(m)$ and
  raising it to the private key $d \bmod N$, how can we demonstrate the scheme's
  insecurity for $\enc(m) = 0||m||0^{L/10}$, where $L = |N|$ and $|m| = 9L/10 - 1$
  and m is not the message of all zeroes?

An RSA signature scheme with public key $(n,e)$, private exponent $d$, and encoding function $enc$ (including but not limited to the question's $enc$), signs message $m$ as $$Sign(m) = enc(m)^d\bmod n$$

Such scheme is insecure if an adversary can figure out $k>0$ distinct messages $m_i$, and integers $u_i$, $r$, $s$ verifying
$$s^e \cdot enc(m_0) \cdot \prod_{0\lt i\lt k} enc(m_i)^{u_i} \equiv r^e \pmod n$$
because this implies (by raising to the power $d$)
$$ Sign(m_0) \equiv r \cdot s^{-1} \cdot\prod_{0\lt i\lt k}Sign(m_i)^{-u_i} \pmod n$$
which allows computing the signature of $m_0$ (if $k\gt 1$, it is also necessary that the attacker obtain the signatures of the other messages $m_i$; that becomes an existential forgery, or chosen-message attack). Although dated, Jean-Francois Misarsky's How (Not) to Design RSA Signature Schemes is an interesting and relatively easy reading on that topic.

In fact, every known attack on an RSA signature scheme is either of the above kind (with more or less involved computations to exhibit $m_i$, $u_i$, $r$, $s$); or amounts to factorization of $n$ (which includes anything recovering $d$, perhaps by side-channel attack); or is some implementation error, perhaps widespread.

In order to mount an attack of the above kind, a relation of the form $enc(m_0)=r^e$ is ideal. It gives the signature of $m_0$ without any consideration on $n$ or known signature. When $e$ is low enough, this can be done with the encoding $enc$ in the question, by considering $r=2^t$ for some appropriate $t$. That's because by definition (and assimilating bit strings to integers using big-endian convention), $enc(m)=m\cdot2^{L/10}$ with $L/10$ an integer; hence $enc(m_0)=r^e$ with $r=2^t$ holds if and only if $m_0$ has a single bit set and $\log_2(m_0)+L/10=e\cdot t$; for all $m$ that $enc$ aims at handling, $\log_2(m)<9L/10$, hence $enc(m_0)=r^e$ can hold only if $e\cdot t<L$; there are no solutions for $e\ge L$, and about $9L\over10e$ solutions for small $e$; the lower $e$, the more solutions. When we extend that with $r=v\cdot2^t$ for odd $v$, the trend for more solutions for low $e$ remains, with no solution when $e\ge L$.

Similarly, $enc(m_0) = r^e\cdot enc(m_1)$ gives the signature of one message from the signature of the other, without any consideration on $n$. This can be done with the encoding $enc$ in the question, for a wider choice of $e$.

Similarly, $enc(m_0) \cdot enc(m_1) = enc(m_2) \cdot enc(m_3)$ gives the signature of one message from the signature of the other three, for any public key $(n,e)$. With the encoding $enc$ in the question, there is ample choice (the equation simplifies to $m_0\cdot m_1=m_2\cdot m_3$, and all messages which left bit is 0 or which integer representation is composite are vulnerable). The ISO/IEC 9796:1991 signature encoding scheme (section 11.3.5 of the Handbook of Applied Cryptography), now withdrawn, turned out to be vulnerable to that, of course if the adversary can obtain the signature of three chosen messages, and is content with the signature of the fourth.

Even the hash-based ISO/IEC 9796-2:1997 (now known as ISO/IEC 9796-2:2010 scheme 1), still in wide use, is vulnerable if the adversary can obtain the signature of many weird chosen messages and is content with the signature of another, which fortunately is seldom the case in practice.

Some require $e>2^{16}$ (FIPS 186-3 appendix B3.1, RGS Annex B1 section 2.2.1.1, and I have seen suggestions for much wider random $e$), because some attacks on weak encoding schemes or implementations of RSA signature/encryption have been easiest for $e=3$ or other small $e$, as is the case for the scheme in the question. I will not condone a course of action that will lead us to loose the main appeal of RSA (or Rabin) signature schemes: fast and simple verification with modest hardware.


Is XOR in a CBC-like mode secure? Assuming that $K_{n}$, $P_{n}$, and $C_{n}$ are individual bytes of the key, plaintext, and ciphertext respectively.

The first byte of ciphertext is computed like this:

$C_{1} = K_{1} \oplus P_{1}$

And the rest of the bytes are computed like this:

$C_{i} = K_{i} \oplus P_{i} \oplus P_{i-1}$

Is this a good way of encrypting data, or is there some loophole that I've overlooked?

Well, that transform can be viewed as an unkeyed transform of the plaintext, followed by exclusive-or'ing the key.  It would also appear to have the same limitations as the usual key exclusive-or; how it works out depends on the details of the key:

If the key is as long as the plaintext, and is chosen at random, this is effectively a One Time Pad, with a same protections and drawbacks; it is perfectly secure such if you use a key once; however, if you ever use it again to encrypt a different message, it is possible (and usually: likely) that someone can recover both messages.
If the key is shorter than the plaintext, and when you run out of key, you start back at the beginning; well, you've got a variation on the Vigenère cipher, and it can be attacked in a similar manner.  The extra unkeyed transform you put on the plaintext may complicate a ciphertext-only attack a bit, but I wouldn't count on that slowing down a knowledgable attacker a great deal.
If you generate the key dynamically via a key stream generator, then you've effectively got a Stream Cipher; if the key stream is indistinguishable from random, then you're good; if not, well, there may be weaknesses.


Conditions for Perfect Secrecy with the Vigenere Cipher Please forgive my ignorance here as I'm far from a math major and I've never looked into cryptography before so if this seems stupid - it probably is. There is a question in a quiz I'm attempting that is just doing my head in. If you are wondering - I'm not doing this course for credit or receiving any certification for passing it, just for my own interest.

I've attempted this question multiple times now and I'm still getting it wrong and I don't understand why. Here is the question:

  Consider the Vigenere cipher over the lowercase English alphabet, where the key has length 6. For which of the following message spaces will this scheme be perfectly secret? (Check all that apply.)

  The set of all 7-character strings of lowercase English letters.
  The set of all strings of lowercase English letters containing at most 6 characters.
  The set of all 6-character strings of lowercase English letters.
  The set of all 5-character strings of lowercase English letters.

I know I'm getting punished by the combinations that are available due to the 'check all that apply' criteria, but I'm now at the point of blind guessing - which just isn't learning.

I'm particularly annoyed with this because further down in the same quiz the following is considered to be a correct answer for an aspect of another question:

  'The Vigenere cipher is perfectly secret if the length of the key is equal to the length of the messages in the message space.'

To me then, it seems that the answer would be:
2 and 3 and 4 - Wrong

Perhaps this is wrong because 'the key' is only as long as one individual member of 'the strings' in the message space, not the length of 'all the messages in the message' space combined?
(i.e. which would effectively be turning it into a One Time Pad where the key is the same length as the total message space?)

How should I go about breaking down this question to arrive at the answer with some sort of mathematical reasoning, rather than taking blind shots at it (which is where I'm at now)?

Description of the Vigenere Cipher

  Now when we introduced the Vigenère cipher, we presented it in the
  following way. We said that the key was a string of letters. From the
  English alphabet and the plaintext will also consist of letters from
  the English alphabet. To encrypt a given plaintext with a key, what
  you do is simply shift every character in the plaintext by the amount
  dictated by the next character of the key. You can view this simple as
  addition modular 26, because there are 26 letters in the English
  alphabet. And if the key is shorter then the plaintext you simply wrap
  around in the key as needed, and decryption just reverses the process.

As far as I can tell, your original reasoning is correct.  To obtain perfect secrecy with a Vigenère cipher, the key must not repeat.  The key does not repeat whenever it is at least as long as the message, so option 2 is clearly a sufficient (and indeed necessary) condition for perfect secrecy, at least as far as only key length is considered.  Options 3 and 4 are subsets of option 2, so if choice 2 is correct, then they must be correct as well.  Thus, the correct answer (unless this is a trick question) should be (2, 3, 4).

Note, however, that there are conditions on the perfect secrecy of a Vigenère cipher other than key length.  In particular, to obtain perfect secrecy with a Vigenère cipher:

the key must be at least as long as the message,
each of the key letters must be selected independently and uniformly at random from the entire ciphertext alphabet, and
the same key must not be used for more than one message.

The options in the question you quote make no mention of the second and third conditions, so arguably, none of them is sufficient to guarantee perfect secrecy.  While I would consider this to be a rather nasty trick to play on the test-taker (especially given that such an argument would seem to contradict the "correct" answer to the other question you quote), technically this would be a valid answer (and arguably the valid answer) to the question.

Ps. One possible interpretation, which just occurred to me, is that your course might be using a definition of perfect secrecy which is violated if the length of the message is revealed to the attacker (and is not the same for all valid messages).  This is actually a reasonable definition to adopt: if the attacker knows in advance e.g. that your message is either yes or no, then simply learning the length of the message will tell them which one it is.

Since Vigenère encryption does reveal the message length, this would rule out option 2, leaving only options 3 and 4 (where revealing the message length gives no information to the attacker, since all valid messages have the same length) as correct answers.


Can any block cipher in CTR mode be used as a CSPRNG? I have been learning about block ciphers, modes of operations, and csprngs by myself for a few days and there are some things I'm unsure about.

Assuming we only talk about cryptographically secure block ciphers; can any block cipher in CTR mode be used as a CSPRNG? Or are there specifc characteristics a block cipher should have to be used as such?
Can such a CSPRNG be used to produce key material, or do I have to specifically use a key generation/derivation algorithm for that purpose?

can any block cipher in CTR mode be used as a CSPRNG?

Formally speaking the CTR mode transforms a PRF (or a PRP) into a PRG and as the PRP notion is the standard notion to model block ciphers, pretty much all secure block ciphers should yield a secure PRG when used in CTR mode.

Less formally speaking CTR mode transforms a secure block cipher into a secure stream cipher. This implies that you "encrypt a stream of zeroes" which should be properly secure as a CSPRNG because chances are that you could break the stream cipher otherwise.

Finally you'll also see CTR mode as a building block for a sophisticated CSPRNG in practice quite often, for example with CTR_DRBG (PDF) (which among other applications is used by Intel's RdRand).

  Or are there specifc characteristics a block cipher should have to be
  used as such?

As said above, it should behave like a PRP, that's all, but (nearly?) all secure block ciphers do just that.

  Can such a CSPRNG be used to produce key material, or do I have to
  specifically use a key generation/derivation algorithm for that
  purpose?

Technically you could use CTR mode directly to derive keying material. However specialized CSPRNG constructions and KBKDFs exist for reason. So if you have a properly seeded CSPRNG, you can directly derive keys from that or else you want to use a KBKDF if you're basing of some shared keying material (like a DH shared secret).

These specialized algorithms usually allow for customization and have advanced usage scenarios in mind. So for example you have a static secret and a counter? You can use CTR_DRBG to turn this into a CSPRNG! Or you have a secret key and some context? You can use HKDF to derive keying material with a context label and context info!


OpenSSL des-ede3 not producing same output as test vector implies it should be I'm encrypting one of the standard TDEA/3DES/DES-EDE test vectors with openssl:

<?php
$key = pack('H*', '0123456789ABCDEF' . '23456789ABCDEF01' . '456789ABCDEF0123');

$result = openssl_encrypt('The quick brown fox jump', 'des-ede3', $key, OPENSSL_RAW_DATA | OPENSSL_ZERO_PADDING);

echo chunk_split(bin2hex($result), 16, ' ');

(des-ede3 is ecb mode)

This gives 1ccf23869d09333e cce21c8112256fe6 68d5c05dd9b6b900 as the result.

But the test vector for TDEA in ECB mode in NIST SP 800-67 Appendix B.1 states that the output should be A826FD8CE53B855F CCE21C8112256FE6 68D5C05DD9B6B900.

So what's up?

It looks like there's an error in the test vector.

The text of Appendix B.1 states:

  P1 = “The quic” = 5468652071756663

... which is incorrect.

The hex encoding of The quic is actually 5468652071756963 (note the transposition of the i/69 to an f/66 in the encoding.

e.g. encrypting the test vector as intended:

$ echo -n 'The quick brown fox jump' | openssl  des-ede3 -nosalt -nopad -K '0123456789ABCDEF23456789ABCDEF01456789ABCDEF0123'  | xxd -c 8 -ps
1ccf23869d09333e
cce21c8112256fe6
68d5c05dd9b6b900

... and encrypting the test vector as hex encoded:

$ echo -n 'The qufck brown fox jump' | openssl  des-ede3 -nosalt -nopad -K '0123456789ABCDEF23456789ABCDEF01456789ABCDEF0123'  | xxd -c 8 -ps
a826fd8ce53b855f
cce21c8112256fe6
68d5c05dd9b6b900

It looks like this error has been in NIST SP 800-67 since version 1 in 2004.


Would possessing a string with the SHA-256 hash of all zeros lead to an attack on SHA-256? Would possessing a string with the SHA-256 hash of all zero bits lead to an attack on SHA-256?

I could easily imagine that a specialized attack leaked knowledge of how to do it, but I could equally imagine that a bitcoin miner randomed onto one.

Would possessing a string with the sha-256 hash of all zero bits lead to an attack on sha-256?

No, it would not lead to any useful attack on SHA-256. You’ld only have an input string that hashes to 256 zero-bit output. It may be nice to know and look at, but it doesn’t buy you anything useful to attack SHA-256. All in all, it’s no different from any other hash value produced by hashing some value to another specific SHA-256 output. Just because your input renders an SHA-256 output of 256 zero-bits doesn’t mean, nor indicate that SHA-256 is broken and it certainly doesn’t open an attack vector on SHA-256.

  I could easily imagine that a specialized attack leaked knowledge of how to do it,

At the time of writing this, no such attack is known. Remember that SHA-256 has been around for a few years. The algorithm has been tested, analysed, attacked, and verified by governmental agencies as well as independant people worldwide. If there would be any weakness/shortcut in the algorithm which would enable someone to produce a 256 zero-bit hash, it would have been found. But no such findings have been made… which is why we all SHA-256 a “well vetted, cryptographically secure hash”.

Besides, being able to say “I have this set of bytes that, when I feed it to SHA-256, outputs an all-zero hash” doesn’t open any door to a cryptographical attack. It’s no different from knowing that “hello world” hashes to “b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9”.

Having knowledge of something like that doesn’t point at a weakness or attack vector. It’s what SHA-256 does: hash a specific input into a specific output. If that output happens to be 000…000 then so be it. It may be nice for some people to know how to produce a 256 zero-bit output, but it doesn‘t have any impact whatsoever on the security claims of SHA-256.

Things would be different if some weakness in the algorithm was found which would enable us to produce any specific, chosen output we like… eg: 256 one-bits (FFF…FFF) or another series of 256 output bits (123…321). Even more interesting would be finding a way to produce collisions for SHA-256 (where two different inputs produce the same output), which would be disasterous. But all that isn’t the case. No such weaknesses have been found over the years.

  but I could equally imagine that a bitcoin miner randomed onto one.

I honestly doubt that any bitcoin miner will produce anything that has any influence on SHA-256 just by hunting down the next Bitcoin block. Even if a Bitcoin miner would happen to find a 256 zero-bit output, it wouldn’t gain you anything as it’s still like the “hello world” hash example I mentioned above. Knowing which input bytes produce an SHA-256 output of 256 zero-bit hash doesn’t buy you anything which could be used as an attack… not even a coffee.

Some distantly related Q&As which might (or might not) be interesting for further reading:

What are the time considerations with regard to security against birthday attack?
Computational requirements for breaking SHA-256?
Are there any well-known examples of SHA-256 collisions?
Cryptocurrency serving as hash breaking?


Are covert and rational adversaries same? Aumann and Lindell defined covert adversaries in 2009 which is informally adversaries which have a epsilon-deterrence to cheat. Some authors (for ex. John R. Wallrabenstein) have defined similar adversaries and called it rational adversaries who act "rationally". I have not seen a simulation-based definition of rational adversaries.

So, in essence, are covert and rational adversaries same? Can they be used interchangeably?

As the previous answer says, they are certainly NOT the same. However, there is certainly a connection between them. Specifically, the covert model just says that there is a deterrent parameter $\epsilon$ and the guarantee is that if the adversary tries to cheat then it will be caught with probability at least $\epsilon$. The question that arises is how should $\epsilon$ be set in real life.

Here, rationality can be utilized. Specifically, if you are given the adversary's utility when it succeeds in cheating undetected, its (presumably lower) utility when it doesn't cheat, and its (presumably even lower) utility when it is detected cheating, then you can compute the value of $\epsilon$ that will guarantee that the rational choice is to behave honestly. I'll leave the details of how to compute this to you (it's not difficult).


Is this mentally computable password system, cryptographically secure? And anything like this out there I can find? Please bear with me on this, I'm not learnt in this field, just trying to ask questions about the security of my encryption method.
I'm trying to create a mentally computable human password manager method that can generate strong passwords using a set of operations and a master password, so that you only have to really remember one password to have strong passwords for all your accounts. And also to never have to change the system in your life so you can have backwards compatibility. The system will work even when everything has been exposed to a public. My desire is to have the system be intuitive and user friendly (instead of having to put effort into memorizing 1pad charts, etc.) yet secure.
I had some feedback elsewhere that my system outputs strong passwords against normal attacks but is vulnerable to a determined adversary, so now I made some changes.
For the sake of simplicity, I will be using weak passwords, but bear in mind it doesn't take that much to obfuscate the final output with scrambling, numbers and symbols.
So, I have a string of 34 letters, each letter representing a word that starts with said letter. That is my master password.
Let's begin with making a Google account:
1. Google
First, I take the word Google to apply the seed
G = 7th letter of the alphabet (position)
Google = 6 letters (length)
2. GoogleLydngr
Then, I add the 6 (length) letters after the 7th (position) letter of the master password
3. GoogleLydAroundngr
At this point, the last letter "r", represents a word which has 3 letters
I move back 3 spaces and add the word "Around", which is the next letter/word after the "r"
GoogleLydAroundngr
So that will be my password for Google. This example is easily bruteforced but my question isn't about the password strength but more of the concept.
Now I create a Facebook account, using the same system:
FacebookGlAndydngra (6 position, 8 length)
You will notice the difference is the letters and number of letters, and that I moved back 6 spaces instead of 3, and has added "And" instead of "Around".
I create 3 more for Instagram, Twitter and Microsoft:
InstagramDngrNeveraadyn (9 position, 9 length)
TwitterNgraNeverady (20 position = 0 = 10 position, 7 length)
MicrosoftYungRunlydng (13 position = 3, 9 length)
So, you hacked my accounts through a keylogger, and got a hold of all my passwords. Also, you discover my order of operations. And finally, I wrote down my master password in a text file, so you know that too. I lose everything.
But I go ahead and create new accounts using the same system. However, I change the master password.
How easy is it to crack my new accounts just based on the fact you know everything now... except for my new master password?
For anyone who's curious, the master password is Nggyunglydngraadyngmycngsgngtalahy

Never gonna give you up
Never gonna let you down
Never gonna run around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you

But seriously, this is a serious question. I'm trying to use the chaos of language and musical timing to generate more variety in place of complex calculations. But I'm not smart or educated in this field to know how flawed my system is.
And just another tidbit, one song alone can generate several passwords for when I need to change a single password exclusively, all I have to do is use a different verse of the song or use syllables instead, or something.
Thanks and appreciate any help or comment given.

Firstly, you shouldn't really invent your own password manager, except for fun/experimentation/learning purposes.  Especially if you are a beginner.
Regarding your comments, I don't really see how managing your own in your head can be less hassle than managing a standard one on a machine.  I use google/chrome's (BOO!) so can use across devices and could give away passwords to certain accounts, for whatever reason.
You may find this interesting reading.  It seems very similar to your idea.  It uses a pin as well as a cue for each site.  It also goes into detail about the reduction in security as you use the system to "generate" more passwords.
Your scheme gives away bits of the master key in each password, and has virtually no real entropy.  There is a 23.5% chance the letters in your passwords will be 'g'.
If we change the lyrics to something tasteful like the opening verse of Dylan's Subterranean homesick blues, we still have 0% chance of a 'z'.
There are 256 possible values in a random byte.
Imagine another scheme I invent which uses a cryptographically secure salted hash, where the salt is the website address/master key/time added to database, and the input to the hash is the master key. My master key is "never gonna give you".

Each of my website passwords might be anything.  They are not all based on the letters in my master key.
If websiteX password is breached, it gives an attacker nothing about the password for websiteY, or the master key.
When I change my password for websiteX, I don't need to change my master key.
The basic security of my system relies on a cryptographically secure hash that wasn't designed by me.

Obviously (as mentioned) I wouldn't use my own scheme because there are already better existing schemes designed (and implemented) by people who know better.


How is the ciphertext labeled with a set of attributes in Key-Policy Attribute-based Encryption (KP-ABE) My question is about Key-Policy ABE (KP-ABE). What does it mean when a "Ciphertext is Labeled with set of attribute"? How is it labeled?

The first Attribute-based Encryption scheme was introduced by Sahai and Waters in 2005: Fuzzy Identity-Based Encryption. It worked by associating a set of attributes with both the ciphertext and the private key of the user.

Take for example the ciphertext which is encrypted with the attribute set $\{A, B, C\}$ and the private key of some user with the attribute set $\{B, C, D\}$. If the system threshold $d$ is chosen as 2 then the user would be able to decrypt the ciphertext with because the cut set of the ciphertext attribute set and the private key attribute set is of size 2 which is greater or equal to the global threshold $d$.

This is of course not very useful, because this only achieves cryptographic access control based on set overlap. One generally wants to use more complicated policies which are more expressive than simple sets. Such expressive policies where later achieved by Goyal et al. in 2006: Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data (KP-ABE).

Instead of using two sets, the private key of the user is generated (associated) from a boolean formula (policy) of attributes and the ciphertext is encrypted with an attribute set. For example, the ciphertext may have been encrypted with the set $\{A, B\}$. Now we have two users with private keys from two different policies. $$SK_1=\text{Keygen}(MSK, ``A\ \text{and}\ (B\ \text{or}\ C)")$$ and $$SK_2=\text{Keygen}(MSK, ``A\ \text{and}\ (C\ \text{or}\ D)").$$

You should see that the user who possesses $SK_1$ can easily decrypt the ciphertext, because ciphertext was encrypted with $B$, the clauses $B\ \text{or}\ C$ is fulfilled as well as the $A$. Since both clauses are fulfilled, the $\texttt{and}$-gate is also fulfilled. This means that the attribute set satisfies the policy in the private key and $SK_1$ can decrypt the ciphertext.

The user who possesses $SK_2$ cannot decrypt the same ciphertext, because the necessary clause $C\ \text{or}\ D$ is not fulfilled by the attributes present in the ciphertext. Therefore the $\texttt{and}$-gate cannot be fulfilled and $SK_2$ cannot decrypt the ciphertext.

There is also CP-ABE by Bethencourt where the roles are reversed, because a policy is used to encrypt the ciphertext and private keys are generated from attribute sets.


Yarrow and weak cryptographic keys on macOS Given that macOS uses Yarrow as a PRNG, and Yarrow is only capable of 160 bit outputs (/dev/random on macOS is actually Yarrow) are keys generated on macOS weaker than Linux?

Even BSD has switched to Fortuna.

Is this is big gaping hole in Modern macOS security?

https://en.m.wikipedia.org/wiki/Yarrow_algorithm

EDIT:

I have looked through the source and it seems as if they switched to a DRBG NIST generator?

https://opensource.apple.com/source/xnu/xnu-4903.221.2/osfmk/corecrypto/ccdbrg/src/ccdrbg_nisthmac.c.auto.html

There are very few references to Yarrow in the 10.14 XNU code compared with older versions of the Kernel, but 10.14 still contains this string in key.c :

/* Our PRNG is based on Yarrow and doesn't need to be seeded */
That said if you looked at older XNU Yarrow is littered everywhere.

Source code for XNU:

Lots of Yarrow references in XNU 2782 - macOS 10.11

Very few Yarrow references in XNU 4903 - macOS 10.14

So, are Apple still using Yarrow?

Update: Apple are using Fortuna.

A 160-bit seed is plenty for a cryptographically-secure PRNG. We are not going to be able to count to 2160 any time soon, so there is no need to worry that this is a "gaping hole". While in theory Linux's random driver may have a larger keyspace, it's not going to make a difference in real life. Fortuna does have advantages over Yarrow, but a larger key size is not what's important. What really matters is resistance to side-channel attacks and adequate entropy collection at boot time.

By default, Yarrow-160 actually uses 3DES in counter mode to generate the random output, which gives it approximately 112 bits of security. Fortuna uses any other block cipher in counter mode, but typically 128-bit AES. The Linux randomness driver uses ChaCha20. It starts out with 320 bits of secret material (a 256-bit key and a 64-bit nonce). Each reseed updates the 256-bit key. So yes, Linux has a larger keyspace. No, this doesn't matter in practice. Yarrow, Fortuna, and Linux's CRNG are all secure.


How can we implement a PRF with 1bit input space and 1024bit output space using AES securely? I'm considering an implementation of PRF
$F:\{0,1\} \times \mathcal{K} \rightarrow \{0,1\}^{1024}$ with a key space $\mathcal{K}$ in particular with AES-128 in counter mode.

Since output space is 1024 bit and one block size is 128 bit, we need to use 8 blocks to encrypt a counter and a nonce.
The counter is incremented in some way every time a block encryption is finished.
Then, an input $m$ is XORed to each of the encrypted blocks.
So a string that concatenates 8 encrypted blocks is considered as an output of the function.

Is this secure? Any correlation between two encrypted blocks?

It is secure. There would be an issue if that you generalize the idea to ridiculously long outputs. Any time you use two distinct inputs with a PRP using the same key, the outputs will necessarily be different. But for an ideal PRF there is a tiny chance that different 128-bit blocks could share the same value.

Because you only have 8 blocks, though, you wouldn't actually see duplicate blocks from an ideal black box PRF in practice. As a rule of thumb, you would not expect to see any duplicates until you look at around $2^{64}$ blocks. (See the "birthday paradox" and switching lemma.)

I'd discourage someone from doing anything more complicated with AES to mask that potential artifact. ECB encrypting the blocks with values 0 through 7, if the input is 0, or the values 8-15, if the input is 1, would be sufficient.

A variable nonce isn't actually needed. You can just use a constant, such as zero.

Alternatively you could replace AES with a (non-block-cipher) PRF. HMAC or ChaCha20, for example.


Why do two Argon hashes with the same password differ? Can someone explain to me what the ArgonHashString function in libsodium returns (i'm using the .net port).

For example i called it twice with the same string:

var foo1 = PasswordHash.ArgonHashString("f");
var foo2 = PasswordHash.ArgonHashString("f");

and i got entirely different answers:

"$argon2i$v=19$m=32768,t=4,p=1$rKEPCGqfhm7zQt8c2QBhRA$7oZHFjWhHdVg/31SottxDyVM5KA9+4IBc5qD5m9DNFI\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
"$argon2i$v=19$m=32768,t=4,p=1$o8MmGW+GoaVcQvBfmPDE8A$3mHVQbZz3JuLI++MIBC4JOI+/G2oVtq75Jbqml8lbEM\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"

ArgonHashString calls the libsodium function crypto_pwhash_str which automatically generates a salt value that is part of the result.


CPA-security of a pseudorandom permutation encryption scheme Let $F$ be a pseudorandom permutation, and define a fixed-length
  encryption scheme $(Gen, Enc, Dec)$ as follows: on input $m \in$
  $\{0,1\}^{n/2}$ and key $k \in \{0,1\}^n$, algorithm $Enc$ chooses a
  random string $r \leftarrow \{0,1\}^{n/2}$ of length $n/2$ and
  computes $c = F_k(r||m)$. Show how to decrypt, and prove that this
  scheme is CPA-secure for messages of length $n/2$.

I see the decryption could be $d = F_k^{-1}(c) = r||m \Rightarrow r_0r_1 ... r_{n/2-1} m_0m_1 ... m_{n/2-1}$, assuming $n$ is even the receiver knows that he must extract $m$ from the first exact half (from right to left) in the ciphertext sequence. As for the CPA-security, I notice that $F_k$ is non deterministic because of $r$, so for a message $m$ the 2 ciphertexts $c = F_k(r||m)$ and $c' = F_k(r'||m)$ are different if $r \neq r'$. Let $q(n)$ be a polynomial number of oracle queries, then $r = r'$ with probability $$\frac{q(n)}{2^{n/2}}$$ which should be negligible.
Is that correct? And should I say something about the security parameter $n$? I feel I'm missing something here.

You're close. As Mikero noted in the comments, this scheme is CCA-secure as proven in his book.

The proof strategy that seems easiest here is to do game-hops and with the IND$-CPA definition:

Start with the real case where $c=F_K(r\mathbin\|m)$ is returned
Swap out $F_K(\cdot)$ for a random permutation $\pi$, so $c=\pi(r\mathbin\|m)$ is returned, you "lose" the PRP advantage on your bound here
Swap out $\pi$ for a random function $f$ using the PRP-PRF-switching lemma, so $c=f(r\mathbin\|m)$ is returned, you lose the PRP-PRF bound here (additively)
Swap out $f$ for the function that instead drops its input and instead returns a fresh random value, you additively lose the probability you named because only if $r$'s (and $m$'s) repeat there's a chance that you can distinguish this from the previous game, $c\gets \{0,1\}^n$
Now you always return a random value as the ciphertext, independent of the input message, therefore it cannot convey any information about it, you're done

  Is that correct?

The basic idea is there, it just needs to be spelled out a bit more explicitly.


SHA1 collision for first 32 bits for two different messages Is it possible to create a program to find the collision of 2 different messages with the same first 32 bits using sha1 hashing? I tried using a while loop, but it ran endlessly as though no match were found. I am doing this in Java. These 2 messages must contain "abc123".

My while logic is adding a number to the end of the string, but it fails.

Below is my sha1 hashing (let's just call it) pseudo-code:

public static String sha1Hashing (String message) {
    String sha1 = "";
    StringBuffer sb = new StringBuffer();
    try {
        MessageDigest mDigest = MessageDigest.getInstance("SHA1");
        byte[] result = mDigest.digest(message.getBytes());

        for (int i = 0; i < result.length; i++) {
            sb.append(Integer.toString((result[i] & 0xff) + 0x100, 16).substring(1));
        }
    } catch(NoSuchAlgorithmException e) {
        e.printStackTrace();
    }
    //return first 32 char
    sha1 = sb.toString().substring(0,32);
    return sha1;
}

To find a collision it would be best to perform a birthday attack (as I already commented below the question).

You could use abc123 as prefix and then append a counter (using any encoding), creating the message to hash. Then you'd calculate a hash over the message and take the first 4 bytes. You'd create a map using the 4 byte hash as key (e.g. encoded as hexadecimals) and the message.

Now you simply add these key / value pairs until you find a duplicate key. In that case you print out the current message and the message in the map, and - of course - the hash collision that you found.

Because of the birthday problem you'd expect to find a match in less than a second and minimal memory use.

Proof:

Found match: abc123_owlstead_1255 and abc123_owlstead_59131 -> 992156E0
That took approximately 430 milli seconds

Note that if you post this as an answer, the word "owlstead" should raise some questions and google will quickly find this answer. So I would not copy paste this answer if I were you.


What's wrong with RSA and OpenSSL? We all know that signing a document is to encrypt its hash using signer's private key.
https://commons.wikimedia.org/wiki/File:Digital_Signature_diagram.svg
I've been searching the web for days, looking for a simple online page where you can sign a text using your private key (you can do this part offline), and others can verify a text's author inputting the received text, signature and signer's public key. But I didn't find anything, just symmetric encryption like https://encipher.it So I decided to create myself an app using PHP's OpenSSL capabilities. Here's the source code http://pastebin.com/Czp3SZHd

The problem is that I've read people saying that "you can't encrypt using your private key", "signing is not the same as encrypting", "raw RSA, without padding, is insecure".

So I'm confused. Isn't public-key cryptography supposed to be secure? That is, it isn't feasible to calculate the private key from the public key, not even having samples of plain and cipher texts, encrypted with the private key.

UPDATE:

I have updated the key length, from RSA-1024 to RSA-2048. Now I use phpseclib with RSA-PSS as default padding for signing. It also uses setHash('sha512').

Source: http://pastebin.com/rSzQ5uKs

Of course, I'm not taking into account other factors like server-client communication, key generation, etc.

To a cryptographer, "signing a document is to encrypt its hash using signer's private key" is wrong, because:

It is specific to RSA and cousin cryptosystems including Rabin, and not even remotely descriptive of other common signature schemes;
It misses an important step, padding, which is different for RSA signature and RSA encryption. If we use no padding, some attacks apply (in particular, that allow computing signature of a document from a moderate number of signatures of other chosen documents).

PHP's openssl_private_encrypt used in the software linked in the question is thus horribly named (it should be openssl_RSA_sign), but when used with OPENSSL_PKCS1_PADDING (which seems to be the default), I believe it uses RSASSA-PKCS1-V1_5, an RSA signature padding; it's a tad obsolete and lacking a strong security argument (contrary to RSASSA-PSS), but stands currently unbroken.

Note: the linked software uses SHA-1, and that's obsolete, and broken by the definition we use in cryptography. It was practically and publicly broken in 2017.

Note: the linked application is at best as worth of trust as the weakest of the web server running it, the web client used to access the website for signature and that used for signature verification, the cryptography between server and clients, the source of the public key, the generator of the private key and anything that was ever used to handle it.


How can a poor RNG impact security? I have read this article and I do somehow "understand" that the reduction of entropy makes it easier to guess.

But how exactly can the security be reduced by that? Can you give a concrete scenario, where a poor (P)RNG leads to security issues?

Suppose that you generate a brand new RSA key pair, that you will use, say, to authenticate yourself when connecting to a SSH server. This will be done through some library that implements RSA key pair generation (say, OpenSSL). That library will produce the key elements by generating random integers of the right length until such integers appear to be prime number.

The random generation uses a seed obtained from "true randomness" and then expanded into an arbitrarily long sequence of random bits with a cryptographically secure PRNG. The point is to make it infeasible for an attacker to predict the bits you came up with.

Now suppose that the seed is of low entropy (e.g. 40 bits) or the PRNG is poorly designed and reduces the entropy. Saying "40 bits entropy" more or less means "there are only 240 possible values for the seed or internal PRNG state". Take note that in the synthetic description above, the conversion from seed to generated private key is completely deterministic. Thus, an attacker can generate all these 240 states, and, for each of them, work out the private key that your application would have come up with, starting with that seed value. It then suffices for the attacker to check these keys against your public key (which is public, as the name says) to learn your private key. And impersonate you. Which is bad.

This actually happened in Debian in 2008 and people had to regenerate new SSH keys (both client and server).


Does it make sense to stretch non-keys? I was thinking about stretching salt.

Key-stretching is good against brute force guessing and assumes your system isn't compromised.

Salting a one-way makes it so you have to compute * n for each password and assumes your system is compromised.

Assuming the system is compromised, derived salts are found, static keys are found, would it make sense to stretch anything at that point?

When using a salted, key-stretching KDF, like PBKDF2 or scrypt, you are in effect stretching both the salt and the password.  That is to say, what you're calculating is

$$\rm key = KDF(password, salt)$$

where changing either of $\rm password$ or $\rm salt$ requires the slow $\rm KDF$ function to be entirely recomputed.

In fact, if changing the salt did not require repeating the entire key derivation process, this would significantly reduce the effectiveness of the salt: instead of requiring $t \times n \times m \times k$ time to test $n$ passwords against $m$ hashes with a KDF iteration count of $k$ (with one iteration taking about $t$ time), the ability to easily change the salt would allow an attacker to carry the same attack out using only about $t \times n \times (m + k)$ time.

In particular, contrast this with extract-then-expand style KDFs like HKDF, used for deriving multiple keys from a single original key or password, which have the general form:

$$\begin{aligned}
\rm PRK &= \rm KDF_{extract}(password, salt) \\
\rm key_{\it i} &= \rm KDF_{expand}(PRK, info_{\it i}) \\
\end{aligned}$$

where ${\rm info}_i$ is a unique string identifying the purpose for which ${\rm key}_i$ is being derived.
One of the advantages of this kind of KDF is that, whereas $\rm KDF_{extract}$ needs to be slow if used with password inputs*, the $\rm KDF_{expand}$ function can be fast, allowing many keys to be efficiently derived from one password.

The important thing to note here is that, as a consequence, the salt and info strings play very different roles: the salt can and should be varied to reduce the effectiveness of parallel brute force attacks on multiple passwords, whereas varying the info strings offers no such protection, since changing the info string does not require recomputation of the slow extract phase.

(*: Note that the extract function defined in the HKDF standard is not slow, and should not be used for password-based key derivation.  However, the standard does include a provision for effectively replacing the extract function with any other source of uniformly distributed pseudorandom keys, such as PBKDF2.)


What is the point at infinity on secp256k1 and how to calculate it? I hear that there should be a point at infinity on secp256k1. I wounder how to calculate it and what does it even mean. I tried to calculate it as $P_{inf}=P+(-P)$ but this gives different results for different P. Are there more than one point at infinity?

Geometrically thinking on an elliptic curve, adding two points that are symmetric against x-axis, should not be feasible because any vertical line on x-y plane will only intersect the curve at TWO points not THREE.

Point at Infinity
Yes, there is a point at infinity $O$ (or denoted as $\infty$) on Elliptic Curves (EC) as the identity element of the Elliptic curve group. Let the EC be given in Weierstrass equation;
$$y^2 = x^3 +a x + b$$
$O$,  the point at infinity can have different values according to the underlying coordinate system;
Coordinate Systems
For an elliptic curve over $\mathbb{F}_p$;

In Homogeneous Coordinates (also known as Projective Coordinate), the points are defined as $(x:y:z),z\neq 0$ corresponding to affine point $(\frac{x}{z},\frac{y}{z})$. The point at infinity  is $(0:1:0)$ and negative value of $(x:y:z)$ is $(x:-y:z)$
In Jacobian Coordinate the points are defined as $(x:y:z),z\neq 0$ corresponding to affine point $(\frac{x}{z^2},\frac{y}{z^3})$. The point at infinity  is $(1:1:0)$ and negative value of $(x:y:z)$ is $(x:-y:z)$

Now, what is $O$ in affine coordinates? Try to convert $O$ back into an affine coordinate! Well, we cannot represent it! See this answer Thus, we simply say it is $O$. But, magically, it can be encoded in implementations.
The Group Law
The points on an elliptic curve form an additive group with an identity $O$. For geometrical meaning please see the below image from Wikipedia Elliptic Curves The group law.

The Group Law on Affine Coordinates
Arithmetically can define the addition rules in affine coordinates. These are derived from the line intersection and tangent equations. The formulas are;
Let $P=(x_1,x_2)$ and $Q=(x_2,y_2)$ be two point in the elliptic curve.

$P+O=O+P=P$
If $x_1 = x_2 $ and $y_1 = - y_2$ and $Q =(x_2,y_2)=(x_1,−y_1)=−P$ then $P + (-P) = O$
If $Q \neq -P$ then the addition $P+Q = (x_3,y_3)$ and the coordinate can be calculated by;

\begin{align}
x_3 = & \lambda^2 -x_1 - x_2  \mod p\\
y_3 = & \lambda(x_1-x_3) -y_1 \mod p
\end{align}
$$
\lambda =
\begin{cases}
\frac{y_2-y_1}{x_2-x_1},  & \text{if $P \neq Q$} \\[2ex]
\frac{3 x_1^2+a}{2y_1},  & \text{if $P = Q$} \\[2ex]
\end{cases}$$
The Group Law on projective Coordinates
Let $P_i = (x_i : y_i : z_i ), i = 1, 2$, be points on the elliptic curve $$y^2 z = x^3 + Axz^2 + Bz^3.$$ Then
$$(x_1 : y_1 : z_1 ) + (x_2 : y_2 : z_2 ) = (x_3 : y_3 : z_3 ).$$ The formulas are;

$P_1 \neq \pm P_2$

$u = y_2 z_1 − y_1 z_2,$
$v = x_2 z_1 − x_1 z_2,$
$w = u^2 z_1 z_2 − v^3 − 2v^2 x_1 z_2,$ then

$$x_3 = vw, \quad y_3 = u(v^2 x_1 z_2 − w) − v^3 y_1z_2, \quad z_3 = v^3 z_1 z_2$$

$P_1 = P_2$

$t = a z_1^2 + 3x_1^2,$
$u = y_1 z_1,$
$v = u x_1 y_1,$
$w = t^2 − 8 v,$

$$x_3 = 2uw, \quad y_3 = t(4v − w) − 8y_1^2 u^2 , \quad z_3 = 8 u^3.$$
For Jacobian Coordinate operations see this link.


determinant of intersection of two lattices Say $L_1,L_2$ are contained in $\mathbb Z^r$ with

\begin{gather*}
  \operatorname{rank}(L_1) = \operatorname{rank}(L_2) = r, \\
  \gcd(\det(L_1), \det(L_2)) = 1.
\end{gather*}

How do I prove $\operatorname{det}(L_1 \cap L_2) = \det(L_1)\cdot \det(L_2)$?

It's easy to show that $\det(L_1 \cap L_2)$ is divisible by $\det(L_1) \cdot \det(L_2)$.  My question is how to prove $\det(L_1 \cap L_2) \leq \det(L_1) \cdot \det(L_2)$?

I know this is really old, but it's still an interesting question that is semi-related to something I am working on.
I will refer to the lattices as $L_0$ and $L_1$, so I can write $L_i$ and $L_{1 - i}$ to refer to both of them without making a particular choices of indices.
I will use $L \leq L'$ to denote sublattice containment.

Let the operation $L_0 + L_1$ be the minkowski (not direct) sum of lattices.
If $L_i = \mathcal{L}(M_i)$ is the lattice generated by the matrix $M_i$, then $L_0 + L_1 = \mathcal{L}([M_0 | M_1])$ is the lattice generated by the concatenation of the matrices.
You can equivalently view this as the sum of all pairs of lattice points, i.e. $L_0 + L_1 = \{l_0 + l_1 | l_0\in L_0, l_1\in L_1\}$.
This operation can be seen as "dual" to the intersection in a formal sense [1], which I will exploit below.

Note that $L_0\cap L_1\leq L_i$, so the quotient $L_i / (L_0\cap L_1)$ is well-defined.
Moreover note that $|L_i / (L_0\cap L_1)| = [L_i : L_0 \cap L_1] = \det(L_0\cap L_1)/\det(L_i)$.
By the second isomorphism theorem (viewing lattices as $\mathbb{Z}$-modules), we have that:
\begin{align*}
L_i / (L_0\cap L_1) &\cong (L_0 + L_1) / L_{1-i}\\
\implies \det(L_0\cap L_1)/\det(L_i) &= \det(L_{1-i})/\det(L_0 + L_1)\\
\implies \det(L_0 \cap L_1) &= \frac{\det(L_0)\det(L_{1})}{\det(L_0 + L_1)}
\end{align*}
This holds for any pair of lattices $L_0, L_1$ such that $L_0 \cap L_1$ and $L_0 + L_1$ are lattices (interestingly, we have not assumed the lattices are integral yet).
This suggests that all we have to do is prove that $\det(L_0 + L_1) = 1$, and we have:

$L_i$ are integral (i.e. $L_i \leq \mathbb{Z}^r$)
The GCD condition

To work with. Note that integral lattices satisfy $\det(L)\mathbb{Z}^r \leq L \leq \mathbb{Z}^r$.
One can show that $L_i \leq L_i'$ implies that $L_0 + L_1 \leq L_0' + L_1'$.
Applying this to the above, we get that:
$$\det(L_0)\mathbb{Z}^r + \det(L_1)\mathbb{Z}^r \leq L_0 + L_1 \leq \mathbb{Z}^r$$
It is not hard to show that $a\mathbb{Z}^r + b\mathbb{Z}^r = \mathsf{gcd}(a, b)\mathbb{Z}^r$, so upon using our GCD condition we get that $\mathbb{Z}^r \leq L_0 + L_1 \leq \mathbb{Z}^r$, and therefore $\det(L_0 + L_1) = 1$.

[1] The submodules of a module form a modular lattice in the sense of order theory, where $\cap$ is the meet, and $+$ is the join respectively. This is to say that $+$ and $\cap$ are "dual" in the same sense that the set union and intersection are "dual".


What if using a block cipher as compression function in Merkle–Damgård? The Merkle–Damgård construction builds a hash by iterating a compression function $F$, with $S_{j+1}=F(B_j,S_j)$ where $B_j$ is one of $n$ padded message blocks, $S_0$ is the IV, and $S_n$ is the hash.

Customarily, $F$ is built from a block cipher $E$ with block width the hash width and key size the message block size, as $F(B,S)=E(B,S)\boxplus S$, where $B$ is at the key input of the block cipher, and $\boxplus$ is some simple group operation (typically addition with carry suppressed across words, or perhaps just XOR).

What security property would suffer if we used $F(B,S)=E(B,S)$, e.g. in SHA-256?

I see only two obvious negative consequences:

For unknown message fragment $A$ of length multiple of the block size, with knowledge of $B$, $C$, and $H(A\|B)$, it would be trivial to compute $H(A\|C)$; sort of a length extension property on steroids, but nothing that breaks collision-resistance, first or second preimage resistance, or indistinguishably from a random oracle for one not knowing some arbitrary constant;
the IV would no longer be suitable as the only arbitrary constant unknown to the adversary in that random oracle model; but we could use a constant part of the definition of $E$ towards that, and there are plenty of such constants in the typical $E$.

On the positive side, the output of the hash of a long random message multiple of the block size would have practically as much entropy as the hash width, when there is less with the standard construction (like, 0.8272... bit less).

One issue is that it would make finding preimages significantly easier; with $O(2^{n/2})$ time rather than $O(2^n)$ time.

Here's how you would do such a search:

Select $2^{n/2}$ distinct initial halves of the message, and determine the intermediate state for the hash after processing each message.
Select $2^{n/2}$ distinct final halves of the message, and starting with the target hash, compute hash state backwards, determining what the state would have to be at the start of the final half of the message to derive the target.
Scan through the two lists to find a common state.

Once you have a collision, the initial half and the final hash concatenated together will hash to the target.

Making the hash compression function noninvertible prevents this, as it blocks the second step.


Issue implementing Pollard's Rho for discrete logarithms I've been trying to implement Pollard's Rho recently. The original idea was to implement the code in several languages and put it up for everyone to see for educational purposes. I first took to Wikipedia and implemented the code from Pollard's rho algorithm for logarithms. I translated the code directly from C++ to Haskell and it generated the same output as C++ so I was happy. It agreed with the example in the Wikipedia page. However, when taking the output and solving $(B - b)\ \gamma \equiv (a - A)\pmod n$, I got results that were different than what the logarithm should be. If you would like to comment on this code, comment on the C++ code in the Wikipedia article please, I guess that's the most accessible version.

Unhappy with the Wikipedia article I searched further and found a gist with Python code that's based on Algorithm 3.60 in the Handbook of Applied Cryptography, linked in the gist. This version could calculate the logarithm for the example mentioned in the code (taken from the book). It yields different results to the code from the Wikipedia page. I have verified, and the Python code reads exactly like the algorithm is described in the book. However, if I feed it something like $n=6,\ Z=7,\ alpha=5,\ beta=4$ then obviously the $dlog$ of $4$ to the base of $5$ in $\mathbb{Z}_7^*$ should be $2$, because $5^2\pmod 7 \equiv 25\pmod 7 \equiv 4 \pmod 7$. But instead it breaks down with an exception, because it tries to get the inverse of $4\pmod 6$, and obviously there isn't one, because $gcd(4, 6) = 2 \neq 1$. It does that because in the last step of the algorithm, described on print page 106, it will arrive at $r = b_i - b_{2i} = 4$ and it has to compute $r^{-1}$. HAC is supposed to be a respectable book, but the code I have yields bad results, so am I doing something wrong? Is the book wrong?

I've spent a few days on this now. And yes, I've read through this stack exchange searching for Pollard's Rho. How do I fix this code? Why does the Python and C++ code break down? Is there a version of Pollard's Rho algorithm that generally just works other than for a few select cases? Is there a book that describes such an algorithm? Can someone point me to a working version?

First of all, Pollard Rho finds an essentially random solution $(B - b) \gamma \equiv (a - A) \pmod{N}$.  This randomness implies that if $N$ has a prime factor $p$, then $B - b$ has a probability $1/p$ of having $p$ as a multiple (and hence it will fail in precisely the way you've seen).

Pollard Rho is normally used with $N$ being a large prime; the only prime factor $N$ has is, in fact, $N$, and so it has a tiny change ($1/N$) of failing. You, of course, are using it with toy parameters, and so the chance of failure is much higher.

This does being up a nontrivial point; in the group $Z_p^*$, $N = p-1$ is always even; doesn't this mean that Pollard-Rho always have a 50% probability of failing?

Well, it would, if we used it in the straight-forward manner.  However, what we do is perform the operation in a prime subfield (or, at least, a subfield with no small factors); this makes the failure probability tiny.

If we do have to do the work in a group with a size that has small factors, say, $N = hq$, where $h$ is smooth, and $q$ has no small factors, then what we can do is compute $a^h$ and $b^h$, and use Pollards-Rho to compute $\gamma'$ such that $(a^h)^{\gamma'} \equiv (b^h)$; this is in the $q$-sized subgroup, and so has a high probability of success.  Given $\gamma'$, it's easy to reconstruct $\gamma$, as $\gamma \equiv \gamma' \pmod q$


In Elliptic Curve, what does the point at infinity look like? We know that for each point $P$ in curve $E$ there exists a minimum scalar $k$ such that $k*P$ equals the point at infinity. And the book Cryptography Theory and Practice by Douglas R. Stinson only mentions that adding $P1=(x,y)$ and $P2=(x,-y)$ equals point at infinity $O$. But in terms of coordinates, how does the point at infinity look like?

The point at infinity is said to give $P+O=P$, but that is not evident from the book/tutorial. As an example, consider the curve $y^2=x^3+x +6$ mod 11 (this appears on slide 15 of this pdf and also on pages 185-186 of the aforementioned book). Taking $P=(2, 7)$ as the basis point, one generates all the points in $E$ up to point $(2, 4)$.

Now, $(2, 7)+(2, 4)$ is the so-called "point at infinity" $0$. But it is just unclear

how $0+(2, 7)=(2, 7)$, and
how $(2, 7)+(2, 4)$ should be visualized so that adding $(2, 7)$ again takes us back to $(2, 7)$.

Same slide (#15) also includes an example with curve $y^2=x^3+2x+3$ mod 5. Scalar multiplication on $P=(1, 1)$ "generates" all the points listed there except $(4, 0)$. How does one actually get to $(4, 0)$? I tried other "starting points" (e.g., $(3, 1)$) but to no avail.

You can think of the point at infinity as an extra point kludged into the set to make the curve work out as a group, but that's a little unsatisfying: in the geometric picture of a curve there's no place for the point at infinity, and in the algebraic construction the point at infinity is this weird magic object $\mathcal O$ with no coordinates.

$$E := \{ (x, y) \in k^2 \mid y^2 = x^3 - x + 1 \} \cup \{\mathcal O\}$$

Instead, it is better to think of things in projective coordinates: $$E := \{ (X : Y : Z) \in \mathbb P^2(k) \mid Y^2 Z = X^3 - X Z^2 + Z^3 \}.$$  Here the notation $(X : Y : Z)$ means the set of all triples $(\lambda X, \lambda Y, \lambda Z)$ for some $\lambda \in k$, or equivalently the line in the three-dimensional space $k^3$ that passes through the origin $(0, 0, 0)$ and the point $(X, Y, Z)$, provided at least one of $X$, $Y$, or $Z$ is nonzero.  Notice that I didn't write $\cdots \cup \{\mathcal O\}$: as it happens, there is a natural set of projective coordinates for the point at infinity, namely $(0 : 1 : 0)$ (or $(0 : 2 : 0)$, or $(0 : 128364/2486 : 0)$, etc.).

Not only is there a natural set of projective coordinates, but there is a geometric picture too.  If we paste the picture above on the plane $z = 1$, we are taking the intersection of all the projective lines $(X : Y : Z)$ satisfying $Y^2 Z = X^3 - X Z^2 + Z^3$ with the affine points $(x, y)$ satisfying $y^2 = x^3 - x + 1$ pasted on the plane $z = 1$—all except for one such projective line:

The one exception is the $y$ axis, $(0 : 1 : 0)$, which is exactly the point at infinity!  If you draw lines from the origin to the affine curve pasted on the plane $z = 1$, that is if you map $(x, y) \mapsto (x : y : 1)$, as you get further and further out the wings of the curve, the line gets closer and closer to the $y$ axis—along both wings!  In the limit toward infinity, which has no affine coordinates, you just get the $y$ axis $x = z = 0$.  For every other point, affine coordinates can be computed by $(X : Y : Z) \mapsto (X/Z, Y/Z)$.

So while it doesn't show up in the affine picture, the point at infinity has a natural geometric and algebraic interpretation in projective coordinates of lines through the origin.

Appendix A: Asymptote code for affine elliptic curve plot

import graph;

size(5cm, 0);

pair O = (0,0);
pair X = (1,0);
pair Y = (0,1);

// y = F(x) = sqrt(f(x))
real f(real x) { return x^3 - x + 1; }
real df(real x) { return 3*x^2 - 1; }
real F(real x) { return sqrt(max(0, f(x))); }

draw(-2X -- 2X, arrow=Arrows(TeXHead), p=gray(2/3) + dashed,
  L=Label("$x$", position=EndPoint, align=S));
draw(-3Y -- 3Y, arrow=Arrows(TeXHead), p=gray(2/3) + dashed,
  L=Label("$y$", position=EndPoint, align=E));

real lo = newton(f, df, -1);
real hi = 2;

guide g = graph(F, lo, hi, Hermite);
draw(g, arrow=Arrow(TeXHead));
draw(reflect(O, X)*g, arrow=Arrow(TeXHead));

Appendix B: Asymptote code for projective elliptic curve plot

import graph;
import three;

size(10cm, 0);
currentprojection = perspective(4, -8, 4);

// y = F(x) = sqrt(f(x))
real f(real x) { return x^3 - x + 1; }
real df(real x) { return 3*x^2 - 1; }
real F(real x) { return sqrt(max(0, f(x))); }

draw(-Z -- 2Z, arrow=Arrows3(TeXHead2), p=black + dashed,
  L=Label("$z$", position=EndPoint, align=N));
draw(-2X -- 2X, arrow=Arrows3(TeXHead2), p=black + dashed,
  L=Label("$x$", position=EndPoint, align=E));
draw(-3Y -- 3Y, arrow=Arrows3(TeXHead2, arrowheadpen=emissive(red)),
  p=red + dashed,
  L=Label("$y$", position=BeginPoint, align=W));

dot(O);
draw(shift(Z)*scale3(0.1)*unitdisk, surfacepen=emissive(gray(2/3)));

real lo = newton(f, df, -1);
real hi = 1.8;

// Draw the curve on the z=1 plane.

guide gp = graph(F, lo, hi, Hermite);

draw(shift(Z)*shift(-2X)*shift(-3Y)*plane(4X, 6Y), p=gray(2/3));
draw(shift(Z)*(-2X -- 2X),
  arrow=Arrows3(TeXHead2(Z), arrowheadpen=emissive(gray(2/3))),
  p=gray(2/3) + dashed);
draw(shift(Z)*(-3Y -- 3Y),
  arrow=Arrows3(TeXHead2(Z), arrowheadpen=emissive(gray(2/3))),
  p=gray(2/3) + dashed);

draw(shift(Z)*path3(gp), arrow=Arrow3(TeXHead2(Z)));
draw(shift(Z)*path3(reflect((0,0),(1,0))*gp), arrow=Arrow3(TeXHead2(Z)));

draw(unitsphere,
  surfacepen=material(white + opacity(0.5), ambientpen=white));

// Draw the curve on the surface of the sphere.

guide3 gs;

int nsamples = 400;

// Sample with linear spacing for the first part of the curve.
for (int i = 0; i < nsamples; ++i) {
  real x = lo + ((hi - lo)*(i/nsamples));
  real y = F(x);
  gs = gs -- unit((x, y, 1));
}

// Then sample with exponential spacing for the rest.
for (int i = 0; i < nsamples; ++i) {
  real x = hi + (exp(200*(i/nsamples)) - 1)/100;
  real y = F(x);
  gs = gs -- unit((x, y, 1));
}

// Oughta converge to the Y axis.
gs = gs -- Y;

// Draw all four copies of the same shape.
draw(gs);
draw(reflect(O,X,Z)*gs);
draw(reflect(O,X,Y)*reflect(O,Y,Z)*gs);
draw(reflect(O,X,Y)*reflect(O,Y,Z)*reflect(O,X,Z)*gs);

// Draw some sample points in projective space on the curve.

void
showpoint(real x, pen p=blue)
{
  real y = F(x);
  triple P = (x, y, 1);
  draw(-P--1.5P, arrow=Arrows3(TeXHead2, arrowheadpen=emissive(p)), p=p);
  dot(P, p=p);
  dot(unit(P), p=p);
  dot(unit(-P), p=p);
}

showpoint(lo + 0.3);
showpoint(lo + 1.0);
showpoint(lo + 2.0);
showpoint(lo + 2.8);

// Axis line already shown; add a dot.

dot(Y, p=red);
dot(-Y, p=red);


Is $H(x) = x^2 \bmod p$ pre-image resistant, second pre-image resistant and/or collision resistant I have the function $H(x) = x^2\bmod p$ , where $p$ is a prime of length n bits and this function maps to the message $x$ to a n-bit hash value $H(x)$.

I need to find out if it is pre-image resistant, second pre-image resistant and/or collision resistant; and if it isn't collision resistant, what are some simple colliding messages.

I think the hash function is pre-image resistant, because for a given $x^2\bmod p$ in the output space of the hash function, it is hard to find any message $x$ with $H(x) = x^2\bmod p$. Is this correct?

It is neither pre-image resistant, second pre-image resistant nor collision resistant.

It is easy to compute square-roots modulo a prime (assuming, of course, a square root exists, it will half the time).  If $p = 3 \bmod 4$, then the simple formula $x^{(p+1)/4} \bmod p$ will work; for $p = 1 \bmod 4$, it's a tad more complicated but still sufficiently easy, for example, by the Tonelli-Shanks algorithm
It is easy to compute second pre-images, even if we consider images outside the range $0 \le x < p$ to be invalid, by taking advantage of $H(x) = H(p-x)$
The easy of computing second pre-images implies a lack of collision resistance.


Current day memory capabilities for cryptanalysis? Out of interest, what would be the largest size lookup table which would be feasible to implement to attack a cipher (possibly  under a fixed key) or in a TMTO setting, for an organisation with a large but not arbitrary budget, say a global multinational.

Is $2^{64}$ within reach?

Edit: Mainly intetested in block ciphers. Let's consider, for concreteness sake, blocklength $n=64$ and a TMTO attack.

Edit 2: There were comments, before the question was put on hold, to the effect that an exabyte is probably not possible but a petabyte ($2^{50}$) is. Assuming this, I'd say that it would be possible to build a $2^{50}/8 = 2^{47}$ size lookup table.

The TMTO scenario is probably more interesting, so any answers/comments directed to that case, assuming a petabyte is feasible, will be interesting.

The answer depends a lot on the latency you may tolerate.

In 2011, Oracle/Sun/StorageTek announced a new storage system with exabyte capability (roughly $2^{60}$ bytes, but that's assuming a 2x compression rate; for crypto purposes, this is closer to $2^{59}$ bytes). Note that this was already seven years ago. Latency for random accesses could be up to a few minutes: the system uses a robotic arm that shuffles through thousands of magnetic tapes in a silo.

In a TMTO with the use of distinguished points (in particular Oechslin's "rainbow tables"), there is a "compression factor"; let's call it $t$. Costs for a rainbow table that cover $N$ preimages for a given function will be the following:

Building the table: about $1.7\times N$ evaluations of the function, and a sorting step (mostly $O((N/t)\log N)$ operations, but details vary a lot; merge sort variants are normally used because they can work with high-bandwidth sequential access).
Storage cost: about $(N/t)\log N$ bits.
For each lookup, about $t^2$ evaluations of the function, and $t$ accesses to the stored data (the original TMTO from Hellman would have needed $t^2$ accesses to storage, but the use of "distinguished points" fixes that).

The different variants of rainbow tables all follow these lines, sometimes with a factor somewhere, but always between 0.5 and 2.

For instance, if you have the half-exabyte storage system described previously, and want to find preimages for a 64-bit problem (e.g. an encryption system with a 64-bit key), then you will need $(N/t)\log N = 2^{59}$, hence $t = 2^{11}$. This means that each attack would require a few days (about three days, assuming an access latency of 2 minutes). This can probably be optimized: the $t$ lookups don't really depend on each other, so they could be collected and sorted so as to be performed in a better order that maximizes the robotic arm efficiency.

Some important notes:

The one-time cost of building the table is larger than the cost of exhaustive search. In fact, average cost for brute force is $N/2$ evaluations of the function. The table is worth the effort only if it will be used for at least four attacks.
The attacked function must be known in advance, completely. In the context of attacking a block cipher used in CBC mode with a random IV, then encryption is applied on plaintexts that are, by definition, randomized (that's the point of CBC mode). Thus, a known plaintext/ciphertext pair is not sufficient in that case.
On the other hand, the attacked system may help. For instance, the attacked system may provide enough "known plaintext" that the attacker can afford to wait for a favourable situation. This is the gist of the Biryukov-Shamir-Wagner attack on A5/1, where attackers wait for the algorithm to reach a "special state".

And with hard disks? Instead of using the tape-driven system, which can store a lot of data but with a high latency, you could try to use mechanical hard disks, which store less data for a given cost, but with a much lower access latency. Suppose that you have a budget of a mere million of dollars, that you may spend on "normal hard disks". You can get 4 TB for \$100; thus, we are here speaking about 40 petabytes. Let's round that down to $2^{55}$ bytes. Now you need $t$ to rise up to $t = 2^{25}$ for a 64-bit problem ($N = 2^{64}$). But you have ten thousands of disks, each able to perform about 100 lookups per second, and the lookups will be spread quite uniformly, so they can be made in parallel to a great extent. You can hope for a million lookups per second in total, and the $2^{25}$ will be done in half a minute... On the other hand, the computation cost of $t^2$ evaluations of the function has risen to $2^{50}$, which is prohibitive.

If the storage budget rises to ten millions of dollars, then you can divide $t$ by 10, which divides $t^2$ by 100, making it totally in range of a small cluster of beefy PC. Take care that we are then talking about a hundred thousands of hard disks, which is bound to have some non-negligible operational costs (if only for heat management and replacing failed units). Still, this would fit in a medium-sized server farm.

To sum up, a 64-bit symmetric problem which is amenable to precomputed tables is certainly in range of big organizations; in fact, it can even be done discreetly by medium-sized enterprises, and even spy agencies. On the other hand, such hardware budget would yield much more money by mining bitcoins.


Verify Messages to Embedded Device I'm building an embedded device that I plan on distributing. Periodically the device will poll my server to check for updates and commands. I'd like the device to verify that any messages(JSON strings parsed by a client written in Go) and updates are actually from me.

My plan is to use use Go's crypto/ecdsa library to generate a private/public key pair for each device, store the public key on the embedded device, and sign every message with the private key. The device will then verify any received messages with its public key.

From what I've learned so far it seems that the RNG (on the server that's signing the messages) could be a potential weak spot. Are there any other obvious flaws/issues I'm missing?

Since you asked in general "Are there any other obvious flaws/issues I'm missing", I would recommend that you would take a critical look at the whole update process flow. I would not consider the quality of the PRNG at your server as an obvious weak point, as long as it is reasonably strong, since on servers you have quite a bit of choice of reasonably good routines to generate a fair PRN (note that it is quite acceptable to generate a pair of good PGP keys on a regular server or client machines).

Critical review of the update process as a whole should consider the following, by no means an exhaustive, list:

A server that is opened to the public internet usually exhibits a fairly wide attack surface - OS, apps, services, open ports etc.
If I were an attacker, I would first try to penetrate your server, and use your private key in there to send malicious update commands out.
You need to secure the environment of your embedded processor. I assume that you discount the possibility of direct physical acess to the embedded system (otherwise all security bets are off), but you do need to think about other issues like flooding the device's comm channel with badely signed messages generated by an attacker, thus causing DOS on your embedded system. You may possibly mitigate this with a watchdog timer that will kill the update loop after a set time.
I concur with maeher - questioning the need to generate a key pair for each device. This will be a nighmare of a management vis a vis the chance of private key compromise: How would you remotely identify the client in order to know which private key to use for the signature going to that particular client? would you send a bunch of records for each client to test them all in order to find the one recognized sig in them? would you first send a client ID in the clear and respond with the appropriate signed message? I would also, as maeher proposed, recommend one key pair with all clients will have the same public key.
If you are really concerned about someone stealing your private keys, you may want to consider having all the keys expired after each update and regenerating a new pair for the next update cycle (the new pair will be signed by the old one before expiring). This is not as strong as a unique pair for each client, but certainly more manageable.

When you consider the above, it does make a difference if your embedded app is just an industrial controller, or a system whose failure due to a rogue update will cause a regional catastrophe.


Public Key Encryption scheme with small messages among many parties Question
Is it possible to create a public key encryption scheme, with $n$ parties, where a party can send all other parties a bit unique to each party in less than $n$ bits?
Assume we can set up a PKI and there exists some public broadcast channel like a trusted forum or a personal webpage.  All users including adversaries are polynomial bound.
Here's an example (completely made up):
I host a website in which people can register their public keys.  Later on the site gets hacked and t accounts got their password stolen. I post a data-blob on my site and users should be able to use their private key to derive either 1, their account got hacked and they should change their password or 0, they didn't get hacked (but should change their password anyway for security reasons).  At the end no one (but me) should know how many users got hacked or the result of any other person.
In addition my site has over eight million keys registered and I would like to minimize the amount of data sent because I have limited bandwidth.  Naively I would think that I would have to host this > 1 MB file and whenever a person visits give them a copy of the file.  After all the users check it would have used over 8 TB of bandwidth.
Ideas
One idea I had was to use a cryptographic accumulator and to somehow insert users based on their public key and post the result.  Later users could check if they are in the accumulator with their secret key.  If they are in the accumulator then their value is 1, otherwise it is 0.
I was considering users generate (sk, pk) pairs like ($sk$, $sk^r$ mod $p$) where $sk$ is a random prime number less than $p$, $r$ is a random number in integers mod $p$ and $p$ is a large prime number.  Next to generate the accumulator I would take all the $pk$ that I want to send 1 to and multiply them together mod p, lets call this $A$.  Then, after I post it, if a user want to check if they are in it they check if their $sk$ divides $A$, if so their value is a 1 otherwise their value is a 0.
A small optimization is that if I have more 1's than 0's then I could create a 0-accumulator instead which identify the users who have 0's.  The problem with this is that users learn if there are more 1's than 0's.  In my application I don't mind if users learn this information.
To throw some numbers around, if I let $p$ = $2^{64} - 59$ then the accumulator will never grow above 64 bits.  The number of keys is about $4.158 \times 10^{17}$ and the odds of a collision in the 8 million keys would be about $7.695\times 10^{-5}$.  In this case I just need to host the 64 bits for all 8 million users which would only cost 64 MB.
I came up with this idea in a few hours so I doubt it would actually work...

No, if you publish an N bit message it can hold at most N bits of information.

An N-bit accumulator value doesn't magically hold more than N bits of information in the same way a hash value does not hold the string it is calculated from. Verifying accumulator membership of a given element X requires storing a witness value for that X (essentially CurrentValue - X). Membership is tested by checking if witness + X = CurrentValue. Accumulators work only because computing a witness value for an arbitrary X is a hard problem, though such a value is guaranteed to exist.


reverse an identicon to its source string Identicons are used to create unique images based on IP address or strings. Lots of programs are available to generate identicons based on an input string.

My question is how hard is to do the reverse. Identify the source string of an identicon. In other words what is the strength of the hash function used to generate an identicon.

Can the concept of identicon be extended to generate public-private key pairs? It would be lot attactive to have two images as public and private key rather than a boring text file

The identicons idea is not bound to some predefined hash, so you will have to look at the specification or at the source code of the specific implementations.

The reversal is obviously is as hard as the hash function used in the particular implementation, if at all possible in case when the identicon representation contains fewer bits than the original data.


How do I prove that an encryption based on a multiplicative cyclic group is IND-CPA? Consider the following encryption and decryption functions where $\mathbb{Z}_{N}^{*}$ is a cyclic multiplicative group, $g$ is a generator for the group and $F$ is a keyed PRF.

$E(m, i, k) = m \times g^{F_k(i)} \bmod N$

$D(c, i, k) = c \times g^{-F_k(i)} \bmod N$

Is the above scheme IND-CPA? How would I prove it?

My first thought is that I need to show that if $g$ is a generator then $m \times g^{F_k(i)} \bmod N$ is a bijection but I am not sure how to come up with a formal proof.

Here is how I would approach the proof (this is a sketch):

A proof with a similar approach can be found in the proof of Theorem 3.26 on p.89 of Introduction To Modern Cryptography.

Step 1) Prove that replacing $F_k$ with a uniform function $f$ only gives the adversary negligibly different advantage in the indistinguishability game. To do this, choose a distinguisher $D$ for the pseudorandom keyed function $F_{k}$. $D$ has access to an oracle that is either equal to $F_k$ or $f$. Have $D$ simulate a view of the indistinguishability game for $A$ by choosing random $i$ and having the oracle output either $f(i)$ or $F_k(i)$ ($D$ doesn't know which one). If $A$ is correct, $D$ outputs 1, otherwise $D$ outputs 0. Since $F_k$ is a pseudorandom function it follows that $A$ must win the game with the actual encryption scheme negligibly different amount than with the modified encryption scheme (where $F_k$ is replaced by $f$).

Step 2) Prove that the modified encryption scheme, where $F_k$ is replaced by $f$ is IND-CPA secure. This you can do via probability analysis. First by noticing that since $g$ is the generator of the group, every element in the group can be expressed via $g^{x}$ for an integer $x$. Therefore, since $f$ is uniform, $g^{f}$ is uniformly distributed in the multiplicative group $\mathbb{Z}_{N}^{*}$ . Next, since $g$ is the generator, and since $m\in\mathbb{Z}_{N}^{*}$, $m=g^{x}$ from some integer x. Therefore we can write $E(m, i, k) = m \times g^{f(i)} \bmod N = g^{x} \times g^{f(i)} \bmod N = g^{x+f(i)} \bmod N$. Since $f$ is uniform, $x+f(i)$ is also uniform and hence $g^{x+f(i)} \bmod N$ is uniform as well. Complete the proof by letting $q(n)$ be the upper bound of number of queries that $A$ can send to the Oracle of the indistinguishability game. The only way A has an advantage is if the same $i$ is used twice. if $i$ is uniformely chosen from ${\{0,1\}}^{n}$, then this probability is $q(n) \times 2^{-n}$ which is negligible.


How can AES-256-CTR be used to construct a CSPRNG? I need to generate thousands of random 128-bit IVs per second and would like to amortize calls to /dev/urandom.

How can AES-256-CTR be used to construct a CSPRNG?

For example, would the following be acceptable?

Get 48 bytes from /dev/urandom.
Use the first 32 bytes as the AES-256-CTR key.
Use the next 16 bytes as the AES-256-CTR IV.
Encrypt 65536 bytes of zeroes.
Slice the ciphertext up into 4096 128-bit IVs (65536 / 16).
Rinse and repeat steps 1 to 6 every 4096 IVs.

Does it matter whether one encrypts 65536 bytes of zeroes at a time, or 16 bytes of zeroes at a time (i.e. should the size of the plaintext be no more than the cipher's block size)?

Would this scheme stretch the 256-bit + 128-bit entropy (initial AES key + intial AES IV) equally across the 65536 bytes of ciphertext? How does this translate to each IV sliced out of it? Would each IV have at least 128-bits of entropy or would the entropy of each IV be reduced in some way?

How could this scheme be improved?

To improve, use NIST SP 800-90A Rev. 1 Recommendation for Random Number Generation Using Deterministic RBGs, section 10.2.1: CTR_DRBG.

  Does it matter whether one encrypts 65536 bytes of zeroes at a time, or 16 bytes of zeroes at a time (i.e. should the size of the plaintext be no more than the cipher's block size)?

No, however you might wonder if you want to store that much data in memory. Stuff may be evicted from cache and I'm not sure that a 64 KiB buffer is much faster than a 1 KiB buffer.

  Would this scheme stretch the 256-bit + 128-bit entropy (initial AES key + intial AES IV) equally across the 65536 bytes of ciphertext?

Yes it does, but note that that is different than saying you've achieved a security strength of 384 bits.

  How does this translate to each IV sliced out of it? Would each IV have at least 128-bits of entropy or would the entropy of each IV be reduced in some way?

The output of a DRBG should probably not be confused with entropy, which is usually the input of a DRBG. You should be concerned if the output is distinguishable from random, and to that the answer is probably no.

The main difference between your scheme and the NIST version is that you directly use /dev/urandom instead of the INITIALIZE and UPDATE functions. I don't think it will usually pose a problem, but you'd lose any security NIST has put in that scheme.

Note that /dev/urandom is just a block device, the security of /dev/urandom depends strongly on the implementation. Some implementations may return data before enough entropy has been gathered; /dev/random does not have this problem, but can and does block even after enough entropy has been gathered.


Lemma KL-Divergence (Differential Privacy) I am studying differential privacy and I got stuck again in proof of a lemma. Which is:

$D_{\infty}^\delta(Y||Z) \leq \epsilon$ if and only if there exists a random variable $Y'$ such that $\Delta(Y,Y') \leq \delta$ and $D_\infty(Y||Z) \leq \epsilon $.

I have a problem understanding the reverse proof.
Definitions:
Be $Y, Z$ two random variables.

$\Delta (Y,Z) \overset{def}{=} \underset{S}{max} \ \ \ | \Pr[Y\in S]-\Pr[Z\in S]|$
$D_{\infty}(Y||Z)=\underset{S\subseteq Supp(Y)}{max}\Big[ln\frac{\Pr[Y\in S]}{\Pr[Z \in S]}\Big]$, which is the KL-Divergence between two distributions $Y,Z$
$D_{\infty}^\delta(Y||Z)=\underset{S\subseteq Supp(Y):\Pr[Y\in S]\geq \delta}{max}\Big[ln\frac{\Pr[Y\in S]-\delta}{\Pr[Z \in S]}\Big]$

Proof:
Suppose that $D_{\infty}^\delta(Y||Z) \leq \epsilon$. Sea $S=\{y:\Pr[Y=y] > e^\epsilon \cdot \Pr[Z=y]\}$. Then
\begin{equation*}
    \sum_{y \in S}(\Pr[Y=y]-e^\epsilon \cdot \Pr[Z=y]) = \Pr[Y \in S]-e^\epsilon \cdot \Pr[Z \in S] \leq \delta
\end{equation*}
(I understand until here)
Moreover, if we let $T=\{y:\Pr[Y=y] \leq \Pr[Z=y]\}$, then :
\begin{equation*}
\begin{split}
    \sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) &= \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=Y]) \ \ \ \text{//I got stuck here} \\
    & \geq \sum _{y \in S}(\Pr[Y=y]-\Pr[Z=Y])\\
    & \geq \sum _{y \in S}(\Pr[Y=y] > e^\epsilon \cdot \Pr[Z=y])
\end{split}
\end{equation*}
I don't' understand why:   $$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) = \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=Y])$$
Thus we can obtain $Y'$ from $Y$ by lowering the probabilities on $S$ and raising the probabilities on $T$ To satisfy:

For all  $y\in S$, $\Pr[Y'=y]=e^\epsilon \cdot \Pr[Z=y] < \Pr[Y=y]]$
For all $y \in T$, $\Pr[Y=y]\leq \Pr[Y'=y]\leq \Pr[Z=y]$
For all $y\notin S \cup T$, $\Pr[Y'=y]=\Pr[Y=y] \leq e^{\epsilon} \cdot \Pr[Z=y]$

Then $D_{\infty}^\delta(Y'||Z) \leq \epsilon$ by inspection
Reference:
Dwork, C. & Roth, A. (2014). The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, page 45.

I don't understand why:

$$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) = \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=y])$$
Well the domain is partitioned into $T$ and its complement. So the sum over the full domain of the difference of the two probability distributions is zero.
$$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) +\sum _{y \notin T}(\Pr[Z=y]-\Pr[Y=y])=0,$$
but now you can just move the second term to the right hand side and get the claimed equation.


How big an RSA key is considered secure today? I think 1024 bit RSA keys were considered secure ~5 years ago, but I assume that's not true anymore. Can 2048 or 4096 keys still be relied upon, or have we gained too much computing power in the meanwhile?

Edit: Lets assume an appropriate padding strategy. Also, I'm asking both about security of signatures and security of data encryption.

Since 2000, on a given $\text{year}$, no RSA key bigger than $(\text{year} - 2000) \cdot 32 + 512$ bits has been openly factored other than by exploitation of a flaw of the key generator (a pitfall observed in poorly implemented devices including Smart Cards). This linear estimate of academic factoring progress should not be used for choosing a key length so as to be safe from attacks with high confidence (or, equivalently, conforming to standards with that aim), a goal best served by this website on keylength.
The current factoring record is the 829-bit RSA-250 in late Feb. 2020, see the summary by the CADO-NFS team. That came shortly after the 795-bit RSA-240 in Dec. 2019, see the detailed paper.
I emphasize that the above is about attacks actually performed by academics. As far as we know, hackers have always been some years behind (see below). On the other hand, it is very conceivable that well-funded government agencies are many years ahead in the factoring game. They have the hardware and CPU time. And there are so many 1024-bit keys around that it is likely a worthwhile technique to be in a position to break these. It is one of the few credible and conjectured explanations for claims of a cryptanalytic breakthrough by the NSA. Also, dedicated hardware could change the picture someday; e.g. as outlined by Daniel Bernstein and Tanja Lange: Batch NFS (in proceedings of SAC 2014; also in Cryptology ePrint Archive, November 2014). Or in the distant future, quantum computers usable for cryptanalysis.
By 2020, the main practical threat to systems still using 1024-bit RSA to protect commercial assets often is not factorization of a public modulus; but rather, penetration of the IT infrastructure by other means, such as hacking, and trust in digital certificates issued to entities that should not be trusted. With 2048 bits or more we are safe from that factorization threat for perhaps two decades, with fair (but not absolute) confidence.
Factorization progress is best shown on a graph (to get at the raw data e.g. to make a better graph, edit this answer)

This also shows the linear approximation at the beginning of this answer, which actually is a conjecture at even odds for the [2000-2016] period that I made privately circa 2002 in the context of deciding if the European Digital Tachograph project should be postponed to upgrade its 1024-bit RSA crypto (still widely used today). I committed it publicly in 2004 (in French). Also pictured are the three single events that I know of hostile factorization of an RSA key (other than copycats of these events, or exploitation of flawed key generator):

The Blacknet PGP Key in 1995. Alec Muffett, Paul Leyland, Arjen Lenstra, and Jim Gillogly covertly factored a 384-bit RSA key that was used to PGP-encipher "the BlackNet message" spammed over many Usenet newsgroup. There was no monetary loss.

The French "YesCard" circa 1998. An individual factored the 321-bit key then used (even though it was clearly much too short) in issuer certificates for French debit/credit bank Smart Cards. By proxy of a lawyer, he contacted the card issuing authority, trying to monetize his work. In order to prove his point, he made a handful of counterfeit Smart Cards and actually used them in metro tickets vending machine(s). He was caught and got a 10 months suspended sentence (judgment in French). In 2000 the factorization of the same key was posted (in French) and soon after, counterfeit Smart Cards burgeoned. These worked with any PIN, hence the name YesCard (in French) (other account in English). For a while, they caused some monetary loss in vending machines.

The TI-83 Plus OS Signing Key in 2009. An individual factored the 512-bit key used to sign downloadable firmware in this calculator, easing installation of custom OS, thus making him a hero among enthusiasts of the machine. There was no direct monetary loss, but the manufacturer was apparently less than amused. Following that, many 512-bit keys (including those of other calculators) have been factored.

Note: 512-bit RSA was no longer providing substantial security by 2000-2005. Despite that, reportedly, certificates with this key size were issued until 2011 by official Certification Authorities and used to sign malware, possibly by means of a hostile factorization.


SSL implementation in windows? SSL (Secure Socket Layer).
windows Webbroswers ( Chrome, Mozilla, Edge, explorer ) are using which winapi set to Encrypt and Decrypt Data. SSL is asymmetric encryption.
So which Api set is being used to decrypt receavied chipher.

SSL/TLS is a secure protocol that encorporates the negotiation of cryptographic parameters for asymmetric and symmetric algorithms, integrity algorithms, and verification algorithms.  You can read more about this on How does TLS work?  You can find more information on the cipher suites used for negotiations in this answer.  The same API used for SSL/TLS is generally used for symmetric decryption/encryption.

Mozilla both use versions of the open source (MPL) NSS library for their SSL implementations.  Since it's open source there are differences between the two, but the guts should be the same.

Chrome used to use a version of NSS, and originally stated that they would switch to OpenSSL.  However, in the wake of various implementation vulnerabilities Google has decided to make their own clean version of OpenSSL called BoringSSL.

Internet Explorer is tied directly into Windows SChannel (Secure Channel) which is run and handled by Windows' LSASS process.  It would surprise me if Windows Edge didn't use this as well.  It uses WinHTTP, and is only available (for now) on Microsoft Windows platforms.