Теоретически, вы не можете. Идентификатор устройства не является особо секретным, и в большинстве случаев его можно легко подделать. Что касается Android, то в этой ОС вообще нет надежного идентификатора устройства - смотрите подробности здесь: Существует ли уникальный идентификатор устройства Android?
Все, на что вы можете положиться - это безопасность от неясности - надеясь, что никто не будет достаточно решителен для обратного проектирования кода и анализа протокола аутентификации. И не разглашать код - не вариант, ведь вы распространяете приложение.
Тем не менее, один не особо безопасный метод аутентификации будет - отправлять идентификатор устройства и хеш идентификатора устройства, соединенные с секретным, жестко закодированным в строке кода клиента. Служба будет содержать копию той же строки, пересчитать хэш (используя предоставленный идентификатор устройства) и сопоставить хэши. Не разбивается при анализе протокола, только копаясь в коде для строки. Уязвим к повторным атакам.
Для более надежного решения аутентифицируйте пользователей, а не устройства. Это зависит от ваших клиентов и зависит от характера бизнеса.