Hadith about haya and salah

Question

I have heard the following hadith (paraphrasing, and perhaps it is longer in some way):

The first thing you lose is haya [and iman?] and the last is salah.

Normally a Google search would give some idea, not this one. What is the original source?

Answer 1

The original source is for example the compilation by abu Ya'ala from al-Mosul in Iraq أبو يعلى الموصلي the author of the two Musnads (al-Kabir -the big- and as-Saghir -the small-) on the authority of abu Hurairah () -see also here- with the wording:
_{In the following I may translate from Arabic, if not otherwise declared these are my own translations take them carefully!}

‏أول ما يرفع من هذه الأمة الحياء والأمانة وآخر ما يبقى الصلاة‏
The first thing you will lose is shyness/modesty (Haya') and trust and the lasting which will remain is the prayer
يخيل إلي أنه قال‏:‏ ‏"‏وقد يصلي قوم لا خلاق لهم‏"‏‏.‏
I think he said: "And (even) people who have no goodness in them may pray."

I found it mentioned in Majma' az-Zawaa'id wa manba' al-Fawaid مجمع الزاوئد ومنبع الفوائد of abu Bakr al-Haythami نور الدين علي بن أبي بكر الهيثمي -see here or here in Arabic- after a similar hadith from at-Tabarni's as-Saghir not quoting "shyness" at all -see for here in Arabic- on the authority of 'Omar ibn al-Khattab, with the following addition on its authenticity:

رواه أبو يعلى وفيه أشعث بن براز وهو متروك‏.‏ ويأتي قول ابن مسعود في الباب بنحوه‏.‏
It was narrated by abu Ya'ala and in its chain there's As-'At ibn Baraz who is left out (matrook) and we may quote a statement of ibn Masu'od on topic with similar words.

There's a slightly different wording in al-Bayhaqi's Sho'ab al-Imaan شعب الإيمان -see here in Arabic- which excludes the addition that prayer are the last thing that will be lost, the hadith is also on the authority of abu Hurairah ():

إِنَّ أَوَّلَ مَا يُرْفَعُ مِنْ هَذِهِ الأُمَّةِ الْحَيَاءُ وَالأَمَانَةُ ، فَسَلُوهُمَا اللَّهَ عَزَّ وَجَلَّ
Verily the first that this ummah will lose is the shyness (Haya') and trust so keep asking them Allah the almighty.

the chain of this hadith has many trustworthy narrators (even of high level of trust) but one accused hadith fabricator Muhammad ibn Ahmad al-'Oody محمد بن أحمد العودي, an unknown sheikh whom Dawod ibn Hind met in Aylah (لَقِيتُ شَيْخًا بِأَيْلَةَ ) and a da'if narrator 'Qaz'ah ibn Suwaid ibn Hujair قزعة بن سويد بن حجير too. And with a similar wording you may find it in Musnad a-Shihaab -see here in Arabic- but the narrator chain of this version has many more issues than that of abu Ya'la (at least two unknown narrators and a da'if narrator).

So it seems that all narrations of this hadith have several issues in the narrator chain especially with the addition of shyness.