What's wrong with how I'm using searchRecords?

What's wrong with how I'm using searchRecords?

This was working not long ago but is failing now:

$ curl -k ' https://crm.zoho.com/crm/private/json/Leads/searchRecords?authtoken=MyToken&scope=crmapi'
{"response":{"error":{"message":"Unable to process your request. Please verify if the name and value is appropriate for the \"criteria\" parameter.","code":"4600"},"uri":"/crm/private/json/Leads/searchRecords"}}

According to the doco, the criteria is not a required field, and even if I add a criteria it still results in the same error.