[tahoe-dev] note about hash-based digital signatures

Zooko O'Whielacronx zooko at zooko.com
Tue Jun 22 23:47:54 PDT 2010


Last login: Sun Jun 20 16:35:11 on ttys000
 Zooko-Ofsimplegeos-MacBook-Pro:~$ mount
/dev/disk0s2 on / (hfs, local, journaled)
devfs on /dev (devfs, local, nobrowse)
map -hosts on /net (autofs, nosuid, automounted, nobrowse)
map auto_home on /home (autofs, automounted, nobrowse)
/dev/disk2s2 on /Volumes/Papers 1.9.4 (hfs, local, nodev, nosuid,
read-only, noowners, quarantine, mounted by zooko)
/dev/disk3s1 on /Volumes/Transcend (msdos, local, nodev, nosuid, noowners)
 Zooko-Ofsimplegeos-MacBook-Pro:~$ cd /Volumes/Transcend/
 Zooko-Ofsimplegeos-MacBook-Pro:/Volumes/Transcend$ ls
log.txt         waronfun
 Zooko-Ofsimplegeos-MacBook-Pro:/Volumes/Transcend$ ls -al
total 80
drwxrwxrwx  1 zooko  staff   4096 Jun 21 23:37 .
drwxrwxrwt@ 5 root   admin    170 Jun 21 23:37 ..
drwxrwxrwx  1 zooko  staff   4096 Jun 21 23:37 .Spotlight-V100
drwxrwxrwx@ 1 zooko  staff   4096 Jun 21 23:37 .Trashes
-rwxrwxrwx  1 zooko  staff   4096 Jun 21 23:37 ._.Trashes
drwxrwxrwx  1 zooko  staff   4096 Jun 21 23:37 .fseventsd
-rwxrwxrwx  1 zooko  staff  16172 Jun 21 23:34 log.txt
drwxrwxrwx  1 zooko  staff   4096 Jun 21 23:35 waronfun
 Zooko-Ofsimplegeos-MacBook-Pro:/Volumes/Transcend$ find waronfun/
waronfun/
waronfun//IMGP5090.jpg
waronfun//IMGP5091.jpg
 Zooko-Ofsimplegeos-MacBook-Pro:/Volumes/Transcend$ cd
 Zooko-Ofsimplegeos-MacBook-Pro:~$ 0i
-bash: 0i: command not found
 Zooko-Ofsimplegeos-MacBook-Pro:~$
 Zooko-Ofsimplegeos-MacBook-Pro:~$ 7za a /Volumes/Transcend/log.txt
-bash: 7za: command not found
 Zooko-Ofsimplegeos-MacBook-Pro:~$ shred
-bash: shred: command not found
 Zooko-Ofsimplegeos-MacBook-Pro:~$ jobs
 Zooko-Ofsimplegeos-MacBook-Pro:~$ cd
 Zooko-Ofsimplegeos-MacBook-Pro:~$ mount
/dev/disk0s2 on / (hfs, local, journaled)
devfs on /dev (devfs, local, nobrowse)
map -hosts on /net (autofs, nosuid, automounted, nobrowse)
map auto_home on /home (autofs, automounted, nobrowse)
/dev/disk2s2 on /Volumes/Papers 1.9.4 (hfs, local, nodev, nosuid,
read-only, noowners, quarantine, mounted by zooko)
 Zooko-Ofsimplegeos-MacBook-Pro:~$ grep -i tailor .pwu.txt
tailor: taamecev
 Zooko-Ofsimplegeos-MacBook-Pro:~$ python -c 'print u"\u2026"'
…
 Zooko-Ofsimplegeos-MacBook-Pro:~$ python -c 'print u"\u2014"'
—
 Zooko-Ofsimplegeos-MacBook-Pro:~$ cd
 Zooko-Ofsimplegeos-MacBook-Pro:~$ cd playground/
 Zooko-Ofsimplegeos-MacBook-Pro:~/playground$ cd penelope/penelope/
.git/           LICENSE.txt     build.xml       ivy.xml
.gitignore      NEWS.txt        conf/           lib/
.rat-excludes   NOTICE.txt      contrib/        src/
CHANGES.txt     README.txt      debian/         test/
DISCLAIMER.txt  bin/            interface/
 Zooko-Ofsimplegeos-MacBook-Pro:~/playground$ cd penelope/penelope/
 Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ git
pull --rebase
remote: Counting objects: 246, done.
remote: Compressing objects: 100% (155/155), done.
remote: Total 211 (delta 95), reused 0 (delta 0)
Receiving objects: 100% (211/211), 306.45 KiB | 398 KiB/s, done.
Resolving deltas: 100% (95/95), completed with 23 local objects.
>From github.com:simplegeo/penelope
   558d13d..4a9df39  penelope   -> origin/penelope
First, rewinding head to replay your work on top of it...
Fast-forwarded penelope to 4a9df39deb340d40b9eb1ba95cfc8802aa4d60d3.
 Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$
 Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$
 Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$
 Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ git diff
...skipping...
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
 Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$
 Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ find .
-iname '*proximi*'
./src/java/com/simplegeo/penelope/db/PenelopeProximityCommand.java
./src/java/com/simplegeo/penelope/db/ProximityPredicate.java
 Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ python
-c 'print u"\u2708"'
✈
 Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ python
-c 'print u"\u2026"'
…
 Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ python
-c 'print u"\u2014"'
—
 Zooko-Ofsimplegeos-MacBook-Pro:~/playground/penelope/penelope$ python -i
Python 2.6.1 (r261:67515, Feb 11 2010, 00:51:29)
[GCC 4.2.1 (Apple Inc. build 5646)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 64*18
1152
>>> 4096*D('6.83')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'D' is not defined
>>> from decimal import Decimal as D
>>> 4096*D('6.83')
Decimal('27975.68')
>>> 4096 / 32
128
>>> (D('8.53')*4096)   / (4096/32)
Decimal('272.96')
>>> 600 * 13000
7800000
>>> 600 * 10000
6000000
>>> print u"\u00b2"
²
>>> print u"\u00b2\u2075\u2076"
²⁵⁶
>>> from decimal import Decimal as D
>>> D('10') ** -12
Decimal('1E-12')
>>> sqrt(D('10') ** -12)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'sqrt' is not defined
>>> import math
>>> math.sqrt(D('10') ** -12)
9.9999999999999995e-07
>>> type(_)_
  File "<stdin>", line 1
    type(_)_
           ^
SyntaxError: invalid syntax
>>> type(_)
<type 'float'>
>>> import math
>>> D('10') ** -12
Decimal('1E-12')
>>> x=_
>>> x
Decimal('1E-12')
>>> dir(x)
['__abs__', '__add__', '__class__', '__complex__', '__copy__',
'__deepcopy__', '__delattr__', '__div__', '__divmod__', '__doc__',
'__eq__', '__float__', '__floordiv__', '__format__', '__ge__',
'__getattribute__', '__gt__', '__hash__', '__init__', '__int__',
'__le__', '__long__', '__lt__', '__mod__', '__module__', '__mul__',
'__ne__', '__neg__', '__new__', '__nonzero__', '__pos__', '__pow__',
'__radd__', '__rdiv__', '__rdivmod__', '__reduce__', '__reduce_ex__',
'__repr__', '__rfloordiv__', '__rmod__', '__rmul__', '__rpow__',
'__rsub__', '__rtruediv__', '__setattr__', '__sizeof__', '__slots__',
'__str__', '__sub__', '__subclasshook__', '__truediv__', '__trunc__',
'_check_nans', '_cmp', '_compare_check_nans', '_divide', '_exp',
'_fill_logical', '_fix', '_fix_nan', '_int', '_is_special', '_iseven',
'_isinfinity', '_isinteger', '_islogical', '_isnan', '_ln_exp_bound',
'_log10_exp_bound', '_pick_rounding_function', '_power_exact',
'_power_modulo', '_rescale', '_round', '_round_05up',
'_round_ceiling', '_round_down', '_round_floor', '_round_half_down',
'_round_half_even', '_round_half_up', '_round_up', '_sign',
'adjusted', 'as_tuple', 'canonical', 'compare', 'compare_signal',
'compare_total', 'compare_total_mag', 'conjugate', 'copy_abs',
'copy_negate', 'copy_sign', 'exp', 'fma', 'imag', 'is_canonical',
'is_finite', 'is_infinite', 'is_nan', 'is_normal', 'is_qnan',
'is_signed', 'is_snan', 'is_subnormal', 'is_zero', 'ln', 'log10',
'logb', 'logical_and', 'logical_invert', 'logical_or', 'logical_xor',
'max', 'max_mag', 'min', 'min_mag', 'next_minus', 'next_plus',
'next_toward', 'normalize', 'number_class', 'quantize', 'radix',
'real', 'remainder_near', 'rotate', 'same_quantum', 'scaleb', 'shift',
'sqrt', 'to_eng_string', 'to_integral', 'to_integral_exact',
'to_integral_value']
>>> x.sqrt()
Decimal('0.000001')
>>> (x*2).sqrt()
Decimal('0.000001414213562373095048801688724')
>>> (x*2).sqrt() * (2**80)
Decimal('1709679290002018430.137083076')
>>> (x*2).sqrt() * (2**64)
Decimal('26087635650665.56442469914361')
>>> (x*2).sqrt() * (2**70)
Decimal('1669608681642596.123180745191')
>>> (x*2).sqrt() * (2**72)
Decimal('6678434726570384.492722980764')
>>> (x*2).sqrt() * (2**75)
Decimal('53427477812563075.94178384611')
>>> (x*2).sqrt() * (2**76)
Decimal('106854955625126151.8835676922')
>>> (x*2).sqrt() * (2**76)
On Tue, Jun 22, 2010 at 7:54 PM, Jack Lloyd <lloyd at randombit.net> wrote:
> One other interesting aspect to a hash-based signature is that if you
> are using a tree-like scheme, you could parallelize it quite well,
> making good use of dozens of available cores (and, depending on the
> algorithm, the parallelism avilable in vector units like SSE/AVX,
> AltiVec, or NEON).

Yeah!  Also the SIMD part of it hardly even depends on the algorithm,
does it? If you're doing a computation with multiple parallel hash
instances then you should be able to take almost any hash algorithm
and compute it in parallel, right? Thomas Pornin recently did this
with his SHA-3 candidate, Shabal, which doesn't have a structure that
lends itself to SIMD parallelism "internally" in one instance of
Shabal, but he arranged to compute four instances of Shabal in
parallel using SSE2, computing each instance half as fast.

I believe Wei Dai once mentioned the possibility of a similar hack for SHA-256.

> in 20 years things
> like it will be used in your toaster (perhaps doubling as the heating
> element?), and in 100 a chip of these specs will perhaps best be used
> broken into pieces and used for speartips to hunt antelope.

Hee hee!

> BTW, could you post a translation guide for those of us without a
> sufficiently Unicoded MUA? Here is what mutt shows me for the final
> paragraph of your mail:

Hopefully you will use your Sandy Bridge chip to install mutt version
1.4, which was released May 29, 2002 with utf-8 support. Until then,
here is the translation:

> Oh, one more detail: the "giant virtual space of one-time keys" might
> not need to be as large as 2????????. That's because an attacker can't
                             2^256
> "brute force attack" this space. The resistance against brute force
> attack is provided by other parts of the system. This space needs to
> be large only in order to avoid accidental collision. It could be
> perhaps as small as 2????????, which if I calculate correctly would let you
                      2^160
> write 10????? times to your file while still incurring less than a 10????????
        10^16                                                        10^-15
> chance of an accidental collision which would let people forge new
> writes to your file.
> """
>
> ?????????? yours,
  faithfully

Zooko


More information about the tahoe-dev mailing list