Re: Encryption and authentication modes

2010-07-15 Thread Matt Ball
On Thu, Jul 15, 2010 at 9:32 AM, markus reichelt wrote:
>
> * james hughes  wrote:
>
> > If there is no room for or an integrity field, you can look at
> > XTS-AES.
> > http://csrc.nist.gov/publications/nistpubs/800-38E/nist-sp-800-38E.pdf
>
> A not so well-known statement of said PDF certainly is the following,
> especially in light of today's storage device capacities:
>
> "The length of the data unit for any instance of an implementation of
> XTS-AES shall not exceed 2^20 AES blocks."

Remember that a 'data unit' as described in IEEE Std 1619-2007 is
analogous to a hard disk's 'sector' or 'logical block' (which is
usually fixed at 512 or 4096 bytes), so in practice this limitation is
not an issue, since you can just use more sectors to encrypt more of
your data under the same key.

--
Cheers,
Matt Ball
Chair, IEEE P1619 Security in Storage Working Group
Cell: 303-717-2717

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Re: Truncating SHA2 hashes vs shortening a MAC for ZFS Crypto

2009-11-02 Thread Matt Ball
Hi Darren,


On Fri, Oct 30, 2009 at 11:30 AM, Darren J Moffat wrote:

> For the encryption functionality in the ZFS filesystem we use AES in CCM or
> GCM mode at the block level to provide confidentiality and authentication.
>  There is also a SHA256 checksum per block (of the ciphertext) that forms a
> Merkle tree of all the blocks in the pool. Note that I have to store the
> full IV in the block.   A block here is a ZFS block which is any power of
> two from 512 bytes to 128k (the default).
>
> The SHA256 checksums are used even for blocks in the pool that aren't
> encrypted and are used for detecting and repairing (resilvering) block
> corruption.  Each filesystem in the pool has its own wrapping key and data
> encryption keys.
>
> Due to some unchangeable constraints I have only 384 bits of space to fit
> in all of: IV, MAC (CCM or GCM Auth Tag), and the SHA256 checksum, which
> best case would need about 480 bits.
>
> Currently I have Option 1 below but I the truncation of SHA256 down to 128
> bits makes me question if this is safe.  Remember the SHA256 is of the
> ciphertext and is used for resilvering.
>
> Option 1
> 
> IV  96 bits  (the max CCM allows given the other params)
> MAC 128 bits
> ChecksumSHA256 truncated to 128 bits
>
>
I personally like the default option 1.  All the others have various
uglinesses.

SHA-224 has patent issues (see US patent
6829355<http://v3.espacenet.com/textdoc?DB=EPODOC&IDX=US6829355>).
It's really identical to SHA-256 except that it uses a different initial
value and truncates to 224 bits.  I would love to see SHA-224 completely
disappear.

Cryptographers will all have different opinions about how big a MAC (i.e.,
cryptographic integrity check) should be, but my take on it is to ask how
big of a CRC would you need in a non-adversarial environment to meet the
undetectable error rate specified within the system, and then use that for
the minimum size of the MAC.  For tape drives I've worked on, this was
typically somewhere around 1 undetected error in 10^27 bits.  If you protect
1 data bit, then you'd roughly need an 90 bit CRC, which you could round up
to 96-bits.  Anything more than 96 bits in my opinion is somewhat overkill.
I'd pick a CCM mac of either 96 bits or 128.

For hashing, it's a little different since you have to worry about the
birthday paradox.  The size of the hashing output depends on the
undetectable error rate of the system, along with the maximum number of
candidate plaintexts that an adversary could create in finding a hash
collision.  Most cryptographers (not knowing more about the system) would be
conservative and say something like "Use the full 256-bits of SHA-256 to get
a minimum of 128-bits of security", but realistically for this system, that
would be way overkill.  There's already a 128-bit CCM MAC to fall back to,
so here again (given the other safety nets in the system), I think that a
128-bit truncated SHA-256 has would be plenty of assurance for the system.

-- 
Thanks!

Matt Ball, Chair, IEEE P1619 Security in Storage Working Group
Staff Engineer, Sun Microsystems, Inc.
500 Eldorado Blvd, Bldg #5 BRM05-212, Broomfield, CO 80021
Work: 303-272-7580, Cell: 303-717-2717


Re: Question about Shamir secret sharing scheme

2009-10-05 Thread Matt Ball
On Sat, Oct 3, 2009 at 12:42 AM, Kevin W. Wall  wrote:
>
> The question that a colleague and I have is there any cryptographic
> purpose of computing the independent coefficients over the finite
> field, Zp ?

Here is a concrete example of information leakage when not using Zp.

Assume that the secret and each additional coefficient is a positive
integer less than 3 (intentionally picking a very small range to keep
the math simple).  Assume there are two shares and that both shares
are needed to recover the secret.  a0 = the secret and a1 is randomly
chosen in the same range.

q(x) = a0 + a1*x

We can make a table of all possible coefficients (a0, a1) and share
values (q(1), q(2)):

(a0, a1, q(1), q(2)) = {
  (0, 0, 0, 0)
  (0, 1, 1, 2)
  (0, 2, 2, 4)
  (1, 0, 1, 1)
  (1, 1, 2, 3)
  (1, 2, 3, 5)
  (2, 0, 2, 2)
  (2, 1, 3, 4)
  (2, 2, 4, 6)
 }

>From this table, it is possible to deduce a0 (the secret) knowing only
q(2), assuming that q(2) is not 4 or 2.  Even then, you know that the
secret is not odd.  Knowing only q(1) leaks a little less information,
but you can still fully determine the secret if q(1) = 0 or 4, and
partially determine the secret if q(1) is 1 or 3.

Intuitively, the information leakage occurs because the range of q(x)
is larger than the range of the secret a0.

Conversely, when using the set of integers mod 3, the table looks like this:

(a0, a1, q(1) mod 3, q(2) mod 3) = {
  (0, 0, 0, 0)
  (0, 1, 1, 2)
  (0, 2, 2, 1)
  (1, 0, 1, 1)
  (1, 1, 2, 0)
  (1, 2, 0, 2)
  (2, 0, 2, 2)
  (2, 1, 0, 1)
  (2, 2, 1, 0)
 }

It's easy to confirm by visual inspection that knowledge of q(1) or
q(2) alone does not reveal any information about the secret a0.

>
>  The only reason that we can see to doing this is to
> keep the sizes of the shares Si bounded within some reasonable range
> and it seems as though one could just do something like allowing T
> choose random coefficients from a sufficient # of bytes and just
> do all the calculations without the 'mod p' stuff.

In any real implementation, you'd want to use a binary finite field,
such as GF(2^8) or GF(2^16).  This is way faster than using a
non-binary finite field.  The 'mod p' stuff would be optimized into a
series of fast table lookups.

For example, if you want to generate shares for a 512-bit ECC Key, you
would first divide it into 64 bytes (each of which fits inside
GF(2^8)), and then compute 64 independent shares.  Each multiply would
be a couple table look-ups and your done.

Conversely, If you were using a non-binary finite field, your best bet
is probably using 2^521-1 (a.k.a., P-521 or the 13th Mersenne prime).
However, this is way slower than 64 GF(2^8) operations because the
time required to multiply two large integers grows with the square of
the size n.  (Technically you can do it in n log n operations by using
Fourier Transforms, but this is only useful with really big integers
and you have to watch for rounding errors).  The modulo computation
with P-521 would just be a couple BIGNUM subtractions.

Even worse, if you used the set of integers (Z), the evaluated points
on the polynomial would require about d*64 bytes of storage, where d
is the degree of your polynomial (i.e., the threshold number of shares
needed to recover the secret).  The time required to do all these
multiples would roughly grow quadratically with the threshold (or
rather n log n because at this point, using Fourier transforms starts
to become appealing).

This is all moot, though, because using Z is not secure.

>
> We thought perhaps
> Shamir did the calculations of Zp because things like Java's BigInteger
> or BigDecimal weren't widely available when came up with this
> scheme back in 1979.
>
Even today, I don't see why anyone would use BigInteger or BigDecimal
for Shamir's Secret Sharing.  As I mentioned above, the time required
for a BigInteger operation grows faster than linearly with the size of
the secret (either n log n or n^2), as opposed to linear growth with a
binary field.

You might argue that BigInteger and BigDecimal are 'easy to use', but
when considering the substantially slower execution time and the extra
burden of dealing with very large shares, it's really not a net
savings.  Besides, there are many useful implementations of Shamir
Secret sharing that you could import into Java with much less work
required than reimplementing the algorithm from scratch.

Cheers,
-Matt

Matt Ball, Chair, IEEE P1619 Security in Storage Working Group
Staff Engineer, Sun Microsystems, Inc.
500 Eldorado Blvd, Bldg #5 BRM05-212, Broomfield, CO 80021
Work: 303-272-7580, Cell: 303-717-2717

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Re: RNG using AES CTR as encryption algorithm

2009-09-09 Thread Matt Ball
On Tue, Sep 1, 2009 at 11:28 PM, priya yelgar wrote:
> I have implemented RNG using AES algorithm in CTR mode.
>
> To test my implementation I needed some test vectors.
>
> How ever I searched on the CSRC site, but found the test vectors for AES_CBC 
> not for AES CTR.
>
> Please  can any one tell me where to look for the test vectors to test RNG 
> using  AES CTR.

The first thing that jumps out at me is that you're looking for a
nebulous "Randon Number Generator" based on AES CTR mode (defined by
SP 800-38A), and this is cast in the context of NIST's CSRC website
(http://csrc.nist.gov/).  Referencing NIST implies that you're looking
for some kind Algorithm Certificate or FIPS 140-2 certification for a
cryptographic module.  If this is true, then you cannot just use 'AES
CTR' to generate FIPS-approved random numbers.  Instead, you need to
use one of the approved RNG methods listed in FIPS 140-2 Annex C
"Approved Random Number Generators".  This includes several RNGs,
including AES and 3DES variants based on ANSI X9.31, and SP 800-90.
The closest thing to AES CTR is the CTR_DRBG defined in SP 800-90,
which uses AES CTR for the random number generation, but also handles
important things like distilling the initial entropy pool and periodic
re-keying.

Even if you're not intending to get FIPS 140-2 certification, I still
highly recommend finding a good standard describing a 'recipe' for
generating pseudo-random numbers, and follow the requirements for
that.  'RNG using AES in CTR mode' is much different than 'Encryption
using AES in CTR mode', and needs to be carefully handled accordingly.
 It's really easy to get things wrong outside of the AES CTR portion
of the problem.  You need to worry about justifying a particular
entropy content of your true random source, which is then distilled
down to create your key and nonce for the AES CTR portion of the RNG.
This is not a task that is taken lightly.

My personal recommendation is to go with the CTR_DRBG as defined in SP
800-90.  You can easily find open source implementations of this
algorithm, so I'm not even sure if you need to spend time implementing
it.  To test it, I recommend going through the process of getting an
algorithm certificate from NIST.

Cheers!

Matt Ball, Chair, IEEE P1619 Security in Storage Working Group
Staff Engineer, Sun Microsystems, Inc.
500 Eldorado Blvd, Bldg #5 BRM05-212, Broomfield, CO 80021
Work: 303-272-7580, Cell: 303-717-2717

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Re: AES-GMAC as a hash

2009-09-04 Thread Matt Ball
On Thu, Aug 27, 2009 at 8:45 AM, Darren J Moffat wrote:
>
> Ignoring performance for now what is the consensus on the suitabilty of using 
> AES-GMAC not as MAC but as a hash ?
>
> Would it be safe ?
>
> The "key" input to AES-GMAC would be something well known to the data and/or 
> software.
>
> The only reason I'm asking is assuming it can be made to perform on some 
> classes of machine better than or close to SHA256 if it would be worth 
> considering as an available alternate now until SHA-3 is choosen.

In the 2005 Security in Storage Workshop (see
http://ieeeia.org/sisw/2005/), David McGrew proposed using GMAC to
protect large dynamic data sets, such a random access memory (RAM)
(see http://ieeeia.org/sisw/2005/PreProceedings/10.pdf).  The general
idea is to use the linear characteristics of GMAC to dynamically
update the MAC when updating a memory address.  If your use-case is
similar to this approach, then it would be possible to securely use
GMAC.

However, there are many caveats when using GMAC, so it's vitally
important to understand all the constraints.

Cheers,

Matt Ball, Chair, IEEE P1619 Security in Storage Working Group
Staff Engineer, Sun Microsystems, Inc.
500 Eldorado Blvd, Bldg #5 BRM05-212, Broomfield, CO 80021
Work: 303-272-7580, Cell: 303-717-2717

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Re: Warning! New cryptographic modes!

2009-05-21 Thread Matt Ball
On Mon, May 11, 2009 at 2:54 PM, Jerry Leichter  wrote:
> On May 11, 2009, at 2:16 PM, Roland Dowdeswell wrote:
>
>> On 1241996128 seconds since the Beginning of the UNIX epoch
>> Jerry Leichter wrote:
>> I'm not convinced that a stream cipher is appropriate here because
>> if you change the data then you'll reveal the plaintext.
>
> Well, XOR of old a new plaintext.  But point taken.
>
> Sounds like this might actually be an argument for a stream cipher with a
> more sophisticated combiner than XOR.  (Every time I've suggested that, the
> response has been "That doesn't actually add any strength, so why 
> bother"-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Re: Warning! New cryptographic modes!

2009-05-11 Thread Matt Ball
On Sun, May 10, 2009 at 4:55 PM, Jerry Leichter  wrote:
>
> I recently stumbled across two attempts to solve a cryptographic problem -
> which has lead to what look like rather unfortunate solutions.
>
> The problem has to do with using rsync to maintain backups of 
> directories-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com


Parallel Skein Hash Construction based on the Subset Sum Problem?

2008-10-30 Thread Matt Ball
On Wed, Oct 29, 2008 at 9:23 AM, Stephan Somogyi wrote:
>
> The Skein team has announced its submission to the NIST hash competition:
>
> <http://www.schneier.com/skein.html>
>

Now that we've all had a chance to read the Skein algorithm, I've got
a question for the list:

Would it be possible to construct an efficient parallel version of
Skein with output size N by creating intermediate results of size >2N,
adding them as integers, and then hashing this sum of intermediate
results as the final result?  (That is, would such a construction be
faster than the Skein tree hashing?)  I suspect that this construction
would be secure according to the computational difficulty of solving
the Subset Sum problem (known to be NP-complete), but haven't
rigorously confirmed this.  Skein is able to efficiently create larger
outputs, so such a construction like this would be easier with Skein
than with, say SHA-512.

For example, with Skein-256, you could hash each 256-bit (or larger,
depending on leaf size choice) message chunk into a 512-bit, or
768-bit intermediate value.  This value would then be added to all
other similar hash results (mod 2^512 or 2^768), and this result would
be hashed one more time for the final result.

It's necessary to make the intermediate results at least 2x the final
hash size because the best known solution to the subset sum problem is
solvable in 2^(N/2) operations.  There's also the issue of tying the
complexity of an addition operation to the complexity of computing a
single hash result (e.g., 1 N-bit Hash might equal 100 N-bit modular
adds).  For this reason, using 3x the final hash size for
intermediates would be more conservative.

General Comments on Skein:

Overall, I'm very happy with the results of Skein, and the three-fish
project.  When Ron Rivest described his "Halloween" hashing function
during Crypto 2008, I liked its simplicity (only simple operators),
but disliked that it was slower than SHA-256 and SHA-512.  Skein has
both delivered on security (so we think) and is faster and simpler
than existing NIST hashing functions and block ciphers.  In my
opinion, SHA-2 and AES have already pegged the meter on practical
security (of course, this may one day be false...), but there hasn't
been enough emphasis on efficiency, cost, and parallelism.

By using 64-bit addition as one of Skein's basic operations, the
resistance against Shamir's "Cube attack" increases, although the
hardware complexity increases quite a bit over Ron Rivest group's
choice of operators that have no carry.

I suspect that (as with the AES competition), that all of the
contestants of the final round with be secure, and the winner will be
the one that is most efficient, and to some extend, most flexible
(although too much flexibility causes implementation issues when
non-cryptographers have to write code to support all the options, and
the designers have to be smart enough to pick the correct
configuration).

With more submissions like this, I expect we will be poised for an
exciting NIST hash competition!

Cheers,
-Matt

Matt Ball, IEEE P1619.x SISWG Chair
Cell: 303-717-2717
http://www.linkedin.com/in/matthewvball
http://www.mavaball.net/

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


NIST has posted public comments on XTS-AES

2008-09-12 Thread Matt Ball
Hi Folks,

NIST has completed the 90-day public review of the proposal from IEEE
1619 to add XTS-AES as an Approved Mode of Operation under FIPS 140.

XTS-AES provides a "narrow-block" tweakable block cipher based on the
XEX construction proposed by Phillip Rogaway.

See the following link for comments, under the section "Comments On
The Proposal To Approve XTS-AES":
http://csrc.nist.gov/groups/ST/toolkit/BCM/comments.html

NIST received comments from the following individuals:
* Moses Liskov, Kazuhiko Minematsu:
http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/XTS/XTS_comments-Liskov_Minematsu.pdf
* Seagate Technology:
http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/XTS/XTS_comments-Seagate.pdf
* Matt Ball: 
http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/XTS/XTS_comments-Ball.pdf
* Collected comments:
http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/XTS/collected_XTS_comments.pdf
 - Boaz Shahar
 - David Clunie
 - Rich Shroeppel
 - Phillip Rogaway
 - Vijay Bharadwaj, Neils Ferguson

Based on these comments, NIST will decide whether or not to approve
XTS for FIPS 140-2/140-3.

--
Thanks!
-Matt

Matt Ball, IEEE P1619.x SISWG Chair
Cell: 303-717-2717
http://www.linkedin.com/in/matthewvball
http://www.mavaball.net/

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Period for public comments on XTS (as standardized by IEEE std 1619-2007) ends Sept 3, 2008

2008-08-24 Thread Matt Ball
Hi Folks,

Please remember that the 90-day public comment period for XTS ends
Sept 3, which is coming up very quickly.  If you have any comments you
would like to submit to NIST concerning XTS-AES (as specified in IEEE
Std 1619-2007), please send an e-mail to [EMAIL PROTECTED]

The excerpt of IEEE 1619-2007 that specifies XTS-AES will be removed
after the public review period ends.  If you would like to get a free
copy of the XTS specification, this will be your last chance!  See
http://grouper.ieee.org/groups/1619tmp/1619-2007-NIST-Submission.pdf

[Original solicitation from NIST:]

Request for Public Comment on XTS (See
http://csrc.nist.gov/groups/ST/documents/Request-for-Public-Comment-on_XTS.pdf)

The P1619 Task Group of the Security in Storage Working Group (SISWG)
of the Institute of Electrical and Electronics Engineers, Inc. (IEEE)
has submitted the XTS-AES algorithm (XTS, for short) to NIST as an
encryption mode of operation of the Advanced Encryption Standard (AES)
block cipher. Although XTS does not provide authentication in order to
avoid expansion of the data, it is designed to provide some protection
against malicious manipulation of the encrypted data. Subject to the
90-day period of public comment that is described below, NIST proposes
to approve XTS for government use under the auspices of FIPS Pub.
140-2.

XTS is specified in IEEE Std 1619-2007. IEEE has agreed to make a
relevant extract from this standard available for free during the
period of public comment. NIST proposes to approve the specification
by reference to IEEE Std 1619-2007, while reserving the right to
specify additional requirements/restrictions on XTS for government
use. After the period of public comment, the standard would be
available for purchase from IEEE for $85 to IEEE members and
affiliates, and $105 to non-members. The chair of the SISWG informed
NIST that he is unaware of any patent claims on XTS, but that NeoScale
Systems, subsequently acquired by nCipher, submitted a Letter of
Assurance of Essential Patents to the IEEE, without elaborating on
what aspect of IEEE 1619 was patented.

The period of public comment for this proposal is from June 5, 2008 to
September 3, 2008. The extract of IEEE Std 1619-2007 is available for
free during this period at
http://grouper.ieee.org/groups/1619tmp/1619-2007-NIST-Submission.pdf.

Comments may be submitted to [EMAIL PROTECTED] NIST
particularly invites comments on the following topics:
* The XTS algorithm itself;
* The depth of support in the storage industry for which it was designed;
* The appeal of XTS for wider applications;
* The proposal for the approved specification to be available only by
purchase from IEEE;
* Concerns of intellectual property rights.

Thanks!
-Matt

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: security questions

2008-08-06 Thread Matt Ball
On Wed, Aug 6, 2008 at 9:23 AM, Peter Saint-Andre wrote:
>
> Wells Fargo is requiring their online banking customers to provide answers to 
> security questions such as these:
>
> ***
>
> What is name of the hospital in which your first child was born?
...
> What was your most memorable gift as a child?
>
> ***
>
> It strikes me that the answers to many of these questions might be public 
> information or subject to social engineering attacks...
>
> Peter

Of course, this problem isn't limited to Wells Fargo:  I think pretty
much all banks do it.

I've given this some thought, and am writing a program called "maiden"
(short for "mother's maiden name") for cryptographically answering
these questions.

The basic idea is that you take either a pass phrase or strong secret,
combine it with the question, compute the SHA hash, and use this to
create a word that looks semi-pronounceable as the answer to the
question.

Right now, I don't answer any of these questions with any guessable
information -- it's all the result of a cryptographic operation on the
question and a hidden secret.

Cheers,
-Matt

--
Thanks!
Matt Ball, IEEE P1619.x SISWG Chair
M.V. Ball Technical Consulting, Inc.
Phone: 303-469-2469, Cell: 303-717-2717
http://www.mvballtech.com
http://www.linkedin.com/in/matthewvball

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: Looking through a modulo operation

2008-07-22 Thread Matt Ball
On Mon, Jul 21, 2008 at 8:33 AM, Matt Ball <[EMAIL PROTECTED]> wrote:
>
>"If someone uses the __random32 function as defined in the 2.6.26
> Linux kernel, and leaks to you the result of taking successive outputs
> modulo 28233 (= 9 * 3137), can you determine the probable 96-bit
> internal state with fewer than 1000 outputs and with modest processing
> power (e.g., a laptop computer running less than a day)?"
>

Another attacking avenue is the 32-bit initial seed.  If the
implementation re-seeds frequently, or leaks to you the first outputs
after initialization, then you only have to brute-force the 32-bit
seed space, times the number of samples since reseeding.

Here is the function that performs the initial seeding, based on a 32-bit seed:

static void __set_random32(struct rnd_state *state, unsigned long s)
{
if (s == 0)
s = 1;  /* default seed is 1 */
#define LCG(n) (69069 * n)
state->s1 = LCG(s);
state->s2 = LCG(state->s1);
state->s3 = LCG(state->s2);
/* "warm it up" */
__random32(state);
__random32(state);
__random32(state);
__random32(state);
__random32(state);
__random32(state);
}

For those who want to get cleaver, I suspect there is an optimization
for running __random32 six times.

--
Thanks!
Matt Ball, IEEE P1619.x SISWG Chair
M.V. Ball Technical Consulting, Inc.
Phone: 303-469-2469, Cell: 303-717-2717
http://www.mvballtech.com
http://www.linkedin.com/in/matthewvball

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: Looking through a modulo operation

2008-07-21 Thread Matt Ball
On Sun, Jul 20, 2008 at 4:50 AM, Florian Weimer wrote:

> I've got a function f : S -> X x S where S = (Z/2Z)**96 and
> X = (Z/2Z)**32.  Suppose that s_0 is fixed and (x_i, s_i) = f(s_{i-1}).
> (f implements a PRNG.  The s_i are subsequent internal states and the
> x_i are results.)
>
> Now f happens to be linear.  I know the values of x_i, x_{i+1}, ...,
> x_{i+k} module N, for a fixed, known N.  N is odd (but divisible by 9).
> Is it possible to recover s_i with reasonable effort (better than brute
> force, and k should be in the hundreds, not thousands)?  And if yes, how?
> Prediction of candidates for x_{i+k+1} with high probability would be
> helpful, too.
>
> (Obviously, using f as an unpredictable PRNG is not a good idea.  But if
> there's a real attack I can present, convincing the authors to replace
> it would be so much easier.)
>

>From a little bit of off-line discussion, I think I've got a restatement of
the problem that is more suitable to those with a stronger programming
background than mathematical background:

"If someone uses the __random32 function as defined in the 2.6.26 Linux
kernel, and leaks to you the result of taking successive outputs modulo
28233 (= 9 * 3137), can you determine the probable 96-bit internal state
with fewer than 1000 outputs and with modest processing power (e.g., a
laptop computer running less than a day)?"

Here is a C implementation of __random32:

typedef unsigned long u32;
struct rnd_state { u32 s1, s2, s3; };
static u32 __random32(struct rnd_state *state)
{
#define TAUSWORTHE(s,a,b,c,d) ((s&c)<>b)

state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12);
state->s2 = TAUSWORTHE(state->s2,  2, 25, 4294967288UL, 4);
state->s3 = TAUSWORTHE(state->s3,  3, 11, 4294967280UL, 17);

return (state->s1 ^ state->s2 ^ state->s3);
}

__random32: See
http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=lib/random32.c;h=ca87d86992bdb7bfd6bb30d4dbe6dcefe2bab7b9;hb=bce7f793daec3e65ec5c5705d2457b81fe7b5725

Cheers,
-Matt

-- 
Thanks!
Matt Ball, IEEE P1619.x SISWG Chair
M.V. Ball Technical Consulting, Inc.
Phone: 303-469-2469, Cell: 303-717-2717
http://www.mvballtech.com
http://www.linkedin.com/in/matthewvball
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


The 2008 IEEE Key Management Summit is Currently Seeking Panelists

2008-07-09 Thread Matt Ball
The 2008 IEEE Key Management Summit (KMS) is currently seeking six panelists
to act as the voice of customers who have purchased or plan to purchase a
cryptographic key management solution.

The panels will be moderated by leading analysts Jon Oltsik of the
Enterprise Strategy Group, and Ramon Krikken of the Burton Group.

If you are interested in participating or know of someone who might be
interested, please send an e-mail to [EMAIL PROTECTED]

Examples of industries we would like to hear from:

   - Financial -- banks, credit card processing, credit unions, mutual fund
   managers, etc
   - Health Care -- key management for HIPAA compliance, etc
   - Government -- handling sensitive but unclassified information


See more details at http://www.keymanagementsummit.com/2008/

About KMS 2008:

> The IEEE Key Management Summit brings together the top companies that
> develop cryptographic key management for storage devices with the standards
> organizations that make interoperability possible and the customers that
> rely on key management to secure their encrypted data.
>
> With recent legislation, such as California's SB 1386 or Sarbanes-Oxley,
> companies now have to publicly disclose when they lose unencrypted personal
> data.  To meet this new need for encryption, many companies have developed
> solutions that encrypt data on hard disks and tape cartridges.  The problem
> is that these data storage vendors need a solution for managing the
> cryptographic keys that protect the encrypted data.
>
> This summit aims to provide clarity to the key management by showing how
> existing products and standards organizations address the problem of
> interoperability and security.
>
> KMS 2008 is co-located with the IEEE Mass Storage and Systems Technologies
> conference <http://storageconference.org/2008/> (MSST) in Baltimore,
> Maryland on September 23-24, 2008.
>

Thanks!
Matt Ball, Chair, KMS 2008
Phone: 303-469-2469, Cell: 303-717-2717
http://www.linkedin.com/in/matthewvball

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]