encryption algorithm preserve order
Lisa Tang
I have posted a similar question subjected "Randomly enlarge number with
sequence preserved". With lot of help and response, I learn more about what
I really need. Since there is some change in the requirement, I just like to
start a new post.
I am looking for algorithms f(p, k), F(P, K) that can fullfill the following
requirements and be practical to be implemented using programmnig language.
p = 8 bytes data
q = 8 bytes data
k = key
K can be equal to k or can be different from k
F() can be equal to f() or can be different from f()
P = 16 bytes data
Q = 16 bytes data
P = f(p, k)
Q = f(q, k)
1. P < Q, for all p < q
p = F(P, K)
q = F(Q, K)
2. given know pair of (p, P), even with knowledge of functions (i.e. f(),
F()), w/o knowledge of K, it is difficult to guess K
3. given some P and Q, even with knowledge of functions (i.e. f(), F()), w/o
knowledge of K, it is difficult to guess p, q
Thank you.
LT
jsa...@ecn.ab.ca
: I am looking for algorithms f(p, k), F(P, K) that can fullfill the following
: requirements
What I suggested meets almost all your requirements, but it does NOT
provide, easily, once one makes it complicated enough not to be obviously
inverted by an attacker, for an inverse function. (One could be done, and
it would work, knowing the key, but it would require a degree of hunting
for the soluton.)
It may be possible a solution exists, but I don't know of one. You might
want to ask your question on sci.math as well, as you might be more likely
to find someone who did know something useful. I believe that what you are
posing is a difficult problem.
Certainly, sequences having the properties of f and F obviously exist. But
can any of them be computed directly by an algorithm?
If you want it to be hard to invert given _one_ P, but you don't expect an
attacker to intercept both a P and a Q, it's easy enough: P = some random
128 bit number + 5 * p, for example. The randomness of the starting point
protects just one message, while the pattern formed by the successive
equivalents of various p's is very poor.
Maybe this is a hint, though, about how to satisfy your requirement. I wil
continue thinking about the problem.
John Savard
John E. Hadstate
"Lisa Tang" <lta...@yahoo.com> wrote in message
news:ai0ujh$sj...@imsp212.netvigator.com...
> Hi,
>
> I have posted a similar question subjected "Randomly enlarge number
with
> sequence preserved". With lot of help and response, I learn more about
what
> I really need. Since there is some change in the requirement, I just
like to
> start a new post.
>
I believe you are over-designing your application. What you are asking
for would be called an "order-preserving cipher". I would expect most
ciphers with this property to be relatively weak.
Perhaps you would be so kind as to describe the real problem you are
trying to solve so that we might bring more experience to bear on a
solution?
Mok-Kong Shen
Lisa Tang wrote:
>
[snip]
> 1. P < Q, for all p < q
[snip]
Could you tell the relevance of this condition in
a practical application? Thanks.
M. K. Shen
jsa...@ecn.ab.ca
: I believe you are over-designing your application. What you are asking
: for would be called an "order-preserving cipher". I would expect most
: ciphers with this property to be relatively weak.
: Perhaps you would be so kind as to describe the real problem you are
: trying to solve so that we might bring more experience to bear on a
: solution?
I would agree that it _may_ be easier to modify the application involved,
to find some other way to meet the needs required, than to construct a
cipher that meets the conditions set forth.
That is not to say, though, that the problem of designing a cipher of that
type is not something of mathematical interest. Simply because it is hard,
it may contain interesting theoretical insights.
John Savard
jsa...@ecn.ab.ca
: P = 16 bytes data
: Q = 16 bytes data
I think you're going to have to accept, in order to meet all your other
requirements, that the size of P and Q will have to be considerably larger
than just twice the size of p and q. Perhaps, say, 256 bytes of data, to
really have a chance of the cipher being secure.
John Savard
jsa...@ecn.ab.ca
I have thought more about the problem, and while the solution I have come
up with does need more than 16 bytes, it is not _too_ bad.
The method I describe uses a number of keys. They can be generated from
some single key using some type of stream cipher, and this is called a key
schedule.
It is based on the idea of a 4-of-8 code.
There are 70 possible combinations of bits of the form:
00001111
00011101
00011110
...
11101000
11110000
that is, where exactly four bits are 1 and four bits are 0.
Each of those can become an order-preserving cipher that takes two bits to
three bits; i.e., the combination
01011001
can be thought of as the cipher
00 -> 001
01 -> 011
10 -> 100
11 -> 111
where if the input is n, the output is the position of the n-th 1 bit in
the code symbol.
As our first order-preserving step, the input p is changed to
(p, DES(p,k1))
k1 is the first 56 bits of key material that we use. Already, our input
has increased from 8 bytes to 16 bytes in size, and it will grow more.
Our second step is to take the first two bits of the result, and encipher
them using one of these 4-of-8 codes. What we do is to take the last 64
bits of the block, and put them in an accumulator on the side, and
encipher them again using k2. Some sort of checksum of the result is used
to pick one of the 70 possible 4-of-8 codes.
So after the second step, we have:
the first two bits of p, encrypted by a 4-of-8 code picked by
DES(DES(p,k1),k2)
the remaining 62 bits of p
DES(p,k1)
Now we keep repeating the step, but we nibble into the remaining parts of
p, so after the third step we have
the first two bits of p, encrypted by a 4-of-8 code picked by
DES(DES(p,k1),k2)
the next two bits of p, encrypted by a 4-of-8 code picked by
DES(DES(DES(p,k1),k2),k2)
the remaining 60 bits of p
DES(p,k1)
and you keep on going until the whole of p is converted from two-bit
portions to three-bit portions.
After this first layer of encryption, if one is presented with a P value,
one already is _somewhat_ uncertain about the p value that was its source.
But the uncertainty isn't really strong enough.
The result at this point is now 20 bytes long.
Starting with DES(p,k1), and this time encrypting it over and over again
with k3 to determine what you do, you take the 96 bits that begin the
block, and expand them to 127 bits by inserting 31 zero bits randomly.
This can be done, for example, by taking the remainder of
DES(DES(p,k1),k3) modulo 97 to pick where the first zero bit goes in,
taking the remainder of DES(DES(DES(p,k1),k3),k3) modulo 98 to pick where
the second zero bit goes in, and so on.
These 127 bits then have a 127-bit random value added to them, and this
value is another part of the key.
Order is still preserved, and the result is now 24 bytes long.
Now, using k4 instead of k2, use the same procedure as before to expand
the first 128 bits of the block to 192 bits.
You have a 32 byte block at the end of the process, and you can invert the
process, because DES(p,k1) is plainly visible, so you can start by
encrypting it by k4 repeatedly to find the 4-of-8 coding that you need to
reverse for each group of three bits to deal with.
Of course, you can just find p by decrypting the last 64 bits with k1 as
well. However, those last 64 bits could just as easily be DES(H(p),k1)
where H(p) is a one-way-hash of p, or they could just be 32 bits in
length, if deriving the intermediate values in the process from a 32 bit
seed is considered secure enough.
I won't say this process is *highly* secure, though. But it should indeed
create some degree of uncertainty about the value of p given P for an
adversary who hasn't captured *too* many valid (p,P) pairs to work from.
John Savard
jsa...@ecn.ab.ca
: I have posted a similar question subjected "Randomly enlarge number with
: sequence preserved". With lot of help and response, I learn more about what
: I really need. Since there is some change in the requirement, I just like to
: start a new post.
I have come up with another idea.
I thought at first it could be used to enlarge 8 bytes to only 16, but it
would be very insecure that way.
The basic idea is that we find a way to generate, at random, a code that
takes the byte values 0 through 255 to other distinct values from 0 to 255
in a random order. Ways to do this from a key are given in the
descriptions of the Quadibloc ciphers on my web page, at
http://home.ecn.ab.ca/~jsavard/crypto/co0407.htm
Then once we have such a code, we can go through it, and see how many
stretches there are of numbers that are increasing. So we can make a code
that takes 8 bits to 16 bits and preserves order that looks like:
0 -> 0 137
1 -> 1 48
2 -> 1 96
3 -> 1 201
4 -> 2 13
where the second byte is the byte in our random permutation, and the first
byte is increased by only the minimum amount needed to maintain order
preservation.
Then we look and see by how much the first byte of the code for 255 falls
short of 255. This lets us know how much freedom we have to increase the
first byte to randomize the code. We could just choose an overall offset,
or choose places at which to add 1 to the first byte of the code in that
place and all following places repeatedly.
Again, use a scrambling of the original p value as the source for picking
these codes somehow.
This has the advantage of spreading things over a wider area than a 4-of-8
code, but it leaves too much structure behind; this is why I think that
perhaps the two methods should be combined, even though this makes the P
values quite long.
One starts with (p,DES(p,k1)) again, and first replaces p by 16 bytes with
this method, and then expands the 16 bytes to in turn to 24 bytes, 32
bytes, and 48 bytes by the other process, to get a 56-byte result.
John Savard
jsa...@ecn.ab.ca
than 16 bytes was because I was making a mistake.
In my methods, many values for each byte, particularly the first byte, are
not used. This is not good for security.
I have a better method now - and it takes 8 bytes to only 16 bytes as
well! But it may still not be perfect.
Using only the key, create (using some random method) 255 random numbers
from 0 to 2^64 which are in numerical order. The intent is to randomly
partition the space from 0 to 2^64-1 into 256 pieces. Just generating 255
random numbers and sorting them, for example, _may_ not give the ideal
distribution for this; this is a fine point which a mathematician could
perhaps answer, or which I will think of an answer for.
Now, then, given p, comparing it to those 255 numbers shows what the first
byte of the code for p is.
Using the key as input, as well as the value of the first byte of the
code, and the range that first byte corresponds to, now partition that
range into 256 pieces.
The using the key, the first two bytes of the code, and the range we are
now in, work out the partition for the next byte...
and do this eight times.
On average, each set of values for the first eight bytes will correspond
to one value, but some will be empty, and some will have multiple values.
But we have eight bytes left, so even if all the bytes went into one set
of pigeonholes, we can still preserve order and code everything!
Using the remaining range, and the eight bytes of the coded part as input,
work out a random multiplication factor and number to add to the value to
spread out the possible values over the 2^64 possibilities for the last
eight bytes.
Since that is a uniform spacing, there is insecurity if one has two (P,p)
pairs with the same first eight bytes, but it comes much closer to what
you are looking for than my previous suggestions. If you are willing to go
to 24 bytes, though, the chance of problems becomes much smaller.
John Savard
David Wagner
>I am looking for algorithms f(p, k), F(P, K) that can fullfill the following
>requirements and be practical to be implemented using programmnig language.
>P = f(p, k)
>Q = f(q, k)
>
>1. P < Q, for all p < q
No algorithm that satisfies these properties can be very secure.
In particular, there will always be a trivial chosen-plaintext attack
to recover p given P using just O(log n) encryptions, if p is n bits long.
I don't think you're likely to find a secure algorithm with the
properties you want. What are you really looking for? What are you
trying to achieve with the algorithm f? What is your application, really?
Maybe we can find a better way to solve your application.
David Wagner
>In particular, there will always be a trivial chosen-plaintext attack
>to recover p given P using just O(log n) encryptions, if p is n bits long.
Sorry, that should be O(n) encryptions, and I should have mentioned
that the algorithm is simply "binary search".
jsa...@ecn.ab.ca
: No algorithm that satisfies these properties can be very secure.
: In particular, there will always be a trivial chosen-plaintext attack
: to recover p given P using just O(log n) encryptions, if p is n bits long.
: I don't think you're likely to find a secure algorithm with the
: properties you want. What are you really looking for? What are you
: trying to achieve with the algorithm f? What is your application, really?
: Maybe we can find a better way to solve your application.
I agree with you that the order-preserving property places a severe limit
on the possible security, and that for just about any imaginable
application, there would be a better way of doing this.
However, I finally have come up with a solution that meets her
constraints.
For the 16 bytes of the final coded result, one proceeds as follows:
Given the key, one starts with the first byte, and produces a distribution
of the range of the input among the 256 possible coded byte values.
Then, when coding a particular value, or decoding a result with a
particular first byte, one works from the remaining range and the key
(suitably scrambled using the first byte actually used, so that all the
distributions used are different) to make a distribution of the remaining
range among the 256 possible coded byte values.
The nature of the distribution, however, changes with each byte.
For the first byte, the distribution will be made highly uneven so that
possibly just one value has almost all the range - but not necessarily.
So the probability that a 16-byte value beginning with 11101111 might be
an eight-byte value beginning with 000000000000 would NOT be impossibly
low, despite order being preserved. This is why the distribution has to
start out as having a tendency to be very uneven.
For the next few bytes, the distribution may just be random, or it may be
highly uneven - and it will be uneven in the case where in the preceding
bytes, the byte used happened to be the one that got most of the range.
Then, for the remainder of the first eight bytes, the distribution will
basically be a plain random one.
After the first eight bytes, the distribution will be constrained. Thus,
if a lot of values have been allocated to the particular combination of
the first eight bytes in use, the distribution for the ninth byte will be
constrained, so that no possible value covers more than 2^56
possibilities.
The limit for the tenth byte will be 2^48 possibilities for each value,
and so on. This ensures it will always be possible to give every input
value a unique code.
This is it; this is about as good a solution to the problem posed as is
possible. I do hope this wasn't a homework problem.
I know this may not be simple and explicit enough to be perfectly clear,
but if one is trying to do this, one's programmer had better know enough
math to be able to work from an outline at this level. Instead of
generating successive values, as I outlined in the similar proposal, one
should try to randomly generate how many of the possible values go in the
various slots, first by choosing between the desired distributions, and
then randomizing the order of the allocation to the 256 codes.
John Savard
John E. Hadstate
<jsa...@ecn.ab.ca> wrote in message
news:cmV09.1424$0f2.380808@localhost...
I suspect it would prove extremely useful in the PKI arena as an
enhancement or alternative to D-H.
John E. Hadstate
Let's try this:
(1) Using your key to seed a PRNG, generate an array of 512 sixteen-bit
numbers.
(2) Sort the array in ascending order. Scan the array and eliminate all
duplicates. If there are not at least 256 sixteen-bit numbers left,
generate enough more random numbers to fill the array and repeat step
(2).
(3) Each time the function f(p,k) is called, ignore k and use p as the
subscript into the array generated in step (2).
(4) The inverse function F(P,K) can be computed any number of ways. You
can do a binary search of the sorted sixteen-bit table looking for which
table entry p contains the value P. You can create a reverse-lookup
table of 65536 entries, 256 of which contain valid p-values (the rest
can contain 0xFFFF or some such thing).
Does this meet your criteria?
YES> p = 8 bytes data
YES> q = 8 bytes data
YES> k = key
YES> K can be equal to k or can be different from k
YES> F() can be equal to f() or can be different from f()
YES> P = 16 bytes data
YES> Q = 16 bytes data
>
YES> P = f(p, k)
YES> Q = f(q, k)
>
YES> 1. P < Q, for all p < q
>
YES> p = F(P, K)
YES> q = F(Q, K)
>
YES> 2. given know pair of (p, P), even with knowledge of
functions (i.e. f(),F()), w/o knowledge of K, it is
difficult to guess K
YES> 3. given some P and Q, even with knowledge of functions
(i.e. f(), F()), w/o
> knowledge of K, it is difficult to guess p, q
>
I think this does what you asked-for. Now, are you really sure that
what you asked-for is what you want? ;-)
Mok-Kong Shen
"John E. Hadstate" wrote:
>
> Let's try this:
>
> (1) Using your key to seed a PRNG, generate an array of 512 sixteen-bit
> numbers.
>
> (2) Sort the array in ascending order. Scan the array and eliminate all
> duplicates. If there are not at least 256 sixteen-bit numbers left,
> generate enough more random numbers to fill the array and repeat step
> (2).
>
> (3) Each time the function f(p,k) is called, ignore k and use p as the
> subscript into the array generated in step (2).
[snip]
I don't understand why one uses '256 sixteen-bit numbers'.
According to OP, p has 8 bytes and P has 16 bytes!
M. K. Shen
Scott Fluhrer
One possibility which formally meets the above criteria (but I suspect will
not meet the requirements of your application) is:
f(p, k) = p + HASH(k)
F(P, K) = P - HASH(K)
where HASH is a one way function with a normally distributed output, with
mean 2**127 and standard deviation perhaps 2**120, and thus has effectively
0 probability at 0 and at 2**128). This is needed to get around the edge
conditions such as "if f(p, k)=0, then p=0".
I say that I suspect it doesn't meet the real criteria, because I suspect
criteria 2 really should be "given p, P,Q s.t. p=f(P,K) and P!=Q, it is
difficult to compute f(Q,K)". Is something like this the correct criteria?
For that matter, what's the real problem you're trying to solve?
--
poncho
Mok-Kong Shen
Could you elaborate how does your function f deliver
16 bytes with input p of 8 bytes? (How large is HASH(k)
and when p is added to it?) Thanks.
M. K. Shen
jsa...@ecn.ab.ca
: I suspect it would prove extremely useful in the PKI arena as an
: enhancement or alternative to D-H.
Hmm. I can't quite see how that would work - my algorithm to do this is
very definitely a symmetric-key method.
I was thinking in terms of very pedestrian applications, such as a
smartcard telling you you have enough money to buy something without
revealing its price, or a case where you need monotonic serial numbers
which don't reveal the exact position of an item in the sequence (maybe
replacing old serial numbers or ID numbers that were compromised).
Perhaps some bizarre deadlock avoidance algorithm in a network which is
attempting to avoid traffic analysis.
John Savard
John E. Hadstate
"Mok-Kong Shen" <mok-ko...@t-online.de> wrote in message
news:3D447BFC...@t-online.de...
Bits, bytes, what's the difference ;-)
Seriously, I just flat misread the OP's specs.
I'm busted :-(
However, since my cipher (it is a substitution cipher, by the way) is
order-preserving, it could be applied byte-by-byte to the input to
transform 8 bytes into 16 bytes. The rest of the conditions, including
order-preservation, will still be met.
Now, if the OP wants to get really kinky, she can recompute the
substitution table for each byte of input. The cipher will begin to
look like dynamic substitution and will gain some strength at the cost
of a substantial performance penalty.
John E. Hadstate
Bits, bytes, what's the difference ;-)
Edward Elliott
> I was thinking in terms of very pedestrian applications, such as a
> smartcard telling you you have enough money to buy something without
> revealing its price,
Egads! Why would I ever want to do that?
Edward Elliott
jsa...@ecn.ab.ca
Yes, I have to count my pennies too... but presumably something
_analogous_ to that which didn't involve purchasing things with a risk of
pauperizing oneself could be the application. I'm just trying to be
comprehensible, not literal.
John Savard
Mok-Kong Shen
"John E. Hadstate" wrote:
>
> "Mok-Kong Shen" <mok-ko...@t-online.de> wrote:
> >
> > "John E. Hadstate" wrote:
> > >
> >
> > > Let's try this:
> > >
> > > (1) Using your key to seed a PRNG, generate an array of 512
> sixteen-bit
> > > numbers.
> > >
> > > (2) Sort the array in ascending order. Scan the array and eliminate
> all
> > > duplicates. If there are not at least 256 sixteen-bit numbers left,
> > > generate enough more random numbers to fill the array and repeat
> step
> > > (2).
> > >
> > > (3) Each time the function f(p,k) is called, ignore k and use p as
> the
> > > subscript into the array generated in step (2).
> > [snip]
> >
> > I don't understand why one uses '256 sixteen-bit numbers'.
> > According to OP, p has 8 bytes and P has 16 bytes!
> >
> > M. K. Shen
>
> Bits, bytes, what's the difference ;-)
A 'huge' difference I am afraid, if you think
practically. In place of '256 sixteen-bit numbers'
you would get what 'X Y-bit numbers' and in total how
much storage for that array? And you would at least
have quite some difficulties, if you attempt to
address the array in C on your PC, I suppose. (It
might not be feasible even with the current topmost
of the list of world's 500 supercomputers, I would
guess.)
M. K. Shen
Joseph Ashwood
> q = 8 bytes data
> k = key
> K can be equal to k or can be different from k
> F() can be equal to f() or can be different from f()
> P = 16 bytes data
> Q = 16 bytes data
>
> P = f(p, k)
> Q = f(q, k)
>
> 1. P < Q, for all p < q
>
> p = F(P, K)
> q = F(Q, K)
Well assuming that these really are the only requirements to be met
(as opposed to actually requiring that it preserve order. The
following will work, and be secure.
primitive1 = AES, except top byte is bit-wise logically OR'd with
11111111 after the encryption
primitive2 = AES, except top byte is bit-wise logically AND'd with
00000000 after the encryption
Observe that primitive1 will always output something that looks like:
11111111XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Primitive2 will always output
00000000XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Now pad p and q with 0's at the front to make 128-bits
So primitive1(X) > primitive2(Y) for all X and Y.
Choose a random R, or two randoms Rs if you'd prefer it won't matter
as long as k and K are different
f(p, K, R) = p XOR primitive1(K, R)
F(q, k, R) = q XOR primitive2(k, R)
This will guarentee that P > Q for all, regardless of p <?> q. Again I
assume that you only care about P > Q being true when p > q, the other
cases don't matter.
Joe
Rob Warnock
+---------------
To restate John's example in a way that may satisfy Edward:
Suppose you wanted your smartcard to be able to prove to a merchant
that your card has enough money on it to buy an item (or more to the
point, to shop in their store generally), *without* the merchant finding
out exactly how much you *do* have available...
-Rob
-----
Rob Warnock, 30-3-510 <rp...@sgi.com>
SGI Network Engineering <http://www.rpw3.org/>
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
[Note: aaan...@sgi.com and zedw...@sgi.com aren't for humans ]
Lassi Hippeläinen
<...>
> Suppose you wanted your smartcard to be able to prove to a merchant
> that your card has enough money on it to buy an item (or more to the
> point, to shop in their store generally), *without* the merchant finding
> out exactly how much you *do* have available...
Is it possible to do that without a TTP? If not, you're reinventing SET.
-- Lassi
John E. Hadstate
<jsa...@ecn.ab.ca> wrote in message
news:doZ09.1440$0f2.384058@localhost...
This is where I got the idea of creating an ordered set of 256
randomly-chosen 16-bit symbols and using the ordered set to map the
input bytes to output words. Think of it in terms of mapping the digits
0-9 into the capital letters A-J. The number 037 would be coded as ADH;
the number 123 would be coded as BCD. The encoded strings will still
sort in the same order as the original numbers.
The function is invertible if you have access to the mapping table, or
if you know the procedure for building the mapping table. A more
sophisticated mapping than my example might be hard to figure out if you
don't have the mapping table, especially if you change the mapping
table's symbol set frequently.
>
> The nature of the distribution, however, changes with each byte.
>
I don't see why this must be true. The mapping could remain constant
for each byte of input or a new mapping could be established for each
byte. In either case, the distribution should be uniform. Because of
the requirement for order-preservation, you must process the input
string from MSB to LSB, which will cause the output string to retain the
same relative sort order.
Scott Fluhrer
p and F(P,K) is an integer between 0 and 2^{64}-1.
HASH(k) and f(p, k) is an integer between 0 and 2^{128}-1.
Additions/subtractions are done in the group of the integers.
If the result of f(p,k) or F(P,K) is out of the range of the result, the
result is formally undefined. For f(p,k), I tweaked the probability
distribution so that this has effectively 0 probability. And, F(P,K) will
never overflow if P=f(p,K) for some p. I assume that a subcondition of (3)
is that P, Q meet the criteria P=f(p,K), Q=f(q,K) for *some* p, q.
I always set k=K.
And, it really should read "approximately normally distributed output", as
the output of HASH is always an integer.
Really, as I mentioned earlier, I suspect that this does not actually meet
any useful security criteria. It does meet the three criteria given (hmmmm,
other than (3) if P-Q = 2^{64}-1), and so I suspect the criteria given are
not complete. It is difficult to say what the criteria should be without
knowing what the application is.
--
poncho
David Wagner
>Rob Warnock wrote:
>> Suppose you wanted your smartcard to be able to prove to a merchant
>> that your card has enough money on it to buy an item (or more to the
>> point, to shop in their store generally), *without* the merchant finding
>> out exactly how much you *do* have available...
>
>Is it possible to do that without a TTP?
Well, in principle, if you can do it with a TTP, you can usually
do it without... (secure multi-party computation, and all that)
David Wagner
>This is where I got the idea of creating an ordered set of 256
>randomly-chosen 16-bit symbols and using the ordered set to map the
>input bytes to output words. Think of it in terms of mapping the digits
>0-9 into the capital letters A-J.
Probably I'm misunderstanding your intent, but this sounds a lot
like simple substitution ciphers to me. Simple substitution is not
particularly secure. Could this approach resist attack?
Edward Elliott
> Suppose you wanted your smartcard to be able to prove to a merchant
> that your card has enough money on it to buy an item (or more to the
> point, to shop in their store generally), *without* the merchant finding
> out exactly how much you *do* have available...
Ok that is a valid example that many people would be willing to
participate in.
I however am not one of them. The fact that I have a certain threshhold
amount of money, or any money at all for that matter, is none of the
merchant's business.
I don't think many merchants would go for it either. Window shopping
(by which I mean browsing inside the store without intending to buy
anything) generates a lot of business. I may not have enough money on
me today, but if I see something I like I may return in the future.
However very high-end merchants would probably like such a scheme for
the prestige: No one shops in _my_ store without at least $1,000,000.
Like the duty-free shops in the airport which prohibit domestic
travelers from even browsing, I say "Nuts to them!"
Edward Elliott
Edward Elliott
It ought to be possible with one or more of secure computation, blind
signatures, and zero-knowledge proofs. I don't know much about these
fields, but they hold the possibility at least that it can be done.
Edward Elliott
Andrew Swallow
news:ai3su1$1k6t$1...@agate.berkeley.edu...
The shop can hack the card by repeated polling. It
starts low and doubles the amount until the card says too
much. If the naughty shop wants the exact amount it
simply bin chops between the OK and too much
figures.
Andrew Swallow
Edward Elliott
> The shop can hack the card by repeated polling. It
> starts low and doubles the amount until the card says too
> much. If the naughty shop wants the exact amount it
> simply bin chops between the OK and too much
> figures.
Add a time delay to the card between polls. Say it only answers one
poll every 5 minutes. Problem solved.
Edward Elliott
Andrew Swallow
news:3D45957E...@bar.com...
find out if you are a millionaire. They can speed
things up by adjusting the starting point.
Andrew Swallow
Edward Elliott
>>Add a time delay to the card between polls. Say it only answers one
>>poll every 5 minutes. Problem solved.
>>
> Assuming that they are not willing to wait 2 hours to
> find out if you are a millionaire. They can speed
> things up by adjusting the starting point.
Assuming _you_ are not willing to wait 2 hours. You swipe your card as
you enter the store, then it goes back in your wallet. The merchant
will only have an opportunity to make one query.
Edward Elliott
John E. Hadstate
It is a simple substitution cipher. It is very little more
sophisticated than your average garden variety Caesar cipher except it
doesn't use fixed offsets to the symbol substitution and the output
symbols have nothing in common with the input symbols. It could be made
stronger, but not much, by several little subterfuges, one of which
would be to liberally use a random key, another of which would be to use
a different set of mapping tables for each of the 8 input bytes.
Don't ask me why :-)
The lady asked for an order-preserving cipher, and this is an
order-preserving cipher. Just as we both warned in earlier posts, we
expected it to be weak, and it is. Since she hasn't told us why she
wanted this peculiar characteristic, I presume that it was a homework
assignment 8-0
Mok-Kong Shen
"John E. Hadstate" wrote:
>
> "David Wagner" <d...@mozart.cs.berkeley.edu> wrote:
> > Probably I'm misunderstanding your intent, but this sounds a lot
> > like simple substitution ciphers to me. Simple substitution is not
> > particularly secure. Could this approach resist attack?
>
> It is a simple substitution cipher. It is very little more
> sophisticated than your average garden variety Caesar cipher except it
> doesn't use fixed offsets to the symbol substitution and the output
> symbols have nothing in common with the input symbols. It could be made
> stronger, but not much, by several little subterfuges, one of which
> would be to liberally use a random key, another of which would be to use
> a different set of mapping tables for each of the 8 input bytes.
>
> Don't ask me why :-)
>
> The lady asked for an order-preserving cipher, and this is an
> order-preserving cipher. Just as we both warned in earlier posts, we
> expected it to be weak, and it is. Since she hasn't told us why she
> wanted this peculiar characteristic, I presume that it was a homework
> assignment 8-0
As a cipher, i.e. it is required that the receiver is
able to invert f, obtining p from any given P, I believe
it would be rather weak. But, suppose f is only required
to be one-way, or more exactly that, given an output
sequence it is provable that a certain key applied on
a certain input sequence generates the output sequence,
I have some feeling that there might be some solutions
that could be (to some limited extent) acceptable, i.e.
not gravely too bad.
M. K. Shen
Andrew Swallow
Andrew Swallow
Edward Elliott
>>you enter the store, then it goes back in your wallet. The merchant
>>will only have an opportunity to make one query.
>
> Providing you do not return to the shop.
Maybe there's a way to anonymize the cards, such that the merchant can't
tell two swipes of one card from two swipes of two different cards.
Nothing comes to my mind at the moment, but I'm having one of those
days. Someone else have any ideas?
Edward Elliott
Andrew Swallow
date as part of the Key Variable so a different value is
returned every time.
The shop may be able to half hack the change in serial
number if his staff recognise the customer.
Andrew Swallow
Jim Felling
>
> LT
>
>
I cannot concieve of a way to do this securely over anything like the long
term. I suppose single use keys may give something resembling security, but
any system meeting this criterion will fall quickly to chosen/known
plaintext attacks, and have some vulnerabilty cyphertext only attacks as
well.
There are any number of methods that can work, however, none of them will
offer you a great degree of security.
Simplest quick method I can think of is as follows.
k is an ordered list of 64 16 bit numbers call them a(0), to a(63) such that
sum {a(i)} is still a 16 byte value.
Encryption proceds as follows.
if p=0 then temp=0,limit =a(0)-1
If p=2^65 -1 then temp =sum{a(i)} and limit=2^128-1
otherwise temp = sum{a(set bits in p)}, and limit= sum{a(set bits in
[p+1] ) } -1
then generate a random integer between temp and limit (inclusive) and that
output is f(p,k).
This should fit your criteria, however it is still not very secure, and I
would suggest a strong RNG
Jim Felling
"Jim Felling" <james_...@hotmail.com> wrote in message
news:HlJ19.539$3_3.1...@news.uswest.net...
One tiny change ( a side condition on the a(i)'s I forgot to add. a(i)
>sum{ a(j) } where j goes from 0 to i-1.