Oleg Zabluda's blog
Saturday, May 28, 2011
California vs New York via Google Correlate
Using Google Correlate to find search queries which correlate with being in CA and anti-correlate with being in NY and vice versa:
Tuesday, January 12, 2010
Alain Delon, "двойной бурбон", "тройной одеколон", "Москва - Петушки"
In the process of learning about hard liquors, and after a recent double bout of 3am karaoke [OZ: this is a repost of my email from Jan 12, 2010], I decided to learn more about "двойной бурбон" that Alain Delon allegedly drinks. Apparently, it's just a two drink's worth of bourbon in one glass. Naturally, this led to a research on "тройной одеколон".


Turns out it's a valid cologne (first made in France in 1810) and is simply настойка лимонa, бергамотa [1] и нероли на спирту (containing 67% alcohol).

It sounds to me like a valid Bitter [2], which are common ingredients in cocktails. So, obviously, drinking "тройной oдеколон" makes perfect sense. In fact, I reasoned that there must have been a lot of cocktails with "тройной одеколон" as ingredient. For example, Веня Ерофеев, provided several famous recipes, with names like "Слеза Комсомолки", "Инеса Арманд", etc.. In fact, we can even make them. I am not very keen on drinking Soviet "тройной одеколон" [3], but with a little loss of authenticity, we can recreate it with oil essences [4]. So, with great hopes, I went to the source of the recipes:


Unfortunately, neither "Слеза Комсомолки" nor any other cocktail recipes contain "тройной одеколон". In fact, recipes are mostly BS (i.e. parodies) :-( What a bummer :-(

[1] This explains why Sergey constantly complains that Earl Grey tea smells of Cologne.

[2] Lemon is a very common ingredient of Bitters (http://en.wikipedia.org/wiki/Bitters). Neroli (http://en.wikipedia.org/wiki/Neroli) aka Bitter Orange blossom and Bergamot are not.

[3] "тройной одеколон" GOST:

Одеколоны. Технические условия. ГОСТ 17236-71* / от 26 октября 1971 г. М.:[Издательство Стандартов, 1979]

Apparently, some batches are made with deviations from GOST:

[4] http://www.google.com/products?q=neroli+essence

Here is a complete list with my comments:

«Ханаанский Бальзам»

Денатурат — 100 г.
Бархатное пиво — 200 г.
Политура очищенная — 100 г.

It's well established that some people drink Денатурат. Политура (http://ru.wikipedia.org/wiki/Политура) is simply 10—20%-ный спиртовой раствор шеллака, and doesn't appear to be toxic to me. Maybe шеллак/denatonium is a good mix. From reference below "Люди, пьющие политуру в просторечии именуются "баклажанами", т. к. кожа их приобретает характерный фиолетовый оттенок."

«Дух Женевы»

«Белая сирень» — 50 г.
Средство от потливости ног — 50 г.
Пиво «жигулевское» — 200 г.
Лак спиртовой — 150 г.


This actually sounds like a valid cocktail recipe to me, если Лак очистить.

«Слеза комсомолки»

Лаванда — 15 г.
Вербена — 15 г.
«Лесная вода» — 30 г.
Лак для ногтей — 2 г.
Зубной эликсир — 150 г.
Лимонад — 150 г.

This also sounds like a valid recipe.

Nail polish does not appear to be toxic (http://en.wikipedia.org/wiki/Nail_polish#Constituents) in such small amounts. Mouth wash (like Listerine) is definitely non-toxic.

For example mine contains 27% alcohol and mint (like Mojito). Unfortunately, I could not establish ingredients of «Лесная вода».

«Сучий Потрох»

Пиво «жигулевское» — 100 г.
Шампунь «Садко — богатый гость» — 30 г.
Резоль для очистки волос от перхоти — 70 г.
Клей БФ —12г.
Средство от потливости ног — 30 г.
Дезинсекталь для уничтожения мелких насекомых — 20 г.

Insecticide by itself is not toxic to mammals in small amounts, don't know what other ingredients were in the can. Shampoo is not toxic. I don't know if the soviet dandruff aerosol was toxic or not. This cocktail sounds like BS to me, because none of the ingredients (except the glue) contains alcohol and none improves the taste of the beer. Beer + purified БФ6 makes much more sense. I would call it "Резиновый Ершик".

More info (partially conflicting with my guesses)

http://www.narcom.ru/ideas/common/17.html (Cyrillic Windows-1251)



Bonus 2: Word problems from the story:

«Знаменитый ударник Алексей Стаханов два раза в день ходил по малой нужде и один раз в два дня – по большой. Когда же с ним случался запой, он четыре раза в день ходил по малой нужде и ни разу – по большой. Подсчитай, сколько раз в год ударник Алексей Стаханов сходил по малой нужде и сколько по большой, если учесть, что у него триста двенадцать дней в году был запой».

«Когда корабли седьмого американского флота пришвартовались к станции Петушки, партийных девиц там не было, но если комсомолок называть партийными, то каждая третья из них была блондинкой. По отбытии кораблей седьмого американского флота обнаружилось следующее: каждая третья комсомолка была изнасилована, каждая четвертая изнасилованная оказалась комсомолкой, каждая пятая изнасилованная комсомолка оказалась блондинкой, каждая девятая изнасилованная блондинка оказалась комсомолкой. Если всех девиц в Петушках 428 – определи, сколько среди них осталось нетронутых беспартийных брюнеток?»

Tuesday, December 15, 2009
Biological energy production systems
Anaerobic (homolactic acid fermentation)Anaerobic (heterolactic acid fermentation)
Tuesday, July 03, 2007
"Elements of Programming" (2009), Alexander A. Stepanov, Paul McJones
Hi, Alex,

It's a great book! It's been my pleasure reading it. Here is a couple of comments I have:

======================> Slide 7  <==================================

All algorithms can be translated 1-to-1 to Python.

======================> Slide 28  <==================================

Let u = number of significant bits in n

maybe would be clearer for a typical programmer:

Let u = number of significant bits in abs(n)

Also the formula is correct only for n !=0 (or else p<0 a="" definition="" for="" natural="" of="" span="">
"significant bits" of 0.

======================> Slide 63  <==================================

No need to do int(x)

======================> Slide 133-134 (annotated_plus) <==================================

It would be cleaner and will reduce code a bit, if you store and pass ostream by
[non-const] reference.

======================> Slide 143 (Fibonacci Matrices) <==================================

Here is how you can continue refining the algorithom (just like the refinement do in the rest
of the book):

First, a short, and simple thing to do is to get rid of the check:

if (n==0)
  return 0;

and use power_nonegative() instead of power_positive.

by introducing zerowth Fibonacci matrix F_0 = |1 0| (identity matrix)
                                              |0 1|

For power_nonnegative() (Slide 126) to compile, one needs to define
identity_element (Slide 86), for op being fibonacci_multiplies (Slides 142-143).

template // I models integer
pair identity_element&>
{ return pair(0, 1); }

I think, it's very a valuable refinement because
1. it provides a nice, simple  and first non-trivial example of identity_element(op).
  This non-trivial example will be important for people who still need to get comfortable
  with monoids.
2. Nicely drives the point of your book about algorithm refinement, axioms, etc... slightly

For more advanced readers, now that we extended isomorphism F: n -> F_n from semigroups to
we can extend it to the whole groups, which will give us a chance to
1. use power() (Slide 127) instead of power_nonnegative()
2. introduce first non-trivial example of inverse_operation(op) (Slide 127, 87, 88), 
  reciprocal, inverse (Slides 87-89)

First we need to extend Fibonacci numbers n -> f_n to negative n. It it trivial by formula
f_n = f_{n-2} + f_{n-1} <=>
f_{n-2} = f_n - f_{n-1} <=>
f_{-n} = -(-1)^n f_n

Now we see that
1. F_0 is the identity matrix, just as above. Before we didn't really provide much justification
  for it.
2. F_{-n} = inverse(F_n) under matrix multiplication (see proof later)
3. F_m F_n = F_{m+n} is still true because everything on Slide 139 is still true, now that
  we proved item 2.

Proof of item 2:

Fibonacci matrices commute, so it's enough to show the reciprocity from the left.

Following Slide  141:

We need to show that (only second row is shown)
identity matrix = (0, 1) = 
F_{-n}F_{n} =
      ( f_{-n}f_{n+1} + f_{-n-1}f_{n}  ,  f_{-n}f_{n} + f_{-n-1}f_{n-1} ) =
(-1)^n (-f_{n} f_{n+1} + f_{n+1} f_{n}  ,  -f_{ n}f_{n} + f_{ n+1}f_{n-1} ) =
(-1)^n ( 0                              ,  -f_{ n}f_{n} + f_{ n+1}f_{n-1} )

So we need to show that 
-f_{n}f_{n} + f_{ n+1}f_{n-1} = (-1)^n

The proof is by induction:

Let's A(n) = f_{ n+1}f_{n-1} - f_{n}f_{n} 
Induction base:
A(0) = 1
Induction step:
A(n+1) = 
f_{n+2}        f_{n} -  f_{n+1}      f_{n+1} =
(f_{n+1}+ f_{n})f_{n} - (f_{n-1}+f_{n})f_{n+1} =
          f_{n} f{n}  -  f_{n-1}      f_{n+1} =
= -A(n) QED.

Now we can get back to the Slide 143 and have our generic algorithm for any n, including negative,
power() instead of power_nonnegative() and no special cases for n>0, n>=0, etc...

In order for power() to compile and work (Slide 127) we need to define 

template inverse_operation(const fibonacci_multiplies&)

Following Slide 88, and taking into account that
the formula for the inverse is (only second row is shown):
inverse(F_n)=F_{-n} = (f_{-n}, f_{-n-1}) = (-1)^n (-f_{n}, f_{n+1})

#define FIBONACCI_TYPE(I) typename pair // I models Integer

template // I models Integer
class reciprocal : unary_function 
    FIBONACCI_TYPE(I) operator()(const FIBONACCI_TYPE(I)& x) const {
      f_n = x.first
      f_n_prev = x.second
      f_n_next = x.first + x.second
      sign = f_next*f_prev - f_n*f_n // (-1)^n

      return FIBONACCI_TYPE(I)(-sign*f_n, sign*f_n_next)
template // I models Integer
reciprocal inverse_operation(const fibonacci_multiplies&)
{ return reciprocal(); }

======================> Slide 155 (Ordering) <==================================

Another excellent example would be a set of subsets of a given set. It's very useful
example for the further discussion of partially ordered sets (esp. which are _not_ weakly
ordered) as well as lattices.

======================> Slide 155 (Asymmetric) <==================================

I would call it antisymmetric, but it's your book :-)

======================> Slide 155 (Symmetric Complement) <==================================

Useful Exercises:

let s(a,b) be  asymmetric complement of r
s(a,b) = !r(a,b) && !r(b,a)

1. Prove that s is symmetric
2. Prove that r is strict => s is reflexive
3. Show for which of the examples on slide 155 s is transitive
(if you include subsets, there will be two non-transitive examples)

======================> Slide 63 (Weak Ordering) <==================================

Useful Exercise:

Prove that strict ordering is asymmetric.


r is strict              <=>
r(a,b) => !r(b,a)        <=>  (X=>Y = !X||Y)
!r(a,b) || !r(b,a) = true <=>
r(a,b) && r(b,a) = false

Proof from the opposite. Suppose
r(a,b) && r(b,a) = true => (transitivity)
r(a,a) = true (contradicts that r is strict)

======================> Slide 169 <==================================

successor was not yet defined at this point in the book

======================> Slide 171 <==================================

Useful Exercises:

Lemma: a>b, a<=b, a>=b are orderings.
Lemma: if "<" is strict => then ">" is strict

======================> Slide 172 (Intervals) <==================================

I think it would be useful to point out that 
a (transitivity) a

You might also point out that "these definitions generalize to" partial orderings,
not just weak orderings.

======================> Slide 196 <==================================

I think it would be useful to point out that although weak orderings allows
binary_search(x, container), unlike for total ordering, the complexity is not log2(N),
as people might immediately assume, but log2(N) + M, where M is the cardinality of the
intersection of equivalence class of x under symmetric complement of the ordering and 
the container itself. In the worst case scenario it might be linear. You can again
refer the math reader to the examples on Slide 155 (or programmer reader to Slides 164-165).

======================> Slide 204 <==================================

Should read "Vectors OF A GIVEN DIMENSION with integer coordinates..."

======================> Slide 207 <==================================

Up until this slide, all C++ code was explicitly generic. Here we see an pretty abrupt
implicit transition to using overloaded operators. That's a perfect time to do it,
since the target reader is supposed to be able to transition by now, without
losing the understanding of genericity,  but it would still help to dedicate a couple of slides
to operator overloading. The Slide 171 (Overloading) does talk about reserving
< for the natural total ordering, but says nothing about -, +, 0, etc.. 

Around Slide 207 is a good time to explicitly transition to implicit operator overloading,
otherwise, the way the code in the future slides would be unreadable, and more importantly,
would not take advantage of the reader's intuition:

Slide 207 is the last one which is readable both ways:

template // T models Ordered Additive Group
T abs(const T& x)
  if(less(x, identity_element()>()) return inverse_operation(plus())(x)
  else                                        return x;

or even

template // T models Ordered Additive Group
T abs(const T& x,
      binary_function r  = less(),
      binary_function<  T, T, T> op = plus())
  if(r(x, identity_element(op)) return inverse_operation(op)(x)
  else                          return x;

======================> Slide 211 (Archimedean Group) <==================================

I think here it would be great to provide examples for all 4 combinations a, b positive
and negative, and compare it to  how programmers and different programming languages
(at least C/C++) treat / % div(N, D) for Integers (Z). Programmers have 3 ways to do it:
Truncating (towards zero), Floor, and Modulus. For example C/C++ division is truncation towards
zero (ISO C99 standard: ISO/IEC 9899:1999 paragraph, while yours is Floor.
Knuths' MMIX is Floor too. No languages or hardware that I know of, uses, Modulus,
(where the remainder is always positive) nor ever did I see it used in Math (Z/nZ),
because n was always positive.


The following items are missing in index:


If I understand correctly, the book is not finished yet? There will be more material, right?
I have 410 Slides.

Monday, May 08, 2006
A crow and a cat
Friday, April 28, 2006
The On-Line Encyclopedia of Integer Sequences

Wednesday, October 19, 2005
Silicon Artwork

Runaway Train This miniature choo-choo train was discovered rolling down the tracks on a LeCroy MVV 200 analog shift register integrated circuit. The "tracks" upon which the train is apparently riding are the high speed shift register.

Fine Print "No purchase necessary", "Keep away from fire", and "not for resale" are clearly visible in the magnified portion shown as an inset within the photomicrograph. The pad containing this warranty is 450 microns tall by 1850 microns wide and sports 25 lines of text, with each character being between six and eight microns high. This disclaimer--probably the smallest ever written--was found on a Hewlett-Packard "Aspen" (Acquisition Signal Processing ENgine) chip used in digital oscilloscopes in the late 1980s and early 1990s.

Tuesday, October 18, 2005
"Ideas for Startups" by Paul Graham
In his essay Ideas for Startups, Paul Graham writes:

They think creating a startup is just a matter of implementing some fabulous initial idea. And since a successful startup is worth millions of dollars, a good idea is therefore a million dollar idea.

If coming up with an idea for a startup equals coming up with a million dollar idea, then of course it's going to seem hard. Too hard to bother trying. Our instincts tell us something so valuable would not be just lying around for anyone to discover.

Actually, startup ideas are not million dollar ideas, and here's an experiment you can try to prove it: just try to sell one. Nothing evolves faster than markets. The fact that there's no market for startup ideas suggests there's no demand. Which means, in the narrow sense of the word, that startup ideas are worthless."

'nuff said.
Wednesday, September 28, 2005
Homo Habilis
Homo Habilis Current view on human evolution says that modern human evolved from Homo Habilis -- Handy Man (Человек умелый). How simplistic! Apparently it takes a degree in paleoanthropology not to see the obvious. Just looking at some of the people around is enough to conclude beyound all doubts that some H. Sapience specimens evolved from a currently undiscovered in the fossil record, Homo ahabilis -- Unskillful Man (Человек Нeумелый). Ditto with Homo ergaster  -- Working Man (Человек работающий).

Monday, September 19, 2005
Electric Eel Fishing
Electric Eel
The Electric eel (Electrophorus electricus) is capable of generating powerful electrical shocks, of up to 600 volts and 1 ampere of for the total of .6Kw for approximately 10 microseconds.
Juveniles produce smaller voltages -- about 110V (220V in Europe).
An electric eel can grow up to 2.5 m in length and 20 kg in weight.
When agitated, it is capable of producing these intermittent electrical shocks over a period of at least an hour without signs of tiring.
Incidentally, 600 volts is exactly the voltage required to cause the initial ionization of a fluorescent lamp, so you can use an instant-start ballast transformer to practice handling eels.
High Voltage How to fish an electric eel:
Troubleshooting and repairing an electric eel:
Electric eel is excellent baked, stewed, grilled or smoked. Though considered a fatty fish, the eel is high in vitamins A and D, as well as being a good source of protein, e- and Na+.
Electric eel recipes:

Wednesday, August 24, 2005
Nukular stuff

As is well-known, atom consist of electrons in orbital(s) around a nukulus, consisting of a subset of nukular particles called nukulons. Nukulons in atomic nukuli are bound by the nukular force (or inter-nukulon potential), which is the residual strong nukular force, which binds up and down quarks and gluons inside nukulons.

[Thermo]nukular bombs (nukes) and [thermo]nukular reactors release nukular energy from the nukuli employing nukular reactions such as nukular fission or nukular fusion.

Another type of nukular reaction is beta decay, caused by weak nukular force, between leptons (such as electron and neutrino) and quarks. Grand unification theory unifies strong nukular, weak nukular and electromagnetic forces into a single electronukular force.

The branch of physics studying these exciting phenomena is called nukular physics and those who study it are called nukular physisists.

Another fascinating discipline is cell and molecular biology. Every eukaryotic cell contains a nukulus. Cell nukulus is where DNA (Deoxyribonukulic acid) is. DNA consists of a sequence of nukulotides. Cell nukulus is filled with nukuloplasm, and, among other things, contains nukuloli. Nukuloli are made of protein and ribonukulic acid (RNA). After nukuloli are synthesized from nukulotides in the nukuloplasm they leave cell nukulus throgh nukular pores.

More on this here:
Monday, August 22, 2005
Robot can get back on its feet
Robot can get back on its feet

Robot can get back on its feet (video).


When They come for us, knocking Them off their feet will not be sufficient anymore. Let's just hope that the "off" button is not too hard to find.

It is clear from this story, that if such a robot has a built-in bluetooth adapter, he will be stealing laptops from cars. What do we do? What dooo we do?!

Here is what: we make sure the laptops smell like food, then just watch Them duking it out with the bears.

But here is a problem: what do we do when robot bears come after us?

Turns out we are all covered. We have the right to bear arms. And as you saw in the video, without arms They can't get back on their feet.

P.S. We've seen a robot get back on its feet about a year ago during a RoboExpo in San Francisco. But that one was small and looked non-threatening. I could have easily smashed him with a sledgehammer. I should've. First they came for the show. I did not speak out because I was not a show....

Anupam comments:

back here(india), we don't [have the right to bear arms]. oh mygawd, are we doomed ? possibly. unless of course the researchers in their infinite wisdom chose to use tcl. in which case we are fine. as the bots would tickle themselves to death after the beer-binge.

It probably does use tcl via Expect.

Somehow antropomorphic robots look scarier. I wonder how arctomorphic robots will be perceived.

"Aw look this little cute mechnical grizzly can get back o...." SMACK

Monday, August 01, 2005
Teddy Bear

In 1902 U.S. President Theodore Roosevelt had an incident on a bear-hunting trip in Mississippi, when he refused to shoot a bear cub. "Teddy's Bear" was immediately publicized by political cartoonists.

On February 15, 1903, Morris Michtom and his wife Rose made and displayed two stuffed bears in the window of their Brooklyn candy store shortly thereafter, and said they had received President Roosevelt's written permission to call them "Teddy's bears". The Bears sold like wildfire, and within a year, Michtom closed his candy store, and founded the Ideal Novelty and Toy Co. - still one of the biggest toy firms in the world over ninety years later.

German toy maker Margarete Steiff had started to produce stuffed toy animals in 1880; the first one was a little elephant. Her nephew Richard Steiff convinced her to produce a toy bear cub in 1902. They were completely unaware of what was going on in New York. The bear first appeared in public at the 1903 Spring Toy Fair at Leipzig, but - to Richard's disappointment, nobody seemed interested. Legend has it that it was only as Richard was packing away the stand at the end of the fair, that an American toy buyer came up to him, seized the bear, and ordered 3000 on the spot.

Michtom's bear had a more endearing, baby-faced appearance, while Steiff's more closely resembled a real bear cub. Within a few years of their invention, Teddy Bear-mania had swept the world. Roosevelt adopted the bear cub as his mascot for a successful re-election campaign, and Steiff redesigned their bears to create a more appealing face.

A.A. Milne created a fictional bear called Winnie-the-Pooh, named after a stuffed bear owned by Milne's son, Christopher Robin Milne. He first appeared appears in the book published October 14, 1926.

Wednesday, July 20, 2005
Rose Family
Flowering plants
Tuesday, June 28, 2005
Cave bears (Ursus spelaeus)
Cave Bears were 30% larger then Brown/Grizzly Bears. About 15000 years ago Cromagnons kicked last of them out of his cave. We needed the caves for ourselves -- there was the first recorded real estate bubble going. And that was that. Don't mess with H. Sapience. Neanderthals attempted to do ths same earlier, but couldn't. Wussies.
Monday, June 20, 2005
Vespids & flies

Thursday, May 19, 2005
Cache-timing attacks on AES.
[via: Schneier on Security]


Daniel J. Bernstein published a profound paper on AES Timing attack. There is very little new in the article from cryptology or cyptography point of view. The side-channel timing attacks of this nature are well known for decades. Moreover, the attacks are not against AES algorithm as such, but against a specific software implementation (OpenSSL on Pentium III).

However it's clear that it is applicable to any other modern CPU, and to any software implementation of any cryptographic algorithm which uses S-boxes. This and other things that I will point out later, led me to conclude that the article and its implications are truly profound. But first of all a quote from the article:

Was there some careless mistake in the OpenSSL implementation of AES? No. The problem lies in AES itself: it is extremely difficult to write constant-time high-speed AES software for common general-purpose CPUs. The underlying problem is that it is extremely difficult to load an array entry in time that does not depend on the entry's index. I chose to focus on OpenSSL because OpenSSL is one of today's most popular cryptographic toolkits. (Constant time low-speed AES software is fairly easy to write but is also unacceptable for many applications. Rijndael would obviously not have survived the fist round of AES competition if it had been implemented in this way.) Is AES the only cryptographic function vulnerable to this type of attack? No. The relevant feature of AES software, namely its heavy reliance upon S-boxes, is shared by cryptographic software for many other functions.

Emphasis is mine. If you don't know the particulars of clock-resolution performance of modern CPUs, just take his word for it. If you do, most likely you don't know half of it. Read the article for all the gory details. The bad news is that an attacker doesn't even need to understand any of the detils. He just need to know that time depends on index, and simply measure it.

Any software algorithm on any modern CPU which involves a table lookup, like S-boxes, for example, is subject to timing attacks. Since many algorithms, including AES, can be implemented without table lookups, it wouldn't be a terribly big deal, if it weren't for one fact: apparently cryptographers participating in AES standardization were completely unaware of the fact that table lookups are a vulnerability. Again quoting from the article: (note that [19] refers to "Report on the Development of the Advanced Encryption Standard (AES)" and [9] refers to "Resistance Against Implementation Attacks: A Comparative Study of the AES Proposals")

7 Errors in the AES standardization process

RAM cache hits can produce timing characteristics," Kocher wrote in 1996 in [16, Section 11], after explaining in detail how to extract secret keys from timing leaks in another operation. A decade later, we still have cryptographic software, in particular, AES libraries, whose timing obviously varies with, among other things, input-dependent RAM cache hits. How did this happen?

Was the National Institute of Standards and Technology unaware of timing attacks during the development of AES? No. In its Report on the development of the Advanced Encryption Standard," NIST spent several pages discussing side-channel attacks, specifically timing attacks and power attacks. It explicitly considered the difficulty of defending various operations against these attacks. For example, NIST stated in [19, Section 5.1.5] that MARS was difficult to defend" against these attacks.

Did NIST decide, after evaluating timing attacks, that those attacks were unimportant? No. Exactly the opposite occurred, as discussed below.

So what went wrong? Answer: NIST failed to recognize that table lookups do not take constant time. Table lookup: not vulnerable to timing attacks," NIST stated in [19, Section 3.6.2]. NIST's statement was, and is, incorrect.

NIST went on to consider the slowness of AES implementations designed to protect against side-channel attacks. For example, NIST stated that providing some defense" for MARS meant severe performance degradation." NIST stated in [19, Section 5.3.5] that Rijndael gained a major speed advantage over its competitors when such protections are considered." This statement was based directly on the incorrect notion that table lookups take constant time. NIST made the same comment in its summary assessments of the finalists," and again in its concluding paragraph explaining the selection of Rijndael as AES. See [19, Section 6.5] and [19, Section 7].

NIST was not the first to make these comments. In a paper Resistance against implementation attacks: a comparative study of the AES proposals," the Rijndael designers commented that a comparative study of the efficiency of the different algorithms on platforms that allow the described attacks should take into account the measures to be taken to thwart these attacks"; incorrectly stated that table lookup is not susceptible to a timing attack"; and concluded that Rijndael was favorable," i.e., relatively easy to secure." See [9, Section 5], [9, Section 3.3], and [9, Section 4.12].

In response to this paper, one of the Rijndael designers characterized cache-timing attacks as irrelevant for cryptographic design." This characterization is out of whack with what actually occurred in the design of the Advanced Encryption Standard. Cryptographic designers should and the AES designers did, at great length consider the difficulty of protecting against timing attacks. Where the AES designers erred was in asserting that table lookups take constant time.

It is hard to guess what might have happened if this error had been pointed out during the AES standardization process. None of the fifteen AES candidates provide high performance on all popular general-purpose CPUs|except by using instructions with input-dependent timings, notably S-box lookups.

As often happens, bugs and vulnerabilities often sneak in in the interface between systems and disciplines. Here it happened on the boundary of three disciplines: cryptography, software, and hardware. Out of 3 pair-wise boundaries, I can speak authoritatively about one: software developers don't understand performance of modern CPUs. It's just too expensive to learn. And by the time you do, the knowledge is obsolete. And I doubt that the other two boundaries are any better.

Monday, May 09, 2005
Stupid translator
Automatic computer translators don't work very well because they don't understand the meaning of what they are translating. Arttu Ylärakkola created a funny illustration of this fact. You type a phrase in English, the translator asks AltaVista Babelfish to translate it to some other language, then back to English. Currently it supports French, German, Italian, Portugese, and Spanish. Here is one example: Here are more examples:
XML, XHTML, CSS, JavaScript books

Tuesday, April 05, 2005
Satellite images of planes from Google Maps
Planes on Moffett Field, sfo, and a Military bone yard, SR-71 on the tarmac, Travis Aitforce Base courtesy of Google maps. More Google Sightseeing
Tuesday, March 29, 2005
Bay Area birds

Friday, March 18, 2005
Animal Classification

Sunday, March 13, 2005
Amazon.com: Books: Refusenik: Trapped in the Soviet Union

Just finished reading two books:

"Refusenik: Trapped in the Soviet Union" by Mark Azbel

Fear No Evil "Fear No Evil: The Classic Memoir of One Man's Triumph over a Police State" by Anatoly (Natan) Sharansky

Both are very good

Thursday, March 10, 2005
Computer-assisted image colorization

Colorization Using Optimization

Colorization is a computer-assisted process of adding color to a monochrome image or movie. The process typically involves segmenting images into regions and tracking these regions across image sequences. Neither of these tasks can be performed reliably in practice; consequently, colorization requires considerable user intervention and remains a tedious, time-consuming, and expensive task.

In this paper we present a simple colorization method that requires neither precise image segmentation, nor accurate region tracking.[...] In our approach an artist only needs to annotate the image with a few color scribbles, and the indicated colors are automatically propagated in both space and time to produce a fully colorized image or sequence. We demonstrate that high quality colorizations of stills and movie clips may be obtained from a relatively modest amount of user input.

Marked B/W image
Gray Manaco
Monaco Color

A pdf paper is also available.

Sunday, March 06, 2005

[via Google Blogoscoped]


Copyright is complicated.

Thursday, March 03, 2005
Side channel attacks: Physical security

[via: Bruce Schneier's Crypto-gram]

Flaw in Winkhaus Blue Chip Lock

The Winkhaus Blue Chip Lock is a very popular, and expensive, 128-bit encrypted door lock. When you insert a key, there is a 128-bit challenge/response exchange between the key and the lock, and when the key is authorized it will pull a small pin down through some sort of solenoid switch. This allows you to turn the lock.

Unfortunately, it has a major security flaw. If you put a strong magnet near the lock, you can also pull this pin down, without authorization -- without damage or any evidence.

A great video and whitepaper on Bumping Locks from CCC Physical Security Workshop. There two more good videos there.

Related Links:

Tuesday, March 01, 2005
White Sturgeon Beluga is a fish right? How does it roar then? Actually, there are two differrent animals that are called beluga. One is a beluga sturgeon from which black caviar is harvested. The other is beluga whale. One is a fish. The other is a mammal. In both cases, "beluga" means "white" (Rus: белый). Who is the most famous White whale? That's right: Moby-Dick. Follow the link to find the connection to "Starbucks".
Killer whale

Killer whale (Rus: Касатка) is not a whale. It's an [oceanic] dolphin. Unlike whales, all dolphins are predatory, including killer whales. However, both are members of order Cetacea.

Orcas are very inventive and playful in their killing. They sometimes will throw seals to one another through the air in order to stun and kill the animal. While salmon are usually hunted by a single orca or a small group of individuals, herring are often caught using carousel feeding: the orcas force the herring into a tight ball by releasing bursts of bubbles or flashing their white underside. The orcas then slap the ball with their tail flukes, either stunning or killing up to 10-15 herring with a successful slap. The herring are then eaten one at a time... Sea lions are killed by head-butting or by being slapped and stunned by a tail fluke...Orcas will spy-hop to locate seals resting on ice floes, and then create a wave to wash over the floe where a second orca waits to kill it.

Other unusual whales are narwhal and beluga.

Monday, February 28, 2005
Unusual Plates on Mars
Unusual Plates on Mars Unusual Plates on Mars

[via Astronomy Picture of the Day]

"What are those unusual plates on Mars? A leading current interpretation holds that they are blocks of ice floating on a recently frozen sea covered by dust."

Update: Water on Mars
Light reading by Richard Feynman

It's time to reread a couple of Feynman books again. Which I did yesterday.

Surely You're Joking, Mr. Feynman! Surely You're Joking, Mr. Feynman!

What Do You Care What Other People Think What Do You Care What Other People Think

XML in a Nutshell

Just finished reading

Fear No Evil

XML in a Nutshell

Pretty good book

Friday, February 25, 2005
Tree kangaroo

Tree kangarooTree kangaroo lives on trees and eats leaves and fruits. Unlike regular kangaroos, they have very strong arms. All kangaroos evolved from a small tree marsupial, but tree kangaroos evolved later from regular land kangaroos.

Photoshop Cubism
Photoshop cubism contest. More here, here, here, and here. [via www.worth1000.com]
Thursday, February 24, 2005
Winged Migration.

What a beautiful and exquisite movie! And a companion book for it.

Winged Migration Encyclopedia of Birds
Wednesday, February 23, 2005
Everyone thinks they're hiring the top 1%
[Via Joel on Software] 1%

Everyone thinks they're hiring the top 1%.

Yeh, right.

Powered by Blogger