2 stories

Those who consume it become immortal, according to myth / THU 12-22-2022 / Methuselah's old man / English king called "the Great" / What smoke coming out of the ears may signal in a cartoon / Name derived from the Greek for "messenger"

1 Share
Constructor: David Steinberg

Relative difficulty: Easy, I think? Solved on paper, did not really look at the theme clues because they were long and I didn't feel like reading them, but it's pretty easy to notice that they all start with CARs coming in from the edges of the grid, and the crossings there are pretty fair, so you don't really need to the clues to solve, but it was an excellent aha moment post-solve when I could actually be arsed to read them and figure out the theme

THEME: ROUNDABOUT ROUTE — four entries are clued as if they are cars entering roundabouts, with three total clues: one for turning right, one for continuing straight, and one for turning left; in all cases the cars enter from the edge of the grid (and turns are oriented w/r/t that), and all turns result in valid entries both with and without the CAR (in some cases with the second part being backwards relative to the direction of the CAR word)

Word of the Day: TED (31D: California congressman ___ Lieu) —
Ted W. Lieu is an American politician and Air Force Reserve Command colonel who has represented California's 33rd congressional district in the U.S. House of Representatives since 2015. The district includes much of western and west Valley Los Angeles, as well as Beverly Hills, Santa Monica, Bel Air, Calabasas, Agoura Hills, the Palos Verdes Peninsula and Beach Cities.
A member of the Democratic Party, Lieu is one of 18 members of Congress who are naturalized U.S. citizens. He represented the 28th district in the California State Senate from 2011 to 2014, after being elected to fill the seat of deceased Senator Jenny Oropeza. From 2005 to 2010 he was a California State Assemblyman, representing the 53rd district, after being elected to fill the seat of deceased Assemblyman Mike Gordon.
Lieu actively served in the United States Air Force Judge Advocate General's Corps from 1995 to 1999 and since 2000 has served in the Air Force Reserve Command with his current rank of colonel upon his promotion in 2015. House Democratic Leader Nancy Pelosi appointed Lieu Assistant whip of the 115th Congress in 2017.
• • •
It's me, hi, I'm the problem, it's me. Christopher Adams here filling in for Rex while he may or may not be in wi-fi purgatory***; fingers crossed that this post doesn't interrupt his vacation like, uh, the last one did.

**Rex says, via wi-fi non-purgatory: "Dear Nora, your friends Mellie & Hilary (and I) want to wish you a very happy 21st birthday 🥳 🎉 🎂 I’m so glad you enjoy the blog, and I hope this blog birthday greeting from weirdo me (currently somewhere in central Otago, NZ) is as meaningful as your friends imagine. Have a wonderful day!"

Very glad that Rex is not in wi-fi purgatory, very glad to be able to relay (and second) the happy birthday greetings, and very glad to have this opportunity to apologize for parts of last Thursday's review, and especially the profanity and ad hominem stuff; that's 100% on me, and I should know better, but at the same time I was very much not in a mood to engage or spend time with a puzzle that (Roger Ebert voice) I hated, hated, hated, and ended up venting a bit too much; again, my sincerest, deepest apologies for that.

(I would also like to not take up too much time on that and get to today's puzzle, because the longer this intro goes, the more this becomes a recipe website where you have to go through five thousand or so words of family history before finding a fifty word recipe that's not as unique or as interesting as the food blogger thinks it is. ANYWAY, again, there's a lot of great puzzles out there, and I try to not solve ones that I don't enjoy. Which is not to say that I hate all NYT puzzles; I just generally don't solve the NYT unless it's by a constructor I know and enjoy (which is today's puzzle!), or if I hear from trusted friends that it's a good puzzle; recent puzzles I liked included Sid's themeless from the 10th and Ryan's Sunday themeless on the 18th.)

On to this puzzle! TL;DR I liked it! A lot! (More below the theme explanation!)

Theme answers:
  • 26A: First exit: Milk containers · Second exit: Rebounded, in billiard · Third exit: Wheeled (away) [CARTONS / CAROMED / CARTED, w/ CAR going into SNOT, DEMO, TED as appropriate]
  • 54A: First exit: Salad bar bowlful · Second exit: French watchmaker · Third exit: Thanksgiving role [CARROTS / CARTIER / CARVER, using ROTS, TIER, REV]
  • 5D: First exit: Floor covers · Second exit: Addition signs · Third exit: Checking the IDs of [CARPETS / CARETS / CARDING, using STEP, ETS, DING]
  • 66D: First exit: Writer Lewis · Second exit: Santana of Santana · Third exit: Dead meat [CARROLL / CARLOS / CARRION, using ROLL, SOL, and NOIR]
It's not terribly difficult to find words that become other words when you remove some letters; it's not terribly difficult, either, to find words that become other words when they're spelled backwards. And there's some flexibility here: since they all start with CAR, the ending parts can go anywhere where they're in the right direction (e.g. STEP could go at 19A, where it is, or 61A, but not at 20A). But: having four of them intersecting the (grid-spanning) revealer in symmetric spots, while accounting for all of the above? Now that's some good construction (and, perhaps, a bit of luck; you can't move the black squares that function as roundabouts around too much, but at the same time, when you're as talented and experienced as David is, sometimes you make your own luck). (I will quibble a little bit and say that I would've liked the NW and SE roundabouts to be visually set apart and not touch other black squares, even diagonally, but that's perhaps asking a bit too much here.)

update: David says in his XWI notes that getting the revealer to "run through the four thematic arrangements might just top the list of lucky moments in my crossword construction career", but I still think that there's still a fair bit of skill involved. I also wouldn't be disappointed if this was a Wednesday, like he thought this might be because he clued all the roundabout exits [which, again, were normal words] rather than leaving them unclued, but like David, I'm very happy to see this published period, and especially on a Thursday (and doubly so on a day I blog!).

Anyway, fun theme! A lot better than last week! Heck, even if I didn't like this, I still would've liked it more than last week, because it's at least trying to do something fun and inventive. (To be fair, I probably would've disliked last week's theme less if it were, say, on a Tuesday instead of a Thursday, but still...) And outside of that, there's some legit fun clues: the image of [What smoke coming out of the ears may signal in a cartoon] (ANGER), the "TIL interesting fact" of [Name derived from the Greek for "messenger"] (ANGELINA), the "tricky but fair" clue for CARETS (see below), plus fun fill like SANTA HAT, FROSH, AMBROSIA, etc.

c'mon, what else could the video be?

ROUNDABOUT (ARC)TANGENT: As a driver, I love roundabouts. As a pedestrian and (especially) a runner, not as much of a fan; I've noticed that at most intersections here in Iowa City where they've replaced stop signs / lights with roundabouts recently, it's a lot harder to cross the street because cars just don't slow down. At least with stop signs and lights, you know (well, at least hope) that cars will stop, and to some degree you can continue safely through the intersection without really stopping. But with roundabouts, cars don't even stop, let alone slow down, and the thought of them even thinking about looking for pedestrians is a pipe dream. ROUNDABOUT (ARC)TANGENT OVER.

Anyway, good puzzle! It's one I would've solved anyway, because I generally like David's puzzles (and know that if it's a Thursday, it's probably really creative), and I'm glad it's also on a day I'm blogging. More fun that way.

  • CARETS [5D: Addition signs] — As a math person, my first thought here was that this was a mistake; carets are usually used for exponentiation. Realized, after a bit, that this is referring to copyediting / proofreading, where carets are used to signal additions to the text
  • THE [71A: French beverage] — Sure, I guess; not a fan of this angle, and it's not like you're avoiding dupes with clues here (because there's quite a few instances of "the" in the clues elsewhere). Would've liked this more if it'd've leaned into that and clued it as [The most common word in the English language, or in the clue for this answer], or if the next clue ([Chinwags], for CHATS) had continued the trend with [French pets] or something
  • ROSIE [66A: Funny O'Donnell] — [citation needed] (at least, not recently, and it's not like you're hurting for other clue angles here)
  • TRIO [52A: Hip-hop's Salt-N-Pepa, contrary to what their name suggest] — on the one hand, yes, DJ Spinderella was absolutely a vital member of that group in their heyday; on the other hand, iirc, she hasn't been part of the group for a few years now, and so it technically isn't a trio right now? FWIW, I like the cluing angle, and think it works, but might've been better to pick a different act (Tony Orlando and Dawn, anybody?) [ETA: apparently this is a print-only clue, possibly for these reasons; the online clue is [The Powerpuff Girls, e.g.] which avoids these issues.]
  • ETS [23D: "We come in peace" speakers, in brief] — no no no no no no no no; the only valid cluing angles here, imo, are the lawful good and maybe the lawful neutral ones on this chart
  • LATIN I [50D: Course in which you might learn "cave canem" — One of the few answers I had to erase, in that I knew the answer in that area was longer than five letters, and so I jumped straight to AP LATI..and whoops, that doesn't fit. Meh on the I, but it's fair, I suppose. ["Cave canem" is "beware of dog", btw.]
  • TAR [35A: Dinosaur bone preserver] — We would also have accepted [2022 film starring Cate Blanchett]
Yours in puzzling, Christopher Adams, Court Jester of CrossWorld

[Follow Rex Parker on Twitter and Facebook]
Read the whole story
535 days ago
Share this story

NSA: Possibly breaking US laws, but still bound by laws of computational complexity


Last week, I got an email from a journalist with the following inquiry. The recent Snowden revelations, which made public for the first time the US government’s “black budget,” contained the following enigmatic line from the Director of National Intelligence: “We are investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.” So, the journalist wanted to know, what could these “groundbreaking” capabilities be? And in particular, could he mean that the NSA was buying quantum computers from D-Wave, and using them to run Shor’s algorithm to break the RSA cryptosystem?

I replied that, yes, that’s “possible,” but only in the same sense that it’s “possible” that the NSA is using the Easter Bunny for the same purpose. (For one thing, D-Wave themselves have said repeatedly that they have no interest in Shor’s algorithm or factoring. Admittedly, I guess that’s what D-Wave would say, were they making deals with NSA on the sly! But it’s also what the Easter Bunny would say.) More generally, I said that if the open scientific world’s understanding is anywhere close to correct, then quantum computing might someday become a practical threat to cryptographic security, but it isn’t one yet.

That, of course, raised the extremely interesting question of what “groundbreaking capabilities” the Director of National Intelligence was referring to. I said my personal guess was that, with ~99% probability, he meant various implementation vulnerabilities and side-channel attacks—the sort of thing that we know has compromised deployed cryptosystems many times in the past, but where it’s very easy to believe that the NSA is ahead of the open world. With ~1% probability, I guessed, the NSA made some sort of big improvement in classical algorithms for factoring, discrete log, or other number-theoretic problems. (I would’ve guessed even less than 1% probability for the latter, before the recent breakthrough by Joux solving discrete log in fields of small characteristic in quasipolynomial time.)

Then, on Thursday, a big New York Times article appeared, based on 50,000 or so documents that Snowden leaked to the Guardian and that still aren’t public. (See also an important Guardian piece by security expert Bruce Schneier, and accompanying Q&A.) While a lot remains vague, there might be more public information right now about current NSA cryptanalytic capabilities than there’s ever been.

So, how did my uninformed, armchair guesses fare? It’s only halfway into the NYT article that we start getting some hints:

The files show that the agency is still stymied by some encryption, as Mr. Snowden suggested in a question-and-answer session on The Guardian’s Web site in June.

“Properly implemented strong crypto systems are one of the few things that you can rely on,” he said, though cautioning that the N.S.A. often bypasses the encryption altogether by targeting the computers at one end or the other and grabbing text before it is encrypted or after it is decrypted…

Because strong encryption can be so effective, classified N.S.A. documents make clear, the agency’s success depends on working with Internet companies — by getting their voluntary collaboration, forcing their cooperation with court orders or surreptitiously stealing their encryption keys or altering their software or hardware…

Simultaneously, the N.S.A. has been deliberately weakening the international encryption standards adopted by developers. One goal in the agency’s 2013 budget request was to “influence policies, standards and specifications for commercial public key technologies,” the most common encryption method.

Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology and later by the International Organization for Standardization, which has 163 countries as members.

Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”

So, in pointing to implementation vulnerabilities as the most likely possibility for an NSA “breakthrough,” I might have actually erred a bit too far on the side of technological interestingness. It seems that a large part of what the NSA has been doing has simply been strong-arming Internet companies and standards bodies into giving it backdoors. To put it bluntly: sure, if it wants to, the NSA can probably read your email. But that isn’t mathematical cryptography’s fault—any more than it would be mathematical crypto’s fault if goons broke into your house and carted away your laptop. On the contrary, properly-implemented, backdoor-less strong crypto is something that apparently scares the NSA enough that they go to some lengths to keep it from being widely used.

I should add that, regardless of how NSA collects all the private information it does—by “beating crypto in a fair fight” (!) or, more likely, by exploiting backdoors that it itself installed—the mere fact that it collects so much is of course unsettling enough from a civil-liberties perspective. So I’m glad that the Snowden revelations have sparked a public debate in the US about how much surveillance we as a society want (i.e., “the balance between preventing 9/11 and preventing Orwell”), what safeguards are in place to prevent abuses, and whether those safeguards actually work. Such a public debate is essential if we’re serious about calling ourselves a democracy.

At the same time, to me, perhaps the most shocking feature of the Snowden revelations is just how unshocking they’ve been. So far, I haven’t seen anything that shows the extent of NSA’s surveillance to be greater than what I would’ve considered plausible a priori. Indeed, the following could serve as a one-sentence summary of what we’ve learned from Snowden:

Yes, the NSA is, in fact, doing the questionable things that anyone not living in a cave had long assumed they were doing—that assumption being so ingrained in nerd culture that countless jokes are based around it.

(Come to think of it, people living in caves might have been even more certain that the NSA was doing those things. Maybe that’s why they moved to caves.)

As many readers of this blog might know, Neal Koblitz—a respected mathematician and pioneer of elliptic curve cryptography, who has some ties to NSA—published a series of scathing articles, in the Notices of the American Mathematical Society and elsewhere, attacking the theoretical computer science approach to cryptography. Koblitz’s criticisms were varied and entertainingly-expressed: the computer scientists are too sloppy, deadline-driven, self-promoting, and corporate-influenced; overly trusting of so-called “security proofs” (a term they shouldn’t even use, given how many errors and exaggerated claims they make); absurdly overreliant on asymptotic analysis; “bodacious” in introducing dubious new hardness assumptions that they then declare to be “standard”; and woefully out of touch with cryptographic realities. Koblitz seemed to suggest that, rather than demanding the security reductions so beloved by theoretical computer scientists, people would do better to rest the security of their cryptosystems on two alternative pillars: first, standards set by organizations like the NSA with actual real-world experience; and second, the judgments of mathematicians with …taste and experience, who can just see what’s likely to be vulnerable and what isn’t.

Back in 2007, my mathematician friend Greg Kuperberg pointed out an irony to me: here we had a mathematician, lambasting computer scientists for trying to do for cryptography what mathematics itself has sought to do for everything since Euclid! That is, when you see an unruly mess of insights, related to each other in some tangled way, systematize and organize it. Turn the tangle into a hierarchical tree (or dag). Isolate the minimal assumptions (one-way functions? decisional Diffie-Hellman?) on which each conclusion can be based, and spell out all the logical steps needed to get from here to there—even if the steps seem obvious or boring. Any time anyone has tried to do that, it’s been easy for the natives of the unruly wilderness to laugh at the systematizing newcomers: the latter often know the terrain less well, and take ten times as long to reach conclusions that are ten times less interesting. And yet, in case after case, the clarity and rigor of the systematizing approach has eventually won out. So it seems weird for a mathematician, of all people, to bet against the systematizing approach when applied to cryptography.

The reason I’m dredging up this old dispute now, is that I think the recent NSA revelations might put it in a slightly new light. In his article—whose main purpose is to offer practical advice on how to safeguard one’s communications against eavesdropping by NSA or others—Bruce Schneier offers the following tip:

Prefer conventional discrete-log-based systems over elliptic-curve systems; the latter have constants that the NSA influences when they can.

Here Schneier is pointing out a specific issue with ECC, which would be solved if we could “merely” ensure that NSA or other interested parties weren’t providing input into which elliptic curves to use. But I think there’s also a broader issue: that, in cryptography, it’s unwise to trust any standard because of the prestige, real-world experience, mathematical good taste, or whatever else of the people or organizations proposing it. What was long a plausible conjecture—that the NSA covertly influences cryptographic standards to give itself backdoors, and that otherwise-inexplicable vulnerabilities in deployed cryptosystems are sometimes there because the NSA wanted them there—now looks close to an established fact. In cryptography, then, it’s not just for idle academic reasons that you’d like a publicly-available trail of research papers and source code, open to criticism and improvement by anyone, that takes you all the way from the presumed hardness of an underlying mathematical problem to the security of your system under whichever class of attacks is relevant to you.

Schneier’s final piece of advice is this: “Trust the math. Encryption is your friend.”

“Trust the math.”On that note, here’s a slightly-embarrassing confession. When I’m watching a suspense movie (or a TV show like Homeland), and I reach one of those nail-biting scenes where the protagonist discovers that everything she ever believed is a lie, I sometimes mentally recite the proof of the Karp-Lipton Theorem. It always calms me down. Even if the entire universe turned out to be a cruel illusion, it would still be the case that NP ⊂ P/poly would collapse the polynomial hierarchy, and I can tell you exactly why. It would likewise be the case that you couldn’t break the GGM pseudorandom function without also breaking the underlying pseudorandom generator on which it’s based. Math could be defined as that which can still be trusted, even when you can’t Trust math—even (or especially) when you don’t trust anything else.

Read the whole story
3931 days ago
Share this story